1 /** 2 Some additional containers. 3 4 Copyright: © 2019 Arne Ludwig <arne.ludwig@posteo.de> 5 License: Subject to the terms of the MIT license, as written in the 6 included LICENSE file. 7 Authors: Arne Ludwig <arne.ludwig@posteo.de> 8 */ 9 module dalicious.container; 10 11 import core.exception; 12 13 14 /// An array-based implementation of a ring buffer. 15 struct RingBuffer(T, size_t staticBufferSize = size_t.max) 16 { 17 private: 18 19 static if (staticBufferSize < size_t.max) 20 T[staticBufferSize] _buffer; 21 else 22 T[] _buffer; 23 ptrdiff_t _frontPtr = -1; 24 ptrdiff_t _backPtr; 25 26 public: 27 28 static if (staticBufferSize == size_t.max) 29 { 30 @disable this(); 31 32 this(size_t bufferSize) 33 { 34 this._buffer = new T[bufferSize]; 35 } 36 } 37 38 39 static if (staticBufferSize < size_t.max) 40 enum bufferSize = _buffer.length; 41 else 42 @property size_t bufferSize() const pure nothrow @safe 43 { 44 return _buffer.length; 45 } 46 47 48 @property RingBuffer!(T, staticBufferSize) save() const pure nothrow @trusted 49 { 50 return cast(typeof(return)) this; 51 } 52 53 54 @property bool empty() const pure nothrow @safe 55 { 56 return _frontPtr < _backPtr || bufferSize == 0; 57 } 58 59 60 @property size_t length() const pure nothrow @safe 61 { 62 return empty ? 0 : _frontPtr - _backPtr + 1; 63 } 64 65 66 @property auto ref T front() 67 { 68 assert(!empty, "Attempting to fetch the front of an empty RingBuffer"); 69 70 return _buffer[indexOf(_frontPtr)]; 71 } 72 73 74 @property void front(T newFront) 75 { 76 assert(!empty, "Attempting to assign to the front of an empty RingBuffer"); 77 78 this.front() = newFront; 79 } 80 81 82 @property auto ref T back() 83 { 84 assert(!empty, "Attempting to fetch the back of an empty RingBuffer"); 85 86 return _buffer[indexOf(_backPtr)]; 87 } 88 89 90 @property void back(T newBack) 91 { 92 assert(!empty, "Attempting to assign to the back of an empty RingBuffer"); 93 94 this.back() = newBack; 95 } 96 97 98 void popFront() pure nothrow @safe 99 { 100 assert(!empty, "Attempting to popFront an empty RingBuffer"); 101 102 --_frontPtr; 103 } 104 105 106 void popBack() pure nothrow @safe 107 { 108 assert(!empty, "Attempting to popBack an empty RingBuffer"); 109 110 ++_backPtr; 111 } 112 113 114 void pushFront(T value) 115 { 116 assert(bufferSize > 0, "Attempting to pushFront an zero-sized RingBuffer"); 117 118 auto wasEmpty = empty; 119 120 ++_frontPtr; 121 if (!wasEmpty && indexOf(_backPtr) == indexOf(_frontPtr)) 122 ++_backPtr; 123 124 front = value; 125 } 126 127 alias put = pushFront; 128 129 130 void pushBack(T value) 131 { 132 assert(bufferSize > 0, "Attempting to pushBack an zero-sized RingBuffer"); 133 134 --_backPtr; 135 136 if (indexOf(_frontPtr) == indexOf(_backPtr)) 137 --_frontPtr; 138 139 back = value; 140 } 141 142 143 private size_t indexOf(ptrdiff_t ptr) const pure nothrow @safe 144 { 145 // make sure the index is positive 146 return cast(size_t) ((ptr % bufferSize) + bufferSize) % bufferSize; 147 } 148 } 149 150 unittest 151 { 152 import std.meta; 153 import std.range.primitives; 154 155 alias Element = int; 156 alias DyanmicRB = RingBuffer!Element; 157 alias StaticRB = RingBuffer!(Element, 10); 158 159 enum isDefaultConstructible(T) = is(typeof(T())); 160 161 static assert(!isDefaultConstructible!DyanmicRB); 162 static assert(isDefaultConstructible!StaticRB); 163 164 static foreach (alias RB; AliasSeq!(DyanmicRB, StaticRB)) 165 { 166 static assert(isInputRange!RB); 167 static assert(isOutputRange!(RB, Element)); 168 static assert(isForwardRange!RB); 169 static assert(isBidirectionalRange!RB); 170 static assert(is(ElementType!RB == Element)); 171 static assert(hasAssignableElements!RB); 172 static assert(hasLvalueElements!RB); 173 static assert(hasLength!RB); 174 static assert(!isInfinite!RB); 175 } 176 } 177 178 /// Ring buffer stores the `bufferSize` most recent elements. 179 unittest 180 { 181 import std.algorithm; 182 183 auto buffer = RingBuffer!int(5); 184 185 buffer.pushFront(1); 186 buffer.pushFront(2); 187 buffer.pushFront(3); 188 buffer.pushFront(4); 189 buffer.pushFront(5); 190 191 assert(buffer.front == 5); 192 assert(equal(buffer, [5, 4, 3, 2, 1])); 193 194 buffer.pushFront(6); 195 196 assert(buffer.front == 6); 197 assert(equal(buffer, [6, 5, 4, 3, 2])); 198 } 199 200 /// Ring buffer may have a static size. 201 unittest 202 { 203 import std.algorithm; 204 205 auto buffer = RingBuffer!(int, 5)(); 206 207 buffer.pushFront(1); 208 buffer.pushFront(2); 209 buffer.pushFront(3); 210 buffer.pushFront(4); 211 buffer.pushFront(5); 212 213 assert(buffer.front == 5); 214 assert(equal(buffer, [5, 4, 3, 2, 1])); 215 216 buffer.pushFront(6); 217 218 assert(buffer.front == 6); 219 assert(equal(buffer, [6, 5, 4, 3, 2])); 220 } 221 222 /// Elements can be removed. 223 unittest 224 { 225 import std.algorithm; 226 227 auto buffer = RingBuffer!int(5); 228 229 buffer.pushFront(1); 230 buffer.pushFront(2); 231 buffer.pushFront(3); 232 buffer.pushFront(4); 233 buffer.pushFront(5); 234 235 assert(buffer.length == 5); 236 assert(equal(buffer, [5, 4, 3, 2, 1])); 237 238 buffer.popFront(); 239 buffer.popBack(); 240 241 assert(buffer.length == 3); 242 assert(equal(buffer, [4, 3, 2])); 243 } 244 245 /// The buffer is double-ended. 246 unittest 247 { 248 import std.algorithm; 249 250 auto buffer = RingBuffer!int(5); 251 252 buffer.pushFront(1); 253 buffer.pushFront(2); 254 buffer.pushFront(3); 255 buffer.pushFront(4); 256 buffer.pushFront(5); 257 buffer.pushFront(6); 258 259 assert(buffer.front == 6); 260 assert(buffer.back == 2); 261 assert(equal(buffer, [6, 5, 4, 3, 2])); 262 263 buffer.pushBack(1); 264 265 assert(buffer.front == 5); 266 assert(buffer.back == 1); 267 assert(equal(buffer, [5, 4, 3, 2, 1])); 268 }