1
|
/*
|
2
|
Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
|
3
|
Permission is hereby granted, free of charge, to any person obtaining a copy
|
4
|
of this software and associated documentation files (the "Software"), to deal
|
5
|
in the Software without restriction, including without limitation the rights
|
6
|
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
|
7
|
copies of the Software, and to permit persons to whom the Software is
|
8
|
furnished to do so, subject to the following conditions:
|
9
|
|
10
|
The above copyright notice and this permission notice shall be included in
|
11
|
all copies or substantial portions of the Software.
|
12
|
|
13
|
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
14
|
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
15
|
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
16
|
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
|
17
|
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
|
18
|
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
|
19
|
SOFTWARE.
|
20
|
*/
|
21
|
|
22
|
using System;
|
23
|
using System.Diagnostics;
|
24
|
using SCG = System.Collections.Generic;
|
25
|
namespace C5
|
26
|
{
|
27
|
/// <summary>
|
28
|
///
|
29
|
/// </summary>
|
30
|
/// <typeparam name="T"></typeparam>
|
31
|
public class CircularQueue<T> : SequencedBase<T>, IQueue<T>, IStack<T>
|
32
|
{
|
33
|
#region Fields
|
34
|
/*
|
35
|
Invariant: the itemes in the queue ar the elements from front upwards,
|
36
|
possibly wrapping around at the end of array, to back.
|
37
|
|
38
|
if front<=back then size = back - front + 1;
|
39
|
else size = array.Length + back - front + 1;
|
40
|
|
41
|
*/
|
42
|
int front, back;
|
43
|
/// <summary>
|
44
|
/// The internal container array is doubled when necessary, but never shrinked.
|
45
|
/// </summary>
|
46
|
T[] array;
|
47
|
bool forwards = true, original = true;
|
48
|
#endregion
|
49
|
|
50
|
#region Events
|
51
|
|
52
|
/// <summary>
|
53
|
///
|
54
|
/// </summary>
|
55
|
/// <value></value>
|
56
|
public override EventTypeEnum ListenableEvents { get { return EventTypeEnum.Basic; } }
|
57
|
|
58
|
#endregion
|
59
|
|
60
|
#region Util
|
61
|
void expand()
|
62
|
{
|
63
|
int newlength = 2 * array.Length;
|
64
|
T[] newarray = new T[newlength];
|
65
|
|
66
|
if (front <= back)
|
67
|
Array.Copy(array, front, newarray, 0, size);
|
68
|
else
|
69
|
{
|
70
|
int half = array.Length - front;
|
71
|
Array.Copy(array, front, newarray, 0, half);
|
72
|
Array.Copy(array, 0, newarray, half, size - half);
|
73
|
}
|
74
|
|
75
|
front = 0;
|
76
|
back = size;
|
77
|
array = newarray;
|
78
|
}
|
79
|
|
80
|
#endregion
|
81
|
|
82
|
#region Constructors
|
83
|
|
84
|
/// <summary>
|
85
|
///
|
86
|
/// </summary>
|
87
|
public CircularQueue() : this(8) { }
|
88
|
|
89
|
/// <summary>
|
90
|
///
|
91
|
/// </summary>
|
92
|
/// <param name="capacity"></param>
|
93
|
public CircularQueue(int capacity)
|
94
|
: base(EqualityComparer<T>.Default)
|
95
|
{
|
96
|
int newlength = 8;
|
97
|
while (newlength < capacity) newlength *= 2;
|
98
|
array = new T[newlength];
|
99
|
}
|
100
|
|
101
|
#endregion
|
102
|
|
103
|
#region IQueue<T> Members
|
104
|
/// <summary>
|
105
|
///
|
106
|
/// </summary>
|
107
|
/// <value></value>
|
108
|
public virtual bool AllowsDuplicates { get { return true; } }
|
109
|
|
110
|
/// <summary>
|
111
|
/// Get the i'th item in the queue. The front of the queue is at index 0.
|
112
|
/// </summary>
|
113
|
/// <param name="i"></param>
|
114
|
/// <returns></returns>
|
115
|
public virtual T this[int i]
|
116
|
{
|
117
|
get
|
118
|
{
|
119
|
if (i < 0 || i >= size)
|
120
|
throw new IndexOutOfRangeException();
|
121
|
i = i + front;
|
122
|
//Bug fix by Steve Wallace 2006/02/10
|
123
|
return array[i >= array.Length ? i - array.Length : i];
|
124
|
}
|
125
|
}
|
126
|
|
127
|
|
128
|
/// <summary>
|
129
|
///
|
130
|
/// </summary>
|
131
|
/// <param name="item"></param>
|
132
|
[Tested]
|
133
|
public virtual void Enqueue(T item)
|
134
|
{
|
135
|
if (!original)
|
136
|
throw new ReadOnlyCollectionException();
|
137
|
stamp++;
|
138
|
if (size == array.Length - 1) expand();
|
139
|
size++;
|
140
|
int oldback = back++;
|
141
|
if (back == array.Length) back = 0;
|
142
|
array[oldback] = item;
|
143
|
if (ActiveEvents != 0)
|
144
|
raiseForAdd(item);
|
145
|
}
|
146
|
|
147
|
/// <summary>
|
148
|
///
|
149
|
/// </summary>
|
150
|
/// <returns></returns>
|
151
|
[Tested]
|
152
|
public virtual T Dequeue()
|
153
|
{
|
154
|
if (!original)
|
155
|
throw new ReadOnlyCollectionException("Object is a non-updatable clone");
|
156
|
stamp++;
|
157
|
if (size == 0)
|
158
|
throw new NoSuchItemException();
|
159
|
size--;
|
160
|
int oldfront = front++;
|
161
|
if (front == array.Length) front = 0;
|
162
|
T retval = array[oldfront];
|
163
|
array[oldfront] = default(T);
|
164
|
if (ActiveEvents != 0)
|
165
|
raiseForRemove(retval);
|
166
|
return retval;
|
167
|
}
|
168
|
|
169
|
/// <summary>
|
170
|
///
|
171
|
/// </summary>
|
172
|
/// <param name="item"></param>
|
173
|
public void Push(T item) //== Enqueue
|
174
|
{
|
175
|
if (!original)
|
176
|
throw new ReadOnlyCollectionException();
|
177
|
stamp++;
|
178
|
if (size == array.Length - 1) expand();
|
179
|
size++;
|
180
|
int oldback = back++;
|
181
|
if (back == array.Length) back = 0;
|
182
|
array[oldback] = item;
|
183
|
if (ActiveEvents != 0)
|
184
|
raiseForAdd(item);
|
185
|
}
|
186
|
|
187
|
/// <summary>
|
188
|
///
|
189
|
/// </summary>
|
190
|
/// <returns></returns>
|
191
|
public T Pop()
|
192
|
{
|
193
|
if (!original)
|
194
|
throw new ReadOnlyCollectionException("Object is a non-updatable clone");
|
195
|
stamp++;
|
196
|
if (size == 0)
|
197
|
throw new NoSuchItemException();
|
198
|
size--;
|
199
|
back--;
|
200
|
if (back == -1) back = array.Length - 1;
|
201
|
T retval = array[back];
|
202
|
array[back] = default(T);
|
203
|
if (ActiveEvents != 0)
|
204
|
raiseForRemove(retval);
|
205
|
return retval;
|
206
|
}
|
207
|
#endregion
|
208
|
|
209
|
#region ICollectionValue<T> Members
|
210
|
|
211
|
//TODO: implement these with Array.Copy instead of relying on XxxBase:
|
212
|
/*
|
213
|
public void CopyTo(T[] a, int i)
|
214
|
{
|
215
|
}
|
216
|
|
217
|
public T[] ToArray()
|
218
|
{
|
219
|
}*/
|
220
|
|
221
|
/// <summary>
|
222
|
///
|
223
|
/// </summary>
|
224
|
/// <returns></returns>
|
225
|
[Tested]
|
226
|
public override T Choose()
|
227
|
{
|
228
|
if (size == 0)
|
229
|
throw new NoSuchItemException();
|
230
|
return array[front];
|
231
|
}
|
232
|
|
233
|
#endregion
|
234
|
|
235
|
#region IEnumerable<T> Members
|
236
|
|
237
|
/// <summary>
|
238
|
///
|
239
|
/// </summary>
|
240
|
/// <returns></returns>
|
241
|
public override SCG.IEnumerator<T> GetEnumerator()
|
242
|
{
|
243
|
int stamp = this.stamp;
|
244
|
if (forwards)
|
245
|
{
|
246
|
int position = front;
|
247
|
int end = front <= back ? back : array.Length;
|
248
|
while (position < end)
|
249
|
{
|
250
|
if (stamp != this.stamp)
|
251
|
throw new CollectionModifiedException();
|
252
|
yield return array[position++];
|
253
|
}
|
254
|
if (front > back)
|
255
|
{
|
256
|
position = 0;
|
257
|
while (position < back)
|
258
|
{
|
259
|
if (stamp != this.stamp)
|
260
|
throw new CollectionModifiedException();
|
261
|
yield return array[position++];
|
262
|
}
|
263
|
}
|
264
|
}
|
265
|
else
|
266
|
{
|
267
|
int position = back - 1;
|
268
|
int end = front <= back ? front : 0;
|
269
|
while (position >= end)
|
270
|
{
|
271
|
if (stamp != this.stamp)
|
272
|
throw new CollectionModifiedException();
|
273
|
yield return array[position--];
|
274
|
}
|
275
|
if (front > back)
|
276
|
{
|
277
|
position = array.Length - 1;
|
278
|
while (position >= front)
|
279
|
{
|
280
|
if (stamp != this.stamp)
|
281
|
throw new CollectionModifiedException();
|
282
|
yield return array[position--];
|
283
|
}
|
284
|
}
|
285
|
}
|
286
|
}
|
287
|
|
288
|
#endregion
|
289
|
|
290
|
#region IDirectedCollectionValue<T> Members
|
291
|
|
292
|
/// <summary>
|
293
|
///
|
294
|
/// </summary>
|
295
|
/// <returns></returns>
|
296
|
public override IDirectedCollectionValue<T> Backwards()
|
297
|
{
|
298
|
CircularQueue<T> retval = (CircularQueue<T>)MemberwiseClone();
|
299
|
retval.original = false;
|
300
|
retval.forwards = !forwards;
|
301
|
return retval;
|
302
|
}
|
303
|
|
304
|
#endregion
|
305
|
|
306
|
#region IDirectedEnumerable<T> Members
|
307
|
|
308
|
/// <summary>
|
309
|
///
|
310
|
/// </summary>
|
311
|
/// <returns></returns>
|
312
|
IDirectedEnumerable<T> IDirectedEnumerable<T>.Backwards()
|
313
|
{
|
314
|
return Backwards();
|
315
|
}
|
316
|
|
317
|
#endregion
|
318
|
|
319
|
/// <summary>
|
320
|
///
|
321
|
/// </summary>
|
322
|
/// <returns></returns>
|
323
|
public virtual bool Check()
|
324
|
{
|
325
|
if (front < 0 || front >= array.Length || back < 0 || back >= array.Length ||
|
326
|
(front <= back && size != back - front) || (front > back && size != array.Length + back - front))
|
327
|
{
|
328
|
Console.WriteLine("Bad combination of (front,back,size,array.Length): ({0},{1},{2},{3})",
|
329
|
front, back, size, array.Length);
|
330
|
return false;
|
331
|
}
|
332
|
return true;
|
333
|
}
|
334
|
}
|
335
|
}
|