Data.FixFile.Tree23

This is an implementation of a Two-Three Tree data structure that can be used with FixFile. It has two interfaces that are

Documentation

type Tree23 d = Tree23F (TreeKey d) (TreeValue d)

Fixed (Tree23 d) represents a Two-Three tree. The data type d should have data families for it's key and value. These data families are not exported from the module. As a result, the only valid types for d are (Set k) as defined here or (Map k v), also defined here.

empty :: Fixed g => g (Tree23 d)

An empty Fixed Tree23.

null :: Fixed g => g (Tree23 d) -> Bool

Predicate that returns true if there are no items in the Tree23.

size :: Fixed g => g (Tree23 d) -> Int

Number of entries in (Tree23 g d).

depth :: Fixed g => g (Tree23 d) -> Int

The depth of (Tree23 g d). 0 represents en empty Tree.

• Set

data Set k

A Set of k represented as a Two-Three Tree.

createSetFile :: (Binary k, Typeable k, f ~ Tree23 (Set k)) => FilePath -> IO (FixFile (Ref f))

Create a FixFile for storing a set of items.

openSetFile :: (Binary k, Typeable k, f ~ Tree23 (Set k)) => FilePath -> IO (FixFile (Ref f))

Open a FixFile for storing a set of items.

insertSet :: (Fixed g, Ord k, f ~ Tree23 (Set k)) => k -> g f -> g f

Insert an item into a set.

lookupSet :: (Fixed g, Ord k, f ~ Tree23 (Set k)) => k -> g f -> Bool

Lookup an item in a set.

deleteSet :: (Fixed g, Ord k, f ~ Tree23 (Set k)) => k -> g f -> g f

Delete an item from a set.

partitionSet :: (Fixed g, Ord k, f ~ Tree23 (Set k)) => k -> g f -> (g f, g f)

Split a set into sets of items and= k

toListSet :: (Fixed g, Ord k, f ~ Tree23 (Set k)) => g f -> [k]

Convert a set into a list of items.

fromListSet :: (Fixed g, Ord k, f ~ Tree23 (Set k)) => [k] -> g f

Convert a list of items into a set.

insertSetT :: (Binary k, Ord k, f ~ Tree23 (Set k)) => k -> Transaction (Ref f) s ()

Transaction version of insertSet.

lookupSetT :: (Binary k, Ord k, f ~ Tree23 (Set k)) => k -> Transaction (Ref f) s Bool

FTransaction version of lookupSet.

deleteSetT :: (Binary k, Ord k, f ~ Tree23 (Set k)) => k -> Transaction (Ref f) s ()

FTransaction version of deleteSet.

partitionSetT :: (Binary k, Ord k, f ~ Tree23 (Set k)) => k -> Transaction (Ref f) s (Stored s f, Stored s f)

Transaction version of partitionSet.

• Map

data Map k v

A Map of keys k to values v represented as a Two-Three Tree.

createMapFile :: (Binary k, Typeable k, Binary v, Typeable v, f ~ Tree23 (Map k v)) => FilePath -> IO (FixFile (Ref f))

Create a FixFile of a Map.

openMapFile :: (Binary k, Typeable k, Binary v, Typeable v, f ~ Tree23 (Map k v)) => FilePath -> IO (FixFile (Ref f))

Open a FixFile of a Map.

insertMap :: (Fixed g, Ord k, f ~ Tree23 (Map k v)) => k -> v -> g f -> g f

Insert value v into a map for key k. Any existing value is replaced.

lookupMap :: (Fixed g, Ord k, f ~ Tree23 (Map k v)) => k -> g f -> Maybe v

Lookup an item in a map corresponding to key k.

deleteMap :: (Fixed g, Ord k, f ~ Tree23 (Map k v)) => k -> g f -> g f

Delete an item from a map at key k.

partitionMap :: (Fixed g, Ord k, f ~ Tree23 (Map k v)) => k -> g f -> (g f, g f)

Split a set into maps for keys and= k

alterMap :: (Fixed g, Ord k, f ~ Tree23 (Map k v)) => k -> (Maybe v -> Maybe v) -> g f -> g f

Apply a function to alter a Map at key k. The function takes (Maybe v) as an argument for any possible exiting value and returns Nothing to delete a value or Just v to set a new value.

mapMap :: (Fixed g, Fixed h, Ord k) => (a -> b) -> g (Tree23 (Map k a)) -> h (Tree23 (Map k b))

Map a function over a map. Because of the way Tree23 is implemented, it is not possible to create a Functor instance to achieve this.

toListMap :: (Fixed g, Ord k, f ~ Tree23 (Map k v)) => g f -> [(k, v)]

Convert a map into a list of key-value tuples.

fromListMap :: (Fixed g, Ord k, f ~ Tree23 (Map k v)) => [(k, v)] -> g f

Convert a lst of key-value tuples into a map.

insertMapT :: (Binary k, Binary v, Ord k, f ~ Tree23 (Map k v)) => k -> v -> Transaction (Ref f) s ()

Transaction version of insertMap.

lookupMapT :: (Binary k, Binary v, Ord k, f ~ Tree23 (Map k v)) => k -> Transaction (Ref f) s (Maybe v)

Transaction version of lookupMap.

deleteMapT :: (Binary k, Binary v, Ord k, f ~ Tree23 (Map k v)) => k -> Transaction (Ref f) s ()

Transaction version of deleteMap.

partitionMapT :: (Binary k, Ord k, Binary v, f ~ Tree23 (Map k v)) => k -> Transaction (Ref f) s (Stored s f, Stored s f)

Transaction version of partitionMap.

alterMapT :: (Binary k, Binary v, Ord k, f ~ Tree23 (Map k v)) => k -> (Maybe v -> Maybe v) -> Transaction (Ref f) s ()

FTransaction version of alterMap.

keysMap :: (Fixed g, Ord k, f ~ Tree23 (Map k v)) => g f -> [k]

Return the list of keys in a map.

valuesMap :: (Fixed g, Ord k, f ~ Tree23 (Map k v)) => g f -> [v]

Return a list of values in a map.

partitionTree23 :: (Fixed g, Ord (TreeKey d)) => TreeKey d -> g (Tree23 d) -> (g (Tree23 d), g (Tree23 d))