{-# LANGUAGE MultiParamTypeClasses #-}

-- | Various structures and algorithms for trees.
module System.TPFS.Tree
  ( BTree(..),
  ) where

import           System.TPFS.Device
import           System.TPFS.Filesystem

-- | Describes functions for accessing a B-tree on a 'Filesystem'. These
-- functions are used to write portable, reusable code for properly managing
-- any B-tree.
class Ord key => BTree key value pointer where

  -- | Returns the optimal Knuth order for the given filesystem.
  btOrder :: (Num a, Device m h)
          => Filesystem m h
          -> (key, value, pointer) -- ^ This parameter is included for the sole purpose of selecting which
                                   --   instance to use. Its value should be assumed undefined.
          -> a

  -- | Retrieves a 'BNode' from storage. Might throw an exception (or use
  -- 'Maybe') in the future if the node failed verification (via a checksum or
  -- similar), but currently it does not.
  btGet :: Device m h
        => Filesystem m h
        -> pointer
        -> m (BNode key value pointer)

  -- | Places a 'BNode' into storage. Attempting to write a 'BNode' to an
  -- unallocated part of storage may result in an exception in some
  -- implementations.
  btPut :: Device m h
        => Filesystem m h
        -> pointer
        -> BNode key value pointer
        -> m ()

  -- | Allocates and returns a pointer to a space where a 'BNode' may be stored.
  btAllocate :: Device m h
             => Filesystem m h
             -> m pointer

  -- | Frees the space used by a 'BNode'.
  btFree :: Device m h
         => Filesystem m h
         -> pointer
         -> m ()

-- | Describes a node of a B-tree in memory.
data BTree key value pointer => BNode key value pointer
     = BNode { bnKeys     :: [key]      -- ^ The keys used for branching in the tree. Must be comparable ('Ord').
             , bnValues   :: [value]    -- ^ The values associated with the keys. These values are not altered or
                                        --   inspected by any portable code.
             , bnChildren :: [pointer]  -- ^ The pointers for each of the branches of the node. Must be valid
                                        --   for use with the functions defined in the 'BTree' class.