RedBlackTree

enum RedBlackTree[k: Type, v: Type]Source

case Leafcase DoubleBlackLeafcase Node(Color, RedBlackTree[k, v], k, v, RedBlackTree[k, v])

An immutable red-black tree implementation with keys of type k and values of type v.

A red-black tree is a self-balancing binary search tree. Each node is either red or black, although a transitory color double-black is allowed during deletion. The red-black tree satisfy the following invariants.

For all nodes with key x, the left subtree contains only nodes with keys y < x and the right subtree contains only nodes with keys z > x.
No red node has a red parent.
Every path from the root to a leaf contains the same number of black nodes.

Instances

instance Eq[RedBlackTree[k, v]] with Eq[k], Eq[v]Source

instance Filterable[RedBlackTree[k]] with Order[k]Source

instance Foldable[RedBlackTree[k]]Source

instance ForEach[RedBlackTree[k, v]]Source

instance Functor[RedBlackTree[k]]Source

instance Iterable[RedBlackTree[k, v]]Source

instance Traversable[RedBlackTree[k]]Source

instance UnorderedFoldable[RedBlackTree[k]]Source

instance Witherable[RedBlackTree[k]] with Order[k]Source

Definitions

def blackHeight(t: RedBlackTree[k, v]): Int32 Source

Returns the black height of t.

def empty(): RedBlackTree[k, v] Source

Returns the empty tree.

def exists(f: k -> (v -> Bool \ ef), t: RedBlackTree[k, v]): Bool \ ef Source

Returns true if and only if at least one key-value pair in t satisfies the predicate f.

Returns false if t is the empty tree.

def filter(f: v -> Bool \ ef, t: RedBlackTree[k, v]): RedBlackTree[k, v] \ ef with Order[k] Source

Returns a new copy of tree t with just the nodes that satisfy the predicate f.

def filterMap(f: a -> Option[b] \ ef, t: RedBlackTree[k, a]): RedBlackTree[k, b] \ ef with Order[k] Source

Collects the results of applying the partial function f to every element in t. This traverses tree t and produces a new tree with just nodes where applying f produces Some(_).

def findLeft(f: k -> (v -> Bool \ ef), t: RedBlackTree[k, v]): Option[(k, v)] \ ef Source

Optionally returns the first key-value pair in t that satisfies the predicate f when searching from left to right.

def findRight(f: k -> (v -> Bool \ ef), t: RedBlackTree[k, v]): Option[(k, v)] \ ef Source

Optionally returns the first key-value pair in t that satisfies the predicate f when searching from right to left.

def foldLeft(f: b -> (k -> (v -> b \ ef)), s: b, t: RedBlackTree[k, v]): b \ ef Source

Applies f to a start value s and all key-value pairs in t going from left to right.

That is, the result is of the form: f(...f(f(s, k1, v1), k2, v2)..., vn).

def foldMap(f: k -> (v -> b \ ef), t: RedBlackTree[k, v]): b \ ef with Monoid[b] Source

Returns the result of mapping each key-value pair and combining the results.

def foldRight(f: k -> (v -> (b -> b \ ef)), s: b, t: RedBlackTree[k, v]): b \ ef Source

Applies f to a start value s and all key-value pairs in tree going from right to left.

That is, the result is of the form: f(k1, v1, ...f(kn-1, vn-1, f(kn, vn, s))).

def forAll(f: k -> (v -> Bool \ ef), t: RedBlackTree[k, v]): Bool \ ef Source

Returns true if and only if all key-value pairs in t satisfy the predicate f.

Returns true if t is the empty tree.

def forEach(f: k -> (v -> Unit \ ef), t: RedBlackTree[k, v]): Unit \ ef Source

Applies f to every key-value pair of t.

def forEachWithIndex(f: Int32 -> (k -> (v -> Unit \ ef)), t: RedBlackTree[k, v]): Unit \ ef Source

Applies f to every key-value pair of t along with that element's index.

def get(k: k, t: RedBlackTree[k, v]): Option[v] with Order[k] Source

Returns Some(v) if k => v is in t.

Otherwise returns None.

def insert(k: k, v: v, t: RedBlackTree[k, v]): RedBlackTree[k, v] with Order[k] Source

Updates t with k => v if k => v1 is in t.

Otherwise, updates t with k => v.

def insertWith(f: k -> (v -> (v -> v \ ef)), k: k, v: v, t: RedBlackTree[k, v]): RedBlackTree[k, v] \ ef with Order[k] Source

Updates t with k => f(k, v, v1) if k => v1 is in t.

Otherwise, updates t with k => v.

def isEmpty(t: RedBlackTree[k, v]): Bool Source

Returns true if and only if t is the empty tree.

def iterator(rc: Region[r], t: RedBlackTree[k, v]): Iterator[(k, v), r, r] \ r Source

Returns an iterator over t.

def joinKeys(sep: String, t: RedBlackTree[k, v]): String with ToString[k] Source

Returns the concatenation of the string representation of each key k in t with sep inserted between each element.

def joinValues(sep: String, t: RedBlackTree[k, v]): String with ToString[v] Source

Returns the concatenation of the string representation of each value v in t with sep inserted between each element.

def joinWith(f: k -> (v -> String \ ef), sep: String, t: RedBlackTree[k, v]): String \ ef Source

Returns the concatenation of the string representation of each key-value pair k => v in t according to f with sep inserted between each element.

def mapAWithKey(f: k -> (v1 -> m[v2] \ ef), t: RedBlackTree[k, v1]): m[RedBlackTree[k, v2]] \ ef with Applicative[m] Source

Returns a RedBlackTree with mappings k => f(v) for every k => v in t.

@ParallelWhenPure

def mapWithKey(f: k -> (v1 -> v2 \ ef), t: RedBlackTree[k, v1]): RedBlackTree[k, v2] \ ef Source

Returns a RedBlackTree with mappings k => f(k, v) for every k => v in t.

Purity reflective: Runs in parallel when given a pure function f.

def maximumKey(t: RedBlackTree[k, v]): Option[(k, v)] Source

Extracts k => v where k is the rightmost (i.e. largest) key in the tree.

def memberOf(k: k, t: RedBlackTree[k, v]): Bool with Order[k] Source

Returns true if and only if t contains the key k.

def minimumKey(t: RedBlackTree[k, v]): Option[(k, v)] Source

Extracts k => v where k is the leftmost (i.e. smallest) key in the tree.

def nonEmpty(t: RedBlackTree[k, v]): Bool Source

Returns true if and only if t is a non-empty tree.

@Parallel

def parCount(f: k -> (v -> Bool), t: RedBlackTree[k, v]): Int32 Source

Applies f over the tree t in parallel and returns the number of elements that satisfy the predicate f.

The implementation spawns a number of threads each applying f sequentially from left to right on some subtree that is disjoint from the rest of the threads.

@Parallel

def parExists(f: k -> (v -> Bool), t: RedBlackTree[k, v]): Bool Source

Returns true if and only if at least one key-value pair in t satisfies the predicate f.

Returns false if t is the empty tree.

The function f must be pure.

Traverses the tree t in parallel.

@Parallel

def parForAll(f: k -> (v -> Bool), t: RedBlackTree[k, v]): Bool Source

Returns true if and only if all key-value pairs in t satisfy the predicate f.

Returns true if t is the empty tree.

The function f must be pure.

Traverses the tree t in parallel.

@Parallel

def parMaximumBy(cmp: k -> (v -> (k -> (v -> Comparison))), t: RedBlackTree[k, v]): Option[(k, v)] Source

Applies cmp over the tree t in parallel and optionally returns the largest element according to cmp.

The implementation spawns a number of threads each applying cmp sequentially from left to right on some subtree that is disjoint from the rest of the threads.

@Parallel

def parMinimumBy(cmp: k -> (v -> (k -> (v -> Comparison))), t: RedBlackTree[k, v]): Option[(k, v)] Source

Applies cmp over the tree t in parallel and optionally returns the lowest element according to cmp.

The implementation spawns a number of threads each applying cmp sequentially from left to right on some subtree that is disjoint from the rest of the threads.

@Parallel

def parSumWith(f: k -> (v -> Int32), t: RedBlackTree[k, v]): Int32 Source

Returns the sum of all key-value pairs k => v in the tree t according to the function f.

The implementation spawns a number of threads each applying f sequentially from left to right on some subtree that is disjoint from the rest of the threads.

def rangeQuery(p: k -> Comparison \ ef1, f: k -> (v -> a \ ef2), t: RedBlackTree[k, v]): List[a] \ ef1 + ef2 Source

Extracts a range of key-value pairs from t.

That is, the result is a list of all pairs f(k, v) where p(k) returns Equal.

def rangeQueryWith(p: k -> Comparison \ ef1, f: k -> (v -> Unit \ ef2), t: RedBlackTree[k, v]): Unit \ ef1 + ef2 Source

Applies f to all key-value pairs from t where p(k) returns Comparison.EqualTo.

The function f must be impure.

def reduceLeft(f: k -> (v -> (k -> (v -> (k, v) \ ef))), t: RedBlackTree[k, v]): Option[(k, v)] \ ef Source

Applies f to all key-value pairs in tree going from left to right until a single pair (k, v) is obtained.

That is, the result is of the form: Some(f(...f(f(k1, v1, k2, v2), k3, v3)..., kn, vn))

Returns None if t is the empty tree.

def reduceRight(f: k -> (v -> (k -> (v -> (k, v) \ ef))), t: RedBlackTree[k, v]): Option[(k, v)] \ ef Source

Applies f to all key-value pairs in t going from right to left until a single pair (k, v) is obtained.

That is, the result is of the form: Some(f(k1, v1, ...f(kn-2, vn-2, f(kn-1, vn-1, kn, vn))...)).

Returns None if t is the empty tree.

def remove(k: k, t: RedBlackTree[k, v]): RedBlackTree[k, v] with Order[k] Source

Removes k => v from t if t contains the key k.

Otherwise, returns t.

def size(t: RedBlackTree[k, v]): Int32 Source

Returns the number of nodes in t.

def sumKeys(t: RedBlackTree[Int32, v]): Int32 Source

Returns the sum of all keys in the tree t.

def sumValues(t: RedBlackTree[k, Int32]): Int32 Source

Returns the sum of all values in the tree t.

def sumWith(f: k -> (v -> Int32 \ ef), t: RedBlackTree[k, v]): Int32 \ ef Source

Returns the sum of all key-value pairs k => v in the tree t according to the function f.

def toList(t: RedBlackTree[k, v]): List[(k, v)] Source

Returns the tree t as a list. Elements are ordered from smallest (left) to largest (right).

def updateWith(f: k -> (v -> Option[v] \ ef), k: k, t: RedBlackTree[k, v]): RedBlackTree[k, v] \ ef with Order[k] Source

Updates t with k => v1 if k => v is in t and f(k, v) = Some(v1).

Otherwise, returns t.