Home » Archived » XML Schema Definition (XSD) » Correct insertion point for child elements according to schema
| Correct insertion point for child elements according to schema [message #49886] |
Tue, 10 August 2004 14:41  |
Eclipse User |
|
|
|
Originally posted by: invalid.soft-gems.net
Hi all,
Has anybody of you ever developed a working solution to find the correct
insertion point for child XML elements in their new parent with respect to
what the schema allows?
Due to the limitations of xs:all (not allowed in model groups, maximum of
1 occurance of child elements) and xs:choice (required child elements can
be omitted, number of child elements cannot individually be determined) we
are forced to use xs:sequence, although it would not matter for us in
which order elements appear in the instance document.
What I have is a schema, an XML parent element and a new XML child element
that must be added to the parent element at the correct location. The
algorithm I have currently in mind goes like:
1) Find the particle of the child element in the element declaration of
the parent element.
2) Go to the previous particle (if there is one) and look if there is
already an element for that particle in the parent element. If so add the
new child after the existing one.
3) If there is no XML element already there then go one back in the
definition and look for that in the parent XML element. Continue until no
more particles exist or one is found.
4) If there is no particle anymore add the new child as first entry to the
XML parent element otherwise as the next sibling.
This sounds simple but has some implications.
1) Navigation (particulary backwards) in perhaps deeply nested model
groups is a bit expensive and slow.
2) The algo does not consider multiple occurances of model groups and
elements.
3) It does not handle xs:choice (perhaps with multiple occurances) well.
To me it appears that the DFA in a particle could help, but since there is
no docu about it nor any example it is hard to know where to start.
Thanks for listening.
Mike
--
www.soft-gems.net
|
|
|
| Re: Correct insertion point for child elements according to schema [message #49917 is a reply to message #49886] |
Tue, 10 August 2004 15:52  |
| Eclipse User |
|
|
|
Originally posted by: merks.ca.ibm.com
Mike,
I think the DFA would definitely be the best way to compute this. The
DFA is used in the XSDEditor in the commented out doLoad method. It's
pretty simple to use. You start with the initialState and can either
look at all its transitions or use the accept method to follow a
transition that matches a particule namespace and name. Given a state,
you can know whether it's an accepting state and given the transition,
you can know what the new state will be when you follow that
transition. Everything else is recursive from there...
Mike Lischke wrote:
>Hi all,
>
>Has anybody of you ever developed a working solution to find the correct
>insertion point for child XML elements in their new parent with respect to
>what the schema allows?
>
>Due to the limitations of xs:all (not allowed in model groups, maximum of
>1 occurance of child elements) and xs:choice (required child elements can
>be omitted, number of child elements cannot individually be determined) we
>are forced to use xs:sequence, although it would not matter for us in
>which order elements appear in the instance document.
>
>What I have is a schema, an XML parent element and a new XML child element
>that must be added to the parent element at the correct location. The
>algorithm I have currently in mind goes like:
>
>1) Find the particle of the child element in the element declaration of
>the parent element.
>2) Go to the previous particle (if there is one) and look if there is
>already an element for that particle in the parent element. If so add the
>new child after the existing one.
>3) If there is no XML element already there then go one back in the
>definition and look for that in the parent XML element. Continue until no
>more particles exist or one is found.
>4) If there is no particle anymore add the new child as first entry to the
>XML parent element otherwise as the next sibling.
>
>This sounds simple but has some implications.
>
>1) Navigation (particulary backwards) in perhaps deeply nested model
>groups is a bit expensive and slow.
>2) The algo does not consider multiple occurances of model groups and
>elements.
>3) It does not handle xs:choice (perhaps with multiple occurances) well.
>
>To me it appears that the DFA in a particle could help, but since there is
>no docu about it nor any example it is hard to know where to start.
>
>Thanks for listening.
>
>Mike
>--
>www.soft-gems.net
>
>
>
|
|
|
| Re: Correct insertion point for child elements according to schema [message #49945 is a reply to message #49917] |
Wed, 11 August 2004 07:06 |
| Eclipse User |
|
|
|
Originally posted by: invalid.soft-gems.net
Ed Merks wrote:
> I think the DFA would definitely be the best way to compute this. The
> DFA is used in the XSDEditor in the commented out doLoad method. It's
> pretty simple to use. You start with the initialState and can either
> look at all its transitions or use the accept method to follow a
> transition that matches a particule namespace and name. Given a state,
> you can know whether it's an accepting state and given the transition,
> you can know what the new state will be when you follow that
> transition. Everything else is recursive from there...
Thank you Ed. So it looks nobody actually has done that already.
Mike
--
www.soft-gems.net
|
|
|
| Re: Correct insertion point for child elements according to schema [message #49975 is a reply to message #49917] |
Wed, 11 August 2004 08:17 |
| Eclipse User |
|
|
|
Originally posted by: invalid.soft-gems.net
Ed Merks wrote:
> You start with the initialState and can either
> look at all its transitions or use the accept method to follow a
> transition that matches a particule namespace and name.
I wrote down all states and transitions for a test case to see how I can
proceed in the DFA. However it seems the DFA cannot help me here. If you
have an element it is quite easy to use the DFA to check its validity.
However in my case the direction is reversed. If one state does not accept
my new element then I have to search all outgoing transitions for an
accepting state. However states may point to itself or other states that
point back to the first state so I can easily get into an endless loop.
How would you handle such a situation?
Mike
--
www.soft-gems.net
|
|
|
| Re: Correct insertion point for child elements according to schema [message #49996 is a reply to message #49975] |
Wed, 11 August 2004 11:36 |
| Eclipse User |
|
|
|
Originally posted by: merks.ca.ibm.com
This is a multi-part message in MIME format.
--------------020007000904090907070908
Content-Type: text/plain; charset=ISO-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Mike,
I think you would use a breadth first search and you would keep track of
a set of already visited states so that no state is considered more than
once. Thinking more about your original problem, there may be more
than one valid place to insert something, or there may be no valid place
unless you insert the element and some other elements to make it
complete. Also, I'm curious if you are always trying to go from one
valid instance to another valid instance; if so, the approach won't work
for something that's initially empty and won't work for the case where
more than one element needs to be inserted to produce a larger valid
instance.
Mike Lischke wrote:
>Ed Merks wrote:
>
>
>
>>You start with the initialState and can either
>>look at all its transitions or use the accept method to follow a
>>transition that matches a particule namespace and name.
>>
>>
>
>I wrote down all states and transitions for a test case to see how I can
>proceed in the DFA. However it seems the DFA cannot help me here. If you
>have an element it is quite easy to use the DFA to check its validity.
>However in my case the direction is reversed. If one state does not accept
>my new element then I have to search all outgoing transitions for an
>accepting state. However states may point to itself or other states that
>point back to the first state so I can easily get into an endless loop.
>How would you handle such a situation?
>
>Mike
>--
>www.soft-gems.net
>
>
>
--------------020007000904090907070908
Content-Type: text/html; charset=ISO-8859-15
Content-Transfer-Encoding: 8bit
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-15"
http-equiv="Content-Type">
<title></title>
</head>
<body bgcolor="#ffffff" text="#000000">
Mike,<br>
<br>
I think you would use a breadth first search and you would keep track
of a set of already visited states so that no state is considered more
than once.
|
|
|
| Re: Correct insertion point for child elements according to schema [message #50211 is a reply to message #49996] |
Thu, 12 August 2004 06:07 |
| Eclipse User |
|
|
|
Originally posted by: invalid.soft-gems.net
Ed Merks wrote:
> Mike,
> I think you would use a breadth first search and you would keep track of
> a set of already visited states so that no state is considered more than
> once. Thinking more about your original problem, there may be more
> than one valid place to insert something, or there may be no valid place
> unless you insert the element and some other elements to make it
> complete. Also, I'm curious if you are always trying to go from one
> valid instance to another valid instance; if so, the approach won't work
> for something that's initially empty and won't work for the case where
> more than one element needs to be inserted to produce a larger valid
> instance.
Well, I got it working with this code (sorry for german comments):
/**
* Fügt das gegebene Kindelement zu <b>parent</b> hinzu, berücksichtigt
dabei aber die richtige
* Position gemäßig aktivem Schema.
*
* @param parent Das Vaterelement, zu dem der neue Knoten hinzugefügt
werden soll.
* @param newChild Der hinzuzufügende Knoten.
* @return Gibt <b>true</b> zurück, wenn die Einfügeoperation
erfolgreich war, sonst <b>false</b>.
*/
public boolean placeChild(Element parent, Element newChild)
{
boolean result = false;
XSDElementDeclaration declaration =
elementDeclarations.find(parent.getNamespace(), parent.getName());
if (declaration != null)
{
XSDTypeDefinition definition = declaration.getTypeDefinition();
XSDParticle content = definition.getComplexType();
if (content != null)
{
State state = content.getDFA().getInitialState();
String uri = newChild.getNamespaceURI();
String name = newChild.getName();
for (int i = 0; i < parent.getChildren().size(); i++)
{
Element currentChild = (Element) parent.getChildren().get(i);
// Akzeptiert der aktuelle Status das neue Kindelement (soll
heißen, kann es vor dem
// aktuellen Kindelement eingefügt werden)?
Transition transition = state.accept(uri, name);
if (transition == null)
{
// Nicht akzeptiert an dieser Stelle. Gehe zum nächsten State.
transition = state.accept(currentChild.getNamespaceURI(),
currentChild.getName());
if (transition == null)
// Wenn es keinen gültigen nächsten State gibt, dann ist das
Vaterelement ungültig.
break;
else
state = transition.getState();
}
else
{
// Kindelement kann an dieser Stelle eingefügt werden, also
tue das.
parent.addContent(i, newChild);
result = true;
break;
}
}
// Wenn die Kindliste durchgearbeitet wurde, ohne dass ein
Zielpunkt bestimmt werden konnte,
// dann kann es möglich sein, dass der neue Knoten als letztes
Element eingefügt werden kann.
if (state.accept(uri, name) != null)
{
parent.addContent(newChild);
result = true;
}
}
}
return result;
}
What actually happens is that I take the existing child list and use this
to execute the DFA until I find a place where I can insert the new child.
This works also for an initially empty child list and multiple occurences.
I have yet to see a case that does not work correctly, but for now it does
what I need.
Now that I got familiar with the DFA I want to continue with code to
determine if a child can be deleted from its parent without making that
parent invalid.
Mike
--
www.soft-gems.net
|
|
| |
| Re: Correct insertion point for child elements according to schema [message #590043 is a reply to message #49886] |
Tue, 10 August 2004 15:52 |
 Ed Merks
Messages: 33264
Registered: July 2009 |
Senior Member |
|
|
Mike,
I think the DFA would definitely be the best way to compute this. The
DFA is used in the XSDEditor in the commented out doLoad method. It's
pretty simple to use. You start with the initialState and can either
look at all its transitions or use the accept method to follow a
transition that matches a particule namespace and name. Given a state,
you can know whether it's an accepting state and given the transition,
you can know what the new state will be when you follow that
transition. Everything else is recursive from there...
Mike Lischke wrote:
>Hi all,
>
>Has anybody of you ever developed a working solution to find the correct
>insertion point for child XML elements in their new parent with respect to
>what the schema allows?
>
>Due to the limitations of xs:all (not allowed in model groups, maximum of
>1 occurance of child elements) and xs:choice (required child elements can
>be omitted, number of child elements cannot individually be determined) we
>are forced to use xs:sequence, although it would not matter for us in
>which order elements appear in the instance document.
>
>What I have is a schema, an XML parent element and a new XML child element
>that must be added to the parent element at the correct location. The
>algorithm I have currently in mind goes like:
>
>1) Find the particle of the child element in the element declaration of
>the parent element.
>2) Go to the previous particle (if there is one) and look if there is
>already an element for that particle in the parent element. If so add the
>new child after the existing one.
>3) If there is no XML element already there then go one back in the
>definition and look for that in the parent XML element. Continue until no
>more particles exist or one is found.
>4) If there is no particle anymore add the new child as first entry to the
>XML parent element otherwise as the next sibling.
>
>This sounds simple but has some implications.
>
>1) Navigation (particulary backwards) in perhaps deeply nested model
>groups is a bit expensive and slow.
>2) The algo does not consider multiple occurances of model groups and
>elements.
>3) It does not handle xs:choice (perhaps with multiple occurances) well.
>
>To me it appears that the DFA in a particle could help, but since there is
>no docu about it nor any example it is hard to know where to start.
>
>Thanks for listening.
>
>Mike
>--
>www.soft-gems.net
>
>
>
Ed Merks
Professional Support: https://www.macromodeling.com/
|
|
| | |
| Re: Correct insertion point for child elements according to schema [message #590070 is a reply to message #49975] |
Wed, 11 August 2004 11:36 |
Ed Merks
Messages: 33264
Registered: July 2009 |
Senior Member |
|
|
This is a multi-part message in MIME format.
--------------020007000904090907070908
Content-Type: text/plain; charset=ISO-8859-15; format=flowed
Content-Transfer-Encoding: 7bit
Mike,
I think you would use a breadth first search and you would keep track of
a set of already visited states so that no state is considered more than
once. Thinking more about your original problem, there may be more
than one valid place to insert something, or there may be no valid place
unless you insert the element and some other elements to make it
complete. Also, I'm curious if you are always trying to go from one
valid instance to another valid instance; if so, the approach won't work
for something that's initially empty and won't work for the case where
more than one element needs to be inserted to produce a larger valid
instance.
Mike Lischke wrote:
>Ed Merks wrote:
>
>
>
>>You start with the initialState and can either
>>look at all its transitions or use the accept method to follow a
>>transition that matches a particule namespace and name.
>>
>>
>
>I wrote down all states and transitions for a test case to see how I can
>proceed in the DFA. However it seems the DFA cannot help me here. If you
>have an element it is quite easy to use the DFA to check its validity.
>However in my case the direction is reversed. If one state does not accept
>my new element then I have to search all outgoing transitions for an
>accepting state. However states may point to itself or other states that
>point back to the first state so I can easily get into an endless loop.
>How would you handle such a situation?
>
>Mike
>--
>www.soft-gems.net
>
>
>
--------------020007000904090907070908
Content-Type: text/html; charset=ISO-8859-15
Content-Transfer-Encoding: 8bit
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html;charset=ISO-8859-15"
http-equiv="Content-Type">
<title></title>
</head>
<body bgcolor="#ffffff" text="#000000">
Mike,<br>
<br>
I think you would use a breadth first search and you would keep track
of a set of already visited states so that no state is considered more
than once.
Ed Merks
Professional Support: https://www.macromodeling.com/
|
|
|
| Re: Correct insertion point for child elements according to schema [message #590158 is a reply to message #49996] |
Thu, 12 August 2004 06:07 |
Mike Lischke
Messages: 78
Registered: July 2009 |
Member |
|
|
Ed Merks wrote:
> Mike,
> I think you would use a breadth first search and you would keep track of
> a set of already visited states so that no state is considered more than
> once. Thinking more about your original problem, there may be more
> than one valid place to insert something, or there may be no valid place
> unless you insert the element and some other elements to make it
> complete. Also, I'm curious if you are always trying to go from one
> valid instance to another valid instance; if so, the approach won't work
> for something that's initially empty and won't work for the case where
> more than one element needs to be inserted to produce a larger valid
> instance.
Well, I got it working with this code (sorry for german comments):
/**
* Fügt das gegebene Kindelement zu <b>parent</b> hinzu, berücksichtigt
dabei aber die richtige
* Position gemäßig aktivem Schema.
*
* @param parent Das Vaterelement, zu dem der neue Knoten hinzugefügt
werden soll.
* @param newChild Der hinzuzufügende Knoten.
* @return Gibt <b>true</b> zurück, wenn die Einfügeoperation
erfolgreich war, sonst <b>false</b>.
*/
public boolean placeChild(Element parent, Element newChild)
{
boolean result = false;
XSDElementDeclaration declaration =
elementDeclarations.find(parent.getNamespace(), parent.getName());
if (declaration != null)
{
XSDTypeDefinition definition = declaration.getTypeDefinition();
XSDParticle content = definition.getComplexType();
if (content != null)
{
State state = content.getDFA().getInitialState();
String uri = newChild.getNamespaceURI();
String name = newChild.getName();
for (int i = 0; i < parent.getChildren().size(); i++)
{
Element currentChild = (Element) parent.getChildren().get(i);
// Akzeptiert der aktuelle Status das neue Kindelement (soll
heißen, kann es vor dem
// aktuellen Kindelement eingefügt werden)?
Transition transition = state.accept(uri, name);
if (transition == null)
{
// Nicht akzeptiert an dieser Stelle. Gehe zum nächsten State.
transition = state.accept(currentChild.getNamespaceURI(),
currentChild.getName());
if (transition == null)
// Wenn es keinen gültigen nächsten State gibt, dann ist das
Vaterelement ungültig.
break;
else
state = transition.getState();
}
else
{
// Kindelement kann an dieser Stelle eingefügt werden, also
tue das.
parent.addContent(i, newChild);
result = true;
break;
}
}
// Wenn die Kindliste durchgearbeitet wurde, ohne dass ein
Zielpunkt bestimmt werden konnte,
// dann kann es möglich sein, dass der neue Knoten als letztes
Element eingefügt werden kann.
if (state.accept(uri, name) != null)
{
parent.addContent(newChild);
result = true;
}
}
}
return result;
}
What actually happens is that I take the existing child list and use this
to execute the DFA until I find a place where I can insert the new child.
This works also for an initially empty child list and multiple occurences.
I have yet to see a case that does not work correctly, but for now it does
what I need.
Now that I got familiar with the DFA I want to continue with code to
determine if a child can be deleted from its parent without making that
parent invalid.
Mike
--
www.soft-gems.net
|
|
| |
Goto Forum:
Current Time: Fri Dec 27 08:11:57 GMT 2024
Powered by FUDForum. Page generated in 0.25285 seconds |
] 
Search
Help
Register
Login
Home
