LinkedList.d

module robikstuff.LinkedList;

import std.algorithm;

/**
 * Represents doubly linked list.
 * 
 * Adding or removing elements at both list ends is constant time,
 * accessing element at specified index takes O(n).
 * List length is cached internally, so accessing list length is always O(1).
 * 
 * Main linked list methods:
 * 
 *  - addLast(el) append(el)
 *    Adds element to end of the list.
 * 
 *  - addFirst(el) prepend(el)
 *    Adds element to beggining of the list.
 * 
 *  - insertAt(index, el)
 *    Inserts element at specified index.
 * 
 *  - removeFirst()
 *    Removes element from beggining of the list.
 * 
 *  - removeLast()
 *    Removes element from end of the list.
 * 
 *  - removeAt(index)
 *    Removes element from list at specified index.
 * 
 *  - replaceAt(index, el)
 *    Replaces element data with new data specified at index.
 * 
 *  - toArray()
 *    Creates array with list data.
 * 
 *  - clear()
 *    Removes all element in list.
 * 
 * 
 * Properties:
 * 
 *  - .empty
 *    Determines if list has no elements.
 * 
 *  - .length
 *    Number of elements in list.
 * 
 *  - .first
 *    First element in list. May be the same as .last if list has one element.
 * 
 *  - .last
 *    Last element in list. May be the same as .first if list has one element.
 * 
 *  - .range
 *    Returns range that iterates list.
 * 
 * 
 * Operators overloaded:
 * 
 *  - index, slice, equals, in, dollar
 * 
 * Examples:
 * ---
 * auto list = new List!string;
 * list.append("a");
 * list.append("b");
 * assert(list[0] == "a");
 * assert(list[-1] == "b");
 * 
 * writeln(map!`a ~ "_1"`(list));
 * ---
 */
class LinkedList(T)
{
    protected Node* _first;
    protected Node* _last;
    protected size_t _count;
    
    protected struct Node
    {
        T data;
        Node* prev;
        Node* next;
        
        this(T data, Node* prev = null, Node* next = null)
        {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
    }
    
    
    /*
     * Returns pointer to node at specified index.
     * 
     * Null if index is out of range
     */
    protected Node* nodeAt(size_t i)
    {
        auto n = _first;
        
        if(!i) return n;
        
        while(n !is null)
        {
            if(--i == 0) break;
            
            n = n.next;
        }
        
        return n;
    }
    
    
    /*
     * Returns pointer to node at specified index, starting from end.
     * 
     * Null if index is out of range
     */
    protected Node* nodeAtFromEnd(size_t i)
    {
        auto n = _last;
        
        if(!i) return n;
        
        while(n !is null)
        {
            if(--i == 0) break;
            
            n = n.prev;
        }
        
        return n;
    }
    
    
    /**
     * Adds element at end of the list.
     * 
     * Params:
     *  el = Element to add
     */
    void addLast(T el)
    {
        _count += 1;
        
        if(_first is null) {
            _first = new Node(el);
            _last = _first;
        } else {
            auto n = new Node(el, _last);
            _last.next = n;
            _last = n;
        }
    }
    
    
    /// ditto
    alias append = addLast;
    
    
    /**
     * Adds element to beggining of the list.
     * 
     * Params:
     *  el = Element to add
     */
    void addFirst(T el)
    {
        _count += 1;
        auto n = new Node(el, null, _first);
        if(_first !is null)
            _first.prev = n;
        else
            _last = n;
        _first = n;
    }
    
    
    /// ditto
    alias prepend = addFirst;
    
    
    /**
     * Inserts element at specifed element in list.
     * 
     * If index is 0 or equal to list length, cost is constant,
     * otherwise it's linear.
     * 
     * Params:
     *  index = Index at which insert element
     *  el = Element to insert
     * 
     * Throws:
     *  OutOfRange if index is bigger than list length.
     */
    void insertAt(size_t index, T el)
    {   
        if(index == 0) {
            prepend(el);
        } else if(index == _count) {
            append(el);
        } else {
            auto node = nodeAt(index);
            if(node is null) {
                throw new OutOfRange();
            }
            
            _count += 1;
            auto n = new Node(el, node, node.next);
            node.next.prev = n;
            node.next = n;
        }
    }
    
    
    /**
     * Removes first element from list
     * 
     * Throws:
     *  AssertError if list is empty.
     */
    void removeFirst()
    {
        assert(!empty, "Cannot remove element from empty list.");
        _count -= 1;
        if(_first.next is null) {
            _first = null;
        } else {
            _first = _first.next;
        }
    }
    
    
    /**
     * Removes first element from list
     * 
     * Throws:
     *  AssertError if list is empty.
     */
    void removeLast()
    {
        assert(!empty, "Cannot remove element from empty list.");
        _count -= 1;
        _last = _last.prev;
        _last.next = null;
    }
    
    
    /**
     * Removes element from list with specified index.
     * 
     * Params:
     *  index = Index of element to remove.
     */
    void removeAt(size_t index)
    {
        if(index == 0) {
            removeFirst();
        } else if(index == _count - 1) {
            removeLast();
        } else {
            auto node = nodeAt(index + 1);
            if(node is null) {
                throw new OutOfRange();
            }
            _count -= 1;
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }
    
    
    /**
     * Replaces element at specified index.
     * 
     * Params:
     *  index = Index of element to replace
     *  el = Value to replace with
     */
    void replaceAt(size_t index, T el)
    {
        auto n = nodeAt(index + 1);
        if(n is null) {
            throw new OutOfRange();
        }
        
        n.data = el;
    }
    
    
    /**
     * Removes all elements from list
     */
    void clear()
    {
        _first = null;
        _last = null;
    }
    
    
    /**
     * Creates new array with list data.
     * 
     * Algorithm complexity is O(n)
     * 
     * Returns:
     *  Array with list data
     */
    T[] toArray()
    {
        T[] ret;
        ret.reserve(_count);
        auto n = _first;
        
        while(n !is null) {
            ret ~= n.data;
            n = n.next;
        }
        
        return ret;
    }
    
    
    /**
     * Checks if list is empty
     * 
     * Returns:
     *  True if list has no elements, false otherwise.
     */
    @property bool empty()
    {
        return _first is null;
    }
    
    
    /**
     * Number of elements in list.
     * 
     * List length is cached, and accessing it takes O(1).
     * 
     * Returns:
     *  List length
     */
    @property size_t length()
    {   
        return _count;
    }
    
    
    /**
     * Value of first element.
     * 
     * Throws:
     *  AssetsError if list is empty
     * 
     * Returns:
     *  First element
     */
    @property T first()
    {
        if(_first is null) {
            assert(0, "Trying to read from empty list");
        }
        
        return _first.data;
    }
    
    
    /**
     * Value of last element.
     * 
     * Throws:
     *  AssetsError if list is empty
     * 
     * Returns:
     *  Last element
     */
    @property T last()
    {
        if(_last is null) {
            assert(0, "Trying to read from empty list");
        }
        
        return _last.data;
    }
    
    
    /**
     * List range
     */
    @property ListRange range()
    {
        return ListRange(_first, _last);
    }
    
    
    // -------------------------- OPERATORS -------------------------------------
    
    /**
     * Checks if specified element is in list.
     * 
     * Performs O(n) operations.
     * 
     * Returns:
     *  True if element is in list, false otherwise.
     */
    bool opIn_r(T el)
    {
        return (countUntil(range, el) > -1);
    }
    
    
    /**
     * Gets element at specified index.
     * 
     * Performs O(n) operations.
     * 
     * Params:
     *  index = Element index. Can be negative.
     * 
     * Returns:
     *  Element data
     */
    T opIndex(ptrdiff_t index)
    {
        Node* node;
        if(index < 0) {
            index = _count + index;
            node = nodeAtFromEnd(index - 1);
        } else {
            node = nodeAt(index + 1);
        }
        
        
        if(node is null) {
            throw new OutOfRange();
        }
        
        return node.data;
    }
    
    
    /**
     * Gets elements with specic indexes.
     * 
     * Throws:
     *  OutOfRange if any of indexes is bigger than list length.
     * 
     * Params:
     *  indexes... = Array of indexes
     * 
     * Returns:
     *  Elements
     */
    T[] opIndex(ptrdiff_t[] indexes...)
    {
        T[] ret;
        ret.reserve(indexes.length);
        
        foreach(i; indexes)
        {
            ret ~= this[i];
        }
        
        return ret;
    }
    
    
    /**
     * Gets list elements fitting specified range.
     * 
     * Negative indexes are supported.
     * 
     * Params:
     *  start = Start index
     *  end = End index.
     * 
     * Returns:
     *  Array of list elements sliced
     */
    T[] opSlice(ptrdiff_t start, ptrdiff_t end)
    {
        if(start < 0)
            start = _count + start;
        
        if(end < 0)
            end = _count + end;
        
        T[] ret;
        ptrdiff_t diff;
        
        if(start < end)
            diff = end - start;
        else if(start > end)
            diff = start - end;
        
        ret.reserve(diff);
        auto node = nodeAt(start + 1);
            
        if(node is null) {
            throw new OutOfRange();
        }
        
        while(node !is null && diff--) 
        {
            ret ~= node.data;
            
            if(start < end)
                node = node.next;
            else
                node = node.prev;
        }
        
        return ret;
    }
    
    
    /**
     * Compares two lists.
     */
    override bool opEquals(Object o)
    {
        auto list = cast(typeof(this))o;
        
        if(list is null)
            return false;
        
        if(list.length != this.length)
            return false;
        
        auto node = _first;
        foreach(element; list.range)
        {
            if(element != node.data)
                return false;
            
            node = node.next;
        }
        
        return true;
    }
    
    
    /**
     * Gets list length
     * 
     * Allows for '$' usage in list indexing or slicing.
     */
    size_t opDollar(size_t dimm)()
    {
        return _count;
    }
    
    // -------------------------- RANGE -------------------------------------
    
    private struct ListRange
    {
        private Node* _front;
        private Node* _back;
        
        
        
        this(Node* back, Node* last)
        {
            _front = back;
            _back = last;
        }
        
        
        @property bool empty()
        {
            return (_front is null) || (_back is null);
        }
        
        
        void popFront()
        {
            _front = _front.next;
        }
        
        
        T front()
        {
            return _front.data;
        }
        
        void popBack()
        {
            _back = _back.prev;
        }
        
        T back()
        {
            return _back.data;
        }
        
        
        ListRange save()
        {
            return this;
        }
    }
    
}

unittest
{
    import std.array;
    
    void assertThrows(void delegate() dg)
    {
        try {
            dg();
            assert(false);
        } catch{}
    }
    
    auto list = new LinkedList!int;
    assert(list.empty);
    assert(list.length == 0);
    
    list.addLast(1);
    assert(list.first == list.last);
    assert(list.last == 1);
    assert(list.length == 1);
    assert(list.toArray() == [1]);
    assert(!list.empty);
    
    list.insertAt(1, 3);
    assert(list.toArray() == [1, 3]);
    assert(list.length == 2);
    assert(list.last == 3);
    
    list.insertAt(1, 2);
    assert(list.toArray() == [1, 2, 3]);
    assert(list.length == 3);
    assert(list.last == 3);
    
    list.insertAt(0, 0);
    assert(list.toArray() == [0, 1, 2, 3]);
    assert(list.length == 4);
    
    list.addFirst(-1);
    assert(list.toArray() == [-1, 0, 1, 2, 3]);
    assert(list.length == 5);
    
    list.replaceAt(0, -2);
    assert(list.first == -2);
    assert(list.toArray() == [-2, 0, 1, 2, 3]);
    assert(2 in list);
    
    list.removeFirst();
    assert(list.toArray() == [0,1,2,3]);
    assert(list[1] == 1);
    assert(list[-1] == 2);
    assert(list.first == 0);
    assert(list.length == 4);
    
    
    list.replaceAt(3, 6);
    assert(list.last == 6);
    assert(list.toArray() == [0, 1, 2, 6]);
    
    list.removeLast();
    assert(list.toArray() == [0,1,2]);
    assert(list.length == 3);
    assert(list.last == 2);
    
    list.replaceAt(1, 11);
    assert(list.toArray() == [0,11,2]);
    
    list.removeAt(1);
    assert(list.toArray() == [0,2]);
    assert(list.length == 2);
    assert(list.last == 2);
    
    list.removeAt(1);
    assert(list.toArray() == [0]);
    assert(list.length == 1);
    assert(list.last == 0);
    
    assertThrows({
        list.removeAt(1);
    });
    list.removeAt(0);
    assert(list.toArray() == []);
    assert(list.length == 0);
    assertThrows({
        list.last;
    });
    
    auto list2 = new LinkedList!string;
    list2.addFirst("a");
    assert(list2.first == list2.last);
    assert(list2.first == "a");
    assert(list2.length == 1);
    list2.clear();
    assertThrows({
            list.first;
    });
    assertThrows({
            list.last;
    });
    
    assert(list2.empty);
    list2.addLast("a");
    
    list2 = new LinkedList!string;
    assert(list2.empty);
    assertThrows({
        list2.first;
    });
    list2.addLast("first");
    assert(!list2.empty);
    assert(list2.first == "first");
    assert(list2.first == list2.last);
    
    list2.addLast("second");    
    assert("second" in list2);
    assert(array(list2.range) == ["first", "second"]);
    
    assert(list2[0..1] == ["first"]);
    assert(list2[1..0] == ["second"]);
    assert(list2[1..2] == ["second"]);
    assert(list2[$-1] == "second");
    assert(list2[$-2] == "first");
    
    assertThrows({
        list2[2..1];
    });
    
    auto list3 = new LinkedList!string;
    list3.append("first");
    assert(list3 != list2);
    list3.append("second");
    assert(list3 == list2);
}

Stack.d

module robikstuff.Stack;

import std.string,
       std.algorithm;


/**
 * Represents stack data structure.
 * 
 * Stack operates on dynamic array, which can be accessed with `.array` property.
 * It implements Range interface, which makes possible iterate over it and callable
 * with std.algorithm functions.
 * 
 * Main stack methods:
 * 
 *  - clear()
 *    Cleans all elements from stack.
 * 
 *  - push(value)
 *    Pushes element on stack.
 * 
 *  - pop()
 *    Returns element on the stack and removes it.
 * 
 *  - peek()
 *    Returns top element from stack without removing it.
 * 
 *  - toArray()
 *    Returns dynamic array with stack data.
 * 
 * 
 * Properties:
 * 
 *  - .length
 *    Number of elements on stack.
 * 
 *  - .size
 *    Stack size/capacity specified.
 * 
 *  - .top
 *    Element on stack's top.
 * 
 * 
 * Operators overloaded:
 * 
 *  - index, slice, in, apply, dollar, equals
 * 
 * 
 * Stack can be initialized in two ways:
 * 
 * - With size specified compile time(static array is used)
 * ----
 *  auto stack = new Stack!(int, 5);
 * ----
 * 
 * - With size specified run time(dynamic array is used)
 * ----
 *  auto stack = new Stack!int(5);
 * ----
 * 
 * Note: `std.algorithm` functions work on stack from its end, so
 * functions like countUntil will return element position from 
 * end of the stack(not from the beginning).
 */
class Stack(T, int asize = 0)
{
    protected size_t _size;
    protected size_t _count;
    
    static if(asize == 0) {
        protected T[]    _array;
    } else {
        protected T[asize] _array;
    }
    
    
    /**
     * Creates new stack instance
     */
    this()
    {
        static if(asize == 0) {
            _size = size_t.max;
            _array.length = 1;
        } else {
            _size = asize;
        }
    }
    
    
    /**
     * Creates new stack instance with elements limit
     * 
     * This can be only used if static size was not specified.
     * 
     * Examples:
     * ---
     * auto stack = new Stack!int(1);
     * stack.push(1,2); // Throws StackOverflow
     * ---
     * 
     * ---
     * auto stack = new Stack!(int, 2)(5); // Error: Size specified twice
     * ---
     * 
     * Params:
     *  size = Size of stack.
     */
  this(size_t size)
	{
        static if(asize == 0) {
    		_size = size;
            _array.length = size;
        } else {
            assert(0, format("Cannot create stack with new size(%d), size already specified(%d)", size, asize));
        }
	}
    
    
    /**
     * Creates new stack instance from another stack
     * 
     * Params:
     *  base = Stack to copy
     */
    this(typeof(this) base)
    {
        _array = base.toArray();
        _count = base.length;
        _size  = base.size;
    }
    
    
    /**
     * Creates new stack instance from array
     * 
     * Params:
     *  base = Stack to copy
     */
    this(T[] array)
    {
        _array = array;
    }
    
    
    /**
     * Adds new element to stack.
     * 
     * Params:
     *  value = Value to add to stack.
     * 
     * Throws:
     *  StackOverflow if stack if full
     */
    void push(T value)
    {
        if(_count + 1 > _size) {
            throw new StackOverflow();
        }
        
        static if(asize == 0)
        {
            if(_count + 1 > _array.length) {
                _array.length = _array.length * 2;
            }
        }
        
        _array[_count++] = value;
    }
    
    
    /**
     * Pushes multiple values to stack.
     * 
     * Examples:
     * ----
     * auto s = new Stack!int();
     * s.push(1,2,3,4,5);
     * assert(s.length == 5);
     * ----
     * 
     * Throws:
     *  StackOverflow exception if stack is full.
     * 
     * Params:
     *  values... = Values to push
     */
    void push(T[] values...)
    {
        if(_count + values.length > _size) {
            throw new StackOverflow();
        }
        
        
        static if(asize == 0)
        {
            if(_count + values.length > _array.length) {
                _array.length = _array.length + values.length * 2;
            }
        }
        
        foreach(value; values)
        {
            _array[_count++] = value;
        }
    }
    
    
    /**
     * Takes element from stack.
     * 
     * Throws:
     *  StackUnderflow if stack is empty.
     * 
     * Returns:
     *  Removed value
     */
    T pop()
    {
        if(_count - 1 < 0)
            throw new StackUnderflow();
        
        return _array[--_count];
    }
    
    
    /**
     * Takes element from stack's top without removing it.
     * 
     * Throws:
     *  StackUnderflow if stack is empty.
     * 
     * Returns:
     *  Element on stack top.
     */
    T peek()
    {
        if(empty)
            throw new StackUnderflow();
        
        return _array[_count - 1];
    }
    
    
    /**
     * Cleans up stack.
     * 
     * Returns:
     *  This
     */
    typeof(this) clear()
    {
        _array = [];
        _count = 0;
        
        return this;
    }
    
    
    /**
     * Creates copy of this stack.
     * 
     * Returns:
     *  Clone of this stack.
     */
    typeof(this) clone()
    {
        return new typeof(this)(this);
    }
    
    
    /**
     * Array with stack data.
     * 
     * Note that length of returned array may not represent
     * real count of stack elements. To get real length of array
     * use `stack.length` method.
     * 
     * Returns:
     *  Stack as array
     */
    T[] toArray()
    {
        return _array.dup;
    }
    
    
    /**
     * Takes element from stack's top without removing it.
     * 
     * Returns:
     *  Element on stack top.
     */
    @property T top()
    {
        return peek();
    }
    
    
    /**
     * Stack size, if set.
     * 
     * If stack size was not set, 0 is returned.
     * 
     * Returns:
     *  Stack size
     */
    @property size_t size()
    {
        return _size;
    }
    
    
    /**
     * Numbers of elements on the stack.
     * 
     * Returns:
     *  Stack elements count
     */
    @property size_t length()
    {
        return _count;
    }
    
    
    /**
     * Numbers of elements on the stack.
     * 
     * Returns:
     *  Stack length
     */
    @property size_t index()
    {
        return _count;
    }
    
    
    /**
     * Checks if stack is empty
     * 
     * Returns:
     *  True if stack is empty, false otherwise.
     */
    @property bool empty()
    {
        return _count == 0;
    }
    
    
    /**
     * Checks if stack if full.
     * 
     * If stack size is not set, this function always returns false.
     * 
     * Returns:
     *  True if stack is full, false otherwise.
     */
    @property bool full()
    {
        return _count >= _size;
    }
    
    
    
    // -------------------------- OPERATORS -------------------------------------
    
    /**
     * Allows to iterate stack with current iteration index and element.
     * 
     * Examples:
     * ----
     * auto stack = new Stack!int;
     * stack.push(1,2,3,4);
     * foreach(element; stack)
     * {
     *      write(element); /// 4321
     * }
     * ----
     */
    int opApply(int delegate(uint, T) dg)
    {
        int result;
        for (int i = _count; i > 0; i--)
        {
            result = dg(cast(uint)i, _array[i]);
            
            if (result) break;
        }
        return result;
    }
    
    
    /**
     * Allows to iterate stack elements
     */
    int opApply(int delegate(T) dg)
    {
        int result;
        for (int i = _count; i > 0; i--)
        {
            result = dg(_array[i]);
            
            if (result) break;
        }
        return result;
    }
    
    
    /**
     * Gets nth element in stack, counting from stack top.
     * 
     * Throws:
     *  OutOfRange if range is bigger than stack length.
     * 
     * Params:
     *  i = Element index
     * 
     * Returns:
     *  Element at specified index
     */
    T opIndex(size_t i)
    {
        if(i > _count) {
            throw new OutOfRange();
        }
        
        return _array[_count - i - 1];
    }
    
    
    /**
     * Gets elements with specic indexes, counting from stack top.
     * 
     * Throws:
     *  OutOfRange if any of indexes is bigger than stack length.
     * 
     * Params:
     *  indexes... = Array of indexes
     * 
     * Returns:
     *  Elements
     */
    T[] opIndex(size_t[] indexes...)
    {
        T[] ret;
        ret.reserve(indexes.length);
        
        foreach(i; indexes)
        {
            ret ~= this[i];
        }
        
        return ret;
    }
    
    
    /**
     * Compares two stacks
     * 
     * Params:
     *  rhs = Stack to compare.s
     * 
     * Returns:
     *  True if stacks are equal, false otherwise.
     */
    override bool opEquals(Object rhs)
    {
        auto stack = cast(typeof(this))rhs;
        if(stack is null)
            return false;
        
        if(stack.length != this.length)
            return false;
        
        if(stack.toArray() != this.toArray())
            return false;
        
        return true;
    }
    
    
    /**
     * Slices stack, counting from stack's top.
     * 
     * Params:
     *  s = Starting index
     *  e = Ending index
     * 
     * Returns:
     *  Array of elements sliced.
     */
    T[] opSlice(size_t s, size_t e)
    {
        if(s > _count || e > _count)
            throw new OutOfRange();
        
        assert(s < e, "Stack Slice can not be reversed");
        
        T[] ret;
        ret.reserve(e-s);
        
        for(int i = s; i < e; i++)
        {
            ret ~= this[i];
        }
        
        return ret;
    }
    
    
    /**
     * Gets stack length
     * 
     * Allows for '$' usage in stack indexing or slicing.
     */
    size_t opDollar(size_t dimm)()
    {
        return _count;
    }
    
    
    /**
     * Checks if specified element is on stack.
     * 
     * Params:
     *  el = Element to check.
     * 
     * Returns:
     *  True if element is on stack, false otherwise.
     */
    bool opIn_r(T el)
    {
        return _array[].countUntil(el) != -1;
    }
    
    
    
    // -------------------------- RANGE -------------------------------------
    
    alias peek  front;
    alias pop   popFront;
    alias clone save;
    alias push  put;
}



/**
 * Thrown when tried to push to full stack.
 */
class StackOverflow : Exception
{
    this(string file = __FILE__, uint line = __LINE__)
    {
        super("Stack Overflow", file, line);
    }
}


/**
 * Thrown when tried to pop/peek empty stack.
 */
class StackUnderflow : Exception
{
    this(string file = __FILE__, uint line = __LINE__)
    {
        super("Stack Underflow", file, line);
    }
}


class OutOfRange : Exception
{
    this(string file = __FILE__, uint line = __LINE__)
    {
        super("Out of Range", file, line);
    }
}



unittest
{
    import std.range;
    void assertThrows(void delegate() dg)
    {
        try {
            dg();
            assert(false);
        } catch{}
    }
    
    Stack!int si = new Stack!int();
    assert(si.empty);
    si.push(5);
    assert(countUntil(si, 5) == 0);
    assert(si.length == 1);
    assert(si[0] == 5);
    assert(si.peek() == 5);
    assert(si[$-1] == 5);
    assertThrows({
        auto t = si[1];
    });
    assert(si.pop() == 5);
    assert(si.empty);
    
    si.push(1,2,3);
    assert(si[0] == 3);
    assert(si[0, 1, 2] == [3,2,1]);
    assert(si[0..$] == [3,2,1]);
    si.clear();
    assert(si.length == 0);
    assert(si.empty);
    
    si = new Stack!int(1);
    assert(si.empty);
    si.push(2);
    assert(si.full);
    assertThrows({
        si.push(1);
    });
    assert(si.length == 1);
    assert(si.peek() == 2);
    assert(si.pop() == 2);
    assert(si.empty);
    
    si = new Stack!int();
    si.push(1,2,3,4,5);
    assert(si.length == 5);
    
    
    auto stack = new Stack!(int, 5);
    assert(stack.empty);
    assert(stack.size == 5);
    stack.push(1,2,3,4,5);
    assertThrows({
        si.push(1);
    });
    assert(stack.length == 5);
    assert(stack.full);
    
    assertThrows({
        auto s = new Stack!(int, 5)(6);
    });
    assert(stack != si);
    auto s1 = new Stack!string();
    auto s2 = new Stack!string();
    assert(s1 == s2);
    s1.push("a");
    assert(s1 != s2);
    s2.push("a");
    assert(s1 == s2);
    s1.clear();
    s2.clear();
    assert(s1 == s2);
    
    static assert(isForwardRange!(typeof(stack)));
    static assert(isForwardRange!(typeof(si)));
    
    si = new Stack!int;
    si.push(1,2,3,4);
    assert(countUntil(si, 4) ==0);
    assert(1 in si);
    assert(6 !in si);
}