author | wenzelm |
Wed, 29 Mar 2023 12:05:56 +0200 | |
changeset 77741 | 1951f6470792 |
parent 77740 | 19c539f5d4d3 |
child 77742 | 676713cba24d |
permissions | -rw-r--r-- |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
1 |
(* Title: Pure/General/set.ML |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
2 |
Author: Makarius |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
3 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
4 |
Efficient representation of sets (see also Pure/General/table.ML). |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
5 |
*) |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
6 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
7 |
signature SET = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
8 |
sig |
77731 | 9 |
structure Key: KEY |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
10 |
type elem |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
11 |
type T |
77725 | 12 |
val size: T -> int |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
13 |
val empty: T |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
14 |
val build: (T -> T) -> T |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
15 |
val is_empty: T -> bool |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
16 |
val fold: (elem -> 'a -> 'a) -> T -> 'a -> 'a |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
17 |
val fold_rev: (elem -> 'a -> 'a) -> T -> 'a -> 'a |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
18 |
val dest: T -> elem list |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
19 |
val exists: (elem -> bool) -> T -> bool |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
20 |
val forall: (elem -> bool) -> T -> bool |
77728 | 21 |
val get_first: (elem -> 'a option) -> T -> 'a option |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
22 |
val member: T -> elem -> bool |
77728 | 23 |
val subset: T * T -> bool |
24 |
val ord: T ord |
|
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
25 |
val insert: elem -> T -> T |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
26 |
val make: elem list -> T |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
27 |
val merge: T * T -> T |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
28 |
val remove: elem -> T -> T |
77728 | 29 |
val subtract: T -> T -> T |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
30 |
end; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
31 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
32 |
functor Set(Key: KEY): SET = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
33 |
struct |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
34 |
|
77733 | 35 |
(* keys *) |
36 |
||
77731 | 37 |
structure Key = Key; |
38 |
type elem = Key.key; |
|
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
39 |
|
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
40 |
val eq_key = is_equal o Key.ord; |
77731 | 41 |
|
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
42 |
|
77731 | 43 |
(* datatype *) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
44 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
45 |
datatype T = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
46 |
Empty | |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
47 |
Leaf1 of elem | |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
48 |
Leaf2 of elem * elem | |
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
49 |
Leaf3 of elem * elem * elem | |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
50 |
Branch2 of T * elem * T | |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
51 |
Branch3 of T * elem * T * elem * T; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
52 |
|
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
53 |
(*literal copy from table.ML*) |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
54 |
fun make2 (Empty, e, Empty) = Leaf1 e |
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
55 |
| make2 (Branch2 (Empty, e1, Empty), e2, right) = make2 (Leaf1 e1, e2, right) |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
56 |
| make2 (left, e1, Branch2 (Empty, e2, Empty)) = make2 (left, e1, Leaf1 e2) |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
57 |
| make2 (Branch3 (Empty, e1, Empty, e2, Empty), e3, right) = make2 (Leaf2 (e1, e2), e3, right) |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
58 |
| make2 (left, e1, Branch3 (Empty, e2, Empty, e3, Empty)) = make2 (left, e1, Leaf2 (e2, e3)) |
77739 | 59 |
| make2 (Leaf1 e1, e2, Empty) = Leaf2 (e1, e2) |
60 |
| make2 (Empty, e1, Leaf1 e2) = Leaf2 (e1, e2) |
|
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
61 |
| make2 (Leaf1 e1, e2, Leaf1 e3) = Leaf3 (e1, e2, e3) |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
62 |
| make2 (Leaf2 (e1, e2), e3, Empty) = Leaf3 (e1, e2, e3) |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
63 |
| make2 (Empty, e1, Leaf2 (e2, e3)) = Leaf3 (e1, e2, e3) |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
64 |
| make2 arg = Branch2 arg; |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
65 |
|
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
66 |
(*literal copy from table.ML*) |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
67 |
fun make3 (Empty, e1, Empty, e2, Empty) = Leaf2 (e1, e2) |
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
68 |
| make3 (Branch2 (Empty, e1, Empty), e2, mid, e3, right) = make3 (Leaf1 e1, e2, mid, e3, right) |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
69 |
| make3 (left, e1, Branch2 (Empty, e2, Empty), e3, right) = make3 (left, e1, Leaf1 e2, e3, right) |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
70 |
| make3 (left, e1, mid, e2, Branch2 (Empty, e3, Empty)) = make3 (left, e1, mid, e2, Leaf1 e3) |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
71 |
| make3 (Leaf1 e1, e2, Empty, e3, Empty) = Leaf3 (e1, e2, e3) |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
72 |
| make3 (Empty, e1, Leaf1 e2, e3, Empty) = Leaf3 (e1, e2, e3) |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
73 |
| make3 (Empty, e1, Empty, e2, Leaf1 e3) = Leaf3 (e1, e2, e3) |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
74 |
| make3 arg = Branch3 arg; |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
75 |
|
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
76 |
(*literal copy from table.ML*) |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
77 |
fun unmake (Leaf1 e) = Branch2 (Empty, e, Empty) |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
78 |
| unmake (Leaf2 (e1, e2)) = Branch3 (Empty, e1, Empty, e2, Empty) |
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
79 |
| unmake (Leaf3 (e1, e2, e3)) = |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
80 |
Branch2 (Branch2 (Empty, e1, Empty), e2, Branch2 (Empty, e3, Empty)) |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
81 |
| unmake arg = arg; |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
82 |
|
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
83 |
|
77725 | 84 |
(* size *) |
85 |
||
86 |
local |
|
87 |
fun add_size Empty n = n |
|
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
88 |
| add_size (Leaf1 _) n = n + 1 |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
89 |
| add_size (Leaf2 _) n = n + 2 |
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
90 |
| add_size (Leaf3 _) n = n + 3 |
77725 | 91 |
| add_size (Branch2 (left, _, right)) n = |
92 |
n + 1 |> add_size left |> add_size right |
|
93 |
| add_size (Branch3 (left, _, mid, _, right)) n = |
|
94 |
n + 2 |> add_size left |> add_size mid |> add_size right; |
|
95 |
in |
|
96 |
fun size set = add_size set 0; |
|
97 |
end; |
|
98 |
||
99 |
||
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
100 |
(* empty and single *) |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
101 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
102 |
val empty = Empty; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
103 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
104 |
fun build (f: T -> T) = f empty; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
105 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
106 |
fun is_empty Empty = true |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
107 |
| is_empty _ = false; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
108 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
109 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
110 |
(* fold combinators *) |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
111 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
112 |
fun fold_set f = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
113 |
let |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
114 |
fun fold Empty x = x |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
115 |
| fold (Leaf1 e) x = f e x |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
116 |
| fold (Leaf2 (e1, e2)) x = f e2 (f e1 x) |
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
117 |
| fold (Leaf3 (e1, e2, e3)) x = f e3 (f e2 (f e1 x)) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
118 |
| fold (Branch2 (left, e, right)) x = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
119 |
fold right (f e (fold left x)) |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
120 |
| fold (Branch3 (left, e1, mid, e2, right)) x = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
121 |
fold right (f e2 (fold mid (f e1 (fold left x)))); |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
122 |
in fold end; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
123 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
124 |
fun fold_rev_set f = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
125 |
let |
77732 | 126 |
fun fold_rev Empty x = x |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
127 |
| fold_rev (Leaf1 e) x = f e x |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
128 |
| fold_rev (Leaf2 (e1, e2)) x = f e1 (f e2 x) |
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
129 |
| fold_rev (Leaf3 (e1, e2, e3)) x = f e1 (f e2 (f e3 x)) |
77732 | 130 |
| fold_rev (Branch2 (left, e, right)) x = |
131 |
fold_rev left (f e (fold_rev right x)) |
|
132 |
| fold_rev (Branch3 (left, e1, mid, e2, right)) x = |
|
133 |
fold_rev left (f e1 (fold_rev mid (f e2 (fold_rev right x)))); |
|
134 |
in fold_rev end; |
|
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
135 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
136 |
fun dest tab = fold_rev_set cons tab []; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
137 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
138 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
139 |
(* exists and forall *) |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
140 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
141 |
fun exists pred = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
142 |
let |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
143 |
fun ex Empty = false |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
144 |
| ex (Leaf1 e) = pred e |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
145 |
| ex (Leaf2 (e1, e2)) = pred e1 orelse pred e2 |
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
146 |
| ex (Leaf3 (e1, e2, e3)) = pred e1 orelse pred e2 orelse pred e3 |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
147 |
| ex (Branch2 (left, e, right)) = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
148 |
ex left orelse pred e orelse ex right |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
149 |
| ex (Branch3 (left, e1, mid, e2, right)) = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
150 |
ex left orelse pred e1 orelse ex mid orelse pred e2 orelse ex right; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
151 |
in ex end; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
152 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
153 |
fun forall pred = not o exists (not o pred); |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
154 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
155 |
|
77728 | 156 |
(* get_first *) |
157 |
||
158 |
fun get_first f = |
|
159 |
let |
|
160 |
fun get Empty = NONE |
|
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
161 |
| get (Leaf1 e) = f e |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
162 |
| get (Leaf2 (e1, e2)) = |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
163 |
(case f e1 of |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
164 |
NONE => f e2 |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
165 |
| some => some) |
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
166 |
| get (Leaf3 (e1, e2, e3)) = |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
167 |
(case f e1 of |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
168 |
NONE => |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
169 |
(case f e2 of |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
170 |
NONE => f e3 |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
171 |
| some => some) |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
172 |
| some => some) |
77728 | 173 |
| get (Branch2 (left, e, right)) = |
174 |
(case get left of |
|
175 |
NONE => |
|
176 |
(case f e of |
|
177 |
NONE => get right |
|
178 |
| some => some) |
|
179 |
| some => some) |
|
180 |
| get (Branch3 (left, e1, mid, e2, right)) = |
|
181 |
(case get left of |
|
182 |
NONE => |
|
183 |
(case f e1 of |
|
184 |
NONE => |
|
185 |
(case get mid of |
|
186 |
NONE => |
|
187 |
(case f e2 of |
|
188 |
NONE => get right |
|
189 |
| some => some) |
|
190 |
| some => some) |
|
191 |
| some => some) |
|
192 |
| some => some); |
|
193 |
in get end; |
|
194 |
||
195 |
||
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
196 |
(* member *) |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
197 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
198 |
fun member set elem = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
199 |
let |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
200 |
fun mem Empty = false |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
201 |
| mem (Leaf1 e) = eq_key (elem, e) |
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
202 |
| mem (Leaf2 (e1, e2)) = |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
203 |
(case Key.ord (elem, e1) of |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
204 |
LESS => false |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
205 |
| EQUAL => true |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
206 |
| GREATER => eq_key (elem, e2)) |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
207 |
| mem (Leaf3 (e1, e2, e3)) = |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
208 |
(case Key.ord (elem, e2) of |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
209 |
LESS => eq_key (elem, e1) |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
210 |
| EQUAL => true |
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
211 |
| GREATER => eq_key (elem, e3)) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
212 |
| mem (Branch2 (left, e, right)) = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
213 |
(case Key.ord (elem, e) of |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
214 |
LESS => mem left |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
215 |
| EQUAL => true |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
216 |
| GREATER => mem right) |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
217 |
| mem (Branch3 (left, e1, mid, e2, right)) = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
218 |
(case Key.ord (elem, e1) of |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
219 |
LESS => mem left |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
220 |
| EQUAL => true |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
221 |
| GREATER => |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
222 |
(case Key.ord (elem, e2) of |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
223 |
LESS => mem mid |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
224 |
| EQUAL => true |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
225 |
| GREATER => mem right)); |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
226 |
in mem set end; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
227 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
228 |
|
77728 | 229 |
(* subset and order *) |
230 |
||
231 |
fun subset (set1, set2) = forall (member set2) set1; |
|
232 |
||
233 |
val ord = |
|
234 |
pointer_eq_ord (fn sets => |
|
235 |
(case int_ord (apply2 size sets) of |
|
236 |
EQUAL => |
|
237 |
if subset sets then EQUAL |
|
238 |
else dict_ord Key.ord (apply2 dest sets) |
|
239 |
| ord => ord)); |
|
240 |
||
241 |
||
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
242 |
(* insert *) |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
243 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
244 |
datatype growth = Stay of T | Sprout of T * elem * T; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
245 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
246 |
fun insert elem set = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
247 |
if member set elem then set |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
248 |
else |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
249 |
let |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
250 |
fun ins Empty = Sprout (Empty, elem, Empty) |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
251 |
| ins (t as Leaf1 _) = ins (unmake t) |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
252 |
| ins (t as Leaf2 _) = ins (unmake t) |
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
253 |
| ins (t as Leaf3 _) = ins (unmake t) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
254 |
| ins (Branch2 (left, e, right)) = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
255 |
(case Key.ord (elem, e) of |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
256 |
LESS => |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
257 |
(case ins left of |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
258 |
Stay left' => Stay (make2 (left', e, right)) |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
259 |
| Sprout (left1, e', left2) => Stay (make3 (left1, e', left2, e, right))) |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
260 |
| EQUAL => Stay (make2 (left, e, right)) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
261 |
| GREATER => |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
262 |
(case ins right of |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
263 |
Stay right' => Stay (make2 (left, e, right')) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
264 |
| Sprout (right1, e', right2) => |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
265 |
Stay (make3 (left, e, right1, e', right2)))) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
266 |
| ins (Branch3 (left, e1, mid, e2, right)) = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
267 |
(case Key.ord (elem, e1) of |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
268 |
LESS => |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
269 |
(case ins left of |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
270 |
Stay left' => Stay (make3 (left', e1, mid, e2, right)) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
271 |
| Sprout (left1, e', left2) => |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
272 |
Sprout (make2 (left1, e', left2), e1, make2 (mid, e2, right))) |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
273 |
| EQUAL => Stay (make3 (left, e1, mid, e2, right)) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
274 |
| GREATER => |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
275 |
(case Key.ord (elem, e2) of |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
276 |
LESS => |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
277 |
(case ins mid of |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
278 |
Stay mid' => Stay (make3 (left, e1, mid', e2, right)) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
279 |
| Sprout (mid1, e', mid2) => |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
280 |
Sprout (make2 (left, e1, mid1), e', make2 (mid2, e2, right))) |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
281 |
| EQUAL => Stay (make3 (left, e1, mid, e2, right)) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
282 |
| GREATER => |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
283 |
(case ins right of |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
284 |
Stay right' => Stay (make3 (left, e1, mid, e2, right')) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
285 |
| Sprout (right1, e', right2) => |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
286 |
Sprout (make2 (left, e1, mid), e2, make2 (right1, e', right2))))); |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
287 |
in |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
288 |
(case ins set of |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
289 |
Stay set' => set' |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
290 |
| Sprout br => make2 br) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
291 |
end; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
292 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
293 |
fun make elems = build (fold insert elems); |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
294 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
295 |
fun merge (set1, set2) = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
296 |
if pointer_eq (set1, set2) then set1 |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
297 |
else if is_empty set1 then set2 |
77725 | 298 |
else if is_empty set2 then set1 |
299 |
else if size set1 >= size set2 |
|
300 |
then fold_set insert set2 set1 |
|
301 |
else fold_set insert set1 set2; |
|
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
302 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
303 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
304 |
(* remove *) |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
305 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
306 |
local |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
307 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
308 |
fun compare NONE _ = LESS |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
309 |
| compare (SOME e1) e2 = Key.ord (e1, e2); |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
310 |
|
77737 | 311 |
fun if_equal ord x y = if is_equal ord then x else y; |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
312 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
313 |
exception UNDEF of elem; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
314 |
|
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
315 |
(*literal copy from table.ML*) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
316 |
fun del (SOME k) Empty = raise UNDEF k |
77735 | 317 |
| del NONE Empty = raise Match |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
318 |
| del NONE (Leaf1 p) = (p, (true, Empty)) |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
319 |
| del NONE (Leaf2 (p, q)) = (p, (false, Leaf1 q)) |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
320 |
| del k (Leaf1 p) = |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
321 |
(case compare k p of |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
322 |
EQUAL => (p, (true, Empty)) |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
323 |
| _ => raise UNDEF (the k)) |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
324 |
| del k (Leaf2 (p, q)) = |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
325 |
(case compare k p of |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
326 |
EQUAL => (p, (false, Leaf1 q)) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
327 |
| _ => |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
328 |
(case compare k q of |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
329 |
EQUAL => (q, (false, Leaf1 p)) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
330 |
| _ => raise UNDEF (the k))) |
77740
19c539f5d4d3
more compact data: approx. 0.85 .. 1.10 of plain list size;
wenzelm
parents:
77739
diff
changeset
|
331 |
| del k (Leaf3 (p, q, r)) = del k (Branch2 (Leaf1 p, q, Leaf1 r)) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
332 |
| del k (Branch2 (l, p, r)) = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
333 |
(case compare k p of |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
334 |
LESS => |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
335 |
(case del k l of |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
336 |
(p', (false, l')) => (p', (false, make2 (l', p, r))) |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
337 |
| (p', (true, l')) => (p', case unmake r of |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
338 |
Branch2 (rl, rp, rr) => |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
339 |
(true, make3 (l', p, rl, rp, rr)) |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
340 |
| Branch3 (rl, rp, rm, rq, rr) => (false, make2 |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
341 |
(make2 (l', p, rl), rp, make2 (rm, rq, rr))))) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
342 |
| ord => |
77737 | 343 |
(case del (if_equal ord NONE k) r of |
344 |
(p', (false, r')) => (p', (false, make2 (l, if_equal ord p' p, r'))) |
|
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
345 |
| (p', (true, r')) => (p', case unmake l of |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
346 |
Branch2 (ll, lp, lr) => |
77737 | 347 |
(true, make3 (ll, lp, lr, if_equal ord p' p, r')) |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
348 |
| Branch3 (ll, lp, lm, lq, lr) => (false, make2 |
77737 | 349 |
(make2 (ll, lp, lm), lq, make2 (lr, if_equal ord p' p, r')))))) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
350 |
| del k (Branch3 (l, p, m, q, r)) = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
351 |
(case compare k q of |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
352 |
LESS => |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
353 |
(case compare k p of |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
354 |
LESS => |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
355 |
(case del k l of |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
356 |
(p', (false, l')) => (p', (false, make3 (l', p, m, q, r))) |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
357 |
| (p', (true, l')) => (p', (false, case (unmake m, unmake r) of |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
358 |
(Branch2 (ml, mp, mr), Branch2 _) => |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
359 |
make2 (make3 (l', p, ml, mp, mr), q, r) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
360 |
| (Branch3 (ml, mp, mm, mq, mr), _) => |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
361 |
make3 (make2 (l', p, ml), mp, make2 (mm, mq, mr), q, r) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
362 |
| (Branch2 (ml, mp, mr), Branch3 (rl, rp, rm, rq, rr)) => |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
363 |
make3 (make2 (l', p, ml), mp, make2 (mr, q, rl), rp, |
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
364 |
make2 (rm, rq, rr))))) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
365 |
| ord => |
77737 | 366 |
(case del (if_equal ord NONE k) m of |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
367 |
(p', (false, m')) => |
77737 | 368 |
(p', (false, make3 (l, if_equal ord p' p, m', q, r))) |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
369 |
| (p', (true, m')) => (p', (false, case (unmake l, unmake r) of |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
370 |
(Branch2 (ll, lp, lr), Branch2 _) => |
77737 | 371 |
make2 (make3 (ll, lp, lr, if_equal ord p' p, m'), q, r) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
372 |
| (Branch3 (ll, lp, lm, lq, lr), _) => |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
373 |
make3 (make2 (ll, lp, lm), lq, |
77737 | 374 |
make2 (lr, if_equal ord p' p, m'), q, r) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
375 |
| (_, Branch3 (rl, rp, rm, rq, rr)) => |
77737 | 376 |
make3 (l, if_equal ord p' p, make2 (m', q, rl), rp, |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
377 |
make2 (rm, rq, rr)))))) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
378 |
| ord => |
77737 | 379 |
(case del (if_equal ord NONE k) r of |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
380 |
(q', (false, r')) => |
77737 | 381 |
(q', (false, make3 (l, p, m, if_equal ord q' q, r'))) |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
382 |
| (q', (true, r')) => (q', (false, case (unmake l, unmake m) of |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
383 |
(Branch2 _, Branch2 (ml, mp, mr)) => |
77737 | 384 |
make2 (l, p, make3 (ml, mp, mr, if_equal ord q' q, r')) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
385 |
| (_, Branch3 (ml, mp, mm, mq, mr)) => |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
386 |
make3 (l, p, make2 (ml, mp, mm), mq, |
77737 | 387 |
make2 (mr, if_equal ord q' q, r')) |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
388 |
| (Branch3 (ll, lp, lm, lq, lr), Branch2 (ml, mp, mr)) => |
77736
570f1436fe0a
more compact representation of leaf nodes: only 1.10 .. 1.33 larger than plain list;
wenzelm
parents:
77735
diff
changeset
|
389 |
make3 (make2 (ll, lp, lm), lq, make2 (lr, p, ml), mp, |
77737 | 390 |
make2 (mr, if_equal ord q' q, r')))))); |
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
391 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
392 |
in |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
393 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
394 |
fun remove elem set = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
395 |
if member set elem then snd (snd (del (SOME elem) set)) else set; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
396 |
|
77728 | 397 |
val subtract = fold_set remove; |
398 |
||
77722
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
399 |
end; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
400 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
401 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
402 |
(* ML pretty-printing *) |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
403 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
404 |
val _ = |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
405 |
ML_system_pp (fn depth => fn _ => fn set => |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
406 |
ML_Pretty.to_polyml |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
407 |
(ML_Pretty.enum "," "{" "}" (ML_Pretty.from_polyml o ML_system_pretty) (dest set, depth))); |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
408 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
409 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
410 |
(*final declarations of this structure!*) |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
411 |
val fold = fold_set; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
412 |
val fold_rev = fold_rev_set; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
413 |
|
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
414 |
end; |
8faf28a80a7f
efficient representation of sets: more compact than Table.set;
wenzelm
parents:
diff
changeset
|
415 |
|
77731 | 416 |
structure Intset = Set(Inttab.Key); |
417 |
structure Symset = Set(Symtab.Key); |