llrbtree-0.1.0: Purely functional data structure

Data.Set.WBTree

Contents

Description

Purely functional weight balanced trees, aka trees of bounded balance.

  • J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", Proceedings of the fourth annual ACM symposium on Theory of computing, pp 137-142, 1972.
  • S. Adams, "Implementing sets efficiently in a functional language", Technical Report CSTR 92-10, University of Southampton, 1992. http://groups.csail.mit.edu/mac/users/adams/BB/
  • S. Adam, "Efficient sets: a balancing act", Journal of Functional Programming, Vol 3, Issue 4, pp 553-562.
  • Y. Hirai and K. Yamamoto, "Balancing Weight-Balanced Trees", Journal of Functional Programming. Vol 21, Issue 03, pp 287-307. http://mew.org/~kazu/proj/weight-balanced-tree/
  • M. Strake, "Adams' Trees Revisited - Correct and Efficient Implementation", TFP 2011. http://fox.ucw.cz/papers/bbtree/

Synopsis

Data structures

data WBTree a Source

Constructors

Leaf 
Node Size (WBTree a) a (WBTree a) 

Instances

Eq a => Eq (WBTree a) 
Show a => Show (WBTree a) 

type Size = IntSource

size :: WBTree a -> SizeSource

Creating sets

empty :: WBTree aSource

Empty set. 

>>> size empty
0

singleton :: a -> WBTree aSource

Singleton set. 

>>> size (singleton 'a')
1

insert :: Ord a => a -> WBTree a -> WBTree aSource

Insertion. O(log N) 

>>> insert 5 (fromList [5,3]) == fromList [3,5]
True
>>> insert 7 (fromList [5,3]) == fromList [3,5,7]
True
>>> insert 5 empty            == singleton 5
True

fromList :: Ord a => [a] -> WBTree aSource

Creating a set from a list. O(N log N) 

>>> empty == fromList []
True
>>> singleton 'a' == fromList ['a']
True
>>> fromList [5,3,5] == fromList [5,3]
True

Converting to a list

toList :: WBTree a -> [a]Source

Creating a list from a set. O(N) 

>>> toList (fromList [5,3])
[3,5]
>>> toList empty
[]

Membership

member :: Ord a => a -> WBTree a -> BoolSource

Checking if this element is a member of a set? 

>>> member 5 (fromList [5,3])
True
>>> member 1 (fromList [5,3])
False

Deleting

delete :: Ord a => a -> WBTree a -> WBTree aSource

Deleting this element from a set. O(log N) 

>>> delete 5 (fromList [5,3]) == singleton 3
True
>>> delete 7 (fromList [5,3]) == fromList [3,5]
True
>>> delete 5 empty            == empty
True

deleteMin :: WBTree a -> WBTree aSource

Deleting the minimum element. O(log N) 

>>> deleteMin (fromList [5,3,7]) == fromList [5,7]
True
>>> deleteMin empty == empty
True

deleteMax :: WBTree a -> WBTree aSource

Deleting the maximum 

>>> deleteMax (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(3,"b"), (5,"a")]
True
>>> deleteMax empty == empty
True

Checking

null :: Eq a => WBTree a -> BoolSource

See if the set is empty. 

>>> Data.Set.WBTree.null empty
True
>>> Data.Set.WBTree.null (singleton 1)
False

Set operations

union :: Ord a => WBTree a -> WBTree a -> WBTree aSource

Creating a union set from two sets. O(N + M) 

>>> union (fromList [5,3]) (fromList [5,7]) == fromList [3,5,7]
True

intersection :: Ord a => WBTree a -> WBTree a -> WBTree aSource

Creating a intersection set from sets. O(N + N) 

>>> intersection (fromList [5,3]) (fromList [5,7]) == singleton 5
True

difference :: Ord a => WBTree a -> WBTree a -> WBTree aSource

Creating a difference set from sets. O(N + N) 

>>> difference (fromList [5,3]) (fromList [5,7]) == singleton 3
True

Helper functions

join :: Ord a => WBTree a -> a -> WBTree a -> WBTree aSource

Joining two sets with an element. O(log N)

Each element of the left set must be less than the element. Each element of the right set must be greater than the element.

merge :: WBTree a -> WBTree a -> WBTree aSource

Merging two sets. O(log N)

Each element of the left set must be less than each element of the right set.

split :: Ord a => a -> WBTree a -> (WBTree a, WBTree a)Source

Splitting a set. O(log N) 

>>> split 2 (fromList [5,3]) == (empty, fromList [3,5])
True
>>> split 3 (fromList [5,3]) == (empty, singleton 5)
True
>>> split 4 (fromList [5,3]) == (singleton 3, singleton 5)
True
>>> split 5 (fromList [5,3]) == (singleton 3, empty)
True
>>> split 6 (fromList [5,3]) == (fromList [3,5], empty)
True

minimum :: WBTree a -> aSource

Finding the minimum element. O(log N) 

>>> minimum (fromList [3,5,1])
1
>>> minimum empty
*** Exception: minimum

maximum :: WBTree a -> aSource

Finding the maximum element. O(log N) 

>>> maximum (fromList [3,5,1])
5
>>> maximum empty
*** Exception: maximum

valid :: Ord a => WBTree a -> BoolSource

Checking validity of a set.