Compiler Explorer

Source code

/*
* Based on zig std.BoundedArray from https://github.com/jedisct1/zig-bounded-array
* license: MIT
*/

module bounded_array;

import core.stdc.string : memcpy, memmove;

/**
 * A structure containing a fixed-size array, as well as the length currently being used.
 * It can be used as a variable-length array that can be freely resized up to the size of the backing array.
 * Useful to pass around small arrays whose exact size is only known at runtime, but whose maximum size
 * is known at compile-time, without requiring dynamic allocation.
 *
 * Bounded arrays are easier and safer to use than maintaining buffers and active lengths separately,
 * or involving structures that include pointers.
 * They can also be safely copied like any value, as they don't use any internal pointers.
 */
struct BoundedArray(T, size_t capacity)
{
    private T[capacity] buffer;
    private size_t _len = 0;

/// Initializes a bounded array with a given length.
    /// Asserts if the initial length exceeds the capacity.
    this(size_t initialLen) @nogc nothrow pure @safe
    {
        assert(initialLen <= capacity, "Initial length exceeds capacity");
        _len = initialLen;
    }

/// Creates a bounded array from a slice.
    /// Asserts if the slice length exceeds the capacity.
    static BoundedArray fromSlice(const(T)[] s) @nogc nothrow pure @trusted
    {
        assert(s.length <= capacity, "Slice length exceeds capacity");
        BoundedArray result;
        memcpy(&result.buffer[0], &s[0], s.length * T.sizeof);
        result._len = s.length;
        return result;
    }

/// Returns a mutable slice of the used portion.
    T[] slice() @nogc nothrow pure @safe
    {
        return buffer[0 .. _len];
    }

/// Returns a const slice of the used portion.
    const(T)[] constSlice() const @nogc nothrow pure @safe
    {
        return buffer[0 .. _len];
    }

/// Resizes the array to a new length.
    /// Asserts if the new length exceeds the capacity.
    void resize(size_t newLen) @nogc nothrow pure @safe
    {
        assert(newLen <= capacity, "New length exceeds capacity");
        _len = newLen;
    }

/// Gets the value at the given index.
    /// Asserts if the index is out of bounds.
    ref T get(size_t i) @nogc nothrow pure @safe
    {
        assert(i < _len, "Index out of bounds");
        return buffer[i];
    }

/// Gets the const value at the given index.
    /// Asserts if the index is out of bounds.
    ref const(T) get(size_t i) const @nogc nothrow pure @safe
    {
        assert(i < _len, "Index out of bounds");
        return buffer[i];
    }

/// Sets the value at the given index.
    /// Asserts if the index is out of bounds.
    void set(size_t i, T value) @nogc nothrow pure @safe
    {
        assert(i < _len, "Index out of bounds");
        buffer[i] = value;
    }

/// Reserves space for one more element and returns a reference to it.
    /// Asserts if the array is full.
    ref T addOne() @nogc nothrow pure @safe
    {
        assert(_len < capacity, "No space left");
        _len++;
        return buffer[_len - 1];
    }

/// Appends a value to the array.
    /// Asserts if the array is full.
    void append(T value) @nogc nothrow pure @safe
    {
        addOne() = value;
    }

/// Appends a slice to the array.
    /// Asserts if there is not enough space.
    void appendSlice(const(T)[] s) @nogc nothrow pure @trusted
    {
        assert(_len + s.length <= capacity, "No space left for slice");
        memcpy(&buffer[0] + _len, &s[0], s.length * T.sizeof);
        _len += s.length;
    }

/// Pops the last element.
    /// Asserts if the array is empty.
    T pop() @nogc nothrow pure @safe
    {
        assert(_len > 0, "Pop from empty array");
        _len--;
        return buffer[_len];
    }

/// Inserts a value at the given index.
    /// Asserts if the array is full or index out of bounds.
    void insert(size_t i, T value) @nogc nothrow pure @trusted
    {
        assert(i <= _len, "Index out of bounds");
        assert(_len < capacity, "No space left");
        if (i < _len)
        {
            memmove(&buffer[0] + i + 1, &buffer[0] + i, (_len - i) * T.sizeof);
        }
        buffer[i] = value;
        _len++;
    }

/// Removes the element at the given index by swapping with the last and popping.
    /// Asserts if index out of bounds.
    void swapRemove(size_t i) @nogc nothrow pure @safe
    {
        assert(i < _len, "Index out of bounds");
        buffer[i] = pop();
    }

/// Clears the array by setting length to 0.
    void clear() @nogc nothrow pure @safe
    {
        _len = 0;
    }

/// The current length.
    @property size_t length() const @nogc nothrow pure @safe
    {
        return _len;
    }
}

version (unittest)
{
    import std.exception : assertThrown;

@("Initialize BoundedArray") unittest
    {
        auto arr = BoundedArray!(int, 10)(5);
        assert(arr.length == 5);
        assert(arr.slice().length == 5);
        assert(arr.constSlice().length == 5);
    }

@("Create from slice") unittest
    {
        int[] data = [1, 2, 3];
        auto arr = BoundedArray!(int, 5).fromSlice(data);
        assert(arr.length == 3);
        assert(arr.slice() == [1, 2, 3]);
        assertThrown!Error(BoundedArray!(int, 2).fromSlice(data));
    }

@("Resize array") unittest
    {
        auto arr = BoundedArray!(int, 10)(3);
        arr.resize(5);
        assert(arr.length == 5);
        assertThrown!Error(arr.resize(11));
    }

@("Get and set elements") unittest
    {
        auto arr = BoundedArray!(int, 5)(2);
        arr.set(0, 42);
        arr.set(1, 43);
        assert(arr.get(0) == 42);
        assert(arr.get(1) == 43);
        assertThrown!Error(arr.get(2));
        assertThrown!Error(arr.set(2, 44));
    }

@("Append elements") unittest
    {
        auto arr = BoundedArray!(int, 5)(0);
        arr.append(1);
        arr.append(2);
        assert(arr.length == 2);
        assert(arr.slice() == [1, 2]);
        arr.appendSlice([3, 4]);
        assert(arr.length == 4);
        assert(arr.slice() == [1, 2, 3, 4]);
        assertThrown!Error(arr.appendSlice([5, 6]));
    }

@("Pop elements") unittest
    {
        auto arr = BoundedArray!(int, 5).fromSlice([1, 2, 3]);
        assert(arr.pop() == 3);
        assert(arr.length == 2);
        assert(arr.slice() == [1, 2]);
        assertThrown!Error(BoundedArray!(int, 5)(0).pop());
    }

@("Insert elements") unittest
    {
        auto arr = BoundedArray!(int, 5).fromSlice([1, 2, 3]);
        arr.insert(1, 42);
        assert(arr.length == 4);
        assert(arr.slice() == [1, 42, 2, 3]);
        arr.insert(0, 43);
        assert(arr.length == 5);
        assert(arr.slice() == [43, 1, 42, 2, 3]);
        assertThrown!Error(arr.insert(0, 44)); // Full
        assertThrown!Error(arr.insert(6, 44)); // Out of bounds
    }

@("Swap remove elements") unittest
    {
        auto arr = BoundedArray!(int, 5).fromSlice([1, 2, 3, 4]);
        arr.swapRemove(1);
        assert(arr.length == 3);
        assert(arr.slice() == [1, 4, 3]);
        assertThrown!Error(arr.swapRemove(3));
    }

@("Clear array") unittest
    {
        auto arr = BoundedArray!(int, 5).fromSlice([1, 2, 3]);
        arr.clear();
        assert(arr.length == 0);
        assert(arr.slice() == []);
    }

@("Const operations") unittest
    {
        const arr = BoundedArray!(int, 5).fromSlice([1, 2, 3]);
        assert(arr.length == 3);
        assert(arr.constSlice() == [1, 2, 3]);
        assert(arr.get(1) == 2);
    }
}
else
{
    extern (C)
    void main()
    {
        import core.stdc.stdio : printf;

// Initialize a BoundedArray for integers with capacity 10
        auto arr = BoundedArray!(int, 10)(0);

// Clear the array
        scope (exit)
        {
            arr.clear();
            printf("\nAfter clearing: length = %zu\n", arr.length);
        }

// Append some elements
        arr.append(1);
        arr.append(2);
        arr.append(3);
        printf("After appending [1, 2, 3]: length = %zu\n", arr.length);
        foreach (i, val; arr.slice())
        {
            printf("arr[%zu] = %d\n", i, val);
        }

// Append a slice
        int[2] slice = [4, 5];
        arr.appendSlice(slice);
        printf("\nAfter appending slice [4, 5]: length = %zu\n", arr.length);
        foreach (i, val; arr.slice())
        {
            printf("arr[%zu] = %d\n", i, val);
        }

// Insert an element
        arr.insert(2, 42);
        printf("\nAfter inserting 42 at index 2: length = %zu\n", arr.length);
        foreach (i, val; arr.slice())
        {
            printf("arr[%zu] = %d\n", i, val);
        }

// Pop an element
        int popped = arr.pop();
        printf("\nPopped element: %d, new length = %zu\n", popped, arr.length);

// Swap remove an element
        arr.swapRemove(1);
        printf("\nAfter swapRemove at index 1: length = %zu\n", arr.length);
        foreach (i, val; arr.slice())
        {
            printf("arr[%zu] = %d\n", i, val);
        }
    }
}