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