message-cache

Maintenance status: Beta. This project is AI-free and bans all AI contributions.

A performant data structure for representing potentially gappy sequences of items. The data is internally represented as one or more disjoint subsequences, which may be accessed by reference to an item contained within. You can incrementally add new partial sequences to the data structure, and if this creates a 'link' between two or more previously disjoint subsequences, they will be merge into a single contiguous subsequence automatically. The result is a sequence that gradually improves its total ordering as more data becomes available.

A typical usecase for this type of data structure would be a remote history of (chat) messages; you might only have certain segments of the full chat history available locally at any given time, eg. because you are jumping through search results and only a limited number of surrounding messages are loaded for each result.

This data structure is tolerant to undeclared gaps in arbitrary positions; if a previously-appended subsequence turns out to have been incomplete, and new items appear that would sort somewhere in the middle of that subsequence, the new items will be inserted in the correct positions. The only requirement is that the underlying full sequence (the one that you do not have available locally) has a single canonical order; if two appended subsequences disagree about the order of any two items relative to each other, this may result in unexpected orderings.

The terminology in this documentation and the API revolves around 'messages', as this library was originally designed for use in a chat client. However, this library can be used for any gappy sequence of items with similar properties, and is not actually specific to chat messages.

Usage

/* The callback specifies how to extract the item ID from each value. In this example, the value *is* the
   item ID, but in real-world applications you would probably access a property instead. */
let cache = messageCache((message) => message);

let testSequences = [
	[ 3 ],
	[ 1, 8 ],
	[ 5, 9 ],
	[ 3, 4, 5 ],
	[ 6, 7, 8, 9 ],
	[ 1, 2, 3, 5, 6, 7, 8 ],
	[ 2, 3, 4, 5, 6, 7 ],
	[ 1, 2, 8 ],
	[ 2 ],
	[ 3, 5, 6, 9 ]
];

for (let sequence of testSequences) {
	cache.addMessages(sequence);
}

let sequence = cache.getSequenceForMessage(1);
console.log(sequence); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

API

This section will be improved in the future.

There are a few different ways to add new subsequences:

• addMessages(messages): adds the specified subsequence of messages. If it overlaps with existing subsequence(s), it will be merged in accordingly; if not, it will be added as a new disjoint subsequence. This method will return the ID of the affected (and potentially new) subsequence.
• prependMessages(sequenceID, messages): adds the new subsequence before the specified existing subsequence. No item overlap is required; using this method asserts that it directly precedes it in the ordering. In a chat client, this would typically be used when a new chunk of history has loaded.
• appendMessages(sequenceID, messages): adds the new subsequence after the specified existing subsequence. No item overlap is required; using this method asserts that it directly succeeds it in the ordering. In a chat client, this would typically be used when new messages come in.
• getSequenceForMessage(messageID): returns the subsequence that currently contains the item with the specified ID. Note that this expects the ID of the item, not the item itself.
• getSequenceByID(sequenceID): returns the subsequence with the specified ID. If you are eg. tracking sequenceIDs in a chat application, you would use this to retrieve a particular chunk of the chat history. However, see the warning below.

Warning: Note that sequenceIDs may become invalid as automatic merges take place; it is strongly recommended that you re-obtain the relevant sequenceID before every sequence operation, using a reference to one of the items contained within.