@etianen/set

Helpers for using unique sorted arrays as sets.

Installing

npm install '@etianen/set'

TypeScript: To take advantage of typings, be sure to set moduleResolution to "node" in your tsconfig.json.

Overview

Unique sorted arrays can be used as relatively performant sets, without requiring a dedicated data structure.

@etianen/set provides helpers for using unique sorted arrays as sets.

import * as set from "@etianen/set";

const setA = set.from([1, 2, 3]);
const setB = set.from([2, 3, 4]);
set.union(setA, setB);  // => [1, 2, 3, 4]
set.intersection(setA, setB);  // => [2, 3]

API

In all the functions below:

• The source arguments are never mutated.
• The input arrays are assumed to be unique and sorted.
• If possible, the function will return one of the input arrays if the operation is a no-op. This helps preserve reference equality.
• If the result is a Set, it will be frozen.

Set

A unique, sorted array containing values of type V.

interface Set<V> extends Array<V> {
    isSet: void;
}

isSet is a compiler-only flag, used by the TypeScript compiler. Do not attempt to access it.

Important: Any function that expects a Set will not behave as expected if the array is not sorted and unique. If you cannot guarantee that an input array is sorted and unique, use from() to convert it.

TypeScript: The compiler will prevent you using an Array as a Set to prevent accidental mistakes. If you can guarantee that the array is sorted and unique, it's safe to use an explicit typecast to convert it.

add()

Adds key to a new copy of set.

Complexity: O(n)

function add<V>(set: Set<V>, key: V): Set<V>;

difference()

Returns a Set of all keys in setA that are not in setB.

Complexity: O(n)

function difference<V>(setA: Set<V>, setB: Set<V>): Set<V>;

empty()

Creates a new empty set.

function create<V>(): Set<V>;

from()

Converts keys into a sorted, unique set.

Complexity: O(2n + n log(n))

function from<V>(keys: Set<V>): Set<V>;

has()

Returns true if key is present in set.

Complexity: O(log(n))

function has<V>(set: Set<V>, key: V): boolean;

intersection()

Returns a Set of all keys present in both setA and setB.

Complexity: O(n)

function intersection<V>(setA: Set<V>, setB: Set<V>): Set<V>;

isDisjoint()

Returns true if setA and setB have no keys in common.

Complexity: O(n)

function isDisjoint<V>(setA: Set<V>, setB: Set<V>): boolean;

isSubset()

Returns true if all keys in setA are present in setB.

Complexity: O(n)

function isSubset<V>(setA: Set<V>, setB: Set<V>): boolean;

isSuperset()

Returns true if all keys in setB are present in setA.

Complexity: O(n)

function isSuperset<V>(setA: Set<V>, setB: Set<V>): boolean;

remove()

Returns a copy of set with key removed.

Complexity: O(n)

function remove<V>(set: Set<V>, key: V): Set<V>;

symmetricDifference()

Returns a Set of all keys not present in both setA and setB.

Complexity: O(n)

function symmetricDifference<V>(setA: Set<V>, setB: Set<V>): Set<V>;

union()

Returns a Set of all keys in both setA and setB.

function union<V>(setA: Set<V>, setB: Set<V>): Set<V>;

Build status

This project is built on every push using the Travis-CI service.

Support and announcements

Downloads and bug tracking can be found at the main project website.

More information

This project was developed by Dave Hall. You can get the code from the project site.

Dave Hall is a freelance web developer, based in Cambridge, UK. You can usually find him on the Internet:

• Website
• Google Profile