drwnIndexQueue.h

/*****************************************************************************
** DARWIN: A FRAMEWORK FOR MACHINE LEARNING RESEARCH AND DEVELOPMENT
** Distributed under the terms of the BSD license (see the LICENSE file)
** Copyright (c) 2007-2015, Stephen Gould
** All rights reserved.
**
******************************************************************************
** FILENAME:    drwnIndexQueue.h
** AUTHOR(S):   Stephen Gould <stephen.gould@anu.edu.au>
**
*****************************************************************************/

#pragma once

#include <vector>

using namespace std;

// drwnIndexQueue -----------------------------------------------------------

class drwnIndexQueue {
 protected:
    static const int TERMINAL = -1;

    int _head, _tail;
    vector<int> _rev;
    vector<int> _fwd;

 public:
    drwnIndexQueue() : _head(TERMINAL), _tail(TERMINAL) { /* do nothing */ }
    drwnIndexQueue(size_t n) : _head(TERMINAL), _tail(TERMINAL),
        _rev(n, TERMINAL), _fwd(n, TERMINAL) { /* do nothing */ }
    ~drwnIndexQueue() { /* do nothing */ }

    inline bool empty() const { return (_head == TERMINAL); }

    inline void clear() {
        _head = _tail = TERMINAL;
        fill(_rev.begin(), _rev.end(), TERMINAL);
        fill(_fwd.begin(), _fwd.end(), TERMINAL);
    }

    inline void resize(size_t n) {
        _rev.resize(n); _fwd.resize(n); clear();
    }

    inline int front() const { return _head; }
    inline int back() const { return _tail; }

    inline bool is_queued(int u) const {
        return (_rev[u] != TERMINAL);
    }

    inline void push_back(int u) {
        if (is_queued(u)) return;

        if (_tail == TERMINAL) {
            _head = _tail = _fwd[u] = _rev[u] = u;
        } else {
            _fwd[u] = _head;
            _rev[u] = _tail;
            _fwd[_tail] = u;
            _rev[_head] = u;
            _tail = u;
        }
    }

    inline void push_front(int u) {
        if (is_queued(u)) return;

        if (_head == TERMINAL) {
            _head = _tail = _fwd[u] = _rev[u] = u;
        } else {
            _fwd[u] = _head;
            _rev[u] = _tail;
            _fwd[_tail] = u;
            _rev[_head] = u;
            _head = u;
        }
    }

    inline void pop_front() {
        DRWN_ASSERT(_head != TERMINAL);
        _rev[_head] = TERMINAL;
        if (_head == _tail) {
            _head = _tail = TERMINAL;
        } else {
            _head = _fwd[_head];
            _rev[_head] = _tail;
            _fwd[_tail] = _head;
        }
    }

    inline void erase(int u) {
        if (!is_queued(u)) return;

        if (_head == _tail) {
            _head = _tail = TERMINAL;
        } else {
            _fwd[_rev[u]] = _fwd[u];
            _rev[_fwd[u]] = _rev[u];
            if (_head == u) _head = _fwd[u];
            if (_tail == u) _tail = _rev[u];
        }

        _rev[u] = TERMINAL;
    }
};

std::string toString(const drwnIndexQueue& q);