Revisioni di queue.ml

capitalex ha revisionato questo gist 1749348107. Vai alla revisione

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 ha revisionato questo gist 1749347910. Vai alla revisione

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 ha revisionato questo gist 1749347782. Vai alla revisione

1 file changed, 153 insertions

queue.ml(file creato)

		@@ -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

Più nuovi Più vecchi