package: pfds

module: tree

The tree module implements a persistent red-black tree that can be used as a key-value store. This module exports a single function make for creating a new tree.

tree.make


tree.make(initial_entries = [])
      

Return a new balanced tree initialized with initial_entries, which should be an empty list, or an association list or a hashtable. Each entry in initial_entries will become a key-value entry in the new tree.

All keys in a tree must be of the same type and must implement the compare generic function.

The new balanced tree is represented as a closure that can respond to the following messages:


set(key, value)
      

Return a new tree with key mapped to value.

    
at(key, default = false)
      

Return the value mapped to key.


ref(key)
      

Return the value mapped to key.


for_each(fn)
      

Applies the function fn to each entry in the tree. Fn should take two arguments - key and value. The return value of fn is ignored.


map(fn)
      

Applies the function fn to each entry in the tree. Fn should take two arguments - key and value and return a new key-value pair. Return a new tree with all the key-values returned by fn.


remove(predic)
      

Return a new tree with all keys that does not satisfy the predicate removed. The function predic must take two arguments - key and value.


filter(predic)
      

Return a new tree with all keys that satisfy the predicate removed. The function predic must take two arguments - key and value.


delete(keys)
      

Return a new tree with all keys in the list keys removed.

    
select(keys)
      

Return a new tree with all keys not in the list keys removed.

Examples:


// initializing a tree from a hashtable:
let t = tree.make(#{1:100, 2:200, 3:300})
t[2]
// 200

// adding or updating an entry will return a new tree:
let t2 = t.set(4, 400)
t2[4]
// 400
t[4]
// false
t.at(4, 4000)
// 4000

t2 = t.map(^(k, v) k*2:v*v)
t2[6]
// 90000
t2[2]
// 10000

t2 = t.remove(^(k, _) is_odd(k))
t2[1]
// false
t2[2]
// 200

// creating a tree from an association list
t = tree.make(['name:'sam, 'age:20, 'salary:1500])
t2 = t.select(['age, 'name])
t2['salary]
false
t2['age]
20
      

Index | Packages Index