Data.Map.TernaryMap

Documentation

data Elem2 a b

Elem2 a b is used to hold elements of a list after insertion, and indicate that we've reached the end of the list.

Constructors

C !a

Val b

Instances

Eq a => Eq (Elem2 a b)

Ord a => Ord (Elem2 a b)

All elements are greater than the Val Elem, otherwise they are ordered according to their own ord instance (for the `compare (C x) (C y)` case).

(Show a, Show b) => Show (Elem2 a b)

(Binary a, Binary b) => Binary (Elem2 a b)

data TernaryMap a b

TernaryMap a b is ternary tree. It is commonly used for storing word lists like dictionaries.

Constructors

TNode !(Elem2 a b) !(TernaryMap a b) !(TernaryMap a b) !(TernaryMap a b)

TEnd

Instances

Eq a => Eq (TernaryMap a b)

(Show a, Show b) => Show (TernaryMap a b)

(Binary a, Binary b) => Binary (TernaryMap a b)

This binary instance saves some space by making special cases of some commonly encountered structures in the trees.

insert' :: Ord a => [a] -> b -> TernaryMap a b

Quickly build a tree without an initial tree. This should be used to create an initial tree, using insert there after.

insert :: Ord a => [a] -> b -> TernaryMap a b -> TernaryMap a b

Inserts an entries into a tree. Values with the same key will be replaced with the newer version.

isKey :: Ord a => [a] -> TernaryMap a b -> Bool

Returns true if the `[a]` is a key in the TernaryMap.

getVal :: Ord a => [a] -> TernaryMap a b -> Maybe b

treeSize :: TernaryMap a b -> Int

Returns the number of non-Val Elems

numEntries :: TernaryMap a b -> Int

Counts how many entries there are in the tree.

fromList :: Ord a => [([a], b)] -> TernaryMap a b

Creates a new tree from a list of strings