| Portability | portable |
|---|---|
| Stability | experimental |
| Maintainer | mihailbogojeski@gmail.com |
| Safe Haskell | Safe-Inferred |
Data.GiST.GiST
Contents
Description
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
Methods
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
Instances
| 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)