summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--source/tanya/container/bitvector.d510
-rw-r--r--source/tanya/container/buffer.d1264
-rw-r--r--source/tanya/container/entry.d10
-rw-r--r--source/tanya/container/package.d5
-rw-r--r--source/tanya/container/queue.d506
-rw-r--r--source/tanya/container/vector.d78
6 files changed, 1444 insertions, 929 deletions
diff --git a/source/tanya/container/bitvector.d b/source/tanya/container/bitvector.d
new file mode 100644
index 0000000..3597a73
--- /dev/null
+++ b/source/tanya/container/bitvector.d
@@ -0,0 +1,510 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/**
+ * Single-dimensioned bit array.
+ *
+ * Copyright: Eugene Wissner 2016-2017.
+ * License: $(LINK2 https://www.mozilla.org/en-US/MPL/2.0/,
+ * Mozilla Public License, v. 2.0).
+ * Authors: $(LINK2 mailto:info@caraus.de, Eugene Wissner)
+ */
+module tanya.container.bitvector;
+
+/**
+ * Wrapper that allows bit manipulation on $(D_KEYWORD ubyte[]) array.
+ */
+struct BitVector
+{
+ protected ubyte[] vector;
+
+ /**
+ * Params:
+ * array = Array should be manipulated on.
+ */
+ this(inout(ubyte[]) array) inout pure nothrow @safe @nogc
+ in
+ {
+ assert(array.length <= size_t.max / 8);
+ assert(array !is null);
+ }
+ body
+ {
+ vector = array;
+ }
+
+ ///
+ unittest
+ {
+ ubyte[5] array1 = [234, 3, 252, 10, 18];
+ ubyte[3] array2 = [65, 13, 173];
+ auto bits = BitVector(array1);
+
+ assert(bits[] is array1);
+ assert(bits[] !is array2);
+
+ bits = BitVector(array2);
+ assert(bits[] is array2);
+ }
+
+ /**
+ * Returns: Number of bits in the vector.
+ */
+ @property inout(size_t) length() inout const pure nothrow @safe @nogc
+ {
+ return vector.length * 8;
+ }
+
+ /// Ditto.
+ inout(size_t) opDollar() inout const pure nothrow @safe @nogc
+ {
+ return vector.length * 8;
+ }
+
+ ///
+ unittest
+ {
+ // [01000001, 00001101, 10101101]
+ ubyte[3] arr = [65, 13, 173];
+ auto bits = BitVector(arr);
+
+ assert(bits.length == 24);
+ }
+
+ /**
+ * Params:
+ * bit = Bit position.
+ *
+ * Returns: $(D_KEYWORD true) if the bit on position $(D_PARAM bit) is set,
+ * $(D_KEYWORD false) if not set.
+ */
+ inout(bool) opIndex(size_t bit) inout const pure nothrow @safe @nogc
+ in
+ {
+ assert(bit / 8 <= vector.length);
+ }
+ body
+ {
+ return (vector[bit / 8] & (0x80 >> (bit % 8))) != 0;
+ }
+
+ ///
+ unittest
+ {
+ // [01000001, 00001101, 10101101]
+ ubyte[3] arr = [65, 13, 173];
+ auto bits = BitVector(arr);
+
+ assert(!bits[0]);
+ assert(bits[1]);
+ assert(bits[7]);
+ assert(!bits[8]);
+ assert(!bits[11]);
+ assert(bits[12]);
+ assert(bits[20]);
+ assert(bits[23]);
+ }
+
+ /**
+ * Returns: Underlying array.
+ */
+ inout(ubyte[]) opIndex() inout pure nothrow @safe @nogc
+ {
+ return vector;
+ }
+
+ ///
+ unittest
+ {
+ // [01000001, 00001101, 10101101]
+ ubyte[3] arr = [65, 13, 173];
+ auto bits = BitVector(arr);
+
+ assert(bits[] is arr);
+ }
+
+ /**
+ * Params:
+ * value = $(D_KEYWORD true) if the bit should be set,
+ * $(D_KEYWORD false) if cleared.
+ * bit = Bit position.
+ *
+ * Returns: $(D_PSYMBOL this).
+ */
+ bool opIndexAssign(bool value, size_t bit) pure nothrow @safe @nogc
+ in
+ {
+ assert(bit / 8 <= vector.length);
+ }
+ body
+ {
+ if (value)
+ {
+ vector[bit / 8] |= (0x80 >> (bit % 8));
+ }
+ else
+ {
+ vector[bit / 8] &= ~(0x80 >> (bit % 8));
+ }
+ return value;
+ }
+
+ ///
+ unittest
+ {
+ // [01000001, 00001101, 10101101]
+ ubyte[3] arr = [65, 13, 173];
+ auto bits = BitVector(arr);
+
+ bits[5] = bits[6] = true;
+ assert(bits[][0] == 71);
+
+ bits[14] = true;
+ bits[15] = false;
+ assert(bits[][1] == 14);
+
+ bits[16] = bits[23] = false;
+ assert(bits[][2] == 44);
+ }
+
+ /**
+ * Copies bits from $(D_PARAM vector) into this $(D_PSYMBOL BitVector).
+ *
+ * The array that should be assigned, can be smaller (but not larger) than
+ * the underlying array of this $(D_PSYMBOL BitVector), leading zeros will
+ * be added in this case to the left.
+ *
+ * Params:
+ * vector = $(D_KEYWORD ubyte[]) array not larger than
+ * `$(D_PSYMBOL length) / 8`.
+ *
+ * Returns: $(D_KEYWORD this).
+ */
+ BitVector opAssign(ubyte[] vector) pure nothrow @safe @nogc
+ in
+ {
+ assert(vector.length <= this.vector.length);
+ }
+ body
+ {
+ immutable delta = this.vector.length - vector.length;
+ if (delta > 0)
+ {
+ this.vector[0..delta] = 0;
+ }
+ this.vector[delta..$] = vector[0..$];
+ return this;
+ }
+
+ ///
+ unittest
+ {
+ ubyte[5] array1 = [234, 3, 252, 10, 18];
+ ubyte[3] array2 = [65, 13, 173];
+ auto bits = BitVector(array1);
+
+ bits = array2;
+ assert(bits[][0] == 0);
+ assert(bits[][1] == 0);
+ assert(bits[][2] == 65);
+ assert(bits[][3] == 13);
+ assert(bits[][4] == 173);
+
+ bits = array2[0..2];
+ assert(bits[][0] == 0);
+ assert(bits[][1] == 0);
+ assert(bits[][2] == 0);
+ assert(bits[][3] == 65);
+ assert(bits[][4] == 13);
+ }
+
+ /**
+ * Support for bitwise operations.
+ *
+ * Params:
+ * that = Another bit vector.
+ *
+ * Returns: $(D_KEYWORD this).
+ */
+ BitVector opOpAssign(string op)(BitVector that) pure nothrow @safe @nogc
+ if ((op == "^") || (op == "|") || (op == "&"))
+ {
+ return opOpAssign(op)(that.vector);
+ }
+
+ /// Ditto.
+ BitVector opOpAssign(string op)(ubyte[] that) pure nothrow @safe @nogc
+ if ((op == "^") || (op == "|") || (op == "&"))
+ in
+ {
+ assert(that.length <= vector.length);
+ }
+ body
+ {
+ for (int i = cast(int) vector.length - 1; i >= 0; --i)
+ {
+ mixin("vector[i] " ~ op ~ "= " ~ "that[i];");
+ }
+ immutable delta = vector.length - that.length;
+ if (delta)
+ {
+ static if (op == "&")
+ {
+ vector[0..delta] = 0;
+ }
+ }
+ return this;
+ }
+
+ ///
+ unittest
+ {
+ // [01000001, 00001101, 10101101]
+ ubyte[3] array1 = [65, 13, 173];
+ ubyte[3] array2 = [0b01010010, 0b10111110, 0b10111110];
+ auto bits = BitVector(array1);
+
+ bits |= array2;
+ assert(bits[][0] == 0b01010011);
+ assert(bits[][1] == 0b10111111);
+ assert(bits[][2] == 0b10111111);
+
+ bits &= array2;
+ assert(bits[][0] == array2[0]);
+ assert(bits[][1] == array2[1]);
+ assert(bits[][2] == array2[2]);
+
+ bits ^= array2;
+ assert(bits[][0] == 0);
+ assert(bits[][1] == 0);
+ assert(bits[][2] == 0);
+ }
+
+ /**
+ * Support for shift operations.
+ *
+ * Params:
+ * n = Number of bits.
+ *
+ * Returns: $(D_KEYWORD this).
+ */
+ BitVector opOpAssign(string op)(in size_t n) pure nothrow @safe @nogc
+ if ((op == "<<") || (op == ">>"))
+ {
+ if (n >= length)
+ {
+ vector[0..$] = 0;
+ }
+ else if (n != 0)
+ {
+ immutable bit = n % 8, step = n / 8;
+ immutable delta = 8 - bit;
+ size_t i, j;
+
+ static if (op == "<<")
+ {
+ for (j = step; j < vector.length - 1; ++i)
+ {
+ vector[i] = cast(ubyte)((vector[j] << bit)
+ | vector[++j] >> delta);
+ }
+ vector[i] = cast(ubyte)(vector[j] << bit);
+ vector[$ - step ..$] = 0;
+ }
+ else static if (op == ">>")
+ {
+ for (i = vector.length - 1, j = i - step; j > 0; --i)
+ {
+ vector[i] = cast(ubyte)((vector[j] >> bit)
+ | vector[--j] << delta);
+ }
+ vector[i] = cast(ubyte)(vector[j] >> bit);
+ vector[0..step] = 0;
+ }
+ }
+ return this;
+ }
+
+ ///
+ nothrow @safe @nogc unittest
+ {
+ ubyte[4] arr = [0b10111110, 0b11110010, 0b01010010, 0b01010011];
+ auto bits = BitVector(arr);
+
+ bits <<= 0;
+ assert(bits[][0] == 0b10111110 && bits[][1] == 0b11110010
+ && bits[][2] == 0b01010010 && bits[][3] == 0b01010011);
+
+ bits <<= 2;
+ assert(bits[][0] == 0b11111011 && bits[][1] == 0b11001001
+ && bits[][2] == 0b01001001 && bits[][3] == 0b01001100);
+
+ bits <<= 4;
+ assert(bits[][0] == 0b10111100 && bits[][1] == 0b10010100
+ && bits[][2] == 0b10010100 && bits[][3] == 0b11000000);
+
+ bits <<= 8;
+ assert(bits[][0] == 0b10010100 && bits[][1] == 0b10010100
+ && bits[][2] == 0b11000000 && bits[][3] == 0b00000000);
+
+ bits <<= 7;
+ assert(bits[][0] == 0b01001010 && bits[][1] == 0b01100000
+ && bits[][2] == 0b00000000 && bits[][3] == 0b00000000);
+
+ bits <<= 25;
+ assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000
+ && bits[][2] == 0b00000000 && bits[][3] == 0b00000000);
+
+ arr = [0b00110011, 0b11001100, 0b11111111, 0b01010101];
+ bits <<= 24;
+ assert(bits[][0] == 0b01010101 && bits[][1] == 0b00000000
+ && bits[][2] == 0b00000000 && bits[][3] == 0b00000000);
+
+ arr[1] = 0b11001100;
+ arr[2] = 0b11111111;
+ arr[3] = 0b01010101;
+ bits <<= 12;
+ assert(bits[][0] == 0b11001111 && bits[][1] == 0b11110101
+ && bits[][2] == 0b01010000 && bits[][3] == 0b00000000);
+
+ bits <<= 100;
+ assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000
+ && bits[][2] == 0b00000000 && bits[][3] == 0b00000000);
+
+ arr = [0b10111110, 0b11110010, 0b01010010, 0b01010011];
+ bits >>= 0;
+ assert(bits[][0] == 0b10111110 && bits[][1] == 0b11110010
+ && bits[][2] == 0b01010010 && bits[][3] == 0b01010011);
+
+ bits >>= 2;
+ assert(bits[][0] == 0b00101111 && bits[][1] == 0b10111100
+ && bits[][2] == 0b10010100 && bits[][3] == 0b10010100);
+
+ bits >>= 4;
+ assert(bits[][0] == 0b00000010 && bits[][1] == 0b11111011
+ && bits[][2] == 0b11001001 && bits[][3] == 0b01001001);
+
+ bits >>= 8;
+ assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000010
+ && bits[][2] == 0b11111011 && bits[][3] == 0b11001001);
+
+ bits >>= 7;
+ assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000
+ && bits[][2] == 0b00000101 && bits[][3] == 0b11110111);
+
+ bits >>= 25;
+ assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000
+ && bits[][2] == 0b00000000 && bits[][3] == 0b00000000);
+
+ arr = [0b00110011, 0b11001100, 0b11111111, 0b01010101];
+ bits >>= 24;
+ assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000
+ && bits[][2] == 0b00000000 && bits[][3] == 0b00110011);
+
+ arr[1] = 0b11001100;
+ arr[2] = 0b11111111;
+ arr[3] = 0b01010101;
+ bits >>= 12;
+ assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000
+ && bits[][2] == 0b00001100 && bits[][3] == 0b11001111);
+
+ bits >>= 100;
+ assert(bits[][0] == 0b00000000 && bits[][1] == 0b00000000
+ && bits[][2] == 0b00000000 && bits[][3] == 0b00000000);
+ }
+
+ /**
+ * Negates all bits.
+ *
+ * Returns: $(D_KEYWORD this).
+ */
+ BitVector opUnary(string op)() pure nothrow @safe @nogc
+ if (op == "~")
+ {
+ foreach (ref b; vector)
+ {
+ b = ~b;
+ }
+ return this;
+ }
+
+ ///
+ unittest
+ {
+ // [01000001, 00001101, 10101101]
+ ubyte[3] arr = [65, 13, 173];
+ auto bits = BitVector(arr);
+
+ ~bits;
+ assert(bits[][0] == 0b10111110);
+ assert(bits[][1] == 0b11110010);
+ assert(bits[][2] == 0b01010010);
+ }
+
+ /**
+ * Iterates through all bits.
+ *
+ * Params:
+ * dg = $(D_KEYWORD foreach) delegate.
+ *
+ * Returns: By $(D_PARAM dg) returned value.
+ */
+ int opApply(int delegate(size_t, bool) dg)
+ {
+ int result;
+ foreach (i, ref v; vector)
+ {
+ foreach (c; 0..8)
+ {
+ result = dg(i * 8 + c, (v & (0x80 >> c)) != 0);
+ if (result)
+ {
+ return result;
+ }
+ }
+ }
+ return result;
+ }
+
+ /// Ditto.
+ int opApply(int delegate(bool) dg)
+ {
+ int result;
+ foreach (ref v; vector)
+ {
+ foreach (c; 0..8)
+ {
+ result = dg((v & (0x80 >> c)) != 0);
+ if (result)
+ {
+ return result;
+ }
+ }
+ }
+ return result;
+ }
+
+ ///
+ unittest
+ {
+ ubyte[2] arr = [0b01000001, 0b00001101];
+ auto bits = BitVector(arr);
+ size_t c;
+
+ foreach (i, v; bits)
+ {
+ assert(i == c);
+ if (i == 1 || i == 7 || i == 15 || i == 13 || i == 12)
+ {
+ assert(v);
+ }
+ else
+ {
+ assert(!v);
+ }
+ ++c;
+ }
+ assert(c == 16);
+ }
+}
diff --git a/source/tanya/container/buffer.d b/source/tanya/container/buffer.d
index 4d01ad5..9dde930 100644
--- a/source/tanya/container/buffer.d
+++ b/source/tanya/container/buffer.d
@@ -7,7 +7,7 @@
* License: $(LINK2 https://www.mozilla.org/en-US/MPL/2.0/,
* Mozilla Public License, v. 2.0).
* Authors: $(LINK2 mailto:info@caraus.de, Eugene Wissner)
- */
+ */
module tanya.container.buffer;
import std.traits;
@@ -15,23 +15,23 @@ import tanya.memory;
version (unittest)
{
- private int fillBuffer(ubyte[] buffer,
- in size_t size,
- int start = 0,
- int end = 10) @nogc pure nothrow
- in
- {
- assert(start < end);
- }
- body
- {
- auto numberRead = end - start;
- for (ubyte i; i < numberRead; ++i)
- {
- buffer[i] = cast(ubyte) (start + i);
- }
- return numberRead;
- }
+ private int fillBuffer(ubyte[] buffer,
+ in size_t size,
+ int start = 0,
+ int end = 10) @nogc pure nothrow
+ in
+ {
+ assert(start < end);
+ }
+ body
+ {
+ auto numberRead = end - start;
+ for (ubyte i; i < numberRead; ++i)
+ {
+ buffer[i] = cast(ubyte) (start + i);
+ }
+ return numberRead;
+ }
}
/**
@@ -45,253 +45,253 @@ version (unittest)
* of the pended asynchronous call.
*
* Params:
- * T = Buffer type.
+ * T = Buffer type.
*/
struct ReadBuffer(T = ubyte)
- if (isScalarType!T)
+ if (isScalarType!T)
{
- /// Internal buffer.
- private T[] buffer_;
-
- /// Filled buffer length.
- private size_t length_;
-
- /// Start of available data.
- private size_t start;
-
- /// Last position returned with $(D_KEYWORD []).
- private size_t ring;
-
- /// Available space.
- private immutable size_t minAvailable = 1024;
-
- /// Size by which the buffer will grow.
- private immutable size_t blockSize = 8192;
-
- invariant
- {
- assert(length_ <= buffer_.length);
- assert(blockSize > 0);
- assert(minAvailable > 0);
- }
-
- /**
- * Creates a new read buffer.
- *
- * Params:
- * size = Initial buffer size and the size by which the buffer
- * will grow.
- * minAvailable = minimal size should be always available to fill.
- * So it will reallocate if $(D_INLINECODE
- * $(D_PSYMBOL free) < $(D_PARAM minAvailable)).
- * allocator = Allocator.
- */
- this(in size_t size,
- in size_t minAvailable = 1024,
- shared Allocator allocator = defaultAllocator) @trusted
- {
- this(allocator);
- this.minAvailable = minAvailable;
- this.blockSize = size;
- buffer_ = cast(T[]) allocator_.allocate(size * T.sizeof);
- }
-
- /// Ditto.
- this(shared Allocator allocator)
- in
- {
- assert(allocator_ is null);
- }
- body
- {
- allocator_ = allocator;
- }
-
- /**
- * Deallocates the internal buffer.
- */
- ~this() @trusted
- {
- allocator.deallocate(buffer_);
- }
-
- ///
- unittest
- {
- ReadBuffer!ubyte b;
- assert(b.capacity == 0);
- assert(b.length == 0);
- }
-
- /**
- * Returns: The size of the internal buffer.
- */
- @property size_t capacity() const
- {
- return buffer_.length;
- }
-
- /**
- * Returns: Data size.
- */
- @property size_t length() const
- {
- return length_ - start;
- }
-
- /// Ditto.
- alias opDollar = length;
-
- /**
- * Clears the buffer.
- *
- * Returns: $(D_KEYWORD this).
- */
- void clear()
- {
- start = length_ = ring;
- }
-
- /**
- * Returns: Available space.
- */
- @property size_t free() const
- {
- return length > ring ? capacity - length : capacity - ring;
- }
-
- ///
- unittest
- {
- ReadBuffer!ubyte b;
- size_t numberRead;
-
- assert(b.free == 0);
-
- // Fills the buffer with values 0..10
- numberRead = fillBuffer(b[], b.free, 0, 10);
- b += numberRead;
- assert(b.free == b.blockSize - numberRead);
- b.clear();
- assert(b.free == b.blockSize);
- }
-
- /**
- * Appends some data to the buffer.
- *
- * Params:
- * length = Number of the bytes read.
- *
- * Returns: $(D_KEYWORD this).
- */
- ref ReadBuffer opOpAssign(string op)(in size_t length)
- if (op == "+")
- {
- length_ += length;
- ring = start;
- return this;
- }
-
- ///
- unittest
- {
- ReadBuffer!ubyte b;
- size_t numberRead;
- ubyte[] result;
-
- // Fills the buffer with values 0..10
- numberRead = fillBuffer(b[], b.free, 0, 10);
- b += numberRead;
-
- result = b[0 .. $];
- assert(result[0] == 0);
- assert(result[1] == 1);
- assert(result[9] == 9);
- b.clear();
-
- // It shouldn't overwrite, but append another 5 bytes to the buffer
- numberRead = fillBuffer(b[], b.free, 0, 10);
- b += numberRead;
-
- numberRead = fillBuffer(b[], b.free, 20, 25);
- b += numberRead;
-
- result = b[0..$];
- assert(result[0] == 0);
- assert(result[1] == 1);
- assert(result[9] == 9);
- assert(result[10] == 20);
- assert(result[14] == 24);
- }
-
- /**
- * Params:
- * start = Start position.
- * end = End position.
- *
- * Returns: Array between $(D_PARAM start) and $(D_PARAM end).
- */
- T[] opSlice(in size_t start, in size_t end)
- {
- return buffer_[this.start + start .. this.start + end];
- }
-
- /**
- * Returns a free chunk of the buffer.
- *
- * Add ($(D_KEYWORD +=)) the number of the read bytes after using it.
- *
- * Returns: A free chunk of the buffer.
- */
- T[] opIndex()
- {
- if (start > 0)
- {
- auto ret = buffer_[0 .. start];
- ring = 0;
- return ret;
- }
- else
- {
- if (capacity - length < minAvailable)
- {
- void[] buf = buffer_;
- immutable cap = capacity;
- () @trusted {
- allocator.reallocate(buf, (cap + blockSize) * T.sizeof);
- buffer_ = cast(T[]) buf;
- }();
- }
- ring = length_;
- return buffer_[length_ .. $];
- }
- }
-
- ///
- unittest
- {
- ReadBuffer!ubyte b;
- size_t numberRead;
- ubyte[] result;
-
- // Fills the buffer with values 0..10
- numberRead = fillBuffer(b[], b.free, 0, 10);
- b += numberRead;
-
- assert(b.length == 10);
- result = b[0 .. $];
- assert(result[0] == 0);
- assert(result[9] == 9);
- b.clear();
- assert(b.length == 0);
- }
-
- mixin DefaultAllocator;
+ /// Internal buffer.
+ private T[] buffer_;
+
+ /// Filled buffer length.
+ private size_t length_;
+
+ /// Start of available data.
+ private size_t start;
+
+ /// Last position returned with $(D_KEYWORD []).
+ private size_t ring;
+
+ /// Available space.
+ private immutable size_t minAvailable = 1024;
+
+ /// Size by which the buffer will grow.
+ private immutable size_t blockSize = 8192;
+
+ invariant
+ {
+ assert(length_ <= buffer_.length);
+ assert(blockSize > 0);
+ assert(minAvailable > 0);
+ }
+
+ /**
+ * Creates a new read buffer.
+ *
+ * Params:
+ * size = Initial buffer size and the size by which the buffer
+ * will grow.
+ * minAvailable = minimal size should be always available to fill.
+ * So it will reallocate if $(D_INLINECODE
+ * $(D_PSYMBOL free) < $(D_PARAM minAvailable)).
+ * allocator = Allocator.
+ */
+ this(in size_t size,
+ in size_t minAvailable = 1024,
+ shared Allocator allocator = defaultAllocator) @trusted
+ {
+ this(allocator);
+ this.minAvailable = minAvailable;
+ this.blockSize = size;
+ buffer_ = cast(T[]) allocator_.allocate(size * T.sizeof);
+ }
+
+ /// Ditto.
+ this(shared Allocator allocator)
+ in
+ {
+ assert(allocator_ is null);
+ }
+ body
+ {
+ allocator_ = allocator;
+ }
+
+ /**
+ * Deallocates the internal buffer.
+ */
+ ~this() @trusted
+ {
+ allocator.deallocate(buffer_);
+ }
+
+ ///
+ unittest
+ {
+ ReadBuffer!ubyte b;
+ assert(b.capacity == 0);
+ assert(b.length == 0);
+ }
+
+ /**
+ * Returns: The size of the internal buffer.
+ */
+ @property size_t capacity() const
+ {
+ return buffer_.length;
+ }
+
+ /**
+ * Returns: Data size.
+ */
+ @property size_t length() const
+ {
+ return length_ - start;
+ }
+
+ /// Ditto.
+ alias opDollar = length;
+
+ /**
+ * Clears the buffer.
+ *
+ * Returns: $(D_KEYWORD this).
+ */
+ void clear()
+ {
+ start = length_ = ring;
+ }
+
+ /**
+ * Returns: Available space.
+ */
+ @property size_t free() const
+ {
+ return length > ring ? capacity - length : capacity - ring;
+ }
+
+ ///
+ unittest
+ {
+ ReadBuffer!ubyte b;
+ size_t numberRead;
+
+ assert(b.free == 0);
+
+ // Fills the buffer with values 0..10
+ numberRead = fillBuffer(b[], b.free, 0, 10);
+ b += numberRead;
+ assert(b.free == b.blockSize - numberRead);
+ b.clear();
+ assert(b.free == b.blockSize);
+ }
+
+ /**
+ * Appends some data to the buffer.
+ *
+ * Params:
+ * length = Number of the bytes read.
+ *
+ * Returns: $(D_KEYWORD this).
+ */
+ ref ReadBuffer opOpAssign(string op)(in size_t length)
+ if (op == "+")
+ {
+ length_ += length;
+ ring = start;
+ return this;
+ }
+
+ ///
+ unittest
+ {
+ ReadBuffer!ubyte b;
+ size_t numberRead;
+ ubyte[] result;
+
+ // Fills the buffer with values 0..10
+ numberRead = fillBuffer(b[], b.free, 0, 10);
+ b += numberRead;
+
+ result = b[0 .. $];
+ assert(result[0] == 0);
+ assert(result[1] == 1);
+ assert(result[9] == 9);
+ b.clear();
+
+ // It shouldn't overwrite, but append another 5 bytes to the buffer
+ numberRead = fillBuffer(b[], b.free, 0, 10);
+ b += numberRead;
+
+ numberRead = fillBuffer(b[], b.free, 20, 25);
+ b += numberRead;
+
+ result = b[0..$];
+ assert(result[0] == 0);
+ assert(result[1] == 1);
+ assert(result[9] == 9);
+ assert(result[10] == 20);
+ assert(result[14] == 24);
+ }
+
+ /**
+ * Params:
+ * start = Start position.
+ * end = End position.
+ *
+ * Returns: Array between $(D_PARAM start) and $(D_PARAM end).
+ */
+ T[] opSlice(in size_t start, in size_t end)
+ {
+ return buffer_[this.start + start .. this.start + end];
+ }
+
+ /**
+ * Returns a free chunk of the buffer.
+ *
+ * Add ($(D_KEYWORD +=)) the number of the read bytes after using it.
+ *
+ * Returns: A free chunk of the buffer.
+ */
+ T[] opIndex()
+ {
+ if (start > 0)
+ {
+ auto ret = buffer_[0 .. start];
+ ring = 0;
+ return ret;
+ }
+ else
+ {
+ if (capacity - length < minAvailable)
+ {
+ void[] buf = buffer_;
+ immutable cap = capacity;
+ () @trusted {
+ allocator.reallocate(buf, (cap + blockSize) * T.sizeof);
+ buffer_ = cast(T[]) buf;
+ }();
+ }
+ ring = length_;
+ return buffer_[length_ .. $];
+ }
+ }
+
+ ///
+ unittest
+ {
+ ReadBuffer!ubyte b;
+ size_t numberRead;
+ ubyte[] result;
+
+ // Fills the buffer with values 0..10
+ numberRead = fillBuffer(b[], b.free, 0, 10);
+ b += numberRead;
+
+ assert(b.length == 10);
+ result = b[0 .. $];
+ assert(result[0] == 0);
+ assert(result[9] == 9);
+ b.clear();
+ assert(b.length == 0);
+ }
+
+ mixin DefaultAllocator;
}
private unittest
{
- static assert(is(ReadBuffer!int));
+ static assert(is(ReadBuffer!int));
}
/**
@@ -304,385 +304,385 @@ private unittest
* reading, because it may allocate and move elements.
*
* Params:
- * T = Buffer type.
+ * T = Buffer type.
*/
struct WriteBuffer(T = ubyte)
- if (isScalarType!T)
+ if (isScalarType!T)
{
- /// Internal buffer.
- private T[] buffer_;
-
- /// Buffer start position.
- private size_t start;
-
- /// Buffer ring area size. After this position begins buffer overflow area.
- private size_t ring;
-
- /// Size by which the buffer will grow.
- private immutable size_t blockSize;
-
- /// The position of the free area in the buffer.
- private size_t position;
-
- invariant
- {
- assert(blockSize > 0);
- // Position can refer to an element outside the buffer if the buffer is full.
- assert(position <= buffer_.length);
- }
-
- /**
- * Params:
- * size = Initial buffer size and the size by which the buffer will
- * grow.
- * allocator = Allocator.
- *
- * Precondition: $(D_INLINECODE size > 0 && allocator !is null)
- */
- this(in size_t size, shared Allocator allocator = defaultAllocator) @trusted
- in
- {
- assert(size > 0);
- assert(allocator !is null);
- }
- body
- {
- blockSize = size;
- ring = size - 1;
- allocator_ = allocator;
- buffer_ = cast(T[]) allocator_.allocate(size * T.sizeof);
- }
-
- @disable this();
-
- /**
- * Deallocates the internal buffer.
- */
- ~this()
- {
- allocator.deallocate(buffer_);
- }
-
- /**
- * Returns: The size of the internal buffer.
- */
- @property size_t capacity() const
- {
- return buffer_.length;
- }
-
- /**
- * Note that $(D_PSYMBOL length) doesn't return the real length of the data,
- * but only the array length that will be returned with $(D_PSYMBOL opIndex)
- * next time. Be sure to call $(D_PSYMBOL opIndex) and set $(D_KEYWORD +=)
- * until $(D_PSYMBOL length) returns 0.
- *
- * Returns: Data size.
- */
- @property size_t length() const
- {
- if (position > ring || position < start) // Buffer overflowed
- {
- return ring - start + 1;
- }
- else
- {
- return position - start;
- }
- }
-
- /// Ditto.
- alias opDollar = length;
-
- ///
- unittest
- {
- auto b = WriteBuffer!ubyte(4);
- ubyte[3] buf = [48, 23, 255];
-
- b ~= buf;
- assert(b.length == 3);
- b += 2;
- assert(b.length == 1);
-
- b ~= buf;
- assert(b.length == 2);
- b += 2;
- assert(b.length == 2);
-
- b ~= buf;
- assert(b.length == 5);
- b += b.length;
- assert(b.length == 0);
- }
-
- /**
- * Returns: Available space.
- */
- @property size_t free() const
- {
- return capacity - length;
- }
-
- /**
- * Appends data to the buffer.
- *
- * Params:
- * buffer = Buffer chunk got with $(D_PSYMBOL opIndex).
- */
- ref WriteBuffer opOpAssign(string op)(in T[] buffer)
- if (op == "~")
- {
- size_t end, start;
-
- if (position >= this.start && position <= ring)
- {
- auto afterRing = ring + 1;
-
- end = position + buffer.length;
- if (end > afterRing)
- {
- end = afterRing;
- }
- start = end - position;
- buffer_[position .. end] = buffer[0 .. start];
- if (end == afterRing)
- {
- position = this.start == 0 ? afterRing : 0;
- }
- else
- {
- position = end;
- }
- }
-
- // Check if we have some free space at the beginning
- if (start < buffer.length && position < this.start)
- {
- end = position + buffer.length - start;
- if (end > this.start)
- {
- end = this.start;
- }
- auto areaEnd = end - position + start;
- buffer_[position .. end] = buffer[start .. areaEnd];
- position = end == this.start ? ring + 1 : end - position;
- start = areaEnd;
- }
-
- // And if we still haven't found any place, save the rest in the overflow area
- if (start < buffer.length)
- {
- end = position + buffer.length - start;
- if (end > capacity)
- {
- auto newSize = (end / blockSize * blockSize + blockSize) * T.sizeof;
- () @trusted {
- void[] buf = buffer_;
- allocator.reallocate(buf, newSize);
- buffer_ = cast(T[]) buf;
- }();
- }
- buffer_[position .. end] = buffer[start .. $];
- position = end;
- if (this.start == 0)
- {
- ring = capacity - 1;
- }
- }
-
- return this;
- }
-
- ///
- unittest
- {
- auto b = WriteBuffer!ubyte(4);
- ubyte[3] buf = [48, 23, 255];
-
- b ~= buf;
- assert(b.capacity == 4);
- assert(b.buffer_[0] == 48 && b.buffer_[1] == 23 && b.buffer_[2] == 255);
-
- b += 2;
- b ~= buf;
- assert(b.capacity == 4);
- assert(b.buffer_[0] == 23 && b.buffer_[1] == 255
- && b.buffer_[2] == 255 && b.buffer_[3] == 48);
-
- b += 2;
- b ~= buf;
- assert(b.capacity == 8);
- assert(b.buffer_[0] == 23 && b.buffer_[1] == 255
- && b.buffer_[2] == 48 && b.buffer_[3] == 23 && b.buffer_[4] == 255);
- }
-
- ///
- unittest
- {
- auto b = WriteBuffer!ubyte(2);
- ubyte[3] buf = [48, 23, 255];
-
- b ~= buf;
- assert(b.start == 0);
- assert(b.capacity == 4);
- assert(b.ring == 3);
- assert(b.position == 3);
- }
-
- /**
- * Sets how many bytes were written. It will shrink the buffer
- * appropriately. Always call it after $(D_PSYMBOL opIndex).
- *
- * Params:
- * length = Length of the written data.
- *
- * Returns: $(D_KEYWORD this).
- */
- ref WriteBuffer opOpAssign(string op)(in size_t length)
- if (op == "+")
- in
- {
- assert(length <= this.length);
- }
- body
- {
- auto afterRing = ring + 1;
- auto oldStart = start;
-
- if (length <= 0)
- {
- return this;
- }
- else if (position <= afterRing)
- {
- start += length;
- if (start > 0 && position == afterRing)
- {
- position = oldStart;
- }
- }
- else
- {
- auto overflow = position - afterRing;
-
- if (overflow > length)
- {
- immutable afterLength = afterRing + length;
- buffer_[start .. start + length] = buffer_[afterRing .. afterLength];
- buffer_[afterRing .. afterLength] = buffer_[afterLength .. position];
- position -= length;
- }
- else if (overflow == length)
- {
- buffer_[start .. start + overflow] = buffer_[afterRing .. position];
- position -= overflow;
- }
- else
- {
- buffer_[start .. start + overflow] = buffer_[afterRing .. position];
- position = overflow;
- }
- start += length;
-
- if (start == position)
- {
- if (position != afterRing)
- {
- position = 0;
- }
- start = 0;
- ring = capacity - 1;
- }
- }
- if (start > ring)
- {
- start = 0;
- }
- return this;
- }
-
- ///
- unittest
- {
- auto b = WriteBuffer!ubyte(6);
- ubyte[6] buf = [23, 23, 255, 128, 127, 9];
-
- b ~= buf;
- assert(b.length == 6);
- b += 2;
- assert(b.length == 4);
- b += 4;
- assert(b.length == 0);
- }
-
- /**
- * Returns a chunk with data.
- *
- * After calling it, set $(D_KEYWORD +=) to the length could be
- * written.
- *
- * $(D_PSYMBOL opIndex) may return only part of the data. You may need
- * to call it and set $(D_KEYWORD +=) several times until
- * $(D_PSYMBOL length) is 0. If all the data can be written,
- * maximally 3 calls are required.
- *
- * Returns: A chunk of data buffer.
- */
- T[] opSlice(in size_t start, in size_t end)
- {
- immutable internStart = this.start + start;
-
- if (position > ring || position < start) // Buffer overflowed
- {
- return buffer_[this.start .. ring + 1 - length + end];
- }
- else
- {
- return buffer_[this.start .. this.start + end];
- }
- }
-
- ///
- unittest
- {
- auto b = WriteBuffer!ubyte(6);
- ubyte[6] buf = [23, 23, 255, 128, 127, 9];
-
- b ~= buf;
- assert(b[0 .. $] == buf[0 .. 6]);
- b += 2;
-
- assert(b[0 .. $] == buf[2 .. 6]);
-
- b ~= buf;
- assert(b[0 .. $] == buf[2 .. 6]);
- b += b.length;
-
- assert(b[0 .. $] == buf[0 .. 6]);
- b += b.length;
- }
-
- /**
- * After calling it, set $(D_KEYWORD +=) to the length could be
- * written.
- *
- * $(D_PSYMBOL opIndex) may return only part of the data. You may need
- * to call it and set $(D_KEYWORD +=) several times until
- * $(D_PSYMBOL length) is 0. If all the data can be written,
- * maximally 3 calls are required.
- *
- * Returns: A chunk of data buffer.
- */
- T[] opIndex()
- {
- return opSlice(0, length);
- }
-
- mixin DefaultAllocator;
+ /// Internal buffer.
+ private T[] buffer_;
+
+ /// Buffer start position.
+ private size_t start;
+
+ /// Buffer ring area size. After this position begins buffer overflow area.
+ private size_t ring;
+
+ /// Size by which the buffer will grow.
+ private immutable size_t blockSize;
+
+ /// The position of the free area in the buffer.
+ private size_t position;
+
+ invariant
+ {
+ assert(blockSize > 0);
+ // Position can refer to an element outside the buffer if the buffer is full.
+ assert(position <= buffer_.length);
+ }
+
+ /**
+ * Params:
+ * size = Initial buffer size and the size by which the buffer will
+ * grow.
+ * allocator = Allocator.
+ *
+ * Precondition: $(D_INLINECODE size > 0 && allocator !is null)
+ */
+ this(in size_t size, shared Allocator allocator = defaultAllocator) @trusted
+ in
+ {
+ assert(size > 0);
+ assert(allocator !is null);
+ }
+ body
+ {
+ blockSize = size;
+ ring = size - 1;
+ allocator_ = allocator;
+ buffer_ = cast(T[]) allocator_.allocate(size * T.sizeof);
+ }
+
+ @disable this();
+
+ /**
+ * Deallocates the internal buffer.
+ */
+ ~this()
+ {
+ allocator.deallocate(buffer_);
+ }
+
+ /**
+ * Returns: The size of the internal buffer.
+ */
+ @property size_t capacity() const
+ {
+ return buffer_.length;
+ }
+
+ /**
+ * Note that $(D_PSYMBOL length) doesn't return the real length of the data,
+ * but only the array length that will be returned with $(D_PSYMBOL opIndex)
+ * next time. Be sure to call $(D_PSYMBOL opIndex) and set $(D_KEYWORD +=)
+ * until $(D_PSYMBOL length) returns 0.
+ *
+ * Returns: Data size.
+ */
+ @property size_t length() const
+ {
+ if (position > ring || position < start) // Buffer overflowed
+ {
+ return ring - start + 1;
+ }
+ else
+ {
+ return position - start;
+ }
+ }
+
+ /// Ditto.
+ alias opDollar = length;
+
+ ///
+ unittest
+ {
+ auto b = WriteBuffer!ubyte(4);
+ ubyte[3] buf = [48, 23, 255];
+
+ b ~= buf;
+ assert(b.length == 3);
+ b += 2;
+ assert(b.length == 1);
+
+ b ~= buf;
+ assert(b.length == 2);
+ b += 2;
+ assert(b.length == 2);
+
+ b ~= buf;
+ assert(b.length == 5);
+ b += b.length;
+ assert(b.length == 0);
+ }
+
+ /**
+ * Returns: Available space.
+ */
+ @property size_t free() const
+ {
+ return capacity - length;
+ }
+
+ /**
+ * Appends data to the buffer.
+ *
+ * Params:
+ * buffer = Buffer chunk got with $(D_PSYMBOL opIndex).
+ */
+ ref WriteBuffer opOpAssign(string op)(in T[] buffer)
+ if (op == "~")
+ {
+ size_t end, start;
+
+ if (position >= this.start && position <= ring)
+ {
+ auto afterRing = ring + 1;
+
+ end = position + buffer.length;
+ if (end > afterRing)
+ {
+ end = afterRing;
+ }
+ start = end - position;
+ buffer_[position .. end] = buffer[0 .. start];
+ if (end == afterRing)
+ {
+ position = this.start == 0 ? afterRing : 0;
+ }
+ else
+ {
+ position = end;
+ }
+ }
+
+ // Check if we have some free space at the beginning
+ if (start < buffer.length && position < this.start)
+ {
+ end = position + buffer.length - start;
+ if (end > this.start)
+ {
+ end = this.start;
+ }
+ auto areaEnd = end - position + start;
+ buffer_[position .. end] = buffer[start .. areaEnd];
+ position = end == this.start ? ring + 1 : end - position;
+ start = areaEnd;
+ }
+
+ // And if we still haven't found any place, save the rest in the overflow area
+ if (start < buffer.length)
+ {
+ end = position + buffer.length - start;
+ if (end > capacity)
+ {
+ auto newSize = (end / blockSize * blockSize + blockSize) * T.sizeof;
+ () @trusted {
+ void[] buf = buffer_;
+ allocator.reallocate(buf, newSize);
+ buffer_ = cast(T[]) buf;
+ }();
+ }
+ buffer_[position .. end] = buffer[start .. $];
+ position = end;
+ if (this.start == 0)
+ {
+ ring = capacity - 1;
+ }
+ }
+
+ return this;
+ }
+
+ ///
+ unittest
+ {
+ auto b = WriteBuffer!ubyte(4);
+ ubyte[3] buf = [48, 23, 255];
+
+ b ~= buf;
+ assert(b.capacity == 4);
+ assert(b.buffer_[0] == 48 && b.buffer_[1] == 23 && b.buffer_[2] == 255);
+
+ b += 2;
+ b ~= buf;
+ assert(b.capacity == 4);
+ assert(b.buffer_[0] == 23 && b.buffer_[1] == 255
+ && b.buffer_[2] == 255 && b.buffer_[3] == 48);
+
+ b += 2;
+ b ~= buf;
+ assert(b.capacity == 8);
+ assert(b.buffer_[0] == 23 && b.buffer_[1] == 255
+ && b.buffer_[2] == 48 && b.buffer_[3] == 23 && b.buffer_[4] == 255);
+ }
+
+ ///
+ unittest
+ {
+ auto b = WriteBuffer!ubyte(2);
+ ubyte[3] buf = [48, 23, 255];
+
+ b ~= buf;
+ assert(b.start == 0);
+ assert(b.capacity == 4);
+ assert(b.ring == 3);
+ assert(b.position == 3);
+ }
+
+ /**
+ * Sets how many bytes were written. It will shrink the buffer
+ * appropriately. Always call it after $(D_PSYMBOL opIndex).
+ *
+ * Params:
+ * length = Length of the written data.
+ *
+ * Returns: $(D_KEYWORD this).
+ */
+ ref WriteBuffer opOpAssign(string op)(in size_t length)
+ if (op == "+")
+ in
+ {
+ assert(length <= this.length);
+ }
+ body
+ {
+ auto afterRing = ring + 1;
+ auto oldStart = start;
+
+ if (length <= 0)
+ {
+ return this;
+ }
+ else if (position <= afterRing)
+ {
+ start += length;
+ if (start > 0 && position == afterRing)
+ {
+ position = oldStart;
+ }
+ }
+ else
+ {
+ auto overflow = position - afterRing;
+
+ if (overflow > length)
+ {
+ immutable afterLength = afterRing + length;
+ buffer_[start .. start + length] = buffer_[afterRing .. afterLength];
+ buffer_[afterRing .. afterLength] = buffer_[afterLength .. position];
+ position -= length;
+ }
+ else if (overflow == length)
+ {
+ buffer_[start .. start + overflow] = buffer_[afterRing .. position];
+ position -= overflow;
+ }
+ else
+ {
+ buffer_[start .. start + overflow] = buffer_[afterRing .. position];
+ position = overflow;
+ }
+ start += length;
+
+ if (start == position)
+ {
+ if (position != afterRing)
+ {
+ position = 0;
+ }
+ start = 0;
+ ring = capacity - 1;
+ }
+ }
+ if (start > ring)
+ {
+ start = 0;
+ }
+ return this;
+ }
+
+ ///
+ unittest
+ {
+ auto b = WriteBuffer!ubyte(6);
+ ubyte[6] buf = [23, 23, 255, 128, 127, 9];
+
+ b ~= buf;
+ assert(b.length == 6);
+ b += 2;
+ assert(b.length == 4);
+ b += 4;
+ assert(b.length == 0);
+ }
+
+ /**
+ * Returns a chunk with data.
+ *
+ * After calling it, set $(D_KEYWORD +=) to the length could be
+ * written.
+ *
+ * $(D_PSYMBOL opIndex) may return only part of the data. You may need
+ * to call it and set $(D_KEYWORD +=) several times until
+ * $(D_PSYMBOL length) is 0. If all the data can be written,
+ * maximally 3 calls are required.
+ *
+ * Returns: A chunk of data buffer.
+ */
+ T[] opSlice(in size_t start, in size_t end)
+ {
+ immutable internStart = this.start + start;
+
+ if (position > ring || position < start) // Buffer overflowed
+ {
+ return buffer_[this.start .. ring + 1 - length + end];
+ }
+ else
+ {
+ return buffer_[this.start .. this.start + end];
+ }
+ }
+
+ ///
+ unittest
+ {
+ auto b = WriteBuffer!ubyte(6);
+ ubyte[6] buf = [23, 23, 255, 128, 127, 9];
+
+ b ~= buf;
+ assert(b[0 .. $] == buf[0 .. 6]);
+ b += 2;
+
+ assert(b[0 .. $] == buf[2 .. 6]);
+
+ b ~= buf;
+ assert(b[0 .. $] == buf[2 .. 6]);
+ b += b.length;
+
+ assert(b[0 .. $] == buf[0 .. 6]);
+ b += b.length;
+ }
+
+ /**
+ * After calling it, set $(D_KEYWORD +=) to the length could be
+ * written.
+ *
+ * $(D_PSYMBOL opIndex) may return only part of the data. You may need
+ * to call it and set $(D_KEYWORD +=) several times until
+ * $(D_PSYMBOL length) is 0. If all the data can be written,
+ * maximally 3 calls are required.
+ *
+ * Returns: A chunk of data buffer.
+ */
+ T[] opIndex()
+ {
+ return opSlice(0, length);
+ }
+
+ mixin DefaultAllocator;
}
private unittest
{
- static assert(is(typeof(WriteBuffer!int(5))));
+ static assert(is(typeof(WriteBuffer!int(5))));
}
diff --git a/source/tanya/container/entry.d b/source/tanya/container/entry.d
index 1194f6b..cc74204 100644
--- a/source/tanya/container/entry.d
+++ b/source/tanya/container/entry.d
@@ -9,14 +9,14 @@
* License: $(LINK2 https://www.mozilla.org/en-US/MPL/2.0/,
* Mozilla Public License, v. 2.0).
* Authors: $(LINK2 mailto:info@caraus.de, Eugene Wissner)
- */
+ */
module tanya.container.entry;
package struct SEntry(T)
{
- /// Item content.
- T content;
+ /// Item content.
+ T content;
- /// Next item.
- SEntry* next;
+ /// Next item.
+ SEntry* next;
}
diff --git a/source/tanya/container/package.d b/source/tanya/container/package.d
index db8f025..7ba9f20 100644
--- a/source/tanya/container/package.d
+++ b/source/tanya/container/package.d
@@ -3,13 +3,16 @@
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
/**
+ * Abstract data types whose instances are collections of other objects.
+ *
* Copyright: Eugene Wissner 2016-2017.
* License: $(LINK2 https://www.mozilla.org/en-US/MPL/2.0/,
* Mozilla Public License, v. 2.0).
* Authors: $(LINK2 mailto:info@caraus.de, Eugene Wissner)
- */
+ */
module tanya.container;
+public import tanya.container.bitvector;
public import tanya.container.buffer;
public import tanya.container.list;
public import tanya.container.vector;
diff --git a/source/tanya/container/queue.d b/source/tanya/container/queue.d
index 6388013..48cc483 100644
--- a/source/tanya/container/queue.d
+++ b/source/tanya/container/queue.d
@@ -3,11 +3,13 @@
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
/**
+ * FIFO queue.
+ *
* Copyright: Eugene Wissner 2016-2017.
* License: $(LINK2 https://www.mozilla.org/en-US/MPL/2.0/,
* Mozilla Public License, v. 2.0).
* Authors: $(LINK2 mailto:info@caraus.de, Eugene Wissner)
- */
+ */
module tanya.container.queue;
import core.exception;
@@ -20,267 +22,267 @@ import tanya.memory;
* FIFO queue.
*
* Params:
- * T = Content type.
+ * T = Content type.
*/
struct Queue(T)
{
- /**
- * Removes all elements from the queue.
- */
- ~this()
- {
- while (!empty)
- {
- dequeue();
- }
- }
-
- /**
- * Returns how many elements are in the queue. It iterates through the queue
- * to count the elements.
- *
- * Returns: How many elements are in the queue.
- */
- size_t length() const
- {
- size_t len;
- for (const(SEntry!T)* i = first; i !is null; i = i.next)
- {
- ++len;
- }
- return len;
- }
-
- ///
- unittest
- {
- Queue!int q;
-
- assert(q.length == 0);
- q.enqueue(5);
- assert(q.length == 1);
- q.enqueue(4);
- assert(q.length == 2);
- q.enqueue(9);
- assert(q.length == 3);
-
- q.dequeue();
- assert(q.length == 2);
- q.dequeue();
- assert(q.length == 1);
- q.dequeue();
- assert(q.length == 0);
- }
-
- private void enqueueEntry(ref SEntry!T* entry)
- {
- if (empty)
- {
- first = rear = entry;
- }
- else
- {
- rear.next = entry;
- rear = rear.next;
- }
- }
-
- private SEntry!T* allocateEntry()
- {
- auto temp = cast(SEntry!T*) allocator.allocate(SEntry!T.sizeof);
- if (temp is null)
- {
- onOutOfMemoryError();
- }
- return temp;
- }
-
- /**
- * Inserts a new element.
- *
- * Params:
- * x = New element.
- */
- void enqueue(ref T x)
- {
- auto temp = allocateEntry();
-
- *temp = SEntry!T.init;
- temp.content = x;
-
- enqueueEntry(temp);
- }
-
- /// Ditto.
- void enqueue(T x)
- {
- auto temp = allocateEntry();
-
- moveEmplace(x, (*temp).content);
- (*temp).next = null;
-
- enqueueEntry(temp);
- }
-
- ///
- unittest
- {
- Queue!int q;
-
- assert(q.empty);
- q.enqueue(8);
- q.enqueue(9);
- assert(q.dequeue() == 8);
- assert(q.dequeue() == 9);
- }
-
- /**
- * Returns: $(D_KEYWORD true) if the queue is empty.
- */
- @property bool empty() const
- {
- return first is null;
- }
-
- ///
- unittest
- {
- Queue!int q;
- int value = 7;
-
- assert(q.empty);
- q.enqueue(value);
- assert(!q.empty);
- }
-
- /**
- * Move the position to the next element.
- *
- * Returns: Dequeued element.
- */
- T dequeue()
- in
- {
- assert(!empty);
- }
- body
- {
- auto n = first.next;
- T ret = move(first.content);
-
- allocator.dispose(first);
- first = n;
- return ret;
- }
-
- ///
- unittest
- {
- Queue!int q;
-
- q.enqueue(8);
- q.enqueue(9);
- assert(q.dequeue() == 8);
- assert(q.dequeue() == 9);
- }
-
- /**
- * $(D_KEYWORD foreach) iteration. The elements will be automatically
- * dequeued.
- *
- * Params:
- * dg = $(D_KEYWORD foreach) body.
- *
- * Returns: The value returned from $(D_PARAM dg).
- */
- int opApply(scope int delegate(ref size_t i, ref T) @nogc dg)
- {
- int result;
-
- for (size_t i = 0; !empty; ++i)
- {
- auto e = dequeue();
- if ((result = dg(i, e)) != 0)
- {
- return result;
- }
- }
- return result;
- }
-
- /// Ditto.
- int opApply(scope int delegate(ref T) @nogc dg)
- {
- int result;
-
- while (!empty)
- {
- auto e = dequeue();
- if ((result = dg(e)) != 0)
- {
- return result;
- }
- }
- return result;
- }
-
- ///
- unittest
- {
- Queue!int q;
-
- size_t j;
- q.enqueue(5);
- q.enqueue(4);
- q.enqueue(9);
- foreach (i, e; q)
- {
- assert(i != 2 || e == 9);
- assert(i != 1 || e == 4);
- assert(i != 0 || e == 5);
- ++j;
- }
- assert(j == 3);
- assert(q.empty);
-
- j = 0;
- q.enqueue(5);
- q.enqueue(4);
- q.enqueue(9);
- foreach (e; q)
- {
- assert(j != 2 || e == 9);
- assert(j != 1 || e == 4);
- assert(j != 0 || e == 5);
- ++j;
- }
- assert(j == 3);
- assert(q.empty);
- }
-
- private SEntry!T* first;
- private SEntry!T* rear;
-
- mixin DefaultAllocator;
+ /**
+ * Removes all elements from the queue.
+ */
+ ~this()
+ {
+ while (!empty)
+ {
+ dequeue();
+ }
+ }
+
+ /**
+ * Returns how many elements are in the queue. It iterates through the queue
+ * to count the elements.
+ *
+ * Returns: How many elements are in the queue.
+ */
+ size_t length() const
+ {
+ size_t len;
+ for (const(SEntry!T)* i = first; i !is null; i = i.next)
+ {
+ ++len;
+ }
+ return len;
+ }
+
+ ///
+ unittest
+ {
+ Queue!int q;
+
+ assert(q.length == 0);
+ q.enqueue(5);
+ assert(q.length == 1);
+ q.enqueue(4);
+ assert(q.length == 2);
+ q.enqueue(9);
+ assert(q.length == 3);
+
+ q.dequeue();
+ assert(q.length == 2);
+ q.dequeue();
+ assert(q.length == 1);
+ q.dequeue();
+ assert(q.length == 0);
+ }
+
+ private void enqueueEntry(ref SEntry!T* entry)
+ {
+ if (empty)
+ {
+ first = rear = entry;
+ }
+ else
+ {
+ rear.next = entry;
+ rear = rear.next;
+ }
+ }
+
+ private SEntry!T* allocateEntry()
+ {
+ auto temp = cast(SEntry!T*) allocator.allocate(SEntry!T.sizeof);
+ if (temp is null)
+ {
+ onOutOfMemoryError();
+ }
+ return temp;
+ }
+
+ /**
+ * Inserts a new element.
+ *
+ * Params:
+ * x = New element.
+ */
+ void enqueue(ref T x)
+ {
+ auto temp = allocateEntry();
+
+ *temp = SEntry!T.init;
+ temp.content = x;
+
+ enqueueEntry(temp);
+ }
+
+ /// Ditto.
+ void enqueue(T x)
+ {
+ auto temp = allocateEntry();
+
+ moveEmplace(x, (*temp).content);
+ (*temp).next = null;
+
+ enqueueEntry(temp);
+ }
+
+ ///
+ unittest
+ {
+ Queue!int q;
+
+ assert(q.empty);
+ q.enqueue(8);
+ q.enqueue(9);
+ assert(q.dequeue() == 8);
+ assert(q.dequeue() == 9);
+ }
+
+ /**
+ * Returns: $(D_KEYWORD true) if the queue is empty.
+ */
+ @property bool empty() const
+ {
+ return first is null;
+ }
+
+ ///
+ unittest
+ {
+ Queue!int q;
+ int value = 7;
+
+ assert(q.empty);
+ q.enqueue(value);
+ assert(!q.empty);
+ }
+
+ /**
+ * Move the position to the next element.
+ *
+ * Returns: Dequeued element.
+ */
+ T dequeue()
+ in
+ {
+ assert(!empty);
+ }
+ body
+ {
+ auto n = first.next;
+ T ret = move(first.content);
+
+ allocator.dispose(first);
+ first = n;
+ return ret;
+ }
+
+ ///
+ unittest
+ {
+ Queue!int q;
+
+ q.enqueue(8);
+ q.enqueue(9);
+ assert(q.dequeue() == 8);
+ assert(q.dequeue() == 9);
+ }
+
+ /**
+ * $(D_KEYWORD foreach) iteration. The elements will be automatically
+ * dequeued.
+ *
+ * Params:
+ * dg = $(D_KEYWORD foreach) body.
+ *
+ * Returns: The value returned from $(D_PARAM dg).
+ */
+ int opApply(scope int delegate(ref size_t i, ref T) @nogc dg)
+ {
+ int result;
+
+ for (size_t i = 0; !empty; ++i)
+ {
+ auto e = dequeue();
+ if ((result = dg(i, e)) != 0)
+ {
+ return result;
+ }
+ }
+ return result;
+ }
+
+ /// Ditto.
+ int opApply(scope int delegate(ref T) @nogc dg)
+ {
+ int result;
+
+ while (!empty)
+ {
+ auto e = dequeue();
+ if ((result = dg(e)) != 0)
+ {
+ return result;
+ }
+ }
+ return result;
+ }
+
+ ///
+ unittest
+ {
+ Queue!int q;
+
+ size_t j;
+ q.enqueue(5);
+ q.enqueue(4);
+ q.enqueue(9);
+ foreach (i, e; q)
+ {
+ assert(i != 2 || e == 9);
+ assert(i != 1 || e == 4);
+ assert(i != 0 || e == 5);
+ ++j;
+ }
+ assert(j == 3);
+ assert(q.empty);
+
+ j = 0;
+ q.enqueue(5);
+ q.enqueue(4);
+ q.enqueue(9);
+ foreach (e; q)
+ {
+ assert(j != 2 || e == 9);
+ assert(j != 1 || e == 4);
+ assert(j != 0 || e == 5);
+ ++j;
+ }
+ assert(j == 3);
+ assert(q.empty);
+ }
+
+ private SEntry!T* first;
+ private SEntry!T* rear;
+
+ mixin DefaultAllocator;
}
///
unittest
{
- Queue!int q;
+ Queue!int q;
- q.enqueue(5);
- assert(!q.empty);
+ q.enqueue(5);
+ assert(!q.empty);
- q.enqueue(4);
- q.enqueue(9);
+ q.enqueue(4);
+ q.enqueue(9);
- assert(q.dequeue() == 5);
+ assert(q.dequeue() == 5);
- foreach (i, ref e; q)
- {
- assert(i != 0 || e == 4);
- assert(i != 1 || e == 9);
- }
- assert(q.empty);
+ foreach (i, ref e; q)
+ {
+ assert(i != 0 || e == 4);
+ assert(i != 1 || e == 9);
+ }
+ assert(q.empty);
}
diff --git a/source/tanya/container/vector.d b/source/tanya/container/vector.d
index c14e060..0f3dc00 100644
--- a/source/tanya/container/vector.d
+++ b/source/tanya/container/vector.d
@@ -3,7 +3,7 @@
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
/**
- * One-dimensional array.
+ * Single-dimensioned array.
*
* Copyright: Eugene Wissner 2016-2017.
* License: $(LINK2 https://www.mozilla.org/en-US/MPL/2.0/,
@@ -166,10 +166,10 @@ struct Vector(T)
* range or a static array $(D_PARAM init).
*
* Params:
- * R = Type of the initial range or size of the static array.
- * init = Values to initialize the array with.
- * to generate a list.
- * allocator = Allocator.
+ * R = Type of the initial range or size of the static array.
+ * init = Values to initialize the array with.
+ * to generate a list.
+ * allocator = Allocator.
*/
this(size_t R)(T[R] init, shared Allocator allocator = defaultAllocator)
{
@@ -200,9 +200,9 @@ struct Vector(T)
* If $(D_PARAM init) is passed by reference, it will be copied.
*
* Params:
- * R = Vector type.
- * init = Source vector.
- * allocator = Allocator.
+ * R = Vector type.
+ * init = Source vector.
+ * allocator = Allocator.
*/
this(R)(ref R init, shared Allocator allocator = defaultAllocator)
if (is(Unqual!R == Vector))
@@ -268,8 +268,8 @@ struct Vector(T)
* Creates a new $(D_PSYMBOL Vector).
*
* Params:
- * len = Initial length of the vector.
- * allocator = Allocator.
+ * len = Initial length of the vector.
+ * allocator = Allocator.
*/
this(in size_t len, shared Allocator allocator = defaultAllocator)
{
@@ -281,9 +281,9 @@ struct Vector(T)
* Creates a new $(D_PSYMBOL Vector).
*
* Params:
- * len = Initial length of the vector.
- * init = Initial value to fill the vector with.
- * allocator = Allocator.
+ * len = Initial length of the vector.
+ * init = Initial value to fill the vector with.
+ * allocator = Allocator.
*/
this(in size_t len, T init, shared Allocator allocator = defaultAllocator) @trusted
{
@@ -399,7 +399,7 @@ struct Vector(T)
* Expands/shrinks the vector.
*
* Params:
- * len = New length.
+ * len = New length.
*/
@property void length(in size_t len) @trusted
{
@@ -456,7 +456,7 @@ struct Vector(T)
* affected.
*
* Params:
- * size = Desired size.
+ * size = Desired size.
*/
void reserve(in size_t size) @trusted
{
@@ -514,7 +514,7 @@ struct Vector(T)
* $(D_PARAM length).
*
* Params:
- * size = Desired size.
+ * size = Desired size.
*/
void shrink(in size_t size) @trusted
{
@@ -585,7 +585,7 @@ struct Vector(T)
* length, all elements are removed.
*
* Params:
- * howMany = How many elements should be removed.
+ * howMany = How many elements should be removed.
*
* Returns: The number of elements removed
*/
@@ -618,7 +618,7 @@ struct Vector(T)
* Remove all elements beloning to $(D_PARAM r).
*
* Params:
- * r = Range originally obtained from this vector.
+ * r = Range originally obtained from this vector.
*
* Returns: Elements in $(D_PARAM r) after removing.
*
@@ -674,8 +674,8 @@ struct Vector(T)
* Inserts the $(D_PARAM el) into the vector.
*
* Params:
- * R = Type of the inserted value(s) (single value, range or static array).
- * el = Value(s) should be inserted.
+ * R = Type of the inserted value(s) (single value, range or static array).
+ * el = Value(s) should be inserted.
*
* Returns: The number of elements inserted.
*/
@@ -767,9 +767,9 @@ struct Vector(T)
* Inserts $(D_PARAM el) before or after $(D_PARAM r).
*
* Params:
- * R = Type of the inserted value(s) (single value, range or static array).
- * r = Range originally obtained from this vector.
- * el = Value(s) should be inserted.
+ * R = Type of the inserted value(s) (single value, range or static array).
+ * r = Range originally obtained from this vector.
+ * el = Value(s) should be inserted.
*
* Returns: The number of elements inserted.
*/
@@ -946,8 +946,8 @@ struct Vector(T)
* Assigns a value to the element with the index $(D_PARAM pos).
*
* Params:
- * value = Value.
- * pos = Position.
+ * value = Value.
+ * pos = Position.
*
* Returns: Assigned value.
*
@@ -987,8 +987,8 @@ struct Vector(T)
* Assigns a range or a static array.
*
* Params:
- * R = Range type or static array length.
- * value = Value.
+ * R = Range type or static array length.
+ * value = Value.
*
* Returns: Assigned value.
*
@@ -1025,7 +1025,7 @@ struct Vector(T)
/**
* Params:
- * pos = Index.
+ * pos = Index.
*
* Returns: The value at a specified index.
*
@@ -1073,7 +1073,7 @@ struct Vector(T)
* Comparison for equality.
*
* Params:
- * that = The vector to compare with.
+ * that = The vector to compare with.
*
* Returns: $(D_KEYWORD true) if the vectors are equal, $(D_KEYWORD false)
* otherwise.
@@ -1099,8 +1099,8 @@ struct Vector(T)
* Comparison for equality.
*
* Params:
- * R = Right hand side type.
- * that = Right hand side vector range.
+ * R = Right hand side type.
+ * that = Right hand side vector range.
*
* Returns: $(D_KEYWORD true) if the vector and the range are equal,
* $(D_KEYWORD false) otherwise.
@@ -1135,7 +1135,7 @@ struct Vector(T)
* $(D_KEYWORD foreach) iteration.
*
* Params:
- * dg = $(D_KEYWORD foreach) body.
+ * dg = $(D_KEYWORD foreach) body.
*
* Returns: The value returned from $(D_PARAM dg).
*/
@@ -1301,8 +1301,8 @@ struct Vector(T)
/**
* Params:
- * i = Slice start.
- * j = Slice end.
+ * i = Slice start.
+ * j = Slice end.
*
* Returns: A range that iterates over elements of the container from
* index $(D_PARAM i) up to (excluding) index $(D_PARAM j).
@@ -1380,11 +1380,11 @@ struct Vector(T)
* Slicing assignment.
*
* Params:
- * R = Type of the assigned slice or length of the static array should be
- * assigned.
- * value = New value (single value, input range or static array).
- * i = Slice start.
- * j = Slice end.
+ * R = Type of the assigned slice or length of the static array should be
+ * assigned.
+ * value = New value (single value, input range or static array).
+ * i = Slice start.
+ * j = Slice end.
*
* Returns: Slice with the assigned part of the vector.
*
generated by cgit v1.2.3 (git 2.26.2) at 2026-06-27 08:03:22 +0000