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.

Instances

FixedFoldable (Tree23 (Set k))

Methods

foldMapF :: (Fixed g, Monoid m, (* ~ a) (Alg (Tree23 (Set k)))) => (a -> m) -> g (Tree23 (Set k)) -> m

FixedAlg (Tree23 (Set k))

Associated Types

type Alg (Tree23 (Set k) :: * -> *) :: *

type Alg (Tree23 (Set k))

type Alg (Tree23 (Set k)) = k

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

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

return the minimum value

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

return the minimum value

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.

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

FTransaction version of minSet.

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

FTransaction version of minSet.

• Map

data Map k v

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

Instances

FixedTraversable (Tree23 (Map k v))

Methods

traverseF :: (Fixed g, Fixed g', Applicative h, (* ~ a) (Alg (Tree23 (Map k v)))) => (a -> h b) -> g (Tree23 (Map k v)) -> h (g' (Sub (Tree23 (Map k v)) a b))

FixedFoldable (Tree23 (Map k v))

Methods

foldMapF :: (Fixed g, Monoid m, (* ~ a) (Alg (Tree23 (Map k v)))) => (a -> m) -> g (Tree23 (Map k v)) -> m

FixedFunctor (Tree23 (Map k v))

Methods

fmapF :: (Fixed g, Fixed g', (* ~ a) (Alg (Tree23 (Map k v)))) => (a -> b) -> g (Tree23 (Map k v)) -> g' (Sub (Tree23 (Map k v)) a b)

FixedSub (Tree23 (Map k v))

Associated Types

type Sub (Tree23 (Map k v) :: * -> *) v v' :: * -> *

FixedAlg (Tree23 (Map k v))

Associated Types

type Alg (Tree23 (Map k v) :: * -> *) :: *

type Alg (Tree23 (Map k v))

type Alg (Tree23 (Map k v)) = v

type Sub (Tree23 (Map k v)) v v'

type Sub (Tree23 (Map k v)) v v' = Tree23 (Map k v')

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.

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

return the minimum key and value

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

return the maximum key and value

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.

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

FTransaction version of minMap.

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

FTransaction version of minMap.

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.