Namespaces Symbols

RedBlackTree

0.40.0

Enums

enum Color

Source
case Red()
case Black()
case DoubleBlack()

The color of a red-black tree node.

Definitions

def blackHeight [kv] ( t : RedBlackTree[k, v] ) : Int32 \ Pure

Source

Returns the black height of t.

def empty [kv] : RedBlackTree[k, v] \ Pure

Source

Returns the empty tree.

def exists [kvef] ( 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 [vefk] ( 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 [aefbk] ( 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 [kvef] ( 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 [kvef] ( 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 [bkvef] ( 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 [kvefb] ( 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 [kvbef] ( 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 foldRightWithCont [kvefb] ( f : k -> (v -> ((Unit -> b \ ef) -> b \ ef)) z : b t : RedBlackTree[k, v] ) : b \ ef

Source

Applies f to a start value z and all key-value pairs in t 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))). A foldRightWithCont allows early termination by not calling the continuation.

def forAll [kvef] ( 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 [kvef] ( f : k -> (v -> Unit \ ef) t : RedBlackTree[k, v] ) : Unit \ ef

Source

Applies f to every key-value pair of t.

def forEachWithIndex [kvef] ( 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 [kv] ( k : k t : RedBlackTree[k, v] ) : Option[v] \ Pure with Order[k]

Source

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

Otherwise returns None.

def insert [kv] ( k : k v : v t : RedBlackTree[k, v] ) : RedBlackTree[k, v] \ Pure with Order[k]

Source

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

Otherwise, updates t with k => v.

def insertWith [kvef] ( 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 [kv] ( t : RedBlackTree[k, v] ) : Bool \ Pure

Source

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

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

Source

Returns an iterator over t.

def joinKeys [kv] ( sep : String t : RedBlackTree[k, v] ) : String \ Pure 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 [kv] ( sep : String t : RedBlackTree[k, v] ) : String \ Pure 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 [kvef] ( 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 [kv1efmv2] ( 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 [kv1efv2] ( 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 [kv] ( t : RedBlackTree[k, v] ) : Option[(k, v)] \ Pure

Source

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

def memberOf [kv] ( k : k t : RedBlackTree[k, v] ) : Bool \ Pure with Order[k]

Source

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

def minimumKey [kv] ( t : RedBlackTree[k, v] ) : Option[(k, v)] \ Pure

Source

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

@Parallel

def parCount [kv] ( n : Int32 f : k -> (v -> Bool) t : RedBlackTree[k, v] ) : Int32 \ Pure

Source

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

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

@Parallel

def parExists [kv] ( n : Int32 f : k -> (v -> Bool) t : RedBlackTree[k, v] ) : Bool \ Pure

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 [kv] ( n : Int32 f : k -> (v -> Bool) t : RedBlackTree[k, v] ) : Bool \ Pure

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 [kv] ( n : Int32 cmp : k -> (v -> (k -> (v -> Comparison))) t : RedBlackTree[k, v] ) : Option[(k, v)] \ Pure

Source

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

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

@Parallel

def parMinimumBy [kv] ( n : Int32 cmp : k -> (v -> (k -> (v -> Comparison))) t : RedBlackTree[k, v] ) : Option[(k, v)] \ Pure

Source

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

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

@Parallel

def parSumWith [kv] ( n : Int32 f : k -> (v -> Int32) t : RedBlackTree[k, v] ) : Int32 \ Pure

Source

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

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

def query [kef1vef2a] ( 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 queryWith [kef1vef2] ( 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 [kvef] ( 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 [kvef] ( 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 [kv] ( k : k t : RedBlackTree[k, v] ) : RedBlackTree[k, v] \ Pure with Order[k]

Source

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

Otherwise, returns t.

def size [kv] ( t : RedBlackTree[k, v] ) : Int32 \ Pure

Source

Returns the number of nodes in t.

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

Source

Returns the sum of all keys in the tree t.

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

Source

Returns the sum of all values in the tree t.

def sumWith [kvef] ( 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 [kv] ( t : RedBlackTree[k, v] ) : List[(k, v)] \ Pure

Source

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

def toMutDeque [rkv] ( rc : Region[r] t : RedBlackTree[k, v] ) : MutDeque[(k, v), r] \ r

Source

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

def updateWith [kvef] ( 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.