crindex-ts

Maintain sorted and hashed sets of in-memory JS and TS objects

crindex-ts provides three classes for organizing a set of objects:

• SortIndex: maintains objects in sorted order by a simple or compound key. The key must be sufficient to define a consistent order for the objects, so an id is often used as the final property in the compound key.
• HashIndex: maintains objects in a lookup table, mapping each key to one or many objets. Optionally manages its keys in a separate SortIndex. A HashIndex has two flavors:
  • UniqueHashIndex: each key is mapped to a single object, throwing an error if two objects have the same key.
  • ManyHashIndex: each key is mapped to multiple objects, which are themselves organized by a nested index (Sort, UniqueHash, ManyHash). This can continue recursively.

For example, consider a set of Books, and a set of indexes for organizing those books:

• sorted: a SortIndex using sort key [author, title, ISBN]
• byISBN: a UniqueHashIndex using ISBN as key. An application might call byISBN.get("9780061964367") to retrieve a single Book.
• byGenre: a ManyHashIndex using genre as key. Each genre organizes its books with a ManyHashIndex using publisher as key. And each publisher organizes its books with a SortIndex using sort key [author, title, ISBN]. An application might call byGenre.get("Romance").get("Carina Press") to get to the appropriate SortIndex.

The application is responsible for creating the indexes, populating them with objects, and notifying them when keys change their values. Because of this burden, applications rarely maintain these indexes. Instead, these classes are more often incorporated as building blocks of other application-support systems, such as in-memory databases.

Alternatively, a simplified API, described later, allows applications to minimize the implementation burden, at the expense of some performance and flexibility.

Usage API

The indexes are managed through two API's - one for reading and one for writing.

Reading

Index

Implemented by all index types

• count - the total number of objects in the index
• empty - true if there are no objects in the index

SortIndex extends Index

• all - returns an IterableIterator of the index's objects in sorted order
• first - returns the first object in the sorted index, null if the index is empty
• last - returns the last object in the sorted index, null if the index is empty
• toArray() - returns an array of the index's objects in sorted order. The array is a copied "snapshot" of the index, so if the object order changes, the array will not be affected
• range(searchRange: SearchRange) - returns an IterableIterator of objects matching the SearchRange, in sorted order

SearchRange

Used by SortIndex.range(). Has the following properties, all of which are optional:

• reverse - boolean indicating if the values should be returned in reverse order (default is false)
• gt - value of a key. Objects with keys greater than this value will be returned
• ge - value of a key. Objects with keys greater or equal to this value will be returned
• lt - value of a key. Objects with keys less than than this value will be returned
• le - value of a key. Objects with keys less than or equal to this value will be returned

If neither "gt" or "ge" is specified, then the returned objects will start from the beginning of the sorted list. Similarly if neither "lt" or "le" is specified, then the objects will run to the end of the sorted list. It is an error to specify both "gt" and "ge", or to specify both "lt" and "le".

HashIndex extends Index

Implemented by both UniqueHashIndex and ManyHashIndex

• has(key) - returns a boolean indicating if the index contains the given key
• get(key) - returns the value at the given key. The value depends on the index type:
  • UniqueHashIndex - the value is an object. Using the book example above, byISBN.get("9780061964367") would return a Book. Throws an error if the key has no associated value.
  • ManyHashIndex - the value is the index the next "level" down. Again using the book example, byGenre.get("Romance") would return a ManyHashIndex, and byGenre.get("Romance").get("Carina Press") would return a SortIndex. If the key has no associated values, then its behavior depends on the value of suppressDefaultValue supplied to the ManyHashIndexConfig:
    • false (the default): returns an empty index at the next "level" down.
    • true: throws an error
• tryGet(key) - same as get, except that it returns null in those cases where get would have thrown an error
• keys - returns an IterableIterator of the index's keys in no defined order. The iterator's behavior is undefined if the index is modified while the iterator is in use.
• values - returns an IterableIterator of the index's values in no defined order. The iterator's behavior is undefined if the index is modified while the iterator is in use.
• entries - returns an IterableIterator of HashIndexEntry objects containing the index's key/value pairs, in no defined order. The iterator's behavior is undefined if the index is modified while the iterator is in use. The pairs are expressed as

HashIndexEntry

Returned by HashIndex.entries

• key - the entry's key
• value - the entry's value

HashIndexWithSortedKeys extends HashIndex

Both UniqueHashIndex and ManyHashIndex can be configured to maintain their keys in sorted order. This removes the need to sort the keys each time such a sorted list is needed, at some performance cost when adding and removing entries. See createUniqueHashIndexWithSortedKeys and createManyHashIndexWithSortedKeys.

• sortedKeys - returns a SortIndex of the index's keys in sorted order.

Writing

IndexMutations

Implemented by all three index types. Applications must call these methods to inform indexes of object changes.

• add(obj, key) - adds an object to the index with the given key
• remove(obj, key) - removes an object with the given key from the index
• keyChanged(obj, oldKey, newKey) - notifies the index that the object's key has changed

Creating Indexes

Indexes are created using these methods:

• createSortIndex(config: SortIndexConfig) - creates a new SortIndex
• createUniqueHashIndex(config: UniqueHashIndexConfig) - creates a new UniqueHashIndex
• createManyHashIndex(config: ManyHashIndexConfig) - creates a new ManyHashIndex
• createUniqueHashIndexWithSortedKeys(config: UniqueHashIndexWithSortedKeysConfig) - creates a new UniqueHashIndex configured to keep its keys in sorted order (see HashIndexWithSortedKeys)
• createManyHashIndexWithSortedKeys(config: ManyHashIndexWithSortedKeysConfig) - creates a new ManyHashIndex configured to keep its keys in sorted order (see HashIndexWithSortedKeys)

A few notes before describing the config objects:

• SortIndexes make no assumptions about the form of the key. The key is supplied by the application, and methods for testing key equality or comparing keys are also passed in by the application as part of the config. So a SortIndex doesn't need to interpret a key - it just stores it and passes it to the methods that the application supplied to the config as needed.
• HashIndexes treat keys similarly. The only difference is that HashIndexes assume the keys can behave properly as the keys in a Map.
• Indexes have a notion of an "indexable key", which is potentially different from the original key supplied by the application. The "indexable key" is the value actually used by the index to sort or hash. The original key supplied by the application, on the other hand, is typically extracted directly from the properties of the object being indexed. In the TypeScript API, the type of the original key is denoted as K, while the type of the "indexable key" is denoted as IK. There are a couple instances where the distinction between the key and indexable key becomes important.
  • When the application only wants non-null keys in the index, but the key is from a property whose value can be null. In this case the type of K might be something like string|null, while the type of IK would just be string. The config passed to the index has a method isIndexable, which in this case would return true if the key is non-null. The config also has a method toIndexableKey which takes a K and returns an IK - in this case, it would just return the same value, throwing an exception if it encounters a null value. The index automatically calls these methods when determining if objects should be added or removed, and when it needs to use "indexable keys" for sorting and hashing.
  • When the index is a ManyHashIndex. In this case, the key must include all of the information needed for the whole set of nested indexes, but the "indexable key" at each level must only be the key needed for that specific level of the index. Using the byGenre index above as an example, the full key to that index might be something like [genre, publisher, author, title, ISBN], but at the first level, the "indexable key" is only genre, at the next level it's publisher, and at the final level it's [author, title, ISBN]. The toIndexableKey method in this case would extract the required values from the full key for use at each "level" of the index. The isIndexable method is also consulted at each level to determine if the object should be included at each level of the index.
• Indexes can participate in a dependency tracking system, modeled as a DependencyTracker, described later.

IndexConfig

This is the base configuration structure inherited by the other configuration structures.

• isIndexable: (k: K) => boolean - a function that returns true if an object with the given key should be included in the index
• toIndexableKey: (k: K) => IK - a function that converts a key to an indexable key
• keysEqual: (k1: IK, k2: IK) => boolean - a function that returns true if two indexable keys are equal
• dependencyTracker?: DependencyTracker - an optional DependencyTracker that will allow the index to participate in a dependency tracking system
• name: string - an optional name for the index. The name is passed to the DependencyTracker, if one is in place, to assist with debugging.

SortIndexConfig extends IndexConfig

Additional configuration needed for a SortIndex

• compare: (key1: IK, key2: IK) => SortKeyOrdering - a function that compares two indexable keys and returns one of the SortKeyOrdering enumeration values:
  • SortKeyOrdering.KEY1_BEFORE_KEY2
  • SortKeyOrdering.KEY1_AFTER_KEY2
  • SortKeyOrdering.KEY1_EQUALS_KEY2

There are several convenience methods that can be supplied as the compare function:

• compareNumbers - compares two non-null numbers
• compareNumbersNullFirst - compares two possibly-null numbers, treating null values as coming before non-null values
• compareNumbersNullLast - compares two possibly-null numbers, treating null values as coming after non-null values
• compareStrings - compares two non-null strings
• compareStringsNullFirst - compares two possibly-null strings, treating null values as coming before non-null values
• compareStringsNullLast - compares two possibly-null strings, treating null values as coming after non-null values
• compareBooleans - compares two non-null booleans, where false comes before true
• compareBooleansNullFirst - compares two possibly-null booleans, treating null values as coming before non-null values
• compareBooleansNullLast - compares two possibly-null booleans, treating null values as coming after non-null values
• compareValues - general comparison that handles arrays, booleans, numbers, and strings, sorting values of different types in that order. Null and undefined values are considered equivalent, and are sorted last.

HashIndexConfig extends IndexConfig

Base configuration shared by UniqueHashIndex and ManyHashIndex

• compare?: (key1: IK, key2: IK) => SortKeyOrdering - an optional function that compares two indexable keys and returns one of the SortKeyOrdering enumeration values (see SortIndexConfig.compare). If this is supplied, then the index will maintain a SortIndex of its keys and will return it with the keys getter. Otherwise, the keys getter will throw an exception.

UniqueHashIndexConfig extends IndexConfig

Configuration needed for a UniqueHashIndex. Currently a UniqueHashIndex requires no more configuration than the base IndexConfig.

ManyHashIndexConfig extends IndexConfig

Configuration needed for a ManyHashIndex.

• createSecondaryIndex: (key: IK) => I2 - creates a new nested index to hold the multiple values for a given key in the index
• getNextKey: (key: K) => K2 - an index may choose to pass a different key to the nested index, generated from the key passed to the index. This function generates that nested key.
• suppressDefaultValue?: boolean - optional flag that governs what happens if get or tryGet is called for a key that has no values. If not specified or false (the default), then an empty value is returned. If true, an error is thrown (get) or null is returned (tryGet).

UniqueHashIndexWithSortedKeysConfig extends UniqueHashIndexConfig

Used to configure a UniqueHashIndex that keeps its keys in sorted order (see createUniqueHashIndexWithSortedKeys and HashIndexWithSortedKeys)

• compare: (key1: IK, key2: IK) => SortKeyOrdering - compares two indexable keys and returns one of the SortKeyOrdering enumeration values (see SortIndexConfig.compare). Used to maintain the keys in sorted order.

ManyHashIndexWithSortedKeysConfig extends ManyHashIndexConfig

Used to configure a ManyHashIndex that keeps its keys in sorted order (see createManyHashIndexWithSortedKeys and HashIndexWithSortedKeys)

• compare: (key1: IK, key2: IK) => SortKeyOrdering - compares two indexable keys and returns one of the SortKeyOrdering enumeration values (see SortIndexConfig.compare). Used to maintain the keys in sorted order.

Dependency Tracking

Some systems perform dependency tracking, in which an expression is evaluated while tracking the values accessed by that expression. If one of those values later changes, then some action can be taken, such as invalidating that expression's cached value.

The indexes do not explicitly use such a system, but they provide the hooks that allow integration with such a system. With such an integration in place, the system can track an expression's use of the indexes, and be notified when those indexes change.

The DependencyTracker represents the model of tracker compatible with the indexes.

Simplified API

A simplified API is available that allows applications to quickly incorporate indexes at the expense of some performance and flexibility:

• sortIndex(keyFunc: obj=>key) - creates a SortIndex that uses the given function to extract the sort key from each element. The keys are sorted using the compareValues function described above. For example:

const byAge = sortIndex(u=>u.age)

• uniqueHashIndex(keyFunc: obj=>key) - creates a UniqueHashIndex that uses the given function to extract the hash key from each element. For example:

const byName = uniqueHashIndex(u=>u.name)

• manyHashIndex(keyFunc: obj=>key, nextIndex: ()=>SimpleIndex) - creates a ManyHashIndex that uses the given function to extract the hash key from each element, and uses the second function to create the "next" index that indexes objects with the same key. For example, this will index objects by "occupation", and objects with the same "occupation" will be sorted by "age":

const byOccupationAndAge = manyHashIndex(u=>u.occupation, ()=>sortIndex(u=>u.age))

Each of the simplified indexes has the full API of SortIndex, UniqueHashIndexWithSortedKeys, or ManyHashIndexWithSortedIndex, and also adds these simplified API calls:

• addObject(obj) - add an object to the index
• removeObject(obj) - remove an object from the index
• updateObject(obj, f:()=>R):R - update an object in the index. The actual updating should happen in the supplifed function. updateObject will take care of remembering the old key before the change and computing the new key after the change, which are both needed when updating an item in the index.

Because a given object is often managed by multiple indexes, the simplified API provides a way to manage all of those indexes at once:

• indexes(indexes: SimpleIndex[]) - returns a SimpleIndexes that will manage all of the indexes passed to it. Those indexes must have been created by sortIndex, uniqueHashIndex, or manyHashIndex.

The SimpleIndexes object offers these methods:

• add(obj) - add a single object to all of the indexes
• addAll(obj[]) - add all of the objects to all of the indexes
• remove(obj) - remove a single object from all of the indexes
• removeAll(obj[]) - remove all of the objects from all of the indexes
• update(obj, f:()=>R):R - updates an object in all of the indexes. Takes care of remembering the old and new keys for each index.
• updateAll(objs:obj[], f:()=>R):R - updates all of the objects in all of the indexes. Takes care of remembering the old and new keys for each index and object.

This example shows how the indexes can be used to manage instances of a User class, indexing them by name, age, and occupation (then sorted by age). The setter methods simply notify all the indexes of every update. More sophisticated versions might have each setter only update those indexes that might be affected by a change, but for applications that are less concerned with performance, an approach like this might suffice.

export class User {
  _name: string | null = null
  _age: number | null = null
  _occupation: string | null = null

  constructor() {
    allIndexes.add(this)
  }

  destroy() {
    allIndexes.remove(this)
  }

  get name() {
    return this._name
  }

  set name(val: string | null) {
    allIndexes.update(this, () => (this._name = val))
  }

  get age() {
    return this._age
  }

  set age(val: number | null) {
    allIndexes.update(this, () => (this._age = val))
  }

  get occupation() {
    return this._occupation
  }

  set occupation(val: string | null) {
    allIndexes.update(this, () => (this._occupation = val))
  }
}

const byName = uniqueHashIndex((u: User) => u.name)
const byAge = sortIndex((u: User) => u.age)
const byOccupationAndAge = manyHashIndex(
  (u: User) => u.occupation,
  () => sortIndex((u: User) => u.age)
)

const allIndexes = indexes([byName, byAge, byOccupationAndAge])