Method and apparatus for runtime merging of hierarchical trees

• US 7,117,216 B2
• Filed: 10/19/2001
• Issued: 10/03/2006
• Est. Priority Date: 06/07/2001
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Heilig, Joerg, Wong, Amy M., Chakraborty, Krishnendu
• Primary Examiner(s): Gaffin, Jeffrey
• Assistant Examiner(s): Mahmoudi, Hassan
• Application Number:
  US10/038,203
• Publication Number:
  US 20020188613A1
• Time in Patent Office: 1,810 Days
• Field of Search: 707/1, 707/3, 707/5, 707/7, 707/10, 707/102, 707/500, 707/100, 707/104.1, 707/6, 707/513, 717/140, 715/500, 709/242
• US Class Current: 1/1
• 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 in a data processing system comprising:

examining nodes in a plurality of hierarchical trees;

determining if a node is present in only one tree by comparing two or more of the hierarchical trees;

creating a merged tree based on the nodes in the hierarchical trees;

determining if the hierarchical trees comprise a set of equivalent nodes

selecting a node with the highest priority from the set of equivalent nodes if the hierarchical trees comprise a set of equivalent nodes;

creating a shallow clone of the selected node; and

adding the shallow clone to the merged tree.

2. The method of claim 1 further comprising:

creating a reference node to the node determined to be present in only one tree if a node is determined to be present in only one tree; and

adding the reference node to the merged tree.

3. The method of claim 2 wherein the reference node is a pointer.

4. The method of claim 2 wherein the reference node is a Java reference.

5. The method of claim 1 wherein the hierarchical trees comprise a group tree and a user tree.

6. The method of claim 1 wherein the hierarchical trees comprise a group tree and an admin tree.

7. The method of claim 1 wherein the hierarchical trees comprise a user tree and an admin tree.

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

9. The method of claim 1 wherein the hierarchical trees are DOM trees.

10. The method of claim 9 wherein the DOM trees are XML DOM trees.

11. The method of claim 1 further comprising:

printing the merged tree.

12. A data processing computer comprising:

a memory comprising a program that;

examines nodes in a plurality of hierarchical trees;

determines if a node is present in only one tree by comparing two or more of the hierarchical trees;

creates a merged tree based on the nodes in the hierarchical trees;

determines if the hierarchical trees comprise a set of equivalent nodes;

selects a node with the highest priority from the set of equivalent nodes if the hierarchical trees comprise a set of equivalent nodes;

creates a shallow clone of the selected node; and

adds the shallow clone to the merged tree; and

a processor for running the program.

13. The data processing computer of claim 12 wherein the program further:

creates a reference node to the node determined to be present in only one tree if a node is determined to be present in only one tree; and

adds the reference node to the merged tree.

14. The data processing computer of claim 13 wherein the reference node is a pointer.

15. The data processing computer of claim 13 wherein the reference node is a Java reference.

16. The data processing computer of claim 12 wherein the hierarchical trees comprise a group tree and a user tree.

17. The data processing computer of claim 12 wherein the hierarchical trees comprise a group tree and an admin tree.

18. The data processing computer of claim 12 wherein the hierarchical trees comprise a user tree and an admin tree.

19. The data processing computer of claim 12 wherein the hierarchical trees comprise a group tree, a user tree, and an admin tree.

20. The data processing computer of claim 12 wherein the hierarchical trees are DOM trees.

21. The data processing computer of claim 20 wherein the DOM trees are XML DOM trees.

22. The data processing computer of claim 12 wherein the program further:

prints the merged tree.

23. A computer-readable medium storing computer-readable instructions for controlling a data processing system to perform a method comprising the steps of:

examining nodes in a plurality of hierarchical trees;

determining if a node is present in only one tree by comparing two or more of the hierarchical trees; and

creating a merged tree based on the nodes in the hierarchical trees;

determining if the hierarchical trees comprise a set of equivalent nodes;

selecting a node with the highest priority from the set of equivalent nodes if the hierarchical trees comprise a set of equivalent nodes;

creating a shallow clone of the selected node; and

adding the shallow clone to the merged tree.

24. The computer-readable medium of claim 23 wherein the method further comprises the steps of:

creating a reference node to the node determined to be present in only one tree if a node is determined to be present in only one tree; and

adding the reference node to the merged tree.

25. The computer-readable medium of claim 24 wherein the reference node is a pointer.

26. The computer-readable medium of claim 24 wherein the reference node is a Java reference.

27. The computer-readable medium of claim 23 wherein the hierarchical trees comprise a group tree and a user tree.

28. The computer-readable medium of claim 23 wherein the hierarchical trees comprise a group tree and an admin tree.

29. The computer-readable medium of claim 23 wherein the hierarchical trees comprise a user tree and an admin tree.

30. The computer-readable medium of claim 23 wherein the hierarchical trees comprise a group tree, a user tree, and an admin tree.

31. The computer-readable medium of claim 23 wherein the hierarchical trees are DOM trees.

32. The computer-readable medium of claim 31 wherein the DOM trees are XML DOM trees.

33. The computer-readable medium of claim 23 wherein the method further comprises the step of:

printing the merged tree.