-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A Haskell implementation of a Generalized Search Tree (GiST)
--   
--   A simple implementation of the GiST data structure, including a couple
--   of basic predicates used for implementing a GiST based B+ or R-tree.
--   The GiST is also capable und working with any user defined instance of
--   the class Predicates, making this package perfect for developing and
--   testing new types of balanced trees.
@package GiST
@version 0.0.1


-- | 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
module Data.GiST.GiST

-- | The data structure used for building the GiST
data GiST p a

-- | A general entry type for the gist
data Entry p a
LeafEntry :: (LeafEntry p a) -> Entry p a
NodeEntry :: (NodeEntry p a) -> Entry p a

-- | The predicate class that can be instanced by the user to create new
--   types of balanced search trees
class (Eq a, Eq (p a)) => Predicates p a
consistent :: Predicates p a => p a -> Entry p a -> Bool
union :: Predicates p a => [p a] -> p a
penalty :: Predicates p a => p a -> p a -> Penalty
pickSplit :: Predicates p a => [Entry p a] -> ([Entry p a], [Entry p a])

-- | A leaf entry has a predicate and data
type LeafEntry p a = (a, p a)

-- | A node entry has a predicate and a subtree
type NodeEntry p a = (GiST p a, p a)
type Penalty = Int

-- | Returns the predicate of this entry
entryPredicate :: Entry p a -> p a

-- | Searches the GiST for leaf nodes that satisfy the given search
--   predicate
search :: Predicates p a => p a -> GiST p a -> [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)
insert :: 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)
delete :: Predicates p a => LeafEntry p a -> (Int, Int) -> GiST p a -> GiST p a

-- | Create a new empty GiST
empty :: GiST p a

-- | Saves the GiST to file
save :: (Show a, Show (p a)) => GiST p a -> FilePath -> IO ()

-- | Loads a GiST from file
load :: (Read a, Read (p a)) => FilePath -> IO (GiST p a)

-- | Returns all the data stored in a GiST
getData :: GiST p a -> [a]

-- | Return the number of values in a GiST
size :: GiST p a -> Int


-- | A simple implementation of the B+ tree predicate. A containment
--   predicate is a tuple of two integers representing an open interval,
--   while the equality predicate is simply an interger value.
module Data.GiST.BTree
data Predicate a

-- | containment predicate (interval)
Contains :: (a, a) -> Predicate a

-- | equality predicate (integer value)
Equals :: a -> Predicate a

-- | Tests if a value is between two others
between :: Ord a => a -> a -> a -> Bool
instance Eq a => Eq (Predicate a)
instance Ord a => Ord (Predicate a)
instance Show a => Show (Predicate a)
instance Read a => Read (Predicate a)
instance Predicates Predicate Int


-- | A simple implementation of the R-Tree predicate. A containment
--   predicate is a tuple of two points representing a rectangle with the
--   first tuple (minx,maxy) being the upper left corner of the rectangle
--   and the second (maxx,miny) being the lower right corner of the
--   rectangle, while the equality predicate is simply a 2D point (tuple of
--   two integers).
module Data.GiST.RTree
data Predicate a

-- | containment predicate (rectangle)
Contains :: (a, a) -> Predicate a

-- | equality predicate (2D point)
Equals :: a -> Predicate a
instance Eq a => Eq (Predicate a)
instance Ord a => Ord (Predicate a)
instance Show a => Show (Predicate a)
instance Read a => Read (Predicate a)
instance Predicates Predicate (Int, Int)