喜欢 0
派生 0

最后活跃于 6 months ago

capitalex's Avatar capitalex 修订了这个 Gist 6 months ago. 转到此修订

1 file changed, 28 insertions, 29 deletions

queue.ml

@@ -17,33 +17,32 @@ functor HoodMelvilleQueue () : QUEUE =
17 17 struct
18 18
19 19 datatype 'a Queue =
20 - Simple of
21 - {front : 'a list,
22 - rear : 'a list,
23 - diff : int} (* diff = length front - length rear *)
20 + Simple of
21 + { front : 'a list,
22 + rear : 'a list,
23 + diff : int} (* diff = length front - length rear *)
24 24
25 25 | Copy1 of (* in process of reversing f and r *)
26 - { oldfront : 'a list,
27 - rear : 'a list,
28 - f : 'a list,
26 + { oldfront : 'a list,
27 + rear : 'a list,
28 + f : 'a list,
29 29 r : 'a list,
30 30 frev : 'a list,
31 31 rrev : 'a list, (* the partial new front *)
32 - diff : int, (* diff = length rrev - length rear *)
33 - copy : int} (* copy = # of valid elements in frev *)
32 + diff : int, (* diff = length rrev - length rear *)
33 + copy : int} (* copy = # of valid elements in frev *)
34 34
35 35 | Copy2 of (* in process of reversing frev onto newfront *)
36 - { oldfront : 'a list,
37 - rear : 'a list,
36 + { oldfront : 'a list,
37 + rear : 'a list,
38 38 frev : 'a list,
39 39 newfront : 'a list,
40 - diff : int, (* diff = length newfront - length rear *)
41 - copy : int} (* copy = # of valid elements in frev *)
42 -
40 + diff : int, (* diff = length newfront - length rear *)
41 + copy : int} (* copy = # of valid elements in frev *)
43 42
44 43 (* begin process of moving elements from rear to front *)
45 44 fun rotate (front,rear) = (* length rear = length front + 1 *)
46 - Copy1 { oldfront = front
45 + Copy1 { oldfront = front
47 46 , rear = []
48 47 , f = front
49 48 , r = rear
@@ -54,7 +53,7 @@ struct
54 53
55 54 (* do one step in process of moving elements from rear to front *)
56 55 fun tick (Copy1 {oldfront, rear, f=x::f, r=y::r, frev, rrev, diff, copy}) =
57 - Copy1 { oldfront = oldfront
56 + Copy1 { oldfront = oldfront
58 57 , rear = rear
59 58 , f = f
60 59 , r = r
@@ -63,24 +62,24 @@ struct
63 62 , diff = diff + 1
64 63 , copy = copy + 1 }
65 64 | tick (Copy1 {oldfront, rear, f=[], r=[y], frev, rrev, diff, copy}) =
66 - Copy2 { oldfront = oldfront
65 + Copy2 { oldfront = oldfront
67 66 , rear = rear
68 67 , frev = frev
69 68 , newfront = y::rrev
70 69 , diff = diff + 1
71 70 , copy = copy }
72 71 | tick (Copy2 {oldfront, rear, newfront, diff, copy = 0, frev}) =
73 - Simple { front = newfront
72 + Simple { front = newfront
74 73 , rear = rear
75 74 , diff = diff
76 75 }
77 76 | tick (Copy2 {oldfront, rear, newfront, diff, copy = 1, frev = x::_}) =
78 - Simple { front = x::newfront
77 + Simple { front = x::newfront
79 78 , rear = rear
80 79 , diff = diff + 1
81 80 }
82 81 | tick (Copy2 {oldfront, rear, newfront, diff, copy, frev = x::frev}) =
83 - Copy2 { oldfront = oldfront
82 + Copy2 { oldfront = oldfront
84 83 , rear = rear
85 84 , newfront = x::newfront
86 85 , frev = frev
@@ -103,14 +102,14 @@ struct
103 102 | size (Copy1 {rear,diff,copy,f,r,...}) =
104 103 2 * length rear + diff + copy + length f + length r
105 104 | size (Copy2 {rear,diff,copy,...}) =
106 - 2 * length rear + diff + copy
105 + 2 * length rear + diff + copy
107 106
108 107 fun insert (x, Simple {front, rear, diff = 0}) =
109 - tick2 (rotate (front, x::rear))
108 + tick2 (rotate (front, x::rear))
110 109 | insert (x, Simple { front, rear, diff }) =
111 - Simple { front = front, rear = x::rear, diff = diff - 1 }
110 + Simple { front = front, rear = x::rear, diff = diff - 1 }
112 111 | insert (x, Copy1 { oldfront, rear, f, r, frev, rrev, diff, copy }) =
113 - tick2 (Copy1 { oldfront = oldfront
112 + tick2 (Copy1 { oldfront = oldfront
114 113 , rear = x::rear
115 114 , f = f
116 115 , r = r
@@ -119,7 +118,7 @@ struct
119 118 , diff = diff-1
120 119 , copy = copy })
121 120 | insert (x, Copy2 {oldfront, rear, frev, newfront, diff, copy}) =
122 - tick2 (Copy2 { oldfront = oldfront
121 + tick2 (Copy2 { oldfront = oldfront
123 122 , rear = x::rear
124 123 , frev = frev
125 124 , newfront = newfront
@@ -128,11 +127,11 @@ struct
128 127
129 128 fun remove (Simple {front = [], ...}) = raise Empty
130 129 | remove (Simple {front = x::front, rear, diff = 0}) =
131 - (x, tick2 (rotate (front, rear)))
130 + (x, tick2 (rotate (front, rear)))
132 131 | remove (Simple {front = x::front, rear, diff}) =
133 - (x, Simple {front = front, rear = rear, diff = diff - 1})
132 + (x, Simple {front = front, rear = rear, diff = diff - 1})
134 133 | remove (Copy1 {oldfront = x::oldfront, rear, f, r, frev, rrev, diff, copy})=
135 - (x, tick2 (Copy1 { oldfront = oldfront
134 + (x, tick2 (Copy1 { oldfront = oldfront
136 135 , rear = rear
137 136 , f = f
138 137 , r = r
@@ -141,7 +140,7 @@ struct
141 140 , diff = diff
142 141 , copy = copy - 1 } ) )
143 142 | remove (Copy2 {oldfront=x::oldfront,rear,frev,newfront,diff,copy})=
144 - (x, tick2 (Copy2 { oldfront = oldfront
143 + (x, tick2 (Copy2 { oldfront = oldfront
145 144 , rear = rear
146 145 , frev = frev
147 146 , newfront = newfront

capitalex's Avatar capitalex 修订了这个 Gist 6 months ago. 转到此修订

1 file changed, 1 insertion, 1 deletion

queue.ml

@@ -118,7 +118,7 @@ struct
118 118 , rrev = rrev
119 119 , diff = diff-1
120 120 , copy = copy })
121 - | insert (x, Copy2 {oldfront,rear,frev,newfront,diff,copy}) =
121 + | insert (x, Copy2 {oldfront, rear, frev, newfront, diff, copy}) =
122 122 tick2 (Copy2 { oldfront = oldfront
123 123 , rear = x::rear
124 124 , frev = frev

capitalex's Avatar capitalex 修订了这个 Gist 6 months ago. 转到此修订

1 file changed, 153 insertions

queue.ml(文件已创建)

@@ -0,0 +1,153 @@
1 + (* Chris Okasaki
2 + School of Computer Science
3 + Carnegie Mellon University
4 + Pittsburgh, PA 15213
5 + cokasaki@cs.cmu.edu *)
6 +
7 + functor HoodMelvilleQueue () : QUEUE =
8 + (* Alternative implementation of queues with O(1) worst-case *)
9 + (* performance. Provided for comparison. *)
10 + (* *)
11 + (* Taken from *)
12 + (* Hood and Melville *)
13 + (* "Real-time queue operations in pure Lisp" *)
14 + (* IPL 13(2) (Nov 1981), 50-53 *)
15 + (* *)
16 + (* Warning! Does not support insertf! *)
17 + struct
18 +
19 + datatype 'a Queue =
20 + Simple of
21 + {front : 'a list,
22 + rear : 'a list,
23 + diff : int} (* diff = length front - length rear *)
24 +
25 + | Copy1 of (* in process of reversing f and r *)
26 + { oldfront : 'a list,
27 + rear : 'a list,
28 + f : 'a list,
29 + r : 'a list,
30 + frev : 'a list,
31 + rrev : 'a list, (* the partial new front *)
32 + diff : int, (* diff = length rrev - length rear *)
33 + copy : int} (* copy = # of valid elements in frev *)
34 +
35 + | Copy2 of (* in process of reversing frev onto newfront *)
36 + { oldfront : 'a list,
37 + rear : 'a list,
38 + frev : 'a list,
39 + newfront : 'a list,
40 + diff : int, (* diff = length newfront - length rear *)
41 + copy : int} (* copy = # of valid elements in frev *)
42 +
43 +
44 + (* begin process of moving elements from rear to front *)
45 + fun rotate (front,rear) = (* length rear = length front + 1 *)
46 + Copy1 { oldfront = front
47 + , rear = []
48 + , f = front
49 + , r = rear
50 + , frev = []
51 + , rrev = []
52 + , diff = 0
53 + , copy = 0 }
54 +
55 + (* do one step in process of moving elements from rear to front *)
56 + fun tick (Copy1 {oldfront, rear, f=x::f, r=y::r, frev, rrev, diff, copy}) =
57 + Copy1 { oldfront = oldfront
58 + , rear = rear
59 + , f = f
60 + , r = r
61 + , frev = x::frev
62 + , rrev = y::rrev
63 + , diff = diff + 1
64 + , copy = copy + 1 }
65 + | tick (Copy1 {oldfront, rear, f=[], r=[y], frev, rrev, diff, copy}) =
66 + Copy2 { oldfront = oldfront
67 + , rear = rear
68 + , frev = frev
69 + , newfront = y::rrev
70 + , diff = diff + 1
71 + , copy = copy }
72 + | tick (Copy2 {oldfront, rear, newfront, diff, copy = 0, frev}) =
73 + Simple { front = newfront
74 + , rear = rear
75 + , diff = diff
76 + }
77 + | tick (Copy2 {oldfront, rear, newfront, diff, copy = 1, frev = x::_}) =
78 + Simple { front = x::newfront
79 + , rear = rear
80 + , diff = diff + 1
81 + }
82 + | tick (Copy2 {oldfront, rear, newfront, diff, copy, frev = x::frev}) =
83 + Copy2 { oldfront = oldfront
84 + , rear = rear
85 + , newfront = x::newfront
86 + , frev = frev
87 + , diff = diff + 1
88 + , copy = copy - 1 }
89 + | tick simpleq = simpleq
90 +
91 + fun tick2 q = tick (tick q)
92 +
93 +
94 + exception Empty
95 +
96 + val empty = Simple {front = [], rear = [], diff = 0}
97 +
98 + fun isempty (Simple {front = [], ...}) = true
99 + | isempty _ = false
100 +
101 + fun size (Simple {rear, diff, ...}) =
102 + 2 * length rear + diff
103 + | size (Copy1 {rear,diff,copy,f,r,...}) =
104 + 2 * length rear + diff + copy + length f + length r
105 + | size (Copy2 {rear,diff,copy,...}) =
106 + 2 * length rear + diff + copy
107 +
108 + fun insert (x, Simple {front, rear, diff = 0}) =
109 + tick2 (rotate (front, x::rear))
110 + | insert (x, Simple { front, rear, diff }) =
111 + Simple { front = front, rear = x::rear, diff = diff - 1 }
112 + | insert (x, Copy1 { oldfront, rear, f, r, frev, rrev, diff, copy }) =
113 + tick2 (Copy1 { oldfront = oldfront
114 + , rear = x::rear
115 + , f = f
116 + , r = r
117 + , frev = frev
118 + , rrev = rrev
119 + , diff = diff-1
120 + , copy = copy })
121 + | insert (x, Copy2 {oldfront,rear,frev,newfront,diff,copy}) =
122 + tick2 (Copy2 { oldfront = oldfront
123 + , rear = x::rear
124 + , frev = frev
125 + , newfront = newfront
126 + , diff = diff - 1
127 + , copy = copy})
128 +
129 + fun remove (Simple {front = [], ...}) = raise Empty
130 + | remove (Simple {front = x::front, rear, diff = 0}) =
131 + (x, tick2 (rotate (front, rear)))
132 + | remove (Simple {front = x::front, rear, diff}) =
133 + (x, Simple {front = front, rear = rear, diff = diff - 1})
134 + | remove (Copy1 {oldfront = x::oldfront, rear, f, r, frev, rrev, diff, copy})=
135 + (x, tick2 (Copy1 { oldfront = oldfront
136 + , rear = rear
137 + , f = f
138 + , r = r
139 + , frev = frev
140 + , rrev = rrev
141 + , diff = diff
142 + , copy = copy - 1 } ) )
143 + | remove (Copy2 {oldfront=x::oldfront,rear,frev,newfront,diff,copy})=
144 + (x, tick2 (Copy2 { oldfront = oldfront
145 + , rear = rear
146 + , frev = frev
147 + , newfront = newfront
148 + , diff = diff
149 + , copy = copy - 1 } ) )
150 +
151 + exception InsertfNotSupported
152 + fun insertf (_,_) = raise InsertfNotSupported
153 + end
上一页 下一页

由 Opengist 强力驱动 ⋅ Load: 24ms⋅

中文