llrbtree-0.1.0: Purely functional data structure

Data.Set.WBTree

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)

# Creating sets

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.