☯️ Classifier Class

☯️ Classifier Class — A Rich Map

Overview

Classifier is a hierarchical, prefix-based multimap where keys are sequences and values are stored in equivalence classes determined by those key-sequences.

  • Behaves like a generalized Map where keys are iterable sequences.
  • Supports multiple values per key-sequence.
  • Implements a sorted trie for efficient prefix queries.
  • Values at each node form an equivalence class, optionally sorted.

Node Structure

Each node contains:

  • parent — parent node (null for root)
  • key — key associated with this node (undefined for root)
  • depth — depth in the tree (root = 0)
  • sortedKeys — a SortedArray of child keys
  • keyToChild — a Map from key → child node
  • nin — number of sequences ending exactly at this node
  • nout — number of sequences ending strictly below this node
  • class — a collection of items forming the equivalence class at this node
  • sorter(node) — returns [keyComparator, itemComparator?] to define order

Constructor

new Classifier(sorter, parent, key)
  • sorter — function receiving the node and returning [keyComparator, itemComparator?].
  • parent — parent node, null for root.
  • key — key leading from parent to this node, undefined for root.

Collection Interface

n()

Returns total number of item occurrences in the subtree (nin + nout).

has(keys)

Checks if a key sequence exists and ends at a terminating node.

add(keys, item, xTimes=1)

Adds an item to a sequence of keys. Creates nodes if necessary.

remove(keys, xTimes=Infinity)

Removes occurrences of a stored sequence, up to xTimes. Prunes this node if becomes empty.

clear()

Removes all entries in this node and subtree, clearing .class and children. Prunes this node.

get(query, first=true)

Returns all items matching a key prefix (supports undefined as wildcard).

Queue Interface

reverse()

Returns all items in the classifier in reverse traversal order.

peek(first=true)

Returns the first or last item in the subtree without removing it.

poll(first=true)

Returns and removes the first or last item in the subtree.

Traversal Methods

path()

Returns a Path<Classifier> from the root to this node.

with(path)

Returns the descendant Classifier addressed by the given path (iterable) of keys.

descendants(query=[], first=true)

Depth-first traversal of nodes, optionally filtered by prefix query.

  • query — optional array of keys; undefined is a wildcard.
  • first — traversal order, true = ascending.

*keys()

Yields all stored key sequences in the classifier.

*values()

Yields all stored items in traversal order.

*entries()

Yields [keys, item] pairs for all stored items.

Example Usage

const clf = new Classifier();
clf.add(['a','b','c'], 'abc');

// Prefix query
for (const item of clf.get([undefined,'b'])) {
    console.log(item);  // all items where repr[1] === 'b'
}


Comments

Post a Comment

Popular posts from this blog

🧠 Contemplating a True Set

🧠 Equivalence in JavaScript: Contemplating a True Set In JavaScript,   equivalence   behaves differently depending on whether you're working with primitive or non-primitive types. For   primitives —such as numbers, booleans, strings, and symbols—equivalence is determined by comparing actual values. If two variables hold the same value, they are considered equivalent. However, for   objects and arrays , equivalence is   by reference . Two arrays   [0]   and   [0]   are not considered equal because they are separate instances, even though they contain identical content. 🔬 Snippet 1: Equivalence by Value and by Reference new Set ([ 0 , 0 ]); // => Set { 0 } new Set ([[ 0 ], [ 0 ]]); // => Set { [0], [0] } JavaScript’s   Set   treats the two   0   values as equivalent but considers   [0]   and   [0]   as distinct because they are different object instances. This reveals JavaScript’s mini...
Read more

🧱 v0.0.0-dev.1 — First Brick

🧱 v0.0.0-dev.1 — First Brick We’re excited to announce the   first prerelease   of   @fizzwiz/sorted :   v0.0.0-dev.1   — the   First Brick   in what aims to become a foundational library for   priority-aware collections   and   custom equivalence models . This release introduces the core building blocks: 🔧 Core Abstractions Collection   – a base interface for iterable containers Queue   – an extension for prioritizing and structuring exploration 📦 Concrete Implementations ArrayQueue   – a simple queue based on insertion order SortedArray   – a comparator-based queue maintaining sorted state These implementations offer different   notions of equivalence   — by insertion order or by comparator — laying the groundwork for more powerful models based on   representation functions , coming soon. 🧪 This is a   prerelease , but it’s ready to explore. Your early feedback will help guide the evolution o...
Read more

☯️ v0.0.0-dev.3 — Classifier & TrueSet

☯️ v0.0.0-dev.3 — Classifier & TrueSet We’re thrilled to announce   v0.0.0-dev.3   of   @fizzwiz/sorted , introducing two powerful new abstractions:   Classifier   and   TrueSet . This release takes the library far beyond simple sorted collections, enabling   hierarchical keys ,   prefix queries , and   representation-based equivalence . 🔧 Core Enhancements Classifier   — a rich, multidimensional map A   Classifier   stores entries whose keys are   arrays (any iterable) . It supports: Storing multiple items per key Efficient   prefix queries   with wildcards Sorted traversal of both keys and items Flexible equivalence via custom sorting rules TrueSet   — a representation-based set A   TrueSet   defines equivalence using a   representation function   ( repr ). It enables: Equivalence among   objects , not just primitives Aggregation of equivalent items in sorted, enumerable class...
Read more