Concurrent editing of a document by multiple clients

A computing device comprising:

• a processing unit;
• and
• a computer-readable data storage medium that stores computer-executable instructions that, when executed by the processing unit, cause the computing device to:
• open a local copy of a document on the computing device, the local copy of the document comprising underlying data that represent virtual element arrays of real element arrays in the document, the underlying data comprising an index tree and a piece descriptor table, the piece descriptor table comprising piece descriptors that each identify a different element in the real element array, the index tree comprising a hierarchy of index nodes, each of the index nodes corresponding to a different piece descriptor in the piece descriptor table and indicating where each element in the real element array belong in the virtual element array, for each index node in the index tree, elements associated with index nodes in a left subtree of the index node are to the left in a given virtual element array of the elements associated with the index node, and for each index node in the index tree, elements associated with index nodes in a right subtree of the index node are to the right in the given virtual element array of the elements associated with the index node;
• and
• perform the following actions concurrently on the computing device while the local copy of the document is open on the computing device and a remote copy of the document is open on a remote client:
• update the local copy of the document to reflect a local change, the local change being a change made to the local copy of the document by a first user, the first user using the computing device;
• and
• update the local copy of the document to reflect a remote change, the remote change being a change made to the remote copy of the document by a second user, the second user using the remote client.

A computer-readable data storage medium that stores computer-executable instructions that, when executed by a processing unit of a computing device, cause the computing device to:

• retrieve a local copy of a document from a server, the local copy of the document comprising underlying data that represents a virtual element array, the virtual element array comprising elements that represent a document tree that contains document elements,
• wherein the underlying data comprises a real element array, the real element array comprising each of the elements in the virtual element array,
• wherein the underlying data comprises a piece descriptor table, the piece descriptor table comprising piece descriptors, each of the piece descriptors identifying a different piece of the real element array,
• wherein the underlying data comprises an index tree, the index tree comprising a hierarchy of index nodes, each of the index nodes indicating one of the piece descriptors,
• wherein for each index node in the index tree, elements associated with index nodes in a left subtree of the index node are to the left in the virtual element array of the elements associated with the index node, and
• wherein for each index node in the index tree, elements associated with index nodes in a right subtree of the index node are to the right in the virtual element array of the elements associated with the index node;
• in response to receiving the local copy, setting a local reference version (LRV) pointer to indicate a root index node in the index tree and a current local version (CLV) pointer to indicate the root index node, a LRV being a version of the local copy associated with the root index node indicated by the LRV pointer, a CLV being a version of the local copy associated with the root index node indicated by the CLV pointer;
• receive input to make an edit to the local copy, the input received from a first user, the first user using the computing device;
• apply the edit to the CLV, wherein when the edit is applied to the CLV, a new root index node is added to the index tree;
• set the CLV pointer to indicate the new root index node;
• generate a local difference list, the local difference list describing differences between virtual element arrays of the CLV and the LRV;
• send the local difference list to the server;
• receive a remote difference list from the server, the remote difference list describing differences between the LRV and a CSV, the CSV being a version of the document at the server that reflects remote edits to the document, the remote edits being made by a remote client;
• recreate the CSV by applying the remote difference list to the LRV;
• identify differences between the CSV and the CLV;
• apply the identified differences to the CLV;
• set the CLV pointer to indicate a second root index node that results from applying the identified differences to the CLV;
• and
• run a reader thread that draws the local copy to a display screen using the virtual element array of the CLV.