Method and apparatus for runtime merging of hierarchical trees

• US 20020188613A1
• Filed: 10/19/2001
• Published: 12/12/2002
• Est. Priority Date: 06/07/2001
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Heillig, Joerg, Chakraborty, Krishneadu, Wong, Amy M.
• Granted Patent: US 7,117,216 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/80 of semi-structured data, e.g. markup language structured data such as SGML, XML or HTML content-based retrieval of web data G06F16/95
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 7/32 Merging, i.e. combining data contained in ordered sequence on at least two record carriers to produce a single carrier or set of carriers having all the original data in the ordered sequence merging methods in generalG06F7/36 takes precedence
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Embodiments of the present invention relate to a method and apparatus for a runtime merging system of hierarchical trees with a reference node implementation. According to one or more embodiments of the present invention, a reference node is implemented which holds a reference to a node in a DOM tree active in memory. The reference node class allows adding nodes to the merged tree without having to make a clone of the node, which is an expensive operation. In one embodiment, if a particular node is not present below a certain level of the tree in any layer except a unique layer, it renders visiting the children of that node unnecessary. A reference is kept to the node in the memory.

Claims

1. A method for merging one or more hierarchical trees at runtime comprising:

examining one or more nodes in each of said hierarchical trees;

determining if there are one or more sets of equivalent nodes in said hierarchical trees;

picking one or more winning nodes from each of said sets of equivalent nodes; and

storing one or more reference nodes to said winning nodes.

2. The method of claim 1 wherein said hierarchical trees are document object model (DOM) trees.

3. The method of claim 1 further comprising:

printing a merged tree using said reference nodes.

4. The method of claim 1 wherein said reference nodes are one or more pointers.

5. The method of claim 1 wherein said reference nodes are one or more Java references.

6. The method of claim 1 wherein said picking further comprises:

examining one or more priorities associated with one or more members in each set of said equivalent nodes; and

selecting said winning node as said member with a highest of said priorities.

7. The method of claim 1 further comprising

generating one or more shallow clones for said winning nodes;

and

adding said shallow clones to a merged tree.

8. The method of claim 1 wherein said hierarchical trees include a group tree, a user tree, and an admin tree.

9. The method of claim 2 wherein said DOM trees are eXtensible Markup Language (XML) DOM trees.

10. A system for merging one or more hierarchical trees at runtime comprising:

one or more nodes in each of said hierarchical trees configured to be examined;

one or more sets of equivalent nodes in said hierarchical trees configured to be located if said sets of equivalent nodes exist;

one or more winning nodes configured to be picked from each set of said equivalent nodes; and

one or more reference nodes to said wing nodes configured to be stored.

11. The system of claim 10 wherein said hierarchical trees are document object model (DOM) trees.

12. The system of claim 10 further comprising:

a merged tree configured to be printed using said reference nodes.

13. The system of claim 10 wherein said reference nodes are one or more pointers.

14. The system of claim 10 wherein said reference nodes are one or more Java references.

15. The system of claim 10 wherein further comprising:

one or more priorities associated with one or members in each set of said equivalent nodes configured to be examined wherein said winning node is selected as said member with a highest of said priorities.

16. The system of claim 10 further comprising

one or more shallow clones for said winning nodes configured to be generated wherein said shallow clones are added to a merged tree.

17. The system of claim 10 wherein said hierarchical trees include a group tree, a user tree, and an admin tree.

18. The system of claim 11 wherein said DOM trees are eXtensible Markup Language (XML) DOM trees.

20. The computer program product of claim 19 wherein said hierarchical trees are document object model (DOM) trees.

21. The computer program product of claim 19 further comprising:

computer readable code configured to cause a computer to print a merged tree using said reference nodes.

22. The computer program product of claim 19 wherein said reference nodes are one or more pointers.

23. The computer program product of claim 19 wherein said reference nodes are one or more Java references.

24. The computer program product of claim 19 wherein said computer readable code configured to cause a computer to pick further comprises:

computer readable code configured to cause a computer to examine one or more priorities associated with one or more members in each set of said equivalent nodes; and

computer readable code configured to cause a computer to select said winning node as said member with a highest of said priorities.

25. The computer program product of claim 19 further comprising

computer readable code configured to cause a computer to generate one or more shallow clones for said wining nodes;

and

computer readable code configured to cause a computer to add said shallow clones to a merged tree.

26. The computer program product of claim 19 wherein said hierarchical trees include a group tree, a user tree, and an admin tree.

27. The computer program product of claim 20 wherein said DOM trees are eXtensible Markup Language (XML) DOM trees.

29. The apparatus of claim 28 wherein said hierarchical trees are document object model (DOM) trees.

30. The apparatus of claim 28 further comprising:

means for printing a merged tree using said reference nodes.

31. The apparatus of claim 28 wherein said reference nodes are one or more pointers.

32. The apparatus of claim 28 wherein said reference nodes are one or more Java references.

33. The apparatus of claim 28 further comprising:

means for examining one or more priorities associated with one or members in each set of said equivalent nodes; and

means for selecting said winning node as said member with a highest of said priorities.

34. The apparatus of claim 28 further comprising

means for generating one or more shallow clones for said wining nodes wherein said shallow clones are added to a merged tree.

35. The apparatus of claim 28 wherein said hierarchical trees include a group tree, a user tree, and an admin tree.

36. The apparatus of claim 29 wherein said DOM trees are eXtensible Markup Language (XML) DOM trees.

19. A computer program product comprising:

a computer usable medium having computer readable program code embodied therein configured to merge one or more hierarchical trees at runtime comprising;

computer readable code configured to cause a computer to examine one or more nodes in each of said hierarchical trees;

computer readable code configured to cause a computer to determine if there are one or more sets of equivalent nodes in said hierarchical trees;

computer readable code configured to cause a computer to pick one or more winning nodes from each set of said equivalent nodes; and

computer readable code configured to cause a computer to store one or more reference nodes to said winning nodes.

28. An apparatus for merging one or more hierarchical trees at runtime comprising:

means for examining one or more nodes in each of said hierarchical trees;

means for locating one or more sets of equivalent nodes in said hierarchical trees, if said sets of equivalent nodes exist;

means for picking one or more winning nodes from each set of said equivalent nodes; and

means for storing one or more reference nodes to said winning nodes.