Class: Classifier

Classifier(sorteropt, parent, key)

Classifier

A hierarchical, prefix-based multimap where keys are sequences and values are grouped by their key sequence (equivalence classes).

Concept

  • Keys are iterables (e.g., ['a','b','c']).
  • Multiple values may be stored per key sequence.
  • Keys are stored in a SortedArray for efficient prefix queries.
  • Values at each node form an equivalence class, optionally sorted or queued.

Node Structure

Each node contains:

  • parent — parent node (null for root)
  • key — key for this node (undefined for root)
  • depth — depth in the tree (root = 0)
  • sortedKeys — sorted list of child keys
  • keyToChild — map of key → child node
  • nin — number of sequences ending at this node
  • nout — number of sequences ending below this node
  • class — container of values for this node’s key sequence
  • sorter(node) — function defining key and value order

Features

  • Multimap: multiple values per key sequence.
  • SortedMap: both keys and values are ordered.
  • Prefix queries with wildcards.
  • Efficient traversal, insertion, and removal.

Example

const clf = new Classifier();
clf.add(['a','b','c'], 'abc');   // store item "abc"
for (const item of clf.get([undefined,'b'])) {
    console.log(item);            // all items with repr[1] === 'b'
}

Constructor

new Classifier(sorteropt, parent, key)

Creates a classifier node.

Parameters:
Name Type Attributes Default Description
sorter function <optional>

Function receiving the newly created node and returning a pair [keyComparator, itemComparator]: - keyComparator(a, b) — for sorting child keys. - itemComparator(a, b) — for sorting items inside .class. Optional: if a Boolean flag is provided instead of a itemComparator, .class becomes an ArrayQueue(flag) (true | undefined = FIFO, false = LIFO), allowing duplicates.
parent Classifier | null null

The parent node, or null for the root.
key *

The key leading from the parent to this node (undefined for the root node).
Source:

Extends

Classes

Classifier

Members

class :Queue

Items whose representation corresponds exactly to this node's full key-path. Acts as an equivalence class container.

  • If an item-comparator is provided → SortedArray
  • Otherwise → ArrayQueue preserving insertion order
Type:
Source:

depth :number

Type:
  • number
Source:

key :*

Type:
  • *
Source:

keyToChild :Map.<*, Classifier>

Type:
Source:

nin :number

Type:
  • number
Source:

nout :number

Type:
  • number
Source:

parent :Classifier|null

Type:
Source:

(readonly) size :number

Total number of item occurrences .nin + .nout stored in the subtree rooted at this node.

Type:
  • number
Source:

sortedKeys :SortedArray.<*>

Type:
Source:

sorter :function

Function returning a couple of comparators: for child keys and class items.

Type:
  • function
Source:

Methods

add(keys, item, xTimesopt) → {boolean}

Adds or removes occurrences of an entry >keys, obj> . If xTimes > 0, missing nodes are created.

Parameters:
Name Type Attributes Default Description
keys Iterable.<*> | *

(or key)
item any
xTimes number <optional>
 1

Positive to add, negative to remove. A float number is allowed.
Source:
Returns:
  • Whether the operation succeeded.
Type
boolean

children(sortedopt) → {Each.<Classifier>}

Returns the child classifier nodes.

By default, children are returned in arbitrary iteration order (the natural order of Map.prototype.values()).

If sorted is true, the children are returned in the order defined by this.sortedKeys, which stores the classifier's sorted key sequence.

Invariants

  • Every key in this.sortedKeys MUST correspond to an existing child in this.keyToChild.
  • Therefore, calling this method with sorted = true will never return undefined elements.
    If that happens, it indicates an internal consistency error elsewhere.

Notes

  • No filtering is performed: missing children are treated as fatal structural violations and will propagate errors naturally.
Parameters:
Name Type Attributes Default Description
sorted boolean <optional>
 false

Whether to return children in sorted key order.
Source:
Returns:

An Each iterable of child classifier nodes.

Type
Each.<Classifier>

clear() → {void}

Removes all entries stored in this node and its entire subtree.

This method:

  • Resets .nin (sequences ending at this node) and .nout (sequences passing below)
  • Clears all child nodes (keyToChild and sortedKeys)
  • Clears the .class collection of items associated with this node
  • Prunes this node from its parent if it becomes empty
Source:
Returns:
Type
void

descendants(queryopt, firstopt, indexopt) → {Each.<Classifier>}

Performs a depth-first traversal of all descendant classifier nodes starting from this node. The node itself is not included.

This is the primitive traversal operation used internally by keys(), values(), and entries().

Prefix filtering (query)

A query is an array of expected child keys at each depth:

  • query[d] = required key at depth d
  • undefined = wildcard → all keys here are accepted
  • If query.length === 0, the traversal is unrestricted

Matching proceeds depth-by-depth as the traversal descends.

Traversal order

  • first = true → children visited in sorted ascending key order
  • first = false → children visited in reversed order
Parameters:
Name Type Attributes Default Description
query Array.<*> <optional>
 []

Optional prefix constraint. undefined acts as a wildcard.
first boolean <optional>
 true

Whether to traverse children in normal (true) or reversed (false) order.
index number <optional>
 0

Internal recursion depth. Users should normally ignore this.
Source:
Returns:

An Each iterable yielding all matching descendant nodes, in depth-first search order.

Type
Each.<Classifier>
Examples
// Iterate all descendants
for (const node of clf.descendants()) {
    console.log(node.key);
}
// Prefix-filtered traversal (e.g., only under ['A', *, 'C'])
const nodes = clf.descendants(['A', undefined, 'C']);
console.log(nodes.toArray());

entries() → {Each.<Array.<Array.<*>, *>>}

Returns an iterable of [keys, item] pairs, similar to Map.prototype.entries().

  • keys is the full key-path from the root to the node.
  • item is one element stored in that node's class.

Only nodes with positive weight (nin > 0) are included.

Source:
Returns:

An Each iterable yielding [keys, item] pairs.

Type
Each.<Array.<Array.<*>, *>>
Example
for (const [keys, value] of clf.entries()) {
    console.log(keys, value);
}

get(query, firstopt) → {Each.<*>}

Retrieves all items stored in nodes whose key-path matches the given prefix.

  • Each node along the tree whose path matches query contributes its .class items.
  • undefined in query is treated as a wildcard (matches any key at that level).
  • Returns a flattened Each<*> of all matching items.

Conceptually, this works like Map.get(key) but supports prefix matching: all items under nodes that match the query are included.

Parameters:
Name Type Attributes Default Description
query Array.<*>

Prefix of keys to match.
first boolean <optional>
 true

If false, traversal order is reversed.
Source:
Returns:

An iterable of all items stored in nodes matching the query.

Type
Each.<*>
Example
// Store items under sequences
clf.add(['a','b'], 'item1');
clf.add(['a','c'], 'item2');

// Get items under 'a' prefix
const items = clf.get(['a']);
console.log([...items]); // ['item1', 'item2']

getChild(key, creatingopt) → {Classifier|undefined}

Returns the child associated with key. If creating is true and the child does not exist, it is created.

Parameters:
Name Type Attributes Default Description
key *

Child key.
creating boolean <optional>
 false

Whether to create the child if missing.
Source:
Returns:
  • The child node, or undefined.
Type
Classifier | undefined

has(keys) → {boolean}

Returns true iff the sequence exists and ends at a terminating node.

Parameters:
Name Type Description
keys Iterable.<*> | *

(or key)
Source:
Returns:
Type
boolean

increment(valueopt) → {void}

Adjusts occurrence counters along this node's ancestor chain.

  • nin is incremented only on this node.
  • nout is incremented on all ancestor nodes.
Parameters:
Name Type Attributes Default Description
value number <optional>
 1

Amount to increment (or decrement).
Source:
Returns:
Type
void

keys() → {Each.<Array.<*>>}

Returns an iterable over all key-paths in the classifier.

A “key-path” is an array of keys describing the path from the root to a node containing at least one stored item.

Source:
Returns:

An Each iterable yielding arrays of keys.

Type
Each.<Array.<*>>
Example
for (const keys of clf.keys()) {
    console.log(keys);
}

n() → {number}

Returns the number of item occurrences stored in this node's subtree.

Source:
Returns:

Total occurrences .nin + .nout.

Type
number

path() → {Path.<Classifier>}

Returns the path from the root node to this node.

Source:
Returns:

Absolute path containing all nodes from the root (excluded) to this node (included).

Type
Path.<Classifier>

peek(firstopt) → {*|undefined}

Returns the first or last stored item in this subtree.

  • first = true → returns the first item in traversal order
  • first = false → returns the last item
Parameters:
Name Type Attributes Default Description
first boolean <optional>
 true

Whether to retrieve the first (true) or last (false) item.
Overrides:
Source:
Returns:

The first/last item, or undefined if the tree is empty.

Type
* | undefined

poll(firstopt) → {any}

Extracts (removes and returns) the first item of this Queue.

Parameters:
Name Type Attributes Default Description
first boolean <optional>
 true

If false, extracts the last item instead.
Overrides:
Source:
Returns:

The extracted item.

Type
any

pruneIfEmpty() → {void}

Removes empty nodes from the tree, traversing bottom-up.

A node is removed if both its nin and nout are zero. The process continues up the parent chain until reaching a non-empty node or the root.

Source:
Returns:
Type
void

remove(keys, xTimesopt) → {boolean}

Removes occurrences of a stored sequence identified by keys.

  • Decrements .nin of the terminal node by up to xTimes.
  • Updates .nout counters along ancestor nodes.
  • Prunes nodes that become empty.
Parameters:
Name Type Attributes Default Description
keys Iterable.<*> | *

Sequence of keys (or key) representing the stored path.
xTimes number <optional>
 Infinity

Maximum number of occurrences to remove.
Source:
Returns:

true if any sequences were removed, false if the path did not exist.

Type
boolean

reverse() → {Each.<*>}

Returns all items contained in this Classifier in reverse order.

This is equivalent to calling get([], false), i.e., retrieving all items from the tree in reverse traversal order.

Overrides:
Source:
Returns:

Iterable of all stored items, reversed.

Type
Each.<*>

select(n, firstopt) → {Array.<any>}

Selects and keeps the first n items of the queue, removing all other items.

Parameters:
Name Type Attributes Default Description
n number

Number of items to keep in the queue
first boolean <optional>
 true

If true, selects items from the start; if false, from the end.
Overrides:
Source:
Returns:

An array containing the discarded items removed from the queue.

Type
Array.<any>

values() → {Each.<*>}

Returns an iterable over all items stored anywhere in this classifier subtree.

Items are drawn from the equivalence class stored at each node.

Source:
Returns:

An Each iterable yielding all stored items.

Type
Each.<*>
Example
for (const value of clf.values()) {
    console.log(value);
}

with(keys, creatingopt) → {Classifier|undefined}

Descends through a sequence of keys and returns the final node.

Parameters:
Name Type Attributes Default Description
keys Iterable.<*> | *

Sequence of keys (or single key) to follow.
creating boolean <optional>
 false

Whether to create missing nodes.
Source:
Returns:
  • The descendant node, or undefined.
Type
Classifier | undefined