flix

0.69.2

BPlusTree

Type Aliases

Definitions

def adjust(f: v -> v \ ef, k: k, t: BPlusTree[k, v, r]): Unit \ ef + r with Order[k] Source

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

Otherwise, t is unchanged.

Thread-safe.

def adjustWithKey(f: k -> (v -> v \ ef), k: k, t: BPlusTree[k, v, r]): Unit \ ef + r with Order[k] Source

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

Otherwise, t is unchanged.

Thread-safe.

def arity(t: BPlusTree[k, v, r]): Int32 Source

Returns the arity of t.

def assertTreeInvariant(t: BPlusTree[k, v, r]): Bool \ r with Order[k] Source

Returns true if and only if t is a structurally correct tree.

Only used for internal testing.

def computeIfAbsent(f: Unit -> v \ ef, k: k, t: BPlusTree[k, v, r]): v \ ef + r with Order[k] Source

Returns v if k => v is in t. Otherwise, computes v = f(), inserts k => v and returns v. That is, f is only evaluated if k is not in t.

This operation is atomic.

Thread-safe.

@Parallel
def count(f: k -> (v -> Bool), t: BPlusTree[k, v, r]): Int32 \ r with Order[k] Source

Returns the number of mappings in t that satisfy the predicate function f.

This method unsafely removes the effect r when spawning threads.

Not thread-safe: Traverses the live leaf chain of t in parallel.

def empty(rc: Region[r]): BPlusTree[k, v, r] \ r Source

Returns a fresh empty BPlusTree tree of standard arity.

def emptyWithArity(rc: Region[r], m: Int32): BPlusTree[k, v, r] \ r Source

Returns a fresh empty BPlusTree with arity m. A node may have at most m children and m - 1 keys. The arity must be at least 3.

def emptyWithArityAndSearch(rc: Region[r], m: Int32, search: Search): BPlusTree[k, v, r] \ r Source

Returns a fresh empty BPlusTree with arity m. A node may have at most m children and m - 1 keys. The arity must be at least 3.

search decides the comparison order for the stored vectors.

def emptyWithSearch(rc: Region[r], search: Search): BPlusTree[k, v, r] \ r Source

Returns a fresh empty BPlusTree of standard arity.

search decided the comparison order for the stored vectors.

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

Returns true if and only if there exists k => v in t such that f(k, v) == true.

Not thread-safe: Traverses the live leaf chain of t.

def find(f: k -> (v -> Bool \ ef), t: BPlusTree[k, v, r]): Option[(k, v)] \ ef + r Source

Alias for findLeft.

Not thread-safe: Traverses the live leaf chain of t.

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

Optionally returns the first mapping in t satisfying the function f.

Not thread-safe: Traverses the live leaf chain of t.

def foldLeft(f: b -> (v -> b \ ef), i: b, t: BPlusTree[k, v, r]): b \ ef + r with Order[k] Source

Applies f to a start value i and all values in t going from left to right.

Not thread-safe: Traverses the live leaf chain of t.

def foldLeftWithKey(f: b -> (k -> (v -> b \ ef)), i: b, t: BPlusTree[k, v, r]): b \ ef + r with Order[k] Source

Applies f to a start value i and all mappings k => v in t going from left to right.

Not thread-safe: Traverses the live leaf chain of t.

def foldWithKey(f: b -> (k -> (v -> b \ ef)), i: b, t: BPlusTree[k, v, r]): b \ r + ef with Order[k] Source

Alias for foldLeftWithKey

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

Returns true if and only if for all k => v in t, f(k, v) == true.

Not thread-safe: Traverses the live leaf chain of t.

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

Applies f to all mappings k => v in t.

Not thread-safe: Traverses the live leaf chain of t.

def get(k: k, t: BPlusTree[k, v, r]): Option[v] \ r with Order[k] Source

Returns Some(v) if k => v is in t. Otherwise, returns None.

Thread-safe.

def getKeyAndValue(k: k, t: BPlusTree[k, v, r]): Option[(k, v)] \ r with Order[k] Source

Returns Some((k, v)) if k => v is in t. Otherwise, returns None.

Thread-safe.

def getOrElsePut(k: k, d: v, t: BPlusTree[k, v, r]): v \ r with Order[k] Source

Returns v if k => v is in t.

Otherwise updates t with a new mapping k => d and returns d.

Atomic and thread-safe

def getWithDefault(k: k, d: v, t: BPlusTree[k, v, r]): v \ r with Order[k] Source

Returns v if k => v is in t. Otherwise, returns d.

Thread-safe.

def isEmpty(t: BPlusTree[k, v, r]): Bool \ r Source

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

Thread-safe.

def isProperSubmapOf(t1: BPlusTree[k, v, r1], t2: BPlusTree[k, v, r2]): Bool \ r1 + r2 with Order[k], Eq[v] Source

Returns true if t1 is a proper submap of t2, i.e. t1 is a submap of t2 and there exists a key in t2 that is not in t1.

Not thread-safe: Traverses the live leaf chains of t1 and t2.

def isSubmapOf(t1: BPlusTree[k, v, r1], t2: BPlusTree[k, v, r2]): Bool \ r1 + r2 with Order[k], Eq[v] Source

Returns true if t1 is a submap of t2, i.e. for every key in t1, t2 contains the same key with the same value.

Not thread-safe: Traverses the live leaf chains of t1 and t2.

def iterator(rc1: Region[r1], t: BPlusTree[k, v, r]): Iterator[(k, v), r + r1, r1] \ r + r1 Source

Returns an iterator over all key-value pairs in t,

Not thread-safe: The iterator reads from the live leaf chain of t.

def iteratorValues(rc1: Region[r1], t: BPlusTree[k, v, r2]): Iterator[v, r1 + r2, r1] \ r1 + r2 Source

Returns an iterator over values in t.

Not thread-safe: The iterator reads from the live leaf chain of t.

def iteratorWithKeys(rc1: Region[r1], t: BPlusTree[k, v, r2]): Iterator[k, r1 + r2, r1] \ r1 + r2 Source

Returns an iterator over keys in t.

Not thread-safe: The iterator reads from the live leaf chain of t.

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

Returns a string containing all keys in t, in key order, with each key formatted by its ToString instance and separated by sep.

Not thread-safe.

Builds the result by traversing the live leaf chain of t.

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

Returns a string containing all values in t, in key order, with each value formatted by its ToString instance and separated by sep.

Not thread-safe: Builds the result by traversing the live leaf chain of t.

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

Applies f to each key-value pair in t, in key order, to obtain a string and returns all results joined together using sep.

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def keysOf(t: BPlusTree[k, v, r]): Set[k] \ r with Order[k] Source

Returns the set of keys in t.

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def map(rc1: Region[r1], f: v1 -> v2 \ ef, t: BPlusTree[k, v1, r]): BPlusTree[k, v2, r1] \ ef + r + r1 with Order[k] Source

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

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def mapWithKey(rc1: Region[r1], f: k -> (v1 -> v2 \ ef), t: BPlusTree[k, v1, r]): BPlusTree[k, v2, r1] \ ef + r + r1 with Order[k] Source

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

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def maximumKey(t: BPlusTree[k, v, r]): Option[(k, v)] \ r with Order[k] Source

Optionally returns k => v where k is the largest key in t according to the Order instance on k.

Returns None if t is empty.

Thread-safe.

def memberOf(k: k, t: BPlusTree[k, v, r]): Bool \ r with Order[k] Source

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

Thread-safe.

def memberOfPair(k: k, v: v, t: BPlusTree[k, v, r]): Bool \ r with Order[k], Eq[v] Source

Returns true if and only if t contains the mapping k => v.

Thread-safe.

def merge(src: BPlusTree[k, v, r1], dst: BPlusTree[k, v, r2]): Unit \ r1 + r2 with Order[k] Source

Merge src into dst, modifying dst in a left-biased manner.

That is, key collisions are resolved by taking the mapping from src.

Not thread-safe: Traverses the live leaf chain of src.

def mergeWith(f: v -> (v -> v \ ef), src: BPlusTree[k, v, r1], dst: BPlusTree[k, v, r2]): Unit \ r1 + r2 + ef with Order[k] Source

Merges src into dst, modifying dst. If k => v1 is in src and k => v2 is in dst, updates dst with k => f(v1, v2).

Not thread-safe: Traverses the live leaf chain of src.

def mergeWithKey(f: k -> (v -> (v -> v \ ef)), src: BPlusTree[k, v, r1], dst: BPlusTree[k, v, r2]): Unit \ r1 + r2 + ef with Order[k] Source

Merges src into dst, modifying dst in-place. If k => v1 is in src and k => v2 is in dst, then dst is updated with k => f(k, v1, v2).

Not thread-safe: Traverses the live leaf chain of src.

def minimumKey(t: BPlusTree[k, v, r]): Option[(k, v)] \ r with Order[k] Source

Optionally returns k => v where k is the smallest key in t according to the Order instance on k.

Returns None if t is empty.

Thread-safe.

def nonEmpty(t: BPlusTree[k, v, r]): Bool \ r Source

Returns true if and only if t contains at least one mapping.

Thread-safe.

@Parallel
def parForEach(f: k -> (v -> Unit \ r), t: BPlusTree[k, v, r]): Unit \ r Source

Applies f to all mappings k => v in t in parallel. f must not modify t.

This method unsafe removes the r effect when spawning threads.

Not thread-safe: Traverses the live leaf chain of t in parallel.

@Parallel
def parForEachWhen(f1: k -> (v -> Unit \ r), f2: k -> (v -> Unit \ r), parLimit: Int32, t: BPlusTree[k, v, r]): Unit \ r Source

Applies f1 to all mappings k => v in t sequentially if t contains strictly less than parLimit elements. If t contains parLimit or more elements f2 is applied in parallel to all mappings.

f1 and f2 must not modify t.

This method unsafe removes the r effect when spawning threads in case 2.

Not thread-safe: Traverses the live leaf chain of t, potentially in parallel.

def put(k: k, v: v, t: BPlusTree[k, v, r]): Unit \ r with Order[k] Source

Updates the tree t with the mapping k => v, replacing any existing mapping.

Thread-safe.

def putIf(decider: k -> (v -> (k -> (v -> Bool))), k: k, v: v, t: BPlusTree[k, v, r]): Unit \ r with Order[k] Source

Updates the tree t with the mapping k => v, replacing any existing mapping, k2 => v2, if decider(k, v, k2, v2) == true.

Thread-safe and atomic.

def putWith(f: v -> (v -> v \ ef), k: k, v: v, t: BPlusTree[k, v, r]): Unit \ ef + r with Order[k] Source

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

Otherwise, updates t with k => v.

Thread-safe.

def putWithKey(f: k -> (v -> (v -> v \ ef)), k: k, v: v, t: BPlusTree[k, v, r]): Unit \ r + ef with Order[k] Source

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

Otherwise, updates t with the mapping k => v.

Thread-safe.

def rangeQuery(min: k, max: k, t: BPlusTree[k, v, r]): List[(k, v)] \ r with Order[k] Source

Returns the list of mappings k => v in t where min <= k <= max according to the Order instance on k.

Not thread-safe: Builds the result by traversing the live leaf chain of t in range order.

def rangeQueryWith(f: k -> (v -> Unit \ ef), min: k, max: k, t: BPlusTree[k, v, r]): Unit \ r + ef with Order[k] Source

Applies f in ascending order to all mappings k => v in t where min <= k <= max.

Not thread-safe: Traverses the live leaf chain of t in range order.

def rc(t: BPlusTree[k, v, r]): Region[r] Source

Returns the region of t.

def sameElements(t1: BPlusTree[k, v, r1], t2: BPlusTree[k, v, r2]): Bool \ r1 + r2 with Order[k], Eq[v] Source

Returns true if t1 and t2 contain the same keys and values, regardless of each individual tree's internal structure.

Not thread-safe: Compares the live leaf chains of t1 and t2.

def size(t: BPlusTree[k, v, r]): Int32 \ r Source

Returns the size of t. This operation is O(1).

Not atomic.

Thread-safe.

def toList(t: BPlusTree[k, v, r]): List[(k, v)] \ r Source

Returns a list of the key-value pairs in t. Elements are ordered from smallest (left) to largest (right).

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def toMap(t: BPlusTree[k, v, r]): Map[k, v] \ r with Order[k] Source

Returns t as an immutable map.

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def toSet(t: BPlusTree[k, v, r]): Set[(k, v)] \ r with Order[k], Order[v] Source

Returns t as a set of key-value pairs.

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def toString(t: BPlusTree[k, v, r]): String \ r with ToString[k], ToString[v] Source

Returns a string representation of t.

Not thread-safe: Traverses the live tree without synchronization.

def toVector(t: BPlusTree[k, v, r]): Vector[(k, v)] \ r Source

Returns t as a vector of key-value pairs.

Not thread-safe: Builds the result by traversing the live leaf chain of t.

def transform(f: v -> v \ ef, t: BPlusTree[k, v, r]): Unit \ r + ef with Order[k] Source

Applies the function f to every value in t.

Not thread-safe: Mutates the live leaf chain of t in place.

def transformWithKey(f: k -> (v -> v \ ef), t: BPlusTree[k, v, r]): Unit \ r + ef with Order[k] Source

Applies the function f to every mapping k => v in t, replacing it with k => f(k, v).

Not thread-safe: Mutates the live leaf chain of t in place.

def valuesOf(t: BPlusTree[k, v, r]): List[v] \ r with Order[k] Source

Returns the list of values in t.

Not thread-safe: Builds the result by traversing the live leaf chain of t.