module doodle.containers.stack;

class Stack(T) {
    this() {
        _data.length = 1;
    }

    bool isEmpty() {
        return _depth == 0;
    }

    void push(T t) {
        if (_depth == _data.length) {
            // Need it to grow
            _data.length = 2 * _data.length;
        }

        _data[_depth] = t;
        ++_depth;
    }

    T pop() {
        assert(!isEmpty());
        --_depth;
        auto t = _data[_depth];
        _data[_depth] = T.init;
        return t;
    }

    T top() {
        assert(!isEmpty());
        return _data[_depth - 1];
    }

    void top(T t) {
        assert(!isEmpty());
        _data[_depth - 1] = t;
    }

    void clear() {
        while (_depth > 0) {
            --_depth;
            _data[_depth] = T.init;
        }
    }

    void shrink() {
        size_t new_l = _data.length;
        do new_l /= 2; while (new_l > _depth * 2);
        _data.length = new_l;
    }

    void capacity(size_t l) {
        if (l > _data.length) {
            size_t new_l = _data.length;
            do new_l *= 2; while (new_l < l);
            _data.length = new_l;
        }
    }

    private {
        size_t capacity() {
            return _data.length;
        }

        size_t depth() {
            return _depth;
        }

        T[] _data;          //  capacity
        size_t _depth;
    }
}
unittest {
    auto s = new Stack!(int);

    assert(s.capacity() == 1);

    assert(s.depth() == 0);
    s.push(15);
    assert(s.depth() == 1);
    assert(s.top() == 15);
    assert(s.pop() == 15);
    assert(s.depth() == 0);
    assert(s.isEmpty());

    assert(s.capacity() == 1);
    s.push(12);
    assert(s.capacity() == 1);
    s.push(13);
    assert(s.capacity() == 2);
    s.push(14);
    assert(s.depth() == 3);
    assert(s.capacity() == 4);
    s.push(s.pop());
    assert(s.capacity() == 4);
}