Portability | portable |
---|---|

Stability | experimental |

Maintainer | mihailbogojeski@gmail.com |

Safe Haskell | Safe-Inferred |

The implementation of the basic GiST operations. The behaviour of the operations is largely influenced by the predicate used, allowing the GiST to behave like a different type of balanced search tree for a different predicate. Although the operations are influenced by the predicate, it is always ensured that the tree stays balanced after an insertion or deletion, regardless of the predicate used. It is also recommended that the minimum and maximum fill factor for the tree are constant throughout the whole program to ensure optimal behaviour

- data GiST p a
- data Entry p a
- class (Eq a, Eq (p a)) => Predicates p a where
- type LeafEntry p a = (a, p a)
- type NodeEntry p a = (GiST p a, p a)
- type Penalty = Int
- entryPredicate :: Entry p a -> p a
- search :: Predicates p a => p a -> GiST p a -> [a]
- insert :: Predicates p a => LeafEntry p a -> (Int, Int) -> GiST p a -> GiST p a
- delete :: Predicates p a => LeafEntry p a -> (Int, Int) -> GiST p a -> GiST p a
- empty :: GiST p a
- save :: (Show a, Show (p a)) => GiST p a -> FilePath -> IO ()
- load :: (Read a, Read (p a)) => FilePath -> IO (GiST p a)
- getData :: GiST p a -> [a]
- size :: GiST p a -> Int

## Types

The data structure used for building the GiST

A general entry type for the gist

class (Eq a, Eq (p a)) => Predicates p a whereSource

The predicate class that can be instanced by the user to create new types of balanced search trees

consistent :: p a -> Entry p a -> BoolSource

Checks if the given entry is consistent with a given predicate

Returns a predicate that is the union of all predicates of the given list of entries

penalty :: p a -> p a -> PenaltySource

Calculates a numerical penalty for inserting the entry containing the first predicate into a subtree rooted at an entry containing the second predicate

pickSplit :: [Entry p a] -> ([Entry p a], [Entry p a])Source

Given a list of entries, returns two disjunct subsets that contain the entries in the list. Focus is on minimising the overlap between the splitted entries' predicates

Predicates Predicate Int | More documentation on the instance implementation in the source |

Predicates Predicate (Int, Int) | More documentation on the instance implementation in the source |

entryPredicate :: Entry p a -> p aSource

Returns the predicate of this entry

## GiST operations

search :: Predicates p a => p a -> GiST p a -> [a]Source

Searches the GiST for leaf nodes that satisfy the given search predicate

insert :: Predicates p a => LeafEntry p a -> (Int, Int) -> GiST p a -> GiST p aSource

Inserts an entry into the tree, rebalancing the tree if necessary. Rebalancing is done to satisfy the minimum and maximum fill factor of the tree (represented as an integer tuple)