1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

---------------------------------------------------------------------------
--- Library with an implementation of tables as red-black trees:
---
--- A table is a finite mapping from keys to values.
--- All the operations on tables are generic, i.e., one has to provide
--- an explicit order predicate on elements.
--- Each inner node in the red-black tree contains a key-value association.
---
--- @author Johannes Koj, Michael Hanus, Bernd Brassel
--- @version December 2018
----------------------------------------------------------------------------

module Data.Table.RBTree where

import qualified Data.RedBlackTree as RBT

----------------------------------------------------------------------------
-- the main interface:

type TableRBT key a = RBT.RedBlackTree (key,a)

--- Returns an empty table, i.e., an empty red-black tree.
empty :: Eq key => (key -> key -> Bool) -> TableRBT key _
empty lt = RBT.empty (\ x y -> fst x == fst y)
                     (\ x y -> fst x == fst y)
                     (\ x y -> lt (fst x) (fst y))

--- tests whether a given table is empty
isEmpty :: TableRBT _ _ -> Bool
isEmpty = RBT.isEmpty

--- Looks up an entry in a table.
--- @param k - a key under which a value is stored
--- @param t - a table (represented as a red-black tree)
--- @return (Just v) if v is the value stored with key k,
---         otherwise Nothing is returned.
lookup :: key -> TableRBT key a -> Maybe a
lookup k = maybe Nothing (Just . snd) . RBT.lookup (k,failed)

--- Inserts or updates an element in a table.
update :: key -> a -> TableRBT key a -> TableRBT key a
update k e = RBT.update (k,e)

--- Transforms the nodes of red-black tree into a list.
toList :: TableRBT key a -> [(key,a)]
toList = RBT.toList

delete :: key -> TableRBT key a -> TableRBT key a
delete key = RBT.delete (key,failed)

-- end of TableRBT