# sparse-set

> Briggs & Torczon's efficient sparse sets.

Latest version **1.0.0** (published 2022-10-13) · MIT license · 0 weekly downloads

## Install

```sh
npm install sparse-set
pnpm add sparse-set
yarn add sparse-set
bun add sparse-set
```

Provides the command `sparse-set`.

## Health

**Score 25/100 (F)** — status: abandoned.

Positive: has types; no vulnerabilities; high quality score.

Warnings: low downloads; no esm support.

Negative: abandoned; low maintenance score.

## Facts

| | |
|---|---|
| Version | 1.0.0 |
| Published | 2022-10-13 |
| First published | 2022-10-13 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | bundled |
| Module format | CommonJS |
| Dependencies | 163 |
| Unpacked size | 17.5 KB |
| Known vulnerabilities | 0 (+4 in 3 direct dependencies) |
| Install scripts | no |
| Author | Logan R. Kearsley |
| Maintainers | gliese1337 |
| Keywords | sparse, set |

## Links

- npm: https://www.npmjs.com/package/sparse-set
- Repository: https://github.com/gliese1337/sparse-set
- Homepage: https://github.com/gliese1337/sparse-set#readme
- Issues: https://github.com/gliese1337/sparse-set/issues
- npm.io page: https://npm.io/package/sparse-set

## Dependencies (163)

- [he](https://npm.io/package/he.md) ^1.2.0
- [ms](https://npm.io/package/ms.md) ^2.1.2
- [yn](https://npm.io/package/yn.md) ^3.1.1
- [ajv](https://npm.io/package/ajv.md) ^6.12.6
- [arg](https://npm.io/package/arg.md) ^4.1.3
- [diff](https://npm.io/package/diff.md) ^5.0.0
- [flat](https://npm.io/package/flat.md) ^5.0.2
- [glob](https://npm.io/package/glob.md) ^7.1.6
- [levn](https://npm.io/package/levn.md) ^0.4.1
- [once](https://npm.io/package/once.md) ^1.4.0
- [y18n](https://npm.io/package/y18n.md) ^5.0.8
- [acorn](https://npm.io/package/acorn.md) ^7.4.1
- [chalk](https://npm.io/package/chalk.md) ^4.1.2
- [cliui](https://npm.io/package/cliui.md) ^7.0.4
- [debug](https://npm.io/package/debug.md) ^4.3.4
- [fastq](https://npm.io/package/fastq.md) ^1.13.0
- [growl](https://npm.io/package/growl.md) ^1.10.5
- [isexe](https://npm.io/package/isexe.md) ^2.0.0
- [loupe](https://npm.io/package/loupe.md) ^2.3.4
- [slash](https://npm.io/package/slash.md) ^3.0.0
- [table](https://npm.io/package/table.md) ^6.8.0
- [tslib](https://npm.io/package/tslib.md) ^1.14.1
- [which](https://npm.io/package/which.md) ^2.0.2
- [yargs](https://npm.io/package/yargs.md) ^16.2.0
- [braces](https://npm.io/package/braces.md) ^3.0.2
- [espree](https://npm.io/package/espree.md) ^7.3.1
- [globby](https://npm.io/package/globby.md) ^11.1.0
- [ignore](https://npm.io/package/ignore.md) ^5.2.0
- [merge2](https://npm.io/package/merge2.md) ^1.4.1
- [nanoid](https://npm.io/package/nanoid.md) ^3.1.20
- [rimraf](https://npm.io/package/rimraf.md) ^3.0.2
- [semver](https://npm.io/package/semver.md) ^7.3.8
- [uri-js](https://npm.io/package/uri-js.md) ^4.4.1
- [wrappy](https://npm.io/package/wrappy.md) ^1.0.2
- [deep-is](https://npm.io/package/deep-is.md) ^0.1.4
- [esprima](https://npm.io/package/esprima.md) ^4.0.1
- [esquery](https://npm.io/package/esquery.md) ^1.4.0
- [esutils](https://npm.io/package/esutils.md) ^2.0.3
- [find-up](https://npm.io/package/find-up.md) ^5.0.0
- [flatted](https://npm.io/package/flatted.md) ^3.2.7
- [globals](https://npm.io/package/globals.md) ^13.17.0
- [is-glob](https://npm.io/package/is-glob.md) ^4.0.3
- [js-yaml](https://npm.io/package/js-yaml.md) ^3.14.1
- [p-limit](https://npm.io/package/p-limit.md) ^3.1.0
- [pathval](https://npm.io/package/pathval.md) ^1.1.1
- [regexpp](https://npm.io/package/regexpp.md) ^3.2.0
- [reusify](https://npm.io/package/reusify.md) ^1.0.4
- [tsutils](https://npm.io/package/tsutils.md) ^3.21.0
- [yallist](https://npm.io/package/yallist.md) ^4.0.0
- [anymatch](https://npm.io/package/anymatch.md) ^3.1.2
- [argparse](https://npm.io/package/argparse.md) ^1.0.10
- [chokidar](https://npm.io/package/chokidar.md) ^3.5.1
- [deep-eql](https://npm.io/package/deep-eql.md) ^3.0.1
- [dir-glob](https://npm.io/package/dir-glob.md) ^3.0.1
- [doctrine](https://npm.io/package/doctrine.md) ^3.0.0
- [enquirer](https://npm.io/package/enquirer.md) ^2.3.6
- [escalade](https://npm.io/package/escalade.md) ^3.1.1
- [has-flag](https://npm.io/package/has-flag.md) ^4.0.0
- [inflight](https://npm.io/package/inflight.md) ^1.0.6
- [inherits](https://npm.io/package/inherits.md) ^2.0.4
- [p-locate](https://npm.io/package/p-locate.md) ^5.0.0
- [path-key](https://npm.io/package/path-key.md) ^3.1.1
- [progress](https://npm.io/package/progress.md) ^2.0.3
- [punycode](https://npm.io/package/punycode.md) ^2.1.1
- [readdirp](https://npm.io/package/readdirp.md) ^3.5.0
- [acorn-jsx](https://npm.io/package/acorn-jsx.md) ^5.3.2
- [callsites](https://npm.io/package/callsites.md) ^3.1.0
- [camelcase](https://npm.io/package/camelcase.md) ^6.3.0
- [esrecurse](https://npm.io/package/esrecurse.md) ^4.3.0
- [fast-glob](https://npm.io/package/fast-glob.md) ^3.2.12
- [is-number](https://npm.io/package/is-number.md) ^7.0.0
- [js-tokens](https://npm.io/package/js-tokens.md) ^4.0.0
- [lru-cache](https://npm.io/package/lru-cache.md) ^6.0.0
- [minimatch](https://npm.io/package/minimatch.md) ^3.1.2
- [path-type](https://npm.io/package/path-type.md) ^4.0.0
- [picomatch](https://npm.io/package/picomatch.md) ^2.3.1
- [type-fest](https://npm.io/package/type-fest.md) ^0.20.2
- [word-wrap](https://npm.io/package/word-wrap.md) ^1.2.3
- [wrap-ansi](https://npm.io/package/wrap-ansi.md) ^7.0.0
- [ansi-regex](https://npm.io/package/ansi-regex.md) ^5.0.1
- [color-name](https://npm.io/package/color-name.md) ^1.1.4
- [concat-map](https://npm.io/package/concat-map.md) ^0.0.1
- [decamelize](https://npm.io/package/decamelize.md) ^4.0.0
- [estraverse](https://npm.io/package/estraverse.md) ^4.3.0
- [fill-range](https://npm.io/package/fill-range.md) ^7.0.1
- [flat-cache](https://npm.io/package/flat-cache.md) ^3.0.4
- [is-extglob](https://npm.io/package/is-extglob.md) ^2.1.1
- [make-error](https://npm.io/package/make-error.md) ^1.3.6
- [micromatch](https://npm.io/package/micromatch.md) ^4.0.5
- [optionator](https://npm.io/package/optionator.md) ^0.9.1
- [prelude-ls](https://npm.io/package/prelude-ls.md) ^1.2.1
- [slice-ansi](https://npm.io/package/slice-ansi.md) ^4.0.0
- [source-map](https://npm.io/package/source-map.md) ^0.6.1
- [sprintf-js](https://npm.io/package/sprintf-js.md) ^1.0.3
- [strip-ansi](https://npm.io/package/strip-ansi.md) ^6.0.1
- [text-table](https://npm.io/package/text-table.md) ^0.2.0
- [type-check](https://npm.io/package/type-check.md) ^0.4.0
- [wide-align](https://npm.io/package/wide-align.md) ^1.1.3
- [workerpool](https://npm.io/package/workerpool.md) ^6.1.0
- [ansi-colors](https://npm.io/package/ansi-colors.md) ^4.1.3
- [ansi-styles](https://npm.io/package/ansi-styles.md) ^4.3.0
- [array-union](https://npm.io/package/array-union.md) ^2.1.0
- [buffer-from](https://npm.io/package/buffer-from.md) ^1.1.2
- [check-error](https://npm.io/package/check-error.md) ^1.0.2
- [cross-spawn](https://npm.io/package/cross-spawn.md) ^7.0.3
- [emoji-regex](https://npm.io/package/emoji-regex.md) ^8.0.0
- [fs.realpath](https://npm.io/package/fs.realpath.md) ^1.0.0
- [glob-parent](https://npm.io/package/glob-parent.md) ^5.1.2
- [imurmurhash](https://npm.io/package/imurmurhash.md) ^0.1.4
- [locate-path](https://npm.io/package/locate-path.md) ^6.0.0
- [log-symbols](https://npm.io/package/log-symbols.md) ^4.0.0
- [path-exists](https://npm.io/package/path-exists.md) ^4.0.0
- [randombytes](https://npm.io/package/randombytes.md) ^2.1.0
- [safe-buffer](https://npm.io/package/safe-buffer.md) ^5.2.1
- [type-detect](https://npm.io/package/type-detect.md) ^4.0.8
- [yocto-queue](https://npm.io/package/yocto-queue.md) ^0.1.0
- [astral-regex](https://npm.io/package/astral-regex.md) ^2.0.0
- [eslint-scope](https://npm.io/package/eslint-scope.md) ^5.1.1
- [eslint-utils](https://npm.io/package/eslint-utils.md) ^3.0.0
- [import-fresh](https://npm.io/package/import-fresh.md) ^3.3.0
- [is-plain-obj](https://npm.io/package/is-plain-obj.md) ^2.1.0
- [lodash.merge](https://npm.io/package/lodash.merge.md) ^4.6.2
- [resolve-from](https://npm.io/package/resolve-from.md) ^4.0.0
- [run-parallel](https://npm.io/package/run-parallel.md) ^1.2.0
- [string-width](https://npm.io/package/string-width.md) ^4.2.3
- [yargs-parser](https://npm.io/package/yargs-parser.md) ^20.2.4
- [color-convert](https://npm.io/package/color-convert.md) ^2.0.1
- [get-func-name](https://npm.io/package/get-func-name.md) ^2.0.0
- [parent-module](https://npm.io/package/parent-module.md) ^1.0.1
- [shebang-regex](https://npm.io/package/shebang-regex.md) ^3.0.0
- [balanced-match](https://npm.io/package/balanced-match.md) ^1.0.2
- [browser-stdout](https://npm.io/package/browser-stdout.md) ^1.3.1
- [create-require](https://npm.io/package/create-require.md) ^1.1.1
- [is-binary-path](https://npm.io/package/is-binary-path.md) ^2.1.0
- [normalize-path](https://npm.io/package/normalize-path.md) ^3.0.0
- [supports-color](https://npm.io/package/supports-color.md) ^7.2.0
- [to-regex-range](https://npm.io/package/to-regex-range.md) ^5.0.1
- [yargs-unparser](https://npm.io/package/yargs-unparser.md) ^2.0.0
- [assertion-error](https://npm.io/package/assertion-error.md) ^1.1.0
- [brace-expansion](https://npm.io/package/brace-expansion.md) ^1.1.11
- [fast-deep-equal](https://npm.io/package/fast-deep-equal.md) ^3.1.3
- [get-caller-file](https://npm.io/package/get-caller-file.md) ^2.0.5
- [lodash.truncate](https://npm.io/package/lodash.truncate.md) ^4.4.2
- [natural-compare](https://npm.io/package/natural-compare.md) ^1.4.0
- [queue-microtask](https://npm.io/package/queue-microtask.md) ^1.2.3
- [shebang-command](https://npm.io/package/shebang-command.md) ^2.0.0
- [fast-levenshtein](https://npm.io/package/fast-levenshtein.md) ^2.0.6
- [file-entry-cache](https://npm.io/package/file-entry-cache.md) ^6.0.1
- [path-is-absolute](https://npm.io/package/path-is-absolute.md) ^1.0.1
- [v8-compile-cache](https://npm.io/package/v8-compile-cache.md) ^2.3.0
- [binary-extensions](https://npm.io/package/binary-extensions.md) ^2.2.0
- [require-directory](https://npm.io/package/require-directory.md) ^2.1.1
- [source-map-support](https://npm.io/package/source-map-support.md) ^0.5.21
- [eslint-visitor-keys](https://npm.io/package/eslint-visitor-keys.md) ^2.1.0
- [require-from-string](https://npm.io/package/require-from-string.md) ^2.0.2
- [strip-json-comments](https://npm.io/package/strip-json-comments.md) ^3.1.1
- [escape-string-regexp](https://npm.io/package/escape-string-regexp.md) ^4.0.0
- [json-schema-traverse](https://npm.io/package/json-schema-traverse.md) ^0.4.1
- [serialize-javascript](https://npm.io/package/serialize-javascript.md) ^5.0.1
- [is-fullwidth-code-point](https://npm.io/package/is-fullwidth-code-point.md) ^3.0.0
- [functional-red-black-tree](https://npm.io/package/functional-red-black-tree.md) ^1.0.1
- [fast-json-stable-stringify](https://npm.io/package/fast-json-stable-stringify.md) ^2.1.0
- [json-stable-stringify-without-jsonify](https://npm.io/package/json-stable-stringify-without-jsonify.md) ^1.0.1

## Alternatives

- [jsforce](https://npm.io/package/jsforce.md) — 851.2K weekly downloads
- [react-native-qrcode-svg](https://npm.io/package/react-native-qrcode-svg.md) — 693.5K weekly downloads
- [@salesforce/plugin-data](https://npm.io/package/@salesforce/plugin-data.md) — 394.9K weekly downloads
- [@backstage/plugin-search-common](https://npm.io/package/@backstage/plugin-search-common.md) — 308.5K weekly downloads
- [@chain-registry/types](https://npm.io/package/@chain-registry/types.md) — 38.4K weekly downloads

## Recent versions

- 1.0.0 (latest) — 2022-10-13

## README

# sparse-set
An implementation of Briggs and Torczon's [Efficient Representation for Sparse Sets](https://dl.acm.org/doi/pdf/10.1145/176454.176484).

This package exports a single class, `SparseSet`, with the following interface:

```ts
class SparseSet {
    readonly bound: number;
    readonly preserve_order: boolean;
    length: number;
    size: number;

    constructor(bound: number, options?: SparseSetOpts);
    
    has(k: number): boolean;
    add(k: number): SparseSet;
    clear(): SparseSet;
    delete(k: number, preserve_order?: boolean): boolean;
    forEach(cb: (k: number) => void): void;
    copy(options?: SparseSetOpts & { bound?: number; }): SparseSet;
    complement(options?: SparseSetOpts & { bound?: number; }): SparseSet;
    union(s: SparseSet): SparseSet;
    intersect(s: SparseSet, preserve_order?: boolean): SparseSet;
    difference(s: SparseSet, preserve_order?: boolean): SparseSet;
    xor(s: SparseSet, preserve_order?: boolean): SparseSet;
    entries(): Generator<[number, number]>;
    keys(): Generator<number>;
    values(): Generator<number>;
    [Symbol.iterator](): Generator<number>;
}
```

`SparseSetOpts` looks like this:

```ts
export interface SparseSetOpts {
    values?: Iterable<number>;
    preserve_order?: boolean;
    memory?: {
        buffer: ArrayBuffer;
        byteOffset?: number;
    };
}
```

The `SparseSet` constructor requires a `bound` argument which specifies the maximum size of the set (and is one more than the largest value that can be stored in the set). This is used to pre-allocate memory for the entire set, and, by defining a finite universe of set elements, allows performing set complement operations. If `memory` is not provided, a new `ArrayBuffer` is automatically allocated. Note that one of the advantages of this sparse set data structure is that memory can be allocated quickly, because it does not need to be initialized--however, JavaScript does not allow allocating uninitialized memory (`ArrayBuffer`s are always initialized to zero), which eliminates that advantage. However, should you already have a sufficiently large `ArrayBuffer` on hand to re-use, you can pass it through the `memory` object to avoid re-allocation and re-initialization costs. Also note that `TypedArray` and `DataView` objects conform to the necessary interface to be directly passed as `memory` objects. Like the built-in `Set` object, the `SparseSet` constructor can take in an optional iterable of initial elements via the `values` field of `SparseSetOpts`. There is also an optional `preserve_order` argument; by default, `SparseSet` preserves insertion order of elements for iteration; however, `delete`s, `intersection`s, `difference`s, and `xor`s can scramble the insertion order. Setting `preserve_order` to `true` ensures that insertion order is preserved under all operations, at a slight performance penalty. Each of those four methods also takes an optional `preserve_order` argument, which can be used to override the default set by the constructor.

Note that `SparseSet` duplicates the interface of the built-in JavaScript `Set` type, with following additional properties and methods and properties:

* `bound: number`: the maximum size of the set; 1 more than the maximum value that can be stored in the set.
* `length: number`: an alias for `size`. In contrast to a built-in `Set`, the `length` and `size` properties can be set to truncate the latest values added to a `SparseSet`. Attempting to set `length` or `size` to something larger than their current values will throw an exception.
* `copy(options?: SparseSetOpts & { bound?: number; }): SparseSet`: efficiently produces a new `SparseSet` containing a copy of the data in the original `SparseSet`. If `bound` or `preserve_order` options are omitted, they will be copied from the original `SparseSet`. Setting `bound` to a smaller value than that of the original will truncate elements that exceed the new bound. Backing memory is not re-used; pre-allocated memory for the new set can be passed in through the options object, but otherwise new memory will be automatically allocated. 
* `complement(options?: SparseSetOpts & { bound?: number; })`: efficiently produces a new `SparseSet` containing all elements below `bound` which are not in the original `SparseSet`. If `bound` or `preserve_order` options are omitted, they will be copied from the original `SparseSet`. Setting `bound` to a smaller value than that of the original will truncate elements that exceed the new bound. Backing memory is not re-used; pre-allocated memory for the new set can be passed in through the options object, but otherwise new memory will be automatically allocated.
* `union(s: SparseSet): SparseSet`: updates the current `SparseSet` with the elements from the given `SparseSet`, dropping any elements which are outside the current bound.
* `intersection(s: SparseSet, preserve_order?: boolean): SparseSet`: removes elements from the current `SparseSet` that do not occur in the given `SparseSet`.
* `difference(s: SparseSet, preserve_order?: boolean): SparseSet`: removes elements from the current `SparseSet` which *do* occur in the given `SparseSet`.
* `xor(s: SparseSet, preserve_order?: boolean): SparseSet`: removes elements from the current `SparseSet` which occur in the given `SparseSet`, and adds elements from the given `SparseSet` which were not previously in the current `SparseSet`, dropping any elements which are outside the current bound.

---
_Source: https://npm.io/package/sparse-set · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._