npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2026 – Pkg Stats / Ryan Hefner

critbit

v1.0.2

Published

Crit-bit trees for JavaScript: sorted sets and maps of strings with fast prefix queries.

Readme

critbit.js

A JavaScript implementation of crit-bit trees: sorted sets and maps of strings with fast lookups, adds and deletes, plus ordered operations such as prefix queries, minimum, maximum, successor and predecessor. The API follows Set and Map, and TypeScript types are included.

Any JavaScript string can be a key, including strings containing "\0", characters above U+00FF and unpaired surrogates, and keys are kept in the same order as JavaScript's default sort.

import {Tree, TreeMap} from "critbit";

const tree = new Tree(["apple", "banana", "apricot"]);
tree.has("apple"); // true
tree.successor("apple"); // "apricot"
[...tree.keys("b")]; // ["banana"]
tree.prefixed("ap", key => console.log(key)); // apple, apricot

const map = new TreeMap([["apple", 1]]);
map.set("banana", 2);
map.get("banana"); // 2
[...map]; // [["apple", 1], ["banana", 2]]

Keys

Keys are ordered by UTF-16 code units, with a key before any longer key it is a prefix of, so iteration gives the same order as JavaScript's default sort and the < operator. Keys can contain any code units, including "\0": "a", "a\0" and "a\0\0" are distinct keys. By contrast, the original crit-bit trees in C work on NUL-terminated byte strings, so they can't hold keys that contain NUL.

The only exception is a key that is identical to an existing key for its first 226 (about 67 million) characters: adding one throws a RangeError.

API

new Tree([keys])

A sorted set of strings, optionally containing the given iterable of keys. If the keys are in ascending order, the tree is built in a single pass, which is much faster than adding them one at a time.

  • tree.size is the number of keys.
  • tree.has(key) returns whether key is in the tree.
  • tree.add(key) adds key and returns the tree. It throws a TypeError if key isn't a string.
  • tree.delete(key) removes key, returning whether it was present.
  • tree.clear() removes all keys.
  • tree.min() and tree.max() return the smallest and largest keys, or undefined if the tree is empty.
  • tree.successor(key) and tree.predecessor(key) return the smallest key greater than key and the largest key less than key, or undefined if there is none. key need not be in the tree.
  • tree.keys([start]) returns an iterator over the keys in order, starting from the smallest key greater than or equal to start if given. Trees are also iterable, yielding all keys in order. As with Set, tree.values() is the same as tree.keys(), and tree.entries() yields [key, key] pairs.
  • tree.forEach(f[, thisArg]) calls f(key, key, tree) for each key in order, like Set.prototype.forEach.
  • tree.prefixed(prefix, f) calls f(key, value) for each key starting with prefix, in order, stopping early if f returns false.
  • tree.union(other) and tree.intersection(other) return new trees.
  • tree.optimize() rearranges the tree's memory so that it is faster to search, and returns the tree. This happens automatically as the tree grows, but calling it after adding or deleting many keys makes iteration and prefix queries faster, and reuses the slots left by deleted keys.

As with Set and Map, a tree may be changed while iterating over it or inside a forEach or prefixed callback: keys deleted before they are reached are skipped, and keys added after the current key are visited. Iterators support the iterator helpers, such as tree.keys().map(f).

new TreeMap([entries])

A sorted map from strings to values, optionally containing the given iterable of [key, value] entries, with the same methods as Tree except add, plus:

  • map.get(key) returns the value for key, or undefined if it is not present.
  • map.set(key, value) sets the value for key, adding it if needed, and returns the map.
  • map.values([start]) and map.entries([start]) return iterators over the values and [key, value] pairs in key order. Maps are also iterable, yielding entries.
  • map.forEach(f[, thisArg]) calls f(value, key, map) for each entry in key order, like Map.prototype.forEach.

map.union(other) takes values from map for keys in both, and gives keys only in other their values from other, or undefined if other is a Tree.

When to use it

Use a crit-bit tree when you need ordered operations, which hash tables like Set and Map can't do efficiently: prefix queries, iterating in sorted order, or finding the minimum, maximum, next or previous key. Crit-bit trees are also fast for long keys, since a lookup only examines the bits where keys differ, plus one final comparison, while hashing reads the whole key.

Unlike a hash table, a crit-bit tree has no slow cases for unusual or malicious keys: each operation visits at most one node per bit of the longest key, however the keys are distributed. (V8 randomizes its string hashes, which makes such slow cases unlikely for Set and Map too.)

A built-in Set or Map is faster to build from unsorted keys, and faster for repeated lookups of the same string objects, since V8 caches each string's hash. Run npm run bench to compare on your own machine.

Development

  • npm test runs the tests.
  • npm run bench compares Tree with Set, a plain object and a sorted array, using 100,000 keys. Use npm run bench -- 1e6 urls,long tree,set to choose the number of keys, datasets and structures.