1 /* Copyright (C) 2004 - 2009  Versant Inc.  http://www.db4o.com */
2 
3 using System;
4 using System.Collections;
5 using Db4objects.Db4o.Foundation;
6 
7 namespace Db4objects.Db4o.Foundation
8 {
9 	/// <summary>A fixed size double ended queue with O(1) complexity for addFirst, removeFirst and removeLast operations.
10 	/// 	</summary>
11 	/// <remarks>A fixed size double ended queue with O(1) complexity for addFirst, removeFirst and removeLast operations.
12 	/// 	</remarks>
13 	public class CircularLongBuffer4 : IEnumerable
14 	{
15 		private const int Empty = -1;
16 
17 		private readonly long[] _buffer;
18 
19 		private int _head;
20 
21 		private int _tail;
22 
CircularLongBuffer4(int size)23 		public CircularLongBuffer4(int size)
24 		{
25 			_buffer = new long[size + 1];
26 		}
27 
Size()28 		public virtual int Size()
29 		{
30 			return Index(_tail - _head);
31 		}
32 
AddFirst(long value)33 		public virtual void AddFirst(long value)
34 		{
35 			int newHead = CircularIndex(_head - 1);
36 			if (newHead == _tail)
37 			{
38 				throw new InvalidOperationException();
39 			}
40 			_head = newHead;
41 			_buffer[Index(_head)] = value;
42 		}
43 
CircularIndex(int index)44 		private int CircularIndex(int index)
45 		{
46 			return index % _buffer.Length;
47 		}
48 
Index(int i)49 		private int Index(int i)
50 		{
51 			return i < 0 ? _buffer.Length + i : i;
52 		}
53 
RemoveLast()54 		public virtual long RemoveLast()
55 		{
56 			AssertNotEmpty();
57 			_tail = CircularIndex(_tail - 1);
58 			return Erase(_tail);
59 		}
60 
AssertNotEmpty()61 		private void AssertNotEmpty()
62 		{
63 			if (IsEmpty())
64 			{
65 				throw new InvalidOperationException();
66 			}
67 		}
68 
IsEmpty()69 		public virtual bool IsEmpty()
70 		{
71 			return Index(_head) == Index(_tail);
72 		}
73 
IsFull()74 		public virtual bool IsFull()
75 		{
76 			return CircularIndex(_head - 1) == _tail;
77 		}
78 
RemoveFirst()79 		public virtual long RemoveFirst()
80 		{
81 			AssertNotEmpty();
82 			long erased = Erase(_head);
83 			_head = CircularIndex(_head + 1);
84 			return erased;
85 		}
86 
Erase(int index)87 		private long Erase(int index)
88 		{
89 			int bufferIndex = Index(index);
90 			long erasedValue = _buffer[bufferIndex];
91 			_buffer[bufferIndex] = Empty;
92 			return erasedValue;
93 		}
94 
Remove(long value)95 		public virtual bool Remove(long value)
96 		{
97 			int idx = IndexOf(value);
98 			if (idx >= 0)
99 			{
100 				RemoveAt(idx);
101 				return true;
102 			}
103 			return false;
104 		}
105 
Contains(long value)106 		public virtual bool Contains(long value)
107 		{
108 			return IndexOf(value) >= 0;
109 		}
110 
IndexOf(long value)111 		private int IndexOf(long value)
112 		{
113 			int current = Index(_head);
114 			int tail = Index(_tail);
115 			while (current != tail)
116 			{
117 				if (value == _buffer[current])
118 				{
119 					break;
120 				}
121 				current = CircularIndex(current + 1);
122 			}
123 			return (current == tail ? -1 : current);
124 		}
125 
RemoveAt(int index)126 		private void RemoveAt(int index)
127 		{
128 			if (Index(_tail - 1) == index)
129 			{
130 				RemoveLast();
131 				return;
132 			}
133 			if (index == Index(_head))
134 			{
135 				RemoveFirst();
136 				return;
137 			}
138 			int current = index;
139 			int tail = Index(_tail);
140 			while (current != tail)
141 			{
142 				int next = CircularIndex(current + 1);
143 				_buffer[current] = _buffer[next];
144 				current = next;
145 			}
146 			_tail = CircularIndex(_tail - 1);
147 		}
148 
GetEnumerator()149 		public virtual IEnumerator GetEnumerator()
150 		{
151 			int tail = Index(_tail);
152 			int head = Index(_head);
153 			// TODO: detect concurrent modification and throw IllegalStateException
154 			return new _IEnumerator_122(this, head, tail);
155 		}
156 
157 		private sealed class _IEnumerator_122 : IEnumerator
158 		{
_IEnumerator_122(CircularLongBuffer4 _enclosing, int head, int tail)159 			public _IEnumerator_122(CircularLongBuffer4 _enclosing, int head, int tail)
160 			{
161 				this._enclosing = _enclosing;
162 				this.head = head;
163 				this.tail = tail;
164 				this._index = head;
165 				this._current = Iterators.NoElement;
166 			}
167 
168 			private int _index;
169 
170 			private object _current;
171 
172 			public object Current
173 			{
174 				get
175 				{
176 					if (this._current == Iterators.NoElement)
177 					{
178 						throw new InvalidOperationException();
179 					}
180 					return this._current;
181 				}
182 			}
183 
MoveNext()184 			public bool MoveNext()
185 			{
186 				if (this._index == tail)
187 				{
188 					return false;
189 				}
190 				this._current = this._enclosing._buffer[this._index];
191 				this._index = this._enclosing.CircularIndex(this._index + 1);
192 				return true;
193 			}
194 
Reset()195 			public void Reset()
196 			{
197 				throw new NotImplementedException();
198 			}
199 
200 			private readonly CircularLongBuffer4 _enclosing;
201 
202 			private readonly int head;
203 
204 			private readonly int tail;
205 		}
206 	}
207 }
208