Low-level implementation of the size-bounded tree #
This file contains the basic definition implementing the functionality of the size-bounded trees.
Returns the tree l ++ ⟨k, v⟩ ++ r
, with the smallest element chopped off.
Equations
Instances For
Returns the tree l ++ ⟨k, v⟩ ++ r
, with the largest element chopped off.
Equations
Instances For
Modification operations #
An empty tree.
Equations
Instances For
Slower version of containsThenInsert
which can be used in the absence of balance
information but still assumes the preconditions of containsThenInsert
, otherwise might panic.
Equations
Instances For
Adds a new mapping to the tree, leaving the tree unchanged if the key is already present.
Equations
Instances For
Slower version of insertIfNew
which can be used in the absence of balance
information but still assumes the preconditions of insertIfNew
, otherwise might panic.
Equations
Instances For
Returns the pair (t.contains k, t.insertIfNew k v)
.
Equations
Instances For
Slower version of containsThenInsertIfNew
which can be used in the absence of balance
information but still assumes the preconditions of containsThenInsertIfNew
, otherwise might panic.
Equations
Instances For
Slower version of getThenInsertIfNew?
which can be used in the absence of balance
information but still assumes the preconditions of getThenInsertIfNew?
, otherwise might panic.
Equations
Instances For
Slower version of eraseMany
which can be used in absence of balance information but still
assumes the preconditions of eraseMany
, otherwise might panic.
Equations
Instances For
Slower version of insertMany
which can be used in absence of balance information but still
assumes the preconditions of insertMany
, otherwise might panic.
Equations
Instances For
Slower version of insertMany
which can be used in absence of balance information but still
assumes the preconditions of insertMany
, otherwise might panic.
Equations
Instances For
Slower version of insertManyIfNewUnit
which can be used in absence of balance information but still
assumes the preconditions of insertManyIfNewUnit
, otherwise might panic.
Equations
Instances For
Transforms an element of SizedBalancedTree
into a BalancedTree
.
Equations
Instances For
Slower version of getThenInsertIfNew?
which can be used in the absence of balance
information but still assumes the preconditions of getThenInsertIfNew?
, otherwise might panic.
Equations
Instances For
Returns the tree consisting of the mappings (k, (f k v).get)
where (k, v)
was a mapping in
the original tree and (f k v).isSome
.
Equations
Instances For
Slower version of filterMap
which can be used in the absence of balance
information but still assumes the preconditions of filterMap
, otherwise might panic.
Equations
Instances For
Monadic version of map
.
Equations
Instances For
Returns the tree consisting of the mapping (k, v)
where (k, v)
was a mapping in the
original tree and f k v = true
.
Equations
Instances For
Slower version of filter
which can be used in the absence of balance
information but still assumes the preconditions of filter
, otherwise might panic.
Equations
Instances For
Changes the mapping of the key k
by applying the function f
to the current mapped value
(if any). This function can be used to insert a new mapping, modify an existing one or delete it.
This version of the function requires LawfulEqOrd α
. There is an alternative non-dependent version
called Const.alter
.
Equations
Instances For
Slower version of modify
which can be used in the absence of balance
information but still assumes the preconditions of modify
, otherwise might panic.
Equations
Instances For
Internal implementation detail of the tree map
Equations
Instances For
Returns a map that contains all mappings of t₁
and t₂
. In case that both maps contain the
same key k
with respect to cmp
, the provided function is used to determine the new value from
the respective values in t₁
and t₂
.
Equations
Instances For
Returns a map that contains all mappings of t₁
and t₂
. In case that both maps contain the
same key k
with respect to cmp
, the provided function is used to determine the new value from
the respective values in t₁
and t₂
.
Equations
Instances For
Changes the mapping of the key k
by applying the function f
to the current mapped value
(if any). This function can be used to insert a new mapping, modify an existing one or delete it.
This version of the function requires LawfulEqOrd α
. There is an alternative non-dependent version
called Const.alter
.
Equations
Instances For
Slower version of modify
which can be used in the absence of balance
information but still assumes the preconditions of modify
, otherwise might panic.
Equations
Instances For
Returns a map that contains all mappings of t₁
and t₂
. In case that both maps contain the
same key k
with respect to cmp
, the provided function is used to determine the new value from
the respective values in t₁
and t₂
.
Equations
Instances For
Returns a map that contains all mappings of t₁
and t₂
. In case that both maps contain the
same key k
with respect to cmp
, the provided function is used to determine the new value from
the respective values in t₁
and t₂
.