Ordered list management

• US 20060041577A1
• Filed: 08/20/2004
• Published: 02/23/2006
• Est. Priority Date: 08/20/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Guarraci, Brian J., Natarajan, Aarthi, Vert, John D., Wayt, Edward H., Ellicott, Geoffrey John
• Granted Patent: US 7,603,362 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 7/36 Combined merging and sorting

Abstract

Ordered list management is described. An item'"'"'s position within an ordered list is represented by a path value. A globally unique identifier (GUID) is appended to the path value to enable simultaneous or near-simultaneous modifications to the ordered list without conflict. Furthermore, an ordered list-specific seed value may be prepended to each item'"'"'s path value to ensure clustering of ordered list items when two or more ordered lists are merged.

Claims

1. A method comprising:

identifying an item to be placed at a particular position within an ordered list;

associating a path value with the item such that the path value represents the particular position within the ordered list;

generating a unique identifier; and

appending the unique identifier to the path value associated with the item.

2. The method as recited in claim 1 wherein the path value is based on a binary tree structure.

3. The method as recited in claim 1 wherein the associating comprises:

determining a path value associated with an immediately previous item in the ordered list;

determining a path value associated with an immediately next item in the ordered list;

determining a path value that is greater than the path value associated with the immediately previous item in the ordered list and that is less than the path value associated with the immediately next item in the ordered list; and

associating the path value that is greater than the path value associated with the immediately previous item in the ordered list and that is less than the path value associated with the immediately next item in the ordered list with the item.

4. The method as recited in claim 3 wherein the determining a path value that is greater than the path value associated with the immediately previous item in the ordered list and that is less than the path value associated with the immediately next item in the ordered list comprises:

determining a string of corresponding and matching digits from the left of the path values associated with the immediately previous and immediately next items in the ordered list;

determining the first corresponding, but non-matching digits from the left of the path values associated with the immediately previous and immediately next items in the ordered list;

in an event that the first corresponding, but non-matching digit from the immediately previous item is a null, appending to the string of corresponding and matching digits, the first corresponding, but non-matching digit from the path value associated with the immediately next item in the ordered list and a “

0”

.

5. The method as recited in claim 4 further comprising:

in an event that the first corresponding, but non-matching digit from the immediately previous item is not a null, appending to the string of corresponding and matching digits, the first corresponding, but non-matching digit from the path value associated with the immediately previous item in the ordered list and a “

1”

.

6. The method as recited in claim 1 wherein the unique identifier comprises a globally unique identifier (GUID).

7. The method as recited in claim 6 wherein the GUID comprises a binary value.

8. The method as recited in claim 1 further comprising:

determining a seed value associated with the ordered list; and

prepending the seed value to the path value associated with the item.

9. The method as recited in claim 8 wherein the seed value comprises a globally unique identifier (GUID).

10. The method as recited in claim 9 wherein the GUID comprises a binary value.

11. A peer-to-peer application configured to implement the method as recited in claim 1.

12. A server computer system configured to implement the method as recited in claim 1.

13. One or more computer-readable media having computer-readable instructions thereon which, when executed by a computer, cause the computer to implement the method as recited in claim 1.

14. A method comprising:

identifying first and second ordered lists to be merged;

associating path values with each item in each of the ordered lists to be merged such that the path values represent each item'"'"'s relative position in either the first or second ordered list;

associating a first seed value with the first ordered list by prepending the first seed value to the beginning of the path values associated with each item in the first ordered list;

associating a second seed value with the second ordered list by prepending the second seed value to the beginning of the path values associated with each item in the second ordered list;

merging the first and second ordered lists; and

determining the order of the items in a merged list based on the path values associated with each of the items, such that the items associated with the first ordered list are clustered within the merged list, and the items associated with the second ordered list are clustered within the merged list.

15. The method as recited in claim 14 wherein the path values are based on a binary tree structure.

16. A method comprising:

maintaining an ordered list of items comprising item A and item B;

receiving an indication of a first item to be added to the ordered list between existing items A and B;

receiving a near-simultaneous indication of a second item to be added to the ordered list between existing items A and B;

adding the first item to the ordered list between existing items A and B by associating with the first item, a first path value that is greater than a path value associated with existing item A and less than a path value associated with existing item B;

adding the second item to the ordered list between existing items A and B by associating with the second item, a second path value that is greater than a path value associated with existing item A and less than a path value associated with existing item B; and

determining the order of the first and second items between items A and B based on a comparison of the first path value associated with the first item and the second path value associated with the second value.

17. The method as recited in claim 16 wherein the associating with the first item, a first path value that is greater than a path value associated with existing item A and less than a path value associated with existing item B comprises:

determining a path value that is greater than a path value associated with existing item A and less than a path value associated with existing item B;

appending a GUID to the end of the path value; and

associating the path value with the first item.

18. The method as recited in claim 17 wherein the determining comprises:

determining that a path value associated with item B is greater than a path value associated with item A;

determining a string of matching digits from the path value associated with item A and the path value associated with item B;

comparing the first non-matching digits from the path value associated with item A and the path value associated with item B;

in an event that the first non-matching digit from the path value associated with item A is null, appending to the end of the string of matching digits, the first non-matching digit from the path value associated with item B and a 0.

19. The method as recited in claim 18 further comprising:

in an event that the first non-matching digit from the path value associated with item A is not null, appending to the end of the string of matching digits, the first non-matching digit from the path value associated with item A and a 1.

20. A system comprising:

a processor;

a memory;

an application stored in memory and executed on the processor, the application configured to manage an ordered list of items by representing item positions within the ordered list based on each item'"'"'s relative position to other items within the ordered list; and

an insert algorithm configured to generate a path value that represents a relative position of a particular item within the ordered list, such that two items added simultaneously to the same position within the ordered list are assigned different path values.

21. The system as recited in claim 20 wherein the application comprises a peer-to-peer application.

22. The system as recited in claim 20 wherein the path value comprises:

a binary tree structure-based value; and

a GUID.

23. The system as recited in claim 22 wherein the path value further comprises a seed value associated with the ordered list.

24. The system as recited in claim 20 further comprising:

a compare algorithm configured to determine, based on path values associated with items, a relative order of two or more items within an ordered list.

25. One or more computer-readable media comprising computer-readable instructions which, when executed, cause a computer system to:

associate a path value with an item in an ordered list such that the path value represents the item'"'"'s position in the ordered list relative to positions of other items in the ordered list; and

append a GUID to the end of the path value to prevent associating identical path values with two items within the ordered list.

26. The one or more computer-readable media as recited in claim 25 further comprising computer-readable instructions which, when executed, cause the computer system to prepend to the path value a seed value that is associated with the ordered list, such that items associated with the ordered list will appear clustered if the ordered list is merged with another ordered list.