Device, Method, and Graphical User Interface for Collaborative Editing in Documents

• US 20160357720A1
• Filed: 09/30/2015
• Published: 12/08/2016
• Est. Priority Date: 06/07/2015
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Thimbleby, William J.
• Granted Patent: US 9,886,230 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• CPC Class Codes: G06F 3/0484 for the control of specific functions or operations, e.g. selecting or manipulating an object, an image or a displayed text element, setting a parameter value or selecting a range
• CPC Class Codes: G06F 3/0488 using a touch-screen or digitiser, e.g. input of commands through traced gestures
• CPC Class Codes: G06F 3/1423 controlling a plurality of local displays, e.g. CRT and flat panel display
• CPC Class Codes: G06F 3/1454 involving copying of the display data of a local workstation or window to a remote workstation or window so that an actual copy of the data is displayed simultaneously on two or more displays, e.g. teledisplay
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting
• CPC Class Codes: G06F 40/197 Version control for software G06F8/71
• CPC Class Codes: G06F 8/34 Graphical or visual programming
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/101 Collaborative creation, e.g. joint development of products or services
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 2200/24 involving graphical user interfaces [GUIs]
• CPC Class Codes: G09G 2370/10 Use of a protocol of communication by packets in interfaces along the display data pipeline
• CPC Class Codes: G09G 2370/16 Use of wireless transmission of display information
• CPC Class Codes: G09G 5/026 Control of mixing and/or overlay of colours in general G09G5/022 and G09G5/024 take precedence
• CPC Class Codes: G09G 5/12 Synchronisation between the display unit and other units, e.g. other display units, video-disc players
• CPC Class Codes: G09G 5/14 Display of multiple viewports
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data
• CPC Class Codes: H04L 65/4015 where at least one of the additional parallel sessions is real time or time sensitive, e.g. white board sharing, collaboration or spawning of a subconference

Abstract

A first electronic device with a display maintains a consistent output based on concurrent textual edits received at multiple collaborating devices. The first device maintains a directed acyclic graph to represent a textual string concurrently edited by the first device and at least a second device of the multiple collaborating devices. The directed acyclic graph includes: a plurality of nodes each representing a respective character input received from one or more of the multiple collaborating devices, and multiple parallel paths each including at least one node that represents a respective one of multiple concurrent character inputs received from distinct devices of the multiple collaborating devices. The first device topologically traverses the directed acyclic graph in accordance with a predetermined ordering rule to deterministically sort the plurality of nodes into a string sequence. The first device displays the textual string in accordance with the deterministically obtained string sequence.

Claims

1-25. -25. (canceled)

26. A method of maintaining a consistent output based on concurrent drawing edits received at multiple collaborating devices, including:

at a first device of the multiple collaborating devices, wherein the first device comprises one or more processors, memory, and a display;

maintaining a command sequence for a drawing currently rendered at the first device, wherein the command sequence includes a plurality of past drawing commands sorted according to respective sequence numbers of the past drawing commands, and wherein a sequence number of a drawing command is defined by (1) a device identifier for a device at which the drawing command was first received, (2) a primary local sequence number representing a local synchronization epoch during which the drawing command was first received, and (3) a secondary local sequence number representing an order of the drawing command within the local synchronization epoch;

receiving a plurality of additional drawing commands from two or more devices of the multiple collaborating devices, each of the plurality of additional drawing commands having a respective sequence number;

updating the command sequence, including merging and sorting the plurality of additional drawing commands and the plurality of past drawing commands in accordance with an ordering rule based on the respective sequence numbers of the plurality of past drawing commands and the plurality of additional drawing commands, wherein the ordering rule gives more significance to the primary local sequence number than the device identifier, and gives more significance to the device identifier than to the secondary local sequence number when comparing the respective sequence numbers; and

re-rendering at least a portion of the drawing based on the command sequence after updating the command sequence.

27. The method of claim 26, wherein a last drawing command in the plurality of additional drawing commands was received first at a collaborating device other than the first device, and the method further comprises:

starting a next local synchronization epoch at the first device, comprising;

incrementing the primary local sequence number for a subsequent drawing command locally received at the first device; and

restarting the secondary local sequence number for the subsequent drawing command locally received at the first device.

28. The method of claim 26, wherein a last drawing command in the plurality of additional drawing commands was received first at the first device, and the method further comprises:

incrementing the secondary local sequence number for a subsequent drawing command locally received at the first device, while maintaining the primary local sequence number of a current local synchronization epoch for the subsequent drawing command locally received at the first device.

29. The method of claim 26, wherein the plurality of additional drawing commands include an undo command directed to a respective past command in the command sequence, and wherein updating the command sequence by merging and sorting the plurality of additional drawing commands and the plurality of past drawing commands further comprises:

merging the undo command with the respective past command in the command sequence by;

identifying the corresponding past drawing command in the command sequence; and

changing a visibility attribute of the corresponding past drawing command in the command sequence to “

invisible”

, wherein the “

invisible”

attribute of the corresponding past drawing command causes said drawing command to be skipped during the re-rendering of the drawing.

30. The method of claim 29, further comprising:

after receiving the undo command, receiving a redo command directed to the undo command; and

in response receiving the redo command, changing the visibility attribute of the corresponding past drawing command in the command sequence to “

visible”

, wherein the “

visible”

attribute of the corresponding past drawing command causes said drawing command to be rendered in a next re-rendering of the drawing.

31. The method of claim 26, wherein the plurality of additional drawing commands includes an “

erase all”

command first received at the first device, and wherein merging the “

erase all”

command with the plurality of past drawing commands in the command sequence further comprises;

identifying all past drawing commands in the command sequence that were present at the first device before receipt of the “

erase all”

command; and

changing respective visibility attributes of the identified past drawing commands in the command sequence to “

invisible,”

wherein the respective “

invisible”

attributes of the identified past drawing commands cause said identified past drawing commands to be skipped during the re-rendering of the drawing.

32. The method of claim 26, including:

for each change in a respective visibility status of a respective drawing command, updating a timestamp associated with the respective drawing command in accordance with a receipt time of a respective drawing command that triggered the change in the respective visibility status of the respective drawing command.

33. The method of claim 32, wherein merging and sorting the plurality of additional drawing commands and the plurality of past drawing commands in accordance with the respective sequence numbers of the plurality of past drawing commands and the plurality of additional drawing commands further includes:

comparing respective timestamps assigned to two or more conflicting drawing commands in the plurality of past drawing commands and the plurality of additional drawing commands; and

selecting one of the two or more conflicting drawing commands for inclusion in the updated command sequence in lieu of the two or more conflicting drawing commands, wherein the selected drawing command has a latest timestamp among the respective timestamps assigned to the two or more conflicting drawing commands.

34. The method claim 26, wherein the plurality of additional drawing commands include an erase command to erase one or more existing pixels in the drawing, and wherein updating the command sequence by merging and sorting the plurality of additional drawing commands and the plurality of past drawing commands further comprises:

sorting the erase command against at least a first additional drawing command in the plurality of additional drawing commands based on the ordering rule, wherein the sorting places the erase command after the first additional drawing in the updated command sequence, and wherein re-rendering the drawing further comprises;

erasing at least some pixels that would have been drawn in accordance with the first additional drawing command.

35. A first electronic device, comprising:

a display;

one or more processors;

memory; and

one or more programs, wherein the one or more programs are stored in the memory and configured to be executed by the one or more processors, the one or more programs including instructions for;

maintaining a command sequence for a drawing currently rendered at the first electronic device, wherein the command sequence includes a plurality of past drawing commands sorted according to respective sequence numbers of the past drawing commands, and wherein a sequence number of a drawing command is defined by (1) a device identifier for a device at which the drawing command was first received, (2) a primary local sequence number representing a local synchronization epoch during which the drawing command was first received, and (3) a secondary local sequence number representing an order of the drawing command within the local synchronization epoch;

receiving a plurality of additional drawing commands from two or more devices of multiple collaborating devices, each of the plurality of additional drawing commands having a respective sequence number;

updating the command sequence, including merging and sorting the plurality of additional drawing commands and the plurality of past drawing commands in accordance with an ordering rule based on the respective sequence numbers of the plurality of past drawing commands and the plurality of additional drawing commands, wherein the ordering rule gives more significance to the primary local sequence number than the device identifier, and gives more significance to the device identifier than to the secondary local sequence number when comparing the respective sequence numbers; and

re-rendering at least a portion of the drawing based on the command sequence after updating the command sequence.

36. The first electronic device of claim 35, wherein a last drawing command in the plurality of additional drawing commands was received first at a collaborating device other than the first device, and the method further comprises:

starting a next local synchronization epoch at the first device, comprising;

incrementing the primary local sequence number for a subsequent drawing command locally received at the first device; and

restarting the secondary local sequence number for the subsequent drawing command locally received at the first device.

37. The first electronic device of claim 35, wherein a last drawing command in the plurality of additional drawing commands was received first at the first device, and the method further comprises:

incrementing the secondary local sequence number for a subsequent drawing command locally received at the first device, while maintaining the primary local sequence number of a current local synchronization epoch for the subsequent drawing command locally received at the first device.

38. The first electronic device of claim 35, wherein the plurality of additional drawing commands include an undo command directed to a respective past command in the command sequence, and wherein updating the command sequence by merging and sorting the plurality of additional drawing commands and the plurality of past drawing commands further comprises:

merging the undo command with the respective past command in the command sequence by;

identifying the corresponding past drawing command in the command sequence; and

changing a visibility attribute of the corresponding past drawing command in the command sequence to “

invisible”

, wherein the “

invisible”

attribute of the corresponding past drawing command causes said drawing command to be skipped during the re-rendering of the drawing.

39. The first electronic device of claim 38, wherein the one or more programs further include instructions for:

after receiving the undo command, receiving a redo command directed to the undo command; and

in response receiving the redo command, changing the visibility attribute of the corresponding past drawing command in the command sequence to “

visible”

, wherein the “

visible”

attribute of the corresponding past drawing command causes said drawing command to be rendered in a next re-rendering of the drawing.

40. The first electronic device of claim 35, wherein the plurality of additional drawing commands includes an “

erase all”

command first received at the first device, and wherein merging the “

erase all”

command with the plurality of past drawing commands in the command sequence further comprises;

identifying all past drawing commands in the command sequence that were present at the first device before receipt of the “

erase all”

command; and

changing respective visibility attributes of the identified past drawing commands in the command sequence to “

invisible,”

wherein the respective “

invisible”

attributes of the identified past drawing commands cause said identified past drawing commands to be skipped during the re-rendering of the drawing.

41. The first electronic device of claim 35, wherein the one or more programs further include instructions for:

for each change in a respective visibility status of a respective drawing command, updating a timestamp associated with the respective drawing command in accordance with a receipt time of a respective drawing command that triggered the change in the respective visibility status of the respective drawing command.

42. The first electronic device of claim 41, wherein merging and sorting the plurality of additional drawing commands and the plurality of past drawing commands in accordance with the respective sequence numbers of the plurality of past drawing commands and the plurality of additional drawing commands further includes:

comparing respective timestamps assigned to two or more conflicting drawing commands in the plurality of past drawing commands and the plurality of additional drawing commands; and

selecting one of the two or more conflicting drawing commands for inclusion in the updated command sequence in lieu of the two or more conflicting drawing commands, wherein the selected drawing command has a latest timestamp among the respective timestamps assigned to the two or more conflicting drawing commands.

43. The first electronic device of claim 35, wherein the plurality of additional drawing commands include an erase command to erase one or more existing pixels in the drawing, and wherein updating the command sequence by merging and sorting the plurality of additional drawing commands and the plurality of past drawing commands further comprises:

sorting the erase command against at least a first additional drawing command in the plurality of additional drawing commands based on the ordering rule, wherein the sorting places the erase command after the first additional drawing in the updated command sequence, and wherein re-rendering the drawing further comprises;

erasing at least some pixels that would have been drawn in accordance with the first additional drawing command.

44. A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which when executed by a first electronic device with a display, cause the first electronic device to:

maintain a command sequence for a drawing currently rendered at the first electronic device, wherein the command sequence includes a plurality of past drawing commands sorted according to respective sequence numbers of the past drawing commands, and wherein a sequence number of a drawing command is defined by (1) a device identifier for a device at which the drawing command was first received, (2) a primary local sequence number representing a local synchronization epoch during which the drawing command was first received, and (3) a secondary local sequence number representing an order of the drawing command within the local synchronization epoch;

receive a plurality of additional drawing commands from two or more devices of multiple collaborating devices, each of the plurality of additional drawing commands having a respective sequence number;

update the command sequence, including merging and sorting the plurality of additional drawing commands and the plurality of past drawing commands in accordance with an ordering rule based on the respective sequence numbers of the plurality of past drawing commands and the plurality of additional drawing commands, wherein the ordering rule gives more significance to the primary local sequence number than the device identifier, and gives more significance to the device identifier than to the secondary local sequence number when comparing the respective sequence numbers; and

re-render at least a portion of the drawing based on the command sequence after updating the command sequence.

45. The non-transitory computer readable storage medium of claim 44, wherein a last drawing command in the plurality of additional drawing commands was received first at a collaborating device other than the first device, and the method further comprises:

starting a next local synchronization epoch at the first device, comprising;

incrementing the primary local sequence number for a subsequent drawing command locally received at the first device; and

restarting the secondary local sequence number for the subsequent drawing command locally received at the first device.

46. The non-transitory computer readable storage medium of claim 44, wherein a last drawing command in the plurality of additional drawing commands was received first at the first device, and the method further comprises:

incrementing the secondary local sequence number for a subsequent drawing command locally received at the first device, while maintaining the primary local sequence number of a current local synchronization epoch for the subsequent drawing command locally received at the first device.

47. The non-transitory computer readable storage medium of claim 44, wherein the plurality of additional drawing commands include an undo command directed to a respective past command in the command sequence, and wherein updating the command sequence by merging and sorting the plurality of additional drawing commands and the plurality of past drawing commands further comprises:

merging the undo command with the respective past command in the command sequence by;

identifying the corresponding past drawing command in the command sequence; and

changing a visibility attribute of the corresponding past drawing command in the command sequence to “

invisible”

, wherein the “

invisible”

attribute of the corresponding past drawing command causes said drawing command to be skipped during the re-rendering of the drawing.

48. The non-transitory computer readable storage medium of claim 47, wherein the one or more programs comprising instructions, which when executed by the first electronic device with a display, cause the first electronic device to:

after receiving the undo command, receive a redo command directed to the undo command; and

in response receiving the redo command, change the visibility attribute of the corresponding past drawing command in the command sequence to “

visible”

, wherein the “

visible”

attribute of the corresponding past drawing command causes said drawing command to be rendered in a next re-rendering of the drawing.

49. The non-transitory computer readable storage medium of claim 44, wherein the plurality of additional drawing commands includes an “

erase all”

command first received at the first device, and wherein merging the “

erase all”

command with the plurality of past drawing commands in the command sequence further comprises;

identifying all past drawing commands in the command sequence that were present at the first device before receipt of the “

erase all”

command; and

changing respective visibility attributes of the identified past drawing commands in the command sequence to “

invisible,”

wherein the respective “

invisible”

attributes of the identified past drawing commands cause said identified past drawing commands to be skipped during the re-rendering of the drawing.

50. The non-transitory computer readable storage medium of claim 44, wherein the one or more programs comprising instructions, which when executed by the first electronic device with a display, cause the first electronic device to:

for each change in a respective visibility status of a respective drawing command, updating a timestamp associated with the respective drawing command in accordance with a receipt time of a respective drawing command that triggered the change in the respective visibility status of the respective drawing command.

51. The non-transitory computer readable storage medium of claim 50, wherein merging and sorting the plurality of additional drawing commands and the plurality of past drawing commands in accordance with the respective sequence numbers of the plurality of past drawing commands and the plurality of additional drawing commands further includes:

comparing respective timestamps assigned to two or more conflicting drawing commands in the plurality of past drawing commands and the plurality of additional drawing commands; and

selecting one of the two or more conflicting drawing commands for inclusion in the updated command sequence in lieu of the two or more conflicting drawing commands, wherein the selected drawing command has a latest timestamp among the respective timestamps assigned to the two or more conflicting drawing commands.

52. The non-transitory computer readable storage medium of claim 44, wherein the plurality of additional drawing commands include an erase command to erase one or more existing pixels in the drawing, and wherein updating the command sequence by merging and sorting the plurality of additional drawing commands and the plurality of past drawing commands further comprises:

sorting the erase command against at least a first additional drawing command in the plurality of additional drawing commands based on the ordering rule, wherein the sorting places the erase command after the first additional drawing in the updated command sequence, and wherein re-rendering the drawing further comprises;

erasing at least some pixels that would have been drawn in accordance with the first additional drawing command.