-- | Module for adding possible structures and functions modifying the structures
module AllStructures
( allStructures,
rbt,
hash,
ll,
heap) where
import Defs.Structures
import Data.List
import Data.Maybe
-- | A function that adds an extremal element cache to a data structure
extremalElemCache :: Structure -> Structure
extremalElemCache (DS name ops) = DS (name ++ " with extreme element caching") ops' where
extVal = fromJust $ find (\dsop -> getOpName dsop == ExtremalVal) ops
delByRef = fromJust $ find (\dsop -> getOpName dsop == DeleteByRef) ops
ops' = [Op DeleteByRef (max (getComplexity extVal) (getComplexity delByRef)),
Op ExtremalVal (LinLog 0 0, N)] ++
filter (\dsop -> getOpName dsop `notElem` [ExtremalVal, DeleteByRef]) ops
-- | A function that links the elements of a data structure
linkedLeaves :: Structure -> Structure
linkedLeaves (DS name ops) = DS (name ++ " with linked leaves") ops' where
bndByRef = fromJust $ find (\dsop -> getOpName dsop == BoundByRef) ops
insVal = fromJust $ find (\dsop -> getOpName dsop == InsertVal) ops
findByVal = fromJust $ find (\dsop -> getOpName dsop == InsertVal) ops
ops' = [Op BoundByRef (LinLog 0 0, N),
Op InsertVal (max (getComplexity bndByRef) (getComplexity insVal))] ++
filter (\dsop -> getOpName dsop `notElem` [InsertVal, BoundByRef]) ops
{-
Op BoundByRef
Op DecreaseValByRef
Op DeleteByRef
Op DeleteExtremalVal
Op Difference
Op Empty
Op ExtremalVal
Op FindByVal
Op InsertVal
Op Intersection
Op Map
Op Size
Op SymDifference
Op Union
Op UpdateByRef
-}
-- | Linked list
ll :: Structure
ll = DS "Linked List" [
Op BoundByRef (LinLog 1 0, N),
Op DecreaseValByRef (LinLog 0 0, N),
Op DeleteByRef (LinLog 0 0, N),
Op DeleteExtremalVal (LinLog 1 0, N),
Op Difference (LinLog 2 0, N),
Op Empty (LinLog 0 0, N),
Op ExtremalVal (LinLog 1 0, N),
Op FindByVal (LinLog 1 0, N),
Op InsertVal (LinLog 0 0, N),
Op Intersection (LinLog 2 0, N),
Op Map (LinLog 1 0, N),
Op Size (LinLog 0 0, N),
Op SymDifference (LinLog 2 0, N),
Op Union (LinLog 0 0, N),
Op UpdateByRef (LinLog 0 0, N)
]
-- | Red Black Trees
rbt :: Structure
rbt = DS "Red-Black Trees" [
Op BoundByRef (LinLog 0 1, N),
Op DecreaseValByRef (LinLog 0 1, N),
Op DeleteByRef (LinLog 0 1, N),
Op DeleteExtremalVal (LinLog 0 1, N),
Op Difference (LinLog 1 1, N),
Op Empty (LinLog 0 0, N),
Op ExtremalVal (LinLog 1 0, N),
Op FindByVal (LinLog 0 1, N),
Op InsertVal (LinLog 0 1, N),
Op Intersection (LinLog 1 1, N),
Op Map (LinLog 1 0, N),
Op Size (LinLog 0 0, N),
Op SymDifference (LinLog 1 1, N),
Op Union (LinLog 1 1, N),
Op UpdateByRef (LinLog 0 1, N)
]
-- | Hashtable
hash :: Structure
hash = DS "Hashtable" [
Op BoundByRef (LinLog 1 0, N),
Op DecreaseValByRef (LinLog 0 0, N),
Op DeleteByRef (LinLog 0 0, N),
Op DeleteExtremalVal (LinLog 1 0, N),
Op Difference (LinLog 1 0, N),
Op Empty (LinLog 0 0, N),
Op ExtremalVal (LinLog 1 0, N),
Op InsertVal (LinLog 0 0, AE),
Op Intersection (LinLog 1 0, N),
Op Map (LinLog 1 0, N),
Op Size (LinLog 0 0, N),
Op SymDifference (LinLog 1 0, N),
Op Union (LinLog 1 0, AE),
Op UpdateByRef (LinLog 0 0, N)
]
-- | Heap
heap :: Structure
heap = DS "Heap" [
Op BoundByRef (LinLog 0 0, N),
Op DecreaseValByRef (LinLog 0 1, N),
Op DeleteByRef (LinLog 0 1, N),
Op DeleteExtremalVal (LinLog 0 1, N),
Op Difference (LinLog 1 0, N),
Op Empty (LinLog 0 0, N),
Op ExtremalVal (LinLog 0 0, N),
Op FindByVal (LinLog 1 0, N),
Op InsertVal (LinLog 0 1, N),
Op Intersection (LinLog 1 0, N),
Op Map (LinLog 1 0, N),
Op Size (LinLog 0 0, N),
Op SymDifference (LinLog 1 0, N),
Op Union (LinLog 0 0, N),
Op UpdateByRef (LinLog 0 0, N)
]
{-
binom = DS "Binomial Heap" [
Op BoundByRef
Op DeleteByRef
Op Difference
Op FindByVal (LinLog 1 0, N),
Op Intersection
Op SymDifference
Op UpdateByRef
Op InsertVal (LinLog 0 0, A),
Op DeleteExtremalVal (LinLog 0 1, N),
Op DecreaseValByRef (LinLog 0 1, N),
Op ExtremalVal (LinLog 0 0, N),
Op Map (LinLog 1 0, N),
Op Size (LinLog 0 0, N),
Op Union (LinLog 0 1, N),
Op Empty (LinLog 0 0, N)
]
fibo = DS "Fibonacci Heap" [
Op BoundByRef
Op DeleteByRef
Op Difference
Op FindByVal
Op Intersection
Op SymDifference
Op UpdateByRef
Op InsertVal (LinLog 0 0, A),
Op DeleteExtremalVal (LinLog 0 1, N),
Op DecreaseValByRef (LinLog 0 0, N),
Op ExtremalVal (LinLog 0 0, N),
Op Map (LinLog 1 0, N),
Op Size (LinLog 0 0, N),
Op Union (LinLog 0 0, A),
Op Empty (LinLog 0 0, N)
]
array = DS "Array" [
Op BoundByRef (LinLog 0 0, N),
Op DecreaseValByRef (LinLog 0 0, N),
Op DeleteByRef (LinLog 0 0, N),
Op DeleteExtremalVal (LinLog 1 0, N),
Op Difference (LinLog 2 0, N),
Op Empty (LinLog 0 0, N),
Op ExtremalVal (LinLog 0 0, N),
Op FindByVal (LinLog 1 0, N),
Op Intersection (LinLog 2 0, N),
Op Map (LinLog 1 0, N),
Op Size (LinLog 0 0, N),
Op SymDifference (LinLog 2 0, N),
Op Union (LinLog 1 0, N),
Op UpdateByRef (LinLog 0 0, N),
]
-}
-- | List of all possible structures
allStructures :: [Structure]
allStructures = [rbt, hash, heap, ll] ++
map extremalElemCache [rbt, hash, ll] ++
map linkedLeaves [rbt] --, binom, array, fibo]