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