Struct Eips

pub struct Eips<Id, Opt = Options>
where
    Opt: EipsOptions,
{ /* private fields */ }

An intention-preserving sequence CRDT.

Id is the ID data type. Each item in an Eips sequence has a unique ID. Id must implement Clone and Ord and should be small and cheap to clone (Copy is ideal).

Mathematical variables

The following variables may be used to specify the time and space complexity of various operations and types:

• h, the total number of items ever inserted in the sequence.
• n, the number of visible (non-deleted) items in the sequence.

Note that moving an element increases h by 1, but does not affect n.

Space complexity

Θ(h). Note that some of the options in Opt can scale memory usage by a small constant amount by affecting the amount of auxiliary memory used; see EipsOptions for details.

Implementations

impl<Id, Opt> Eips<Id, Opt>

where Id: Id, Opt: EipsOptions,

pub fn new() -> Self

Creates a new Eips.

pub fn len(&self) -> usize

Gets the number of (non-deleted) items in the sequence.

Time complexity

Constant.

pub fn is_empty(&self) -> bool

Checks if there are no (non-deleted) items in the sequence.

Time complexity

Constant.

pub fn get(&self, index: usize) -> Result<Id, IndexError>

Gets the ID of the item at index.

The ID can be turned back into a local index with Self::remote_get.

Errors

Returns an error if index is out of bounds.

Time complexity

Θ(log h).

pub fn remote_get<'a>( &self, id: &'a Id, ) -> Result<Option<usize>, IdError<&'a Id>>

Gets the index of the item with ID id.

Returns None if the item has been deleted.

Errors

Returns an error if there is no item with the given ID.

Time complexity

Θ(log h).

pub fn insert( &self, index: usize, id: Id, ) -> Result<RemoteChange<Id>, IndexError>

Inserts an item at a particular index.

The item’s index will be index once the resulting RemoteChange is applied.

id must be a new, unique ID.

Errors

Returns an error if index is out of bounds.

Time complexity

Θ(log h).

pub fn remove(&self, index: usize) -> Result<RemoteChange<Id>, IndexError>

Removes the item at a particular index.

No actual modification takes place until the resulting RemoteChange is applied.

Errors

Returns an error if index is out of bounds.

Time complexity

Θ(log h).

pub fn mv( &self, old: usize, new: usize, id: Id, ) -> Result<RemoteChange<Id>, IndexError>

where Opt: EipsOptions<SupportsMove = Bool<true>>,

Moves an item to a new index.

The item currently at index old will reside at index new once the resulting RemoteChange is applied.

id must be a new, unique ID.

Errors

Returns an error if old or new are out of bounds.

Time complexity

Θ(log h).

pub fn apply_change( &mut self, change: RemoteChange<Id>, ) -> Result<LocalChange, ChangeError<Id>>

Applies a remote change generated by methods like Self::insert and Self::remove.

Returns the change that should be made to the corresponding local sequence of items.

Time complexity

Θ(log h).

pub fn changes(&self) -> Changes<'_, Id, Opt>

Returns all items in the sequence as RemoteChanges.

This method returns an iterator that yields (change, index) tuples, where change is the RemoteChange and index is the local index corresponding to the change (or None if the change represents a deleted or moved item).

Time complexity

Iteration over the entire sequence is Θ(h + n log h).

If you want to send the entire sequence to another client that does not yet have their own copy, or save the contents to disk, it is faster to serialize this Eips structure and the local list of values and send or save them together. (This cannot be used to merge changes from multiple sources; it can only be used to create the initial Eips object on a client that has not yet made or received any other changes.)

pub fn get_change<'a>( &self, id: &'a Id, ) -> Result<(RemoteChange<Id>, Option<usize>), IdError<&'a Id>>

Gets the item with ID id as a RemoteChange.

Returns a (change, index) tuple, where change is the RemoteChange. For changes that represent the insertion of a non-deleted item, index the local index of the item. Otherwise, for deleted items and changes corresponding to move operations, it is None.

Errors

Returns an error if there is no item with the given ID.

Time complexity

Θ(log h).

Trait Implementations

impl<Id, Opt> Clone for Eips<Id, Opt>

where Id: Id, Opt: EipsOptions,

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<Id, Opt> Default for Eips<Id, Opt>

where Id: Id, Opt: EipsOptions,

fn default() -> Self

Returns the “default value” for a type.

impl<'a, Id, Opt> Deserialize<'a> for Eips<Id, Opt>

where Id: Id + Deserialize<'a>, Opt: EipsOptions,

Available on crate feature serde only.

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'a>,

Deserializes an instance of Eips.

Time complexity

Θ(h log h), assuming the time complexity of individual calls to the deserializer does not depend on the amount of data that has been will be deserialized in other calls.

impl<Id, Opt> Drop for Eips<Id, Opt>

where Opt: EipsOptions,

fn drop(&mut self)

Executes the destructor for this type.

impl<Id, Opt> Serialize for Eips<Id, Opt>

where Id: Id + Serialize, Opt: EipsOptions,

Available on crate feature serde only.

fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>

where S: Serializer,

Serializes this instance of Eips.

The local list of values should usually be serialized at the same time, as the serialized Eips structure will produce incorrect results unless it is used with the particular local list of values that existed at the time of serialization.

Time complexity

Θ(h), assuming the time complexity of individual calls to the serializer does not depend on the amount of data that has been serialized so far.

impl<Id, Opt> Send for Eips<Id, Opt>

where Id: Send, Opt: EipsOptions,

impl<Id, Opt> Sync for Eips<Id, Opt>

where Id: Sync, Opt: EipsOptions,

impl<Id, Opt: EipsOptions> Unpin for Eips<Id, Opt>