Skip to main content

Immutable Balanced OrderedSet in TypeScript

class OrderedSet<T extends OrderedMapKey>

Immutable Ordered Set

The OrderedSet<T> class stores numbers, strings, booleans, dates, or custom objects which implement the ComparableObj interface. OrderedSet implements the typescript-builtin ReadonlySet interface (which consists of the read-only methods of the JS builtin Set).

The OrderedSet is immutable, which means that no changes or mutations are allowed directly to the OrderedSet. Instead, modification operations such as OrderedSet.add return a new OrderedSet which contains the result of the modification. The original OrderedSet is unchanged and can continue to be accessed and used. The OrderedSet implements this efficiently using structural sharing and does not require a full copy; indeed, the OrderedSet.delete method will copy at most O(log n) entries.

Creating Ordered Sets​

static empty<T extends OrderedMapKey>(): OrderedSet<T>
#Source

Static method to create a new empty OrderedSet

The key type must extend OrderedMapKey, which consists of strings, numbers, dates, booleans, or a custom user-defined object which implements the ComparableObj interface.

While you can start with an empty OrderedSet and then use OrderedSet.add to add entries, it is more efficient to create the OrderedSet in bulk using either the static OrderedSet.from or OrderedSet.build or using various methods on LazySeq to convert a LazySeq to an OrderedSet.

static ofKeys<K extends OrderedMapKey, V>(map: OrderedMap<K, V>): OrderedSet<K>
#Source

Static method to produce an OrderedSet of the keys in an OrderedMap

Creates an OrderedSet consisting of all the keys in the given OrderedMap. This function is O(1) and very fast because the backing data structure is reused.

static from<T extends OrderedMapKey>(items: Iterable<T>): OrderedSet<T>
#Source

Efficiently create a new OrderedSet from a collection of items

Runs in time O(n log n)

static build<T extends OrderedMapKey, R>(
    things: Iterable<R>,
    item: (v: R) => T
): OrderedSet<T>
#Source

Efficiently create a new set from a collection of values and an item extraction function

build efficiently creates a new OrderedSet by applying the given function to each thing in the things collection.

Runs in time O(n log n)

IReadOnlySet interface​

𝑜𝑏𝑗.size(): number
#Source

size is a readonly property containing the number of items in the set.

𝑜𝑏𝑗.has(t: T): boolean
#Source

Returns true if the item is in the set

Runs in time O(log n)

𝑜𝑏𝑗.[Symbol.iterator](): IterableIterator<T>
#Source

Iterates the items in the set

This is the default iteration when using for .. of directly on the OrderedSet. It iterates all the items in ascending order.

𝑜𝑏𝑗.entries(): IterableIterator<[T, T]>
#Source

Iterates the items in the OrderedSet

This provides an iterator to iterate all the items in the OrderedSet. Each item is iterated as a length-2 array with the item appearing twice. (This matches the builtin Set.entries method.) The items are iterated in ascending order.

𝑜𝑏𝑗.keys(): IterableIterator<T>
#Source

Iterates the items in the set

This provides an iterator to iterate all the items in the OrderedSet. Items are iterated in ascending order. Both keys and values are equivalent for an OrderedSet.

𝑜𝑏𝑗.values(): IterableIterator<T>
#Source

Iterates the items in the set

This provides an iterator to iterate all the items in the OrderedSet. Items are iterated in ascending order. Both keys and values are equivalent for an OrderedSet.

𝑜𝑏𝑗.forEach(f: (val: T, val2: T, set: OrderedSet<T>) => void): void
#Source

Applys a function to each item in the OrderedSet

This applies the function f to each item in the set. The item is provided twice (so as to match the builtin Set.forEach method). The items are iterated in ascending order.

Iteration​

𝑜𝑏𝑗.foldl<R>(f: (acc: R, t: T) => R, zero: R): R
#Source

Reduce all the entries in the OrderedSet to a single value

The letter-l in foldl stands for left. Thinking of all the items as an ascending list, foldl starts combining items from the left side. Thus, the smallest item is combined with the zero value, which is then combined with the next smallest item, and so on.

𝑜𝑏𝑗.foldr<R>(f: (t: T, acc: R) => R, zero: R): R
#Source

Reduce all the entries in the OrderedSet to a single value

The letter-r in foldr stands for right. Thinking of all the items as an ascending list, foldr starts combining items from the right side. Thus, the largest item is combined with the zero value, which is then combined with the second-to-largest item, and so on.

𝑜𝑏𝑗.toAscLazySeq(): LazySeq<T>
#Source

Creates a LazySeq which iterates all the items in the OrderedSet in ascending order

𝑜𝑏𝑗.toDescLazySeq(): LazySeq<T>
#Source

Creates a LazySeq which iterates all the items in the OrderedSet in descending order

Add and Delete​

𝑜𝑏𝑗.add(t: T): OrderedSet<T>
#Source

Return a new OrderedSet with the given item added

If the item already exists, then the OrderedSet object instance is returned unchanged. Runs in time O(log n)

𝑜𝑏𝑗.delete(t: T): OrderedSet<T>
#Source

Return a new OrderedSet with the given item removed

If the item does not exist, then the OrderedSet object instance is returned unchanged. Runs in time O(log n)

Transformation​

𝑜𝑏𝑗.partition(f: (t: T) => boolean): [OrderedSet<T>, OrderedSet<T>]
#Source

Split an OrderedSet into two OrderedSets based on a function

The function f is applied to each item. The entries for which f returns true are placed in one OrderedSet and entries for which f returns false are placed in the other. The two sets are returned as a tuple, with the true set returned as the first element of the tuple.

If the function f returns true for all entries, then the first OrderedSet object instance is guaranteed to be === to the this object instance. Similar for if f returns false for all entries.

This runs in O(n) time.

𝑜𝑏𝑗.filter(f: (t: T) => boolean): OrderedSet<T>
#Source

Remove entries from the set that return false from a predicate

filter applies the function f to each value and key in the OrderedSet. If f returns false, the key is removed. filter guarantees that if no values are removed, then the OrderedSet object instance is returned unchanged.

This runs in O(n) time.

𝑜𝑏𝑗.split(t: T): {
    readonly below: OrderedSet<T>;
    readonly present: boolean;
    readonly above: OrderedSet<T>;
  }
#Source

Split an OrderedSet into the items below and above a given item

split returns an object with three properties. below is an OrderedSet with all the items which are less than the provided item t. present is a boolean which specifies if the item t exists in the set or not. Finally, the above property consists of all the items in the OrderedSet which are greater than t.

This runs in time O(log n)

𝑜𝑏𝑗.transform<U>(f: (s: OrderedSet<T>) => U): U
#Source

Apply a function to the OrderedSet

Applies the provided function f to this and returns the result. This is a convenience function which allows you to continue to chain operations without having to create a new temporary variable.

Min/Max Items​

𝑜𝑏𝑗.lookupMin(): T | undefined
#Source

Find the minimum item in the set

In O(log n) time, find the minimum item. Returns undefined if the OrderedSet is empty.

𝑜𝑏𝑗.lookupMax(): T | undefined
#Source

Find the maximum item in the set

In O(log n) time, find the maximum item. Returns undefined if the OrderedSet is empty.

𝑜𝑏𝑗.deleteMin(): OrderedSet<T>
#Source

Removes the minimum item in the set

In O(log n) time, return a new OrderedSet with the the minimum item removed.

𝑜𝑏𝑗.deleteMax(): OrderedSet<T>
#Source

Removes the maximum item in the set

In O(log n) time, return a new OrderedSet with the the maximum item removed.

𝑜𝑏𝑗.minView(): { readonly min: T; readonly rest: OrderedSet<T> } | undefined
#Source

Lookup and remove the minimum item

In O(log n) time, find and remove the minimum item. The minimum item and the result of removing the minimum item are returned. If the original OrderedSet is empty, undefined is returned.

𝑜𝑏𝑗.maxView(): { readonly max: T; readonly rest: OrderedSet<T> } | undefined
#Source

Lookup and remove the maximum item

In O(log n) time, find and remove the maximum item. The maximum item and the result of removing the maximum item are returned. If the original OrderedSet is empty, undefined is returned.

Set Operations​

𝑜𝑏𝑗.union(other: OrderedSet<T>): OrderedSet<T>
#Source

Returns a new set which combines all entries in two sets

union produces a new OrderedSet which contains all the items in both OrderedSets. union guarantees that if the resulting OrderedSet is equal to this, then the OrderedSet object instance is returned unchanged.

Runs in time O(m log(n/m)) where m is the size of the smaller set and n is the size of the larger set.

static union<T extends OrderedMapKey>(
    ...sets: readonly OrderedSet<T>[]
): OrderedSet<T>
#Source

Create a new OrderedSet which combines all entries in a sequence of OrderedSets

OrderedSet.union is the static version of OrderedSet.union and allows unioning more than two sets at once. It produces a new OrderedSet which contains all the entries in all the OrderedSets.

union guarantees that if the resulting OrderedSet is equal to the first non-empty OrderedSet in the sequence, then the OrderedSet object instance is returned unchanged.

𝑜𝑏𝑗.intersection(other: OrderedSet<T>): OrderedSet<T>
#Source

Returns a new set which contains only items which appear in both sets

intersection produces a new OrderedSet which contains all the items which appear in both OrderedSets. intersection guarantees that if the resulting OrderedSet is equal to this, then the OrderedSet object instance is returned unchanged.

Runs in time O(m log(n/m)) where m is the size of the smaller set and n is the size of the larger set.

static intersection<T extends OrderedMapKey>(
    ...sets: readonly OrderedSet<T>[]
): OrderedSet<T>
#Source

Returns a new set which contains only items who appear in all sets

OrderedSet.intersection is a static version of OrderedSet.intersection, and produces a new OrderedSet which contains the items which appear in all specified OrderedSet.

intersection guarantees that if the resulting OrderedSet is equal to the first OrderedSet, then the OrderedSet object instance is returned unchanged.

𝑜𝑏𝑗.difference(other: OrderedSet<T>): OrderedSet<T>
#Source

Returns a new set which contains items which appear this but NOT in the provided set

difference produces a new OrderedSet which contains all the items which appear in this OrderedSet, except all the items from the other OrderedSet are removed. difference can be thought of as subtracting: this - other. difference guarantees that if the resulting OrderedSet is equal to this, then the OrderedSet object instance is returned unchanged.

Runs in time O(m log(n/m)) where m is the size of the smaller set and n is the size of the larger set.

𝑜𝑏𝑗.symmetricDifference(other: OrderedSet<T>): OrderedSet<T>
#Source

Returns an OrderedSet which contains only items which appear in exactly one of the two sets

symmetricDifference produces a new set which contains all the items appear in exactly one of this and other. If this or other are empty, the non-empty set is returned unchanged.

Runs in time O(m log(n/m)) where m is the size of the smaller set and n is the size of the larger set.

𝑜𝑏𝑗.isSubsetOf(largerSet: OrderedSet<T>): boolean
#Source

Returns true if each item of this exists in largerSet

isSubsetOf checks if this is a subset of largerSet, that is, if every item in this is also in largerSet.

Runs in time O(m log(n/m)) where m is the size of this and n is the size of largerSet.

𝑜𝑏𝑗.isSupersetOf(smallerSet: OrderedSet<T>): boolean
#Source

Returns true if each item of smallerSet exists in this

isSupersetOf checks if this is a superset of smallerSet, that is, if every item in smallerSet also exists in this.

Runs in time O(m log(n/m)) where m is the size of smallerSet and n is the size of this.

𝑜𝑏𝑗.isDisjointFrom(other: OrderedSet<T>): boolean
#Source

Returns true if each item exists in exactly one of the two sets

isDisjointFrom checks if this is disjoint from other, that is, the intersection is empty.

Runs in time O(m log(n/m)) where m is the size of this and n is the size of other.