BTree

type BTree<K, V> = Types.BTree<K, V>

type Node<K, V> = Types.Node<K, V>

type Internal<K, V> = Types.Internal<K, V>

type Leaf<K, V> = Types.Leaf<K, V>

type Data<K, V> = Types.Data<K, V>

public func init<K, V>(order : ?Nat) : BTree<K, V>

Initializes an empty BTree. By default, set the BTree to have order 8, and enforce the the order be greater than 4, but lower than 512

public func clear<K, V>(tree : BTree<K, V>) : ()

Clears all entries from a BTree

public func fromArray<K, V>(
  order : Nat,
  compare : (K, K) -> O.Order,
  kvPairs : [(K, V)]
) : BTree<K, V>

Allows one to quickly create a BTree from an array of key value pairs

public func fromBuffer<K, V>(
  order : Nat,
  compare : (K, K) -> O.Order,
  kvPairs : Buffer.Buffer<(K, V)>
) : BTree<K, V>

Allows one to quickly create a BTree from an Buffer of key value pairs

The Buffer class type returned is described in the Motoko-base library here: https://github.com/dfinity/motoko-base/blob/master/src/Buffer.mo It does not persist to stable memory

public func size<K, V>(tree : BTree<K, V>) : Nat

Get the current count of key-value pairs present in the BTree

public func get<K, V>(
  tree : BTree<K, V>,
  compare : (K, K) -> O.Order,
  key : K
) : ?V

Retrieves the value corresponding to the key of BTree if it exists

public func has<K, V>(
  tree : BTree<K, V>,
  compare : (K, K) -> O.Order,
  key : K
) : Bool

Returns a boolean representing if the BTree contains the provided key or not

public func insert<K, V>(
  tree : BTree<K, V>,
  compare : (K, K) -> O.Order,
  key : K,
  value : V
) : ?V

Inserts an element into a BTree

public func substituteKey<K, V>(
  tree : BTree<K, V>,
  compare : (K, K) -> O.Order,
  oldKey : K,
  newKey : K
) : ?V

Substitutes in a new key in for the current/old key, preserving the same attributes as the previous key (if the key previously exists in the BTree). This returns the value associated with the old key if it exists, otherwise it returns null

Note: Under the hood, this is implemented as two operations: 1) delete the old key 2) insert the new key with the same value as the previously deleted old key

public func update<K, V>(
  tree : BTree<K, V>,
  compare : (K, K) -> O.Order,
  key : K,
  updateFunction : (?V) -> V
) : ?V

Applies a function to the value of an existing key of a BTree If the element does not yet exist in the BTree it creates a new key and value according to the result of passing null to the updateFunction

public func delete<K, V>(
  tree : BTree<K, V>,
  compare : (K, K) -> O.Order,
  key : K
) : ?V

Deletes an element from a BTree

public func min<K, V>(tree : BTree<K, V>) : ?(K, V)

Returns the minimum key in a BTree with its associated value. If the BTree is empty, returns null

public func max<K, V>(tree : BTree<K, V>) : ?(K, V)

Returns the maximum key in a BTree with its associated value. If the BTree is empty, returns null

public func deleteMin<K, V>(tree : BTree<K, V>, compare : (K, K) -> O.Order) : ?(K, V)

Deletes the minimum key in a BTree and returns its associated value. If the BTree is empty, returns null

public func deleteMax<K, V>(tree : BTree<K, V>, compare : (K, K) -> O.Order) : ?(K, V)

Deletes the maximum key in a BTree and returns its associated value. If the BTree is empty, returns null

public func entries<K, V>(t : BTree<K, V>) : Iter.Iter<(K, V)>

Returns an ascending order BTree iterator

public func toKeyArray<K, V>(t : BTree<K, V>) : [K]

public func toValueArray<K, V>(t : BTree<K, V>) : [V]

public func toArray<K, V>(t : BTree<K, V>) : [(K, V)]

Returns an array of all the key-value pairs in the BTree

Note: If the BTree contains more entries than the message instruction limit will allow you to process in across consensus this may trap mid-iteration

public func toBuffer<K, V>(t : BTree<K, V>) : Buffer.Buffer<(K, V)>

Returns a buffer of all the key-value pairs in the BTree.

The Buffer class type returned is described in the Motoko-base library here: https://github.com/dfinity/motoko-base/blob/master/src/Buffer.mo It does not persist to stable memory

Note: If the BTree contains more entries than the message instruction limit will allow you to process in across consensus this may trap mid-iteration

type Direction = {#fwd; #bwd}

The direction of iteration #fwd -> forward (ascending) #bwd -> backwards (descending)

type ScanLimitResult<K, V> = { results : [(K, V)]; nextKey : ?K }

The object returned from a scan contains:

• results - a key value array of all results found (within the bounds and limit provided)
• nextKey - an optional next key if there exist more results than the limit provided within the given bounds

public func scanLimit<K, V>(
  tree : BTree<K, V>,
  compare : (K, K) -> O.Order,
  lowerBound : K,
  upperBound : K,
  dir : Direction,
  limit : Nat
) : ScanLimitResult<K, V>

Performs a in-order scan of the Red-Black Tree between the provided key bounds, returning a number of matching entries in the direction specified (ascending/descending) limited by the limit parameter specified in an array formatted as (K, V) for each entry

• tree - the BTree being scanned
• compare - the comparison function used to compare (in terms of order) the provided bounds against the keys in the BTree
• lowerBound - the lower bound used in the scan
• upperBound - the upper bound used in the scan
• dir - the direction of the scan
• limit - the maximum possible number of items to scan (that are between the lower and upper bounds) before returning

public func toText<K, V>(
  t : BTree<K, V>,
  keyToText : K -> Text,
  valueToText : V -> Text
) : Text

Opinionated version of generating a textual representation of a BTree. Primarily to be used for testing and debugging

public func equals<K, V>(
  t1 : BTree<K, V>,
  t2 : BTree<K, V>,
  keyEquals : (K, K) -> Bool,
  valueEquals : (V, V) -> Bool
) : Bool

Determines if two BTrees are equivalent