Softwaredesign: Das minimale Datenmodell
| Softwaredesign: Das minimale Datenmodell |
|
|
|
1module RadixTree3
2where
3
4import Data.Maybe
5
6import Data.Map(Map)
7import qualified Data.Map as M
8
9import Data.Set(Set)
10import qualified Data.Set as S
11
12-- ------------------------------------------------------------
13--
14
15type Key = String
16type Attr = Set Int
17
18data Table = Switch (Maybe Attr) (Map Char Table)
19 deriving (Show)
20
21-- ------------------------------------------------------------
22
23emptyTable :: Table
24emptyTable = Switch Nothing M.empty
25
26-- ------------------------------------------------------------
27--
28-- 2 cases (completeness, correctness !!!)
29
30search :: String -> Table -> Maybe Attr
31
32search "" (Switch attr sw)
33 = attr
34
35search k (Switch attr sw)
36 = do
37 tab <- M.lookup (head k) sw
38 search (tail k) tab
39
40-- ------------------------------------------------------------
41--
42-- 2 cases, very fast
43
44searchPrefix :: String -> Table -> Table
45
46searchPrefix "" tab = tab
47
48searchPrefix (c:rest) (Switch attr' sw')
49 | M.member c sw' = searchPrefix rest
50 (fromJust $ M.lookup c sw')
51 | otherwise = emptyTable
52
53-- ------------------------------------------------------------
54--
55-- 3 cases (completeness, correctness !!!)
56
57insert :: String -> Attr -> Table -> Table
58
59
60insert "" a (Switch attr' tab') = Switch (merge attr') tab'
61 where
62 merge Nothing = Just a
63 merge (Just a') = Just (a' `S.union` a)
64
65insert (c:rest) a (Switch attr' sw')
66 | M.member c sw' = Switch attr' (M.adjust (insert rest a) c sw')
67 | otherwise = Switch attr' (M.insert c (insert rest a emptyTable) sw')
68
69-- ------------------------------------------------------------
70
71keys :: Table -> [String]
72
73keys (Switch attr sw) = maybe [] (const [""]) attr
74 ++
75 [ c : w | c <- M.keys sw
76 , w <- keys (fromJust $ M.lookup c sw)
77 ]
78
79-- ------------------------------------------------------------
80--
81-- invariant:
82--
83-- no subtable of a switch is empty
84--
85-- a switch is empty, if no attribute is stored in the node
86-- and the switch map does not contain any entries
87
88invTable :: Table -> Bool
89
90invTable (Switch attr sw)
91 = all invTable' (M.elems sw)
92 where
93
94 invTable' t'
95 = not (isEmptyTable t')
96 &&
97 invTable t'
98
99 isEmptyTable (Switch a' sw')
100 = isNothing a'
101 &&
102 M.null sw'
103
104-- ------------------------------------------------------------
105
106tableSpace :: Table -> Int
107tableSpace (Switch e m)
108 = 3 -- 1 (constructor) + 1 (Maybe) + 1 (Map)
109 + 2 * M.size m -- 2 per Entry (Char, Table)
110 + maybe 0 (const 1) e -- 1 for Just attr
111 + (sum . map tableSpace . M.elems) m
112
113tableSize :: Table -> (Int, Int)
114tableSize t
115 = (length ks, sum . map length $ ks)
116 where
117 ks = keys t
118
119-- ------------------------------------------------------------
|
| Letzte Änderung: 11.07.2012 | © Prof. Dr. Uwe Schmidt |
