Sunday, October 29, 2017

We’ve covered a lot of OpenGL ground this year, but then all of a sudden I needed some kind of stack. Stacks are easily implemented using arrays, but I wanted to be able to push/pop on both ends in a reasonably efficient way. I also wanted it to be dynamic in the sense that there is no maximum size known beforehand. Thus I came up with a data structure that actually turned out to be a deque (pronounced as ‘deck’). There is a std::deque in the C++ STL, but for some reason I always like to code my own. I know it’s much time wasted, but it also builds experience.

The deque is a crossover between a queue and stack, or even queue and vector (array). You can append items at the end, but you can also efficiently prepend items to the beginning, without shifting any elements in place like you would with an array. At the same time, it’s more efficient than a regular queue because it does fewer memory allocation calls. The deque accomplishes this by internally being a list of arrays.

The image shows the linked list of arrays. Each array is a building block for the internals of a deque, and I like to call them “deque elements”. Each deque element has prev and next pointers to chain-link them together. They also have start and end indices, depicted by the red arrows.

The deque instance itself is depicted by the purple circle. It holds two pointers, head and tail, to the first and the last deque element. These pointers allow quick access to both ends of the data structure, and allow growing the deque in both directions.

What happens when you append an item? We follow the deque’s head pointer to the last deque element, and insert the item at the end of the array. Shift the end red arrow one position to the right. If the array is now full, we can extend the deque by chain-linking a new deque element behind it, and update the deque’s head pointer to point to this new final deque element. The new deque element will be empty with both the start and end index at zero.

If we now add an item to the beginning, we follow the deque’s tail pointer to the first deque element. There we can insert the item at the start of the array. Shift the start red arrow one position to the left. If the start index goes past zero, then the deque element is full, and we must chain-link a new deque element to the front of the list. This new deque element will start out with both the start and end indices at the end of the array.

The deque may grow both ‘left’ and ‘right’. When creating a new deque, you can have the very first deque element start with both red arrows at the center of the array.

Besides growing, we can also pop off items at any end. This will shrink the red arrows down until they meet, at which point the deque element is empty and can be deallocated.

In code, the deque element can be embedded inside a deque class as a nested private struct. The deque_elem structure is not exposed outside class deque.

template <typename T>
class deque {

    struct deque_elem {
        static const int DATA_SIZE = 16;

        deque_elem *prev, *next;
        T data[DATA_SIZE];
        int start, end;

        ...
    };

    deque_elem *head, *tail;
    unsigned int length;

public:
    ...

    unsigned int len(void) const { return length; }

    void insert(const T& item) { ... }
    void append(const T& item) { ... }
    T pop(void) { ... ; return item; }
    T pop(int idx) { ... ; return item; }
};

Note how the data type T (the template parameter) is part of the deque_elem, but deque_elem itself is not explicitly a parameterized type. The complete type of the private struct is deque<T>::deque_elem, but we practically never type it out full.

The methods for appending and popping off items at the end go like this:

void append(const T& item) {
    assert(head != nullptr);
    if (head->full()) {
        // allocate new deque_elem
        deque_elem *new_elem = new deque_elem();
        new_elem->prev = head;
        head->next = new_elem;
        head = new_elem;
    }
    head->append(item);
    length++;
}

T pop(void) {
    assert(head != nullptr);
    assert(length > 0);
    T item = head->pop();
    length--;
    if (head->empty() && head->prev != nullptr) {
        // deallocate last deque_elem
        deque_elem *p = head;
        head = head->prev;
        head->next = nullptr;
        delete p;
    }
    return item;
}

Note how we pass the action of appending or popping on to the deque element code, where the remaining work to do is just a simple array operation. Inserting and popping at the front is much the same, but uses the tail pointer and grows in the opposite direction.

Deque instances can be combined (the add operation) by chain-linking them together. Be mindful however that now a deque element somewhere in the middle can be in a state of ‘not full’. This is important to take into account because of the following.

A good deque implementation can also do indexed access, just like a regular array. Taking a good look at the image above, you can see how that would work. It requires traversing the chain-linked deque elements. From this follows that you can also add a random access iterator, which may be a nice topic for another time.