Back to results
US 9,959,338 B2Granted
Document order management via relaxed node indexing
AssigneeInternational Business Machines Corporation
InventorJohn M. Boyer
Life of this patent
Estimating the term…
Abstract
An illustrative embodiment includes processing parse tree data. A parse tree data structure that is representative of a document object model (DOM) tree data structure is received. Concomitant to receiving the parse tree data structure, an assignment of index values for the DOM nodes consisting of distinct index values for each existing DOM node is received by the processor. Requests to manipulate the parse tree data structure that include node inserts and document order comparisons are also performed.
Claims18
A method for processing parse tree data, the method comprising:
- receiving, by a processor, a parse tree data structure, wherein the parse tree data structure is representative of a document object model (DOM) tree data structure;
- concomitant to receiving the parse tree data structure, receiving, by the processor, an assignment of index values for the DOM nodes consisting of distinct index values for each existing DOM node;
- receiving, by the processor, a request to manipulate the parse tree data structure, wherein the request comprises an insert DOM node request for a new DOM node;
- concomitant to receiving the request to manipulate the parse tree data structure, receiving, by the processor, an indication of a parse tree insert location for the new DOM node to be inserted;
- responsive to receiving the indication of the parse tree insert location:
- assigning a distinguishable index value to the new DOM node to be inserted;
- and
- inserting the new DOM node at the indicated parse tree insert location;
- receiving, by the processor, a document order comparison request to determine an earlier of a first given DOM node and a second given DOM node;
- responsive to receiving the document order comparison request, determining whether the document order comparison request can be satisfied by a comparison of the index values of the first given DOM node and the second given DOM node;
- responsive to determining that the document order comparison request can be satisfied by a comparison of the index values of the first given DOM node and the second given DOM node, selecting as the earlier DOM node one of the first given DOM node and the second DOM node based on the comparison of the index values of the first given DOM node and the second given DOM node;
- subsequent to receiving the parse tree data structure, projecting, by the processor, the parse tree data structure received onto a data structure comprising a binary tree, wherein the projecting includes storing a projection that includes an association between each DOM node in a successive pre-order traversal of the parse tree and each binary tree node in a successive in-order traversal of the binary tree thereby creating a map between the parse tree data structure and the binary tree data structure;
- subsequent to inserting the new DOM node at the indicated parse tree insert location, the processor:
- creates a corresponding binary tree node;
- associates the corresponding binary tree node with the new DOM node;
- identifies a binary tree insertion point location for the corresponding binary tree node associated with the new DOM node;
- and
- inserts the corresponding binary tree node into the binary tree at the identified binary tree insertion point location;
- and
- responsive to a determination that the document order comparison request cannot be satisfied by the comparison of the index values of the first given DOM node and the second given DOM node, selecting as the earlier DOM node one of the first given DOM node and the second DOM node using a binary tree document order comparison as a secondary comparison method, wherein the binary tree document order comparison comprises:
- obtaining a first corresponding binary tree node associated by the projection with the first given DOM node and a second corresponding binary tree node associated by the projection with the second given DOM node;
- determining which of the first corresponding binary tree node and the second corresponding binary tree node is earlier in a traversal order of the binary tree;
- selecting a DOM node associated with a determined earlier corresponding binary tree node as the earlier DOM node;
- and
- returning an indication of the selected earlier DOM node as the earlier of the first given DOM node and the second given DOM node.
22 more elements
A computer program product for processing parse tree data, the computer program product comprising:
- a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising:
- receiving a parse tree data structure, wherein the parse tree data structure is representative of a document object model (DOM) tree data structure;
- concomitant to receiving the parse tree data structure, receiving an assignment of index values for the DOM nodes consisting of distinct index values for each existing DOM node;
- receiving a request to manipulate the parse tree data structure, wherein the request comprises an insert DOM node request for a new DOM node;
- concomitant to receiving the request to manipulate the parse tree data structure, receiving an indication of a parse tree insert location for the new DOM node to be inserted;
- responsive to receiving the indication of the parse tree insert location:
- assigning a distinguishable index value to the new DOM node to be inserted;
- and
- inserting the new DOM node at the indicated parse tree insert location;
- receiving a document order comparison request to determine an earlier of a first given DOM node and a second given DOM node;
- responsive to receiving the document order comparison request, determining whether the document order comparison request can be satisfied by a comparison of the index values of the first given DOM node and the second given DOM node;
- responsive to determining that the document order comparison request can be satisfied by a comparison of the index values of the first given DOM node and the second given DOM node, selecting as the earlier DOM node one of the first given DOM node and the second DOM node based on the comparison of the index values of the first given DOM node and the second given DOM node;
- subsequent to receiving the parse tree data structure, projecting, by the processor, the parse tree data structure received onto a data structure comprising a binary tree, wherein the projecting includes storing a projection that includes an association between each DOM node in a successive pre-order traversal of the parse tree and each binary tree node in a successive in-order traversal of the binary tree thereby creating a map between the parse tree data structure and the binary tree data structure;
- subsequent to inserting the new DOM node at the indicated parse tree insert location, the processor:
- creates a corresponding binary tree node;
- associates the corresponding binary tree node with the new DOM node;
- identifies a binary tree insertion point location for the corresponding binary tree node associated with the new DOM node;
- and
- inserts the corresponding binary tree node into the binary tree at the identified binary tree insertion point location;
- and
- responsive to a determination that the document order comparison request cannot be satisfied by the comparison of the index values of the first given DOM node and the second given DOM node, selecting as the earlier DOM node one of the first given DOM node and the second DOM node using a binary tree document order comparison as a secondary comparison method, wherein the binary tree document order comparison comprises:
- obtaining a first corresponding binary tree node associated by the projection with the first given DOM node and a second corresponding binary tree node associated by the projection with the second given DOM node;
- determining which of the first corresponding binary tree node and the second corresponding binary tree node is earlier in a traversal order of the binary tree;
- selecting a DOM node associated with a determined earlier corresponding binary tree node as the earlier DOM node;
- and
- returning an indication of the selected earlier DOM node as the earlier of the first given DOM node and the second given DOM node.
23 more elements
An apparatus for processing parse tree data, the apparatus comprising:
- a memory having computer readable instructions;
- and
- a processor configured to execute the computer readable instructions, the instructions comprising:
- receiving, a parse tree data structure, wherein the parse tree data structure is representative of a document object model (DOM) tree data structure;
- concomitant to receiving the parse tree data structure, receiving an assignment of index values for the DOM nodes consisting of distinct index values for each existing DOM node;
- receiving a request to manipulate the parse tree data structure, wherein the request comprises an insert DOM node request for a new DOM node;
- concomitant to receiving the request to manipulate the parse tree data structure, receiving an indication of a parse tree insert location for the new DOM node to be inserted;
- responsive to receiving the indication of the parse tree insert location:
- assigning a distinguishable index value to the new DOM node to be inserted;
- and
- inserting the new DOM node at the indicated parse tree insert location;
- receiving a document order comparison request to determine an earlier of a first given DOM node and a second given DOM node;
- responsive to receiving the document order comparison request, determining whether the document order comparison request can be satisfied by a comparison of the index values of the first given DOM node and the second given DOM node;
- responsive to determining that the document order comparison request can be satisfied by a comparison of the index values of the first given DOM node and the second given DOM node, selecting as the earlier DOM node one of the first given DOM node and the second DOM node based on the comparison of the index values of the first given DOM node and the second given DOM node;
- subsequent to receiving the parse tree data structure, projecting, by the processor, the parse tree data structure received onto a data structure comprising a binary tree, wherein the projecting includes storing a projection that includes an association between each DOM node in a successive pre-order traversal of the parse tree and each binary tree node in a successive in-order traversal of the binary tree thereby creating a map between the parse tree data structure and the binary tree data structure;
- subsequent to inserting the new DOM node at the indicated parse tree insert location, the processor:
- creates a corresponding binary tree node;
- associates the corresponding binary tree node with the new DOM node;
- identifies a binary tree insertion point location for the corresponding binary tree node associated with the new DOM node;
- and
- inserts the corresponding binary tree node into the binary tree at the identified binary tree insertion point location;
- and
- responsive to a determination that the document order comparison request cannot be satisfied by the comparison of the index values of the first given DOM node and the second given DOM node, selecting as the earlier DOM node one of the first given DOM node and the second DOM node using a binary tree document order comparison as a secondary comparison method, wherein the binary tree document order comparison comprises:
- obtaining a first corresponding binary tree node associated by the projection with the first given DOM node and a second corresponding binary tree node associated by the projection with the second given DOM node;
- determining which of the first corresponding binary tree node and the second corresponding binary tree node is earlier in a traversal order of the binary tree;
- selecting a DOM node associated with a determined earlier corresponding binary tree node as the earlier DOM node;
- and
- returning an indication of the selected earlier DOM node as the earlier of the first given DOM node and the second given DOM node.
25 more elements
Dependencies are inferred from the claim text.