Skip to content

API.md

Latest commit

 

History

History
628 lines (407 loc) · 13.2 KB

API.md

File metadata and controls

628 lines (407 loc) · 13.2 KB

Sawit.js API Reference

Complete API documentation for the SawitTree class.

Table of Contents

Types

Comparator<T>

type Comparator<T> = (a: T, b: T) => number;

Function that compares two values. Returns:

  • Negative number if a < b
  • Positive number if a > b
  • Zero if a === b

ForEachCallback<T>

type ForEachCallback<T> = (value: T, index: number) => void;

Predicate<T>

type Predicate<T> = (value: T) => boolean;

MapFunction<T, U>

type MapFunction<T, U> = (value: T) => U;

Constructor

new SawitTree<T>(comparator?)

Creates a new empty SawitTree.

Parameters:

  • comparator (optional): Custom comparison function

Example:

// Default comparator (works for numbers, strings)
const numTree = new SawitTree<number>();

// Custom comparator for objects
const userTree = new SawitTree<User>((a, b) => a.age - b.age);

// Descending order
const descTree = new SawitTree<number>((a, b) => b - a);

Static Factory Methods

SawitTree.from<T>(iterable, comparator?)

Creates a tree from an iterable.

Complexity: O(n log n)

const tree = SawitTree.from([5, 3, 7, 1, 9]);
const fromSet = SawitTree.from(new Set([1, 2, 3]));

SawitTree.of<T>(...values)

Creates a tree from variable arguments.

Complexity: O(n log n)

const tree = SawitTree.of(5, 3, 7, 1, 9);

Properties

size: number

Returns the number of elements. O(1)

height: number

Returns the height of the tree. O(1)

isEmpty: boolean

Returns true if the tree is empty. O(1)

Core Operations

insert(value: T): this

Inserts a value into the tree. Duplicates are ignored.

Complexity: O(log n)

Returns: this for chaining

tree.insert(5).insert(3).insert(7);

insertAll(values: Iterable<T>): this

Inserts multiple values.

Complexity: O(k log n)

tree.insertAll([1, 2, 3, 4, 5]);

delete(value: T): boolean

Removes a value from the tree.

Complexity: O(log n)

Returns: true if found and removed

const removed = tree.delete(5); // true or false

has(value: T): boolean

Checks if a value exists.

Complexity: O(log n)

if (tree.has(5)) {
    console.log('Found!');
}

contains(value: T): boolean

Alias for has().

clear(): void

Removes all elements.

Complexity: O(1)

tree.clear();
console.log(tree.isEmpty); // true

Min/Max Operations

min(): T | undefined

Returns the minimum value.

Complexity: O(log n)

max(): T | undefined

Returns the maximum value.

Complexity: O(log n)

extractMin(): T | undefined

Removes and returns the minimum value.

Complexity: O(log n)

while (!tree.isEmpty) {
    console.log(tree.extractMin()); // Processes in ascending order
}

extractMax(): T | undefined

Removes and returns the maximum value.

Complexity: O(log n)

Floor/Ceiling Operations

floor(value: T): T | undefined

Returns the largest value ≤ the given value.

Complexity: O(log n)

const tree = SawitTree.from([1, 3, 5, 7, 9]);
tree.floor(6);  // 5
tree.floor(5);  // 5
tree.floor(0);  // undefined

ceiling(value: T): T | undefined

Returns the smallest value ≥ the given value.

Complexity: O(log n)

tree.ceiling(6);  // 7
tree.ceiling(5);  // 5
tree.ceiling(10); // undefined

lower(value: T): T | undefined

Returns the largest value strictly less than the given value.

Complexity: O(log n)

tree.lower(5); // 3

higher(value: T): T | undefined

Returns the smallest value strictly greater than the given value.

Complexity: O(log n)

tree.higher(5); // 7

Order Statistics

rank(value: T): number

Returns the number of elements less than the given value.

Complexity: O(log n)

const tree = SawitTree.from([1, 3, 5, 7, 9]);
tree.rank(5); // 2 (two elements are less than 5)
tree.rank(6); // 3

select(k: number): T | undefined

Returns the element at the given rank (0-indexed).

Complexity: O(log n)

tree.select(0); // 1 (smallest)
tree.select(2); // 5
tree.select(4); // 9 (largest)

kthSmallest(k: number): T | undefined

Returns the k-th smallest element (1-indexed).

Complexity: O(log n)

tree.kthSmallest(1); // 1 (smallest)
tree.kthSmallest(3); // 5

kthLargest(k: number): T | undefined

Returns the k-th largest element (1-indexed).

Complexity: O(log n)

tree.kthLargest(1); // 9 (largest)
tree.kthLargest(3); // 5

Range Queries

range(low: T, high: T): T[]

Returns all elements in the range [low, high] (inclusive).

Complexity: O(k + log n) where k is the number of elements in range

const tree = SawitTree.from([1, 3, 5, 7, 9]);
tree.range(3, 7); // [3, 5, 7]

rangeCount(low: T, high: T): number

Returns the count of elements in the range.

Complexity: O(log n)

tree.rangeCount(3, 7); // 3

Iteration & Traversal

[Symbol.iterator](): Iterator<T>

Enables for...of loops and spread syntax.

for (const value of tree) {
    console.log(value);
}

const arr = [...tree];

inOrder(): Generator<T>

In-order traversal (left, root, right) - produces sorted output.

for (const value of tree.inOrder()) {
    console.log(value);
}

preOrder(): Generator<T>

Pre-order traversal (root, left, right). Useful for tree serialization.

postOrder(): Generator<T>

Post-order traversal (left, right, root). Useful for tree deletion.

levelOrder(): Generator<T>

Level-order (BFS) traversal. Visits nodes level by level.

// Tree:     4
//          / \
//         2   6
//        / \
//       1   3

console.log([...tree.levelOrder()]); // [4, 2, 6, 1, 3]

reverseInOrder(): Generator<T>

Reverse in-order traversal (descending order).

Functional Methods

forEach(callback: ForEachCallback<T>): void

Executes a callback for each element in sorted order.

Complexity: O(n)

tree.forEach((value, index) => {
    console.log(`${index}: ${value}`);
});

map<U>(fn: MapFunction<T, U>, comparator?): SawitTree<U>

Creates a new tree with transformed values.

Complexity: O(n log n)

const doubled = tree.map(x => x * 2);

filter(predicate: Predicate<T>): SawitTree<T>

Creates a new tree with elements that pass the test.

Complexity: O(n log n)

const evens = tree.filter(x => x % 2 === 0);

reduce<U>(fn, initialValue: U): U

Reduces the tree to a single value.

Complexity: O(n)

const sum = tree.reduce((acc, val) => acc + val, 0);

every(predicate: Predicate<T>): boolean

Tests whether all elements pass the predicate.

Complexity: O(n)

const allPositive = tree.every(x => x > 0);

some(predicate: Predicate<T>): boolean

Tests whether any element passes the predicate.

Complexity: O(n)

const hasNegative = tree.some(x => x < 0);

find(predicate: Predicate<T>): T | undefined

Finds the first element that passes the predicate.

Complexity: O(n)

const firstEven = tree.find(x => x % 2 === 0);

Set Operations

union(other: SawitTree<T>): SawitTree<T>

Returns a new tree with elements from both trees.

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

const combined = tree1.union(tree2);

intersection(other: SawitTree<T>): SawitTree<T>

Returns a new tree with elements present in both trees.

Complexity: O(n log m)

const common = tree1.intersection(tree2);

difference(other: SawitTree<T>): SawitTree<T>

Returns a new tree with elements in this tree but not in other.

Complexity: O(n log m)

const diff = tree1.difference(tree2);

symmetricDifference(other: SawitTree<T>): SawitTree<T>

Returns elements in either tree but not both.

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

isSubsetOf(other: SawitTree<T>): boolean

Checks if all elements of this tree are in other.

Complexity: O(n log m)

isSupersetOf(other: SawitTree<T>): boolean

Checks if this tree contains all elements of other.

Complexity: O(m log n)

Conversion Methods

toArray(): T[]

Converts to a sorted array.

Complexity: O(n)

const arr = tree.toArray();

toSet(): Set<T>

Converts to a Set.

Complexity: O(n)

const set = tree.toSet();

clone(): SawitTree<T>

Creates a deep copy.

Complexity: O(n log n)

const copy = tree.clone();

toString(): string

Returns a JSON representation of the tree structure.

Complexity: O(n)

console.log(tree.toString());

isValid(): boolean

Validates AVL tree properties (for debugging).

console.log(tree.isValid()); // true if balanced