Device, method, and graphical user interface for collaborative editing in documents

• US 10,089,056 B2
• Filed: 09/30/2015
• Issued: 10/02/2018
• Est. Priority Date: 06/07/2015
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Thimbleby, William J.
• Primary Examiner(s): Bashore, William L
• Assistant Examiner(s): Parcher, Daniel W
• Application Number:
  US14/871,950
• Publication Number:
  US 20160357496A1
• Time in Patent Office: 1,098 Days
• 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 maintains a directed acyclic graph to represent content collaboratively edited by the first device and one or more second devices of multiple collaborating devices. The first device receives one or more editing inputs from one or more devices of the multiple collaborating devices. The first device modifies the directed acyclic graph based on relationships between the editing inputs and existing content objects embodied in the directed acyclic graph, traverses the directed acyclic graph in accordance with a predetermined ordering rule to obtain an object sequence, and, if a first editing input of the one or more editing inputs modifies a first existing sketch content object represented in the directed acyclic graph, updates a command sequence associated with the first existing sketch content object by merging each individual drawing command included the first editing input with a command sequence associated with the first existing sketch content object.

Claims

1. A method of supporting collaborative editing, including:

at a first device of multiple collaborating devices, wherein the first device comprises one or more processors, memory, and a display, and the first device includes one or more user-interface devices for receiving editing inputs from a user of the first device;

maintaining a directed acyclic graph to represent content collaboratively edited by the first device and one or more second devices of the multiple collaborating devices, wherein the directed acyclic graph includes a plurality of nodes each representing a respective content object that is created or edited by one or more of the multiple collaborating devices, wherein at least a first node of the plurality of nodes represents a textual content object and at least a second node of the plurality of nodes represents a sketch content object, and wherein each node representing a corresponding sketch content object includes a respective command sequence used to create content of the corresponding sketch content object;

during a respective synchronization period, receiving one or more editing inputs from one or more devices of the multiple collaborating devices;

modifying the directed acyclic graph based on relationships between the editing inputs and existing content objects embodied in the directed acyclic graph;

determining whether the one or more editing inputs modifies an existing sketch content object represented in the directed acyclic graph; and

in accordance with a determination that a first editing input of the one or more editing inputs modifies a first existing sketch content object represented by a first command sequence in a first respective node in the directed acyclic graph, updating the first command sequence in the first respective node by merging each individual drawing command included in the first editing input with the first command sequence to produce, in the first respective node, an updated first command sequence of two or more commands that represents the first existing sketch content object as modified by the first editing input.

2. The method of claim 1, further comprising:

rendering the first existing sketch content object represented in the modified directed acyclic graph, the rendering comprising;

determining a global position or state of the first existing sketch content object in the content in accordance with a topological traversal of the directed acyclic graph;

determining an internal appearance of the first existing sketch content object in accordance with the updated first command sequence in the first respective node; and

rendering the first existing sketch content in accordance with the determined global position or state of the first existing sketch content object and in accordance with the determined internal appearance of the first existing sketch content object.

3. The method of claim 1, wherein the directed acyclic graph includes multiple parallel paths each including at least one node that represents a respective one of multiple concurrent editing inputs received from distinct devices of the multiple collaborating devices.

4. The method of claim 1, wherein each node in the directed acyclic graph includes a unique object sequence number for the respective content object associated with the node, and wherein the unique object sequence number includes (1) a unique device identifier for a respective device at which the respective content object was first created, and (2) a local sequence number assigned to the respective content object in accordance with a local order by which the respective content object was first created at said respective device.

5. The method of claim 1, including traversing the directed acyclic graph in accordance with a predetermined ordering rule to obtain an object sequence, said traversing including:

sorting nodes between a starting node to an end node of a set of multiple parallel paths in the directed acyclic graph by traversing the set of multiple parallel paths in an order based on a comparison between respective lowest object sequence numbers present in each of the set of multiple parallel paths.

6. The method of claim 1, wherein, for each node representing a sketch content object, the node includes a sequence of one or more drawing commands directed to the sketch content object, each of the one or more drawing commands has a respective command sequence number, and the respective command sequence number includes (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.

7. The method of claim 6, wherein updating the first command sequence in the first respective node comprises:

merging and sorting each individual drawing command and one or more past drawing commands in the first command sequence in accordance with an ordering rule based on respective command sequence numbers of the one or more past drawing commands and said each individual drawing command, 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 command sequence numbers.

8. The method of claim 1, wherein modifying the directed acyclic graph based on relationships between the editing inputs and existing content objects embodied in the directed acyclic graph further comprises:

detecting that the one or more editing inputs include at least two concurrent insertion inputs between a first node and a second node in the directed acyclic graph from multiple ones of the multiple collaborating devices, and

for each of the concurrent insertion inputs, creating a respective path from the first node to the second node in the directed acyclic graph to include one or more nodes represented in the insertion input.

9. The method of claim 1, wherein modifying the directed acyclic graph based on relationships between the editing inputs and existing content objects embodied in the directed graph further comprises:

detecting that the one or more editing inputs include a deletion input deleting a content object represented by a second respective node in the directed acyclic graph; and

in response to the deletion input, changing a status of the second respective node for the object to “

deleted”

, wherein the second respective node having the “

deleted”

status is omitted during display rendering of the content based on the modified directed acyclic graph.

10. The method of claim 1, wherein modifying the directed acyclic graph based on relationships between the editing inputs and existing content objects embodied in the directed acyclic graph further comprises:

detecting that the one or more editing inputs include an undo input restoring a deleted content object represented by a second respective node in the directed acyclic graph, wherein a status of the second respective node is a “

deleted”

status; and

in response to the undo input,

removing the “

deleted”

status from the second respective node for the deleted content object in the directed acyclic graph; and

updating a unique object sequence number of the second respective node for the deleted content object in the directed acyclic graph based on a respective timestamp and a respective source device associated with the undo input.

11. The method of claim 1, wherein modifying the directed acyclic graph based on relationships between the editing inputs and existing content objects embodied in the directed acyclic graph further comprises:

detecting that the one or more editing inputs include a style input changing a style of a content object represented by a second respective node in the directed acyclic graph; and

in response to the style input, changing a style attribute of the second respective node for the content object in the directed acyclic graph, wherein the style attribute includes a respective style and a respective timestamp associated with the style input.

12. The method of claim 1, wherein modifying the directed acyclic graph based on relationships between the editing inputs and existing content objects embodied in the directed acyclic graph further comprises:

detecting that the one or more editing inputs include at least two concurrent style inputs changing a style of a content object represented by a second respective node in the directed acyclic graph, wherein the concurrent style inputs are associated with difference devices and timestamps; and

in response to receiving the concurrent style inputs, changing a style attribute of the second respective node for said content object in the directed acyclic graph in accordance with the style input having a latest timestamp among the concurrent style inputs.

13. The method of claim 1, wherein updating the first command sequence in the first respective node comprises:

detecting that the first editing input is an undo command directed to a respective past drawing command in the first command sequence; and

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

invisible”

, wherein the “

invisible”

attribute of the respective past drawing command causes said past drawing command to be skipped during a re-rendering of the first existing sketch content object at the first device.

14. The method of claim 13, further comprising:

receiving a redo command directed to the undo command in a later synchronization period; and

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

visible”

, wherein the “

visible”

attribute of the respective past drawing command causes said past drawing command to be rendered in a next re-rendering of the first existing sketch object associated with the later synchronization period.

15. A first electronic device, comprising:

a display;

one or more processors;

memory; and

one or more programs, wherein the first electronic device includes one or more user-interface devices for receiving editing inputs from a user of the first electronic device, and 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 directed acyclic graph to represent content collaboratively edited by the first electronic device and one or more second electronic devices of multiple collaborating devices, wherein the directed acyclic graph includes a plurality of nodes each representing a respective content object that is created or edited by one or more of the multiple collaborating devices, wherein at least a first node of the plurality of nodes represents a textual content object and at least a second node of the plurality of nodes represents a sketch content object, and wherein each node representing a corresponding sketch content object includes a respective command sequence used to create content of the corresponding sketch content object;

during a respective synchronization period, receiving one or more editing inputs from one or more devices of the multiple collaborating devices;

modifying the directed acyclic graph based on relationships between the editing inputs and existing content objects embodied in the directed acyclic graph;

determining whether the one or more editing inputs modifies an existing sketch content object represented in the directed acyclic graph; and

in accordance with a determination that a first editing input of the one or more editing inputs modifies a first existing sketch content object represented by a first command sequence in a first respective node in the directed acyclic graph, updating the first command sequence in the first respective node by merging each individual drawing command included in the first editing input with the first command sequence to produce, in the first respective node, an updated first command sequence of two or more commands that represents the first existing sketch content object as modified by the first editing input.

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

rendering the first existing sketch content object represented in the modified directed acyclic graph, the rendering comprising;

determining a global position or state of the first existing sketch content object in the content in accordance with a topological traversal of the directed acyclic graph;

determining an internal appearance of the first existing sketch content object in accordance with the updated first command sequence in the first respective node; and

rendering the first existing sketch content in accordance with the determined global position or state of the first existing sketch content object and in accordance with the determined internal appearance of the first existing sketch content object.

17. The first electronic device of claim 15, wherein the directed acyclic graph includes multiple parallel paths each including at least one node that represents a respective one of multiple concurrent editing inputs received from distinct devices of the multiple collaborating devices.

18. The first electronic device of claim 15, wherein each node in the directed acyclic graph includes a unique object sequence number for the respective content object associated with the node, and wherein the unique object sequence number includes (1) a unique device identifier for a respective device at which the respective content object was first created, and (2) a local sequence number assigned to the respective content object in accordance with a local order by which the respective content object was first created at said respective device.

19. The first electronic device of claim 15, wherein the one or more programs include instructions for traversing the directed acyclic graph in accordance with a predetermined ordering rule to obtain an object sequence, said traversing including:

sorting nodes between a starting node to an end node of a set of multiple parallel paths in the directed acyclic graph by traversing the set of multiple parallel paths in an order based on a comparison between respective lowest object sequence numbers present in each of the set of multiple parallel paths.

20. The first electronic device of claim 15, wherein, for each node representing a sketch content object, the node includes a sequence of one or more drawing commands directed to the sketch content object, each of the one or more drawing commands has a respective command sequence number, and the respective command sequence number includes (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.

21. The first electronic device of claim 20, wherein updating the first command sequence in the first respective node comprises:

merging and sorting each individual drawing command and one or more past drawing commands in the first command sequence in accordance with an ordering rule based on respective command sequence numbers of the one or more past drawing commands and said each individual drawing command, 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 command sequence numbers.

22. 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, the first electronic device including one or more user-interface devices for receiving editing inputs from a user of the first electronic device, cause the first electronic device to:

maintain a directed acyclic graph to represent content collaboratively edited by the first electronic device and one or more second electronic devices of multiple collaborating devices, wherein the directed acyclic graph includes a plurality of nodes each representing a respective content object that is created or edited by one or more of the multiple collaborating devices, wherein at least a first node of the plurality of nodes represents a textual content object and at least a second node of the plurality of nodes represents a sketch content object, and wherein each node representing a corresponding sketch content object includes a respective command sequence used to create content of the corresponding sketch content object;

during a respective synchronization period, receive one or more editing inputs from one or more devices of the multiple collaborating devices;

modify the directed acyclic graph based on relationships between the editing inputs and existing content objects embodied in the directed acyclic graph;

determine whether the one or more editing inputs modifies an existing sketch content object represented in the directed acyclic graph; and

in accordance with a determination that a first editing input of the one or more editing inputs modifies a first existing sketch content object represented by a first command sequence in a first respective node in the directed acyclic graph, update the first command sequence in the first respective node by merging each individual drawing command included in the first editing input with the first command sequence to produce, in the first respective node, an updated first command sequence of two or more commands that represents the first existing sketch content object as modified by the first editing input.

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

render the first existing sketch content object represented in the modified directed acyclic graph, the rendering comprising;

determining a global position or state of the first existing sketch content object in the content in accordance with a topological traversal of the directed acyclic graph;

determining an internal appearance of the first existing sketch content object in accordance with the updated first command sequence in the first respective node; and

rendering the first existing sketch content in accordance with the determined global position or state of the first existing sketch content object and in accordance with the determined internal appearance of the first existing sketch content object.

24. The non-transitory computer readable storage medium of claim 22, wherein the directed acyclic graph includes multiple parallel paths each including at least one node that represents a respective one of multiple concurrent editing inputs received from distinct devices of the multiple collaborating devices.

25. The non-transitory computer readable storage medium of claim 22, wherein each node in the directed acyclic graph includes a unique object sequence number for the respective content object associated with the node, and wherein the unique object sequence number includes (1) a unique device identifier for a respective device at which the respective content object was first created, and (2) a local sequence number assigned to the respective content object in accordance with a local order by which the respective content object was first created at said respective device.

26. The non-transitory computer readable storage medium of claim 22, wherein the one or more programs include instructions for traversing the directed acyclic graph in accordance with a predetermined ordering rule to obtain an object sequence, said traversing including:

sorting nodes between a starting node to an end node of a set of multiple parallel paths in the directed acyclic graph by traversing the set of multiple parallel paths in an order based on a comparison between respective lowest object sequence numbers present in each of the set of multiple parallel paths.

27. The non-transitory computer readable storage medium of claim 22, wherein, for each node representing a sketch content object, the node includes a sequence of one or more drawing commands directed to the sketch content object, each of the one or more drawing commands has a respective command sequence number, and the respective command sequence number includes (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.

28. The non-transitory computer readable storage medium of claim 27, wherein updating the first command sequence in the first respective node comprises:

merging and sorting each individual drawing command and one or more past drawing commands in the first command sequence in accordance with an ordering rule based on respective command sequence numbers of the one or more past drawing commands and said each individual drawing command, 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 command sequence numbers.