queue_bag.h

Go to the documentation of this file.

#ifndef XMIPP_QUEUE_BAG_H
#define XMIPP_QUEUE_BAG_H

#include <vector>
#include <type_traits>

#define RFS_QUEUE_BAG_RUN_TESTS 0

namespace rfs {

    void testQueueBag();

    template<typename T>
    class queue_bag {
        static_assert(std::is_trivially_copyable<T>::value,
                      "queue_bag is designed only for trivially copyable elements");

    private:
        T *elements = nullptr;
        size_t elementsCapacity = 0;

        size_t head = 0;
        size_t tail = 0;
        size_t size = 0;

        size_t internalIndex(size_t externalIndex) const {
            assert(size > 0);
            assert(externalIndex < size);
            size_t index = head + externalIndex;
            if (index >= elementsCapacity) {
                index -= elementsCapacity;
            }
            return index;
        }

    public:

#if RFS_QUEUE_BAG_RUN_TESTS
        queue_bag() {
            testQueueBag();
        }
#endif

        void addLast(T object) noexcept {
            if (size == elementsCapacity) {
                resize(elementsCapacity * 2);
            }

            elements[tail++] = object;
            if (tail == elementsCapacity) {
                tail = 0;
            }
            size++;
        }

        void addFirst(T object) noexcept {
            if (size == elementsCapacity) {
                resize(elementsCapacity * 2);
            }

            if (head == 0) {
                head = elementsCapacity - 1;
            } else {
                head--;
            }
            elements[head] = object;
            size++;
        }

        void ensureCapacity(size_t additional) noexcept {
            size_t needed = size + additional;
            if (elementsCapacity < needed) {
                resize(needed);
            }
        }

        void resize(int newSize) noexcept {
            if (newSize < 32) {
                newSize = 32;
            }
            assert(newSize > elementsCapacity);

            T *newArray = (T*)malloc(sizeof(T) * newSize);
            if (head < tail) {
                // Continuous
                memcpy(newArray, elements + head, sizeof(T) * size);
            } else if (size > 0) {
                // Wrapped
                size_t rest = elementsCapacity - head;
                assert(rest + tail == size);
                memcpy(newArray, elements + head, sizeof(T) * rest);
                memcpy(newArray + rest, elements, sizeof(T) * tail);
            }

            free(elements);
            elements = newArray;
            elementsCapacity = newSize;
            head = 0;
            tail = size;
        }

        T removeFirst() noexcept {
            assert(size > 0);

            size_t index = head;
            head++;
            if (head == elementsCapacity) {
                head = 0;
            }
            size--;

            return elements[index];
        }

        T removeLast() noexcept {
            assert(size > 0);

            if (tail == 0) {
                tail = elementsCapacity - 1;
            } else {
                tail--;
            }
            size--;
            return elements[tail];
        }

        T removeIndex(int index) noexcept {
            assert(index >= 0);
            assert(index < size);

            if (index == 0) {
                return removeFirst();
            } else if (index + 1 == size) {
                return removeLast();
            } else {
                // Remove last, put it in place of this one
                size_t elementsIndex = internalIndex(index);
                T result = elements[elementsIndex];
                elements[elementsIndex] = removeLast();
                return result;
            }
        }

        size_t getSize() const noexcept {
            return size;
        }

        bool empty() const noexcept {
            return size == 0;
        }

        const T &first() const noexcept {
            return elements[internalIndex(0)];
        }

        T &first() noexcept {
            return elements[internalIndex(0)];
        }

        const T &last() const noexcept {
            return elements[internalIndex(size - 1)];
        }

        T &last() noexcept {
            return elements[internalIndex(size - 1)];
        }

        const T &operator[](int index) const noexcept {
            return elements[internalIndex(index)];
        }

        T &operator[](int index) noexcept {
            return elements[internalIndex(index)];
        }

        ~queue_bag() {
            free(elements);
        }
    };

    template<typename T, typename Consumer>
    void forEach(queue_bag<T>& queue, Consumer consumer) {
        for (size_t i = 0; i < queue.getSize(); ++i) {
            if (!consumer(queue[i])) {
                return;
            }
        }
    }

    enum class RemoveResult {
        KeepContinue,
        KeepBreak,
        RemoveContinue,
        RemoveBreak
    };

    template<typename T, typename Predicate>
    size_t removeMatching(queue_bag<T>& queue, Predicate predicate) {
        size_t removed = 0;
        size_t i = 0;
        while (i < queue.getSize()) {
            RemoveResult res = predicate(queue[i]);
            if (res == RemoveResult::RemoveContinue || res == RemoveResult::RemoveBreak) {
                queue.removeIndex(i);
            } else {
                i++;
            }

            if (res == RemoveResult::KeepBreak || res == RemoveResult::RemoveBreak) {
                break;
            }
        }
        return removed;
    }

#if RFS_QUEUE_BAG_RUN_TESTS
    inline void testQueueBag() {
        static bool tested = false;
        if (tested) {
            return;
        }
        tested = true;

        queue_bag<int> queue;
        queue.addFirst(42);
        int stairs = 20;

        for (int i = 0; i < stairs; ++i) {
            queue.addFirst(i);
            queue.addLast(i);
            assert(queue.first() == i);
            assert(queue.last() == i);
            assert(queue[queue.getSize() / 2] == 42);
        }

        for (int i = 0; i < stairs; ++i) {
            assert(queue[i] == stairs - 1 - i);
            assert(queue[stairs + 1 + i] == i);
        }

        int stairCheckIndex = 0;
        forEach(queue, [&stairCheckIndex, stairs](const int value){
            if (stairCheckIndex < stairs) {
                assert(value == stairs - 1 - stairCheckIndex);
            } else if (stairCheckIndex == stairs) {
                assert(value == 42);
            } else {
                assert(stairCheckIndex - stairs - 1 == value);
            }
            stairCheckIndex++;
            return true;
        });

        for (int i = stairs-1; i >= 0; --i) {
            assert(queue.removeFirst() == i);
            assert(queue.removeLast() == i);
        }
        assert(queue.removeFirst() == 42);
    }
#endif
}

#endif //XMIPP_QUEUE_BAG_H