Data.GiST.GiST

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

Types

data GiST p a

The data structure used for building the GiST

Instances

(Eq a, Eq (p a)) => Eq (GiST p a)

(Read a, Read (p a)) => Read (GiST p a)

(Show a, Show (p a)) => Show (GiST p a)

data Entry p a

A general entry type for the gist

Constructors

LeafEntry (LeafEntry p a)

NodeEntry (NodeEntry p a)

Instances

(Eq a, Eq (p a)) => Eq (Entry p a)

(Eq a, Ord (p a)) => Ord (Entry p a)

Comparison only based on the predicate

(Read a, Read (p a)) => Read (Entry p a)

(Show a, Show (p a)) => Show (Entry p a)

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

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 -> Bool

Checks if the given entry is consistent with a given predicate

union :: [p a] -> p a

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

penalty :: p a -> p a -> Penalty

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])

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

type LeafEntry p a = (a, p a)

A leaf entry has a predicate and data

type NodeEntry p a = (GiST p a, p a)

A node entry has a predicate and a subtree

type Penalty = Int

entryPredicate :: Entry p a -> p a

Returns the predicate of this entry

GiST operations

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

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 a

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)

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

Deletes a leaf entry from 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)

empty :: GiST p a

Create a new empty GiST

save :: (Show a, Show (p a)) => GiST p a -> FilePath -> IO ()

Saves the GiST to file

load :: (Read a, Read (p a)) => FilePath -> IO (GiST p a)

Loads a GiST from file

getData :: GiST p a -> [a]

Returns all the data stored in a GiST

size :: GiST p a -> Int

Return the number of values in a GiST