SortedSequence.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/basic.h>
#include <ogdf/basic/comparer.h>
#include <ogdf/basic/exceptions.h>
#include <ogdf/basic/memory.h>
 
#include <cstdlib>
#include <initializer_list>
#include <random>
#include <type_traits>
#include <utility>
 
namespace ogdf {
 
template<class KEY, class INFO, class CMP, bool isConst, bool isReverse>
class SortedSequenceIteratorBase;
 
template<class KEY, class INFO, class CMP>
using SortedSequenceIterator = SortedSequenceIteratorBase<KEY, INFO, CMP, false, false>;
 
template<class KEY, class INFO, class CMP>
using SortedSequenceConstIterator = SortedSequenceIteratorBase<KEY, INFO, CMP, true, false>;
 
template<class KEY, class INFO, class CMP>
using SortedSequenceReverseIterator = SortedSequenceIteratorBase<KEY, INFO, CMP, false, true>;
 
template<class KEY, class INFO, class CMP>
using SortedSequenceConstReverseIterator = SortedSequenceIteratorBase<KEY, INFO, CMP, true, true>;
 
 
template<class KEY, class INFO, class CMP = StdComparer<KEY>>
class SortedSequence {
    friend class SortedSequenceIteratorBase<KEY, INFO, CMP, false, false>;
    friend class SortedSequenceIteratorBase<KEY, INFO, CMP, true, false>;
    friend class SortedSequenceIteratorBase<KEY, INFO, CMP, false, true>;
    friend class SortedSequenceIteratorBase<KEY, INFO, CMP, true, true>;
 
    struct Element {
        KEY m_key; 
        INFO m_info; 
        int m_height; 
 
        Element** m_next; 
        Element** m_prev; 
 
        Element(const KEY& key, const INFO& info, int height)
            : m_key(key), m_info(info), m_height(height) {
            m_next = (Element**)malloc(height * sizeof(Element*));
            m_prev = (Element**)malloc(height * sizeof(Element*));
        }
 
 
        Element(int height) : m_height(0) {
            m_next = (Element**)malloc(height * sizeof(Element*));
            m_prev = (Element**)malloc(height * sizeof(Element*));
        }
 
        Element(const Element&) = delete;
 
        ~Element() {
            free(m_prev);
            free(m_next);
        }
 
        void grow(int newHeight) {
            Element** p = static_cast<Element**>(realloc(m_next, newHeight * sizeof(Element*)));
            if (p == nullptr) {
                OGDF_THROW(InsufficientMemoryException);
            }
            m_next = p;
 
            p = static_cast<Element**>(realloc(m_prev, newHeight * sizeof(Element*)));
            if (p == nullptr) {
                OGDF_THROW(InsufficientMemoryException);
            }
            m_prev = p;
        }
 
        OGDF_NEW_DELETE
    };
 
public:
    using iterator = SortedSequenceIterator<KEY, INFO, CMP>;
    using const_iterator = SortedSequenceConstIterator<KEY, INFO, CMP>;
    using reverse_iterator = SortedSequenceReverseIterator<KEY, INFO, CMP>;
    using const_reverse_iterator = SortedSequenceConstReverseIterator<KEY, INFO, CMP>;
 
    SortedSequence(const CMP& comparer = CMP())
        : m_comparer(comparer), m_rng(randomSeed()), m_randomBits(0, 1) {
        initEmpty();
    }
 
    SortedSequence(std::initializer_list<std::pair<KEY, INFO>> initList);
 
    SortedSequence(const SortedSequence<KEY, INFO, CMP>& S);
 
 
    SortedSequence(SortedSequence<KEY, INFO, CMP>&& S);
 
    ~SortedSequence() {
        clear();
        delete m_dummy;
    }
 
 
    int size() const { return m_size; }
 
    bool empty() const { return m_size == 0; }
 
    iterator begin();
 
    const_iterator begin() const;
 
    const_iterator cbegin() const { return begin(); }
 
    iterator end();
 
    const_iterator end() const;
 
    const_iterator cend() const { return end(); }
 
    reverse_iterator rbegin();
 
    const_reverse_iterator rbegin() const;
 
    const_reverse_iterator crbegin() const { return rbegin(); }
 
    reverse_iterator rend();
 
    const_reverse_iterator rend() const;
 
    const_reverse_iterator crend() const { return rend(); }
 
 
    iterator lookup(const KEY& key);
 
    const_iterator lookup(const KEY& key) const;
 
    iterator locate(const KEY& key);
 
    const_iterator locate(const KEY& key) const;
 
 
    iterator minItem() { return begin(); }
 
 
    const_iterator minItem() const { return begin(); }
 
 
    reverse_iterator maxItem() { return rbegin(); }
 
 
    const_reverse_iterator maxItem() const { return rbegin(); }
 
 
 
    iterator insert(const KEY& key, const INFO& info);
 
    void del(const KEY& key);
 
    void delItem(iterator it);
 
    void clear() {
        Element* item = m_dummy->m_next[0];
        while (item != m_dummy) {
            Element* old = item;
            item = item->m_next[0];
            delete old;
        }
        m_size = 0;
        m_height = 1;
        m_dummy->m_next[0] = m_dummy->m_prev[0] = m_dummy;
    }
 
 
 
    SortedSequence<KEY, INFO, CMP>& operator=(const SortedSequence<KEY, INFO, CMP>& S);
 
 
    SortedSequence<KEY, INFO, CMP>& operator=(SortedSequence<KEY, INFO, CMP>&& S);
 
 
    bool operator==(const SortedSequence<KEY, INFO, CMP>& S);
 
 
    bool operator!=(const SortedSequence<KEY, INFO, CMP>& S) { return !operator==(S); }
 
 
 
 
    iterator insertAfter(iterator it, const KEY& key, const INFO& info);
 
 
    void reverseItems(iterator itBegin, iterator itEnd) {
        reverseElements(itBegin.m_pElement, itEnd.m_pElement);
    }
 
 
private:
    CMP m_comparer;
    int m_size; 
    Element* m_dummy; 
    int m_height; 
    int m_realHeight; 
 
    std::minstd_rand m_rng; 
    std::uniform_int_distribution<> m_randomBits;
 
    void initEmpty() {
        m_size = 0;
        m_realHeight = 5;
        m_height = 1;
 
        m_dummy = new Element(m_realHeight);
        m_dummy->m_next[0] = m_dummy;
        m_dummy->m_prev[0] = m_dummy;
    }
 
    int randomHeightAndGrow();
    void grow(int newHeight);
 
    const Element* _lookup(const KEY& key) const;
    const Element* _locate(const KEY& key) const;
 
    void removeElement(Element* p);
    void insertElementAfterElement(Element* p, Element* q);
    void reverseElements(Element* p, Element* q);
};
 
template<class KEY, class INFO, class CMP, bool isConst, bool isReverse>
class SortedSequenceIteratorBase {
    friend class SortedSequence<KEY, INFO, CMP>;
    friend class SortedSequenceIteratorBase<KEY, INFO, CMP, !isConst, isReverse>;
    friend class SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, !isReverse>;
    friend class SortedSequenceIteratorBase<KEY, INFO, CMP, !isConst, !isReverse>;
 
    using Element =
            typename std::conditional<isConst, const typename SortedSequence<KEY, INFO, CMP>::Element,
                    typename SortedSequence<KEY, INFO, CMP>::Element>::type;
    Element* m_pElement;
 
    SortedSequenceIteratorBase(Element* pElement) : m_pElement(pElement) { }
 
public:
    SortedSequenceIteratorBase() : m_pElement(nullptr) { }
 
    template<bool isArgConst, typename std::enable_if<isConst || !isArgConst, int>::type = 0, bool isArgReverse>
    SortedSequenceIteratorBase(
            const SortedSequenceIteratorBase<KEY, INFO, CMP, isArgConst, isArgReverse>& it)
        : m_pElement(it.m_pElement) { }
 
    // gcc9 complains since it cannot match the templated constructor above (-Werror=deprecated-copy).
    SortedSequenceIteratorBase(
            const SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& it)
        : m_pElement(it.m_pElement) { }
 
    const KEY& key() const {
        OGDF_ASSERT(valid());
        return m_pElement->m_key;
    }
 
    typename std::conditional<isConst, const INFO, INFO>::type& info() const {
        OGDF_ASSERT(valid());
        return m_pElement->m_info;
    }
 
    bool valid() const { return m_pElement != nullptr; }
 
    SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& operator++() {
        m_pElement = isReverse ? predElement() : succElement();
        return *this;
    }
 
    SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> operator++(int) {
        SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> it = *this;
        m_pElement = isReverse ? predElement() : succElement();
        return it;
    }
 
    SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& operator--() {
        m_pElement = isReverse ? succElement() : predElement();
        return *this;
    }
 
    SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> operator--(int) {
        SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> it = *this;
        m_pElement = isReverse ? succElement() : predElement();
        return it;
    }
 
    SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> succ() const {
        return isReverse ? predElement() : succElement();
    }
 
    SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse> pred() const {
        return isReverse ? succElement() : predElement();
    }
 
    SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& operator=(
            const SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& it) {
        m_pElement = it.m_pElement;
        return *this;
    }
 
    bool operator==(const SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& it) const {
        return m_pElement == it.m_pElement;
    }
 
    bool operator!=(const SortedSequenceIteratorBase<KEY, INFO, CMP, isConst, isReverse>& it) const {
        return m_pElement != it.m_pElement;
    }
 
private:
    typename SortedSequence<KEY, INFO, CMP>::Element* succElement() const {
        OGDF_ASSERT(valid());
        return (m_pElement->m_next[0]->m_height > 0) ? m_pElement->m_next[0] : nullptr;
    }
 
    typename SortedSequence<KEY, INFO, CMP>::Element* predElement() const {
        OGDF_ASSERT(valid());
        return (m_pElement->m_prev[0]->m_height > 0) ? m_pElement->m_prev[0] : nullptr;
    }
};
 
template<class KEY, class INFO, class CMP>
SortedSequence<KEY, INFO, CMP>::SortedSequence(std::initializer_list<std::pair<KEY, INFO>> initList)
    : SortedSequence() {
    for (const auto& p : initList) {
        insert(p.first, p.second);
    }
}
 
template<class KEY, class INFO, class CMP>
SortedSequence<KEY, INFO, CMP>::SortedSequence(const SortedSequence<KEY, INFO, CMP>& S)
    : m_comparer(S.m_comparer), m_rng(randomSeed()), m_randomBits(0, 1) {
    initEmpty();
 
    iterator it = m_dummy;
    for (Element* pS = S.m_dummy->m_next[0]; pS != S.m_dummy; pS = pS->m_next[0]) {
        it = insertAfter(it, pS->m_key, pS->m_info);
    }
}
 
template<class KEY, class INFO, class CMP>
SortedSequence<KEY, INFO, CMP>::SortedSequence(SortedSequence<KEY, INFO, CMP>&& S)
    : m_comparer(S.m_comparer)
    , m_size(S.m_size)
    , m_height(S.m_height)
    , m_realHeight(S.m_realHeight)
    , m_rng(randomSeed())
    , m_randomBits(0, 1) {
    // move all elements to this sequence
    m_dummy = S.m_dummy;
 
    // initalize S with an empty sequence
    S.initEmpty();
}
 
template<class KEY, class INFO, class CMP>
SortedSequence<KEY, INFO, CMP>& SortedSequence<KEY, INFO, CMP>::operator=(
        const SortedSequence<KEY, INFO, CMP>& S) {
    clear();
 
    iterator it = m_dummy;
    for (Element* pS = S.m_dummy->m_next[0]; pS != S.m_dummy; pS = pS->m_next[0]) {
        it = insertAfter(it, pS->m_key, pS->m_info);
    }
 
    return *this;
}
 
template<class KEY, class INFO, class CMP>
SortedSequence<KEY, INFO, CMP>& SortedSequence<KEY, INFO, CMP>::operator=(
        SortedSequence<KEY, INFO, CMP>&& S) {
    // clear this sequence
    Element* item = m_dummy->m_next[0];
    while (item != m_dummy) {
        Element* old = item;
        item = item->m_next[0];
        delete old;
    }
    delete m_dummy;
 
    // move elements from S to this sequence
    m_comparer = S.m_comparer;
    m_size = S.m_size;
    m_height = S.m_height;
    m_realHeight = S.m_realHeight;
    m_dummy = S.m_dummy;
 
    // make S the empty sequence
    S.initEmpty();
 
    return *this;
}
 
template<class KEY, class INFO, class CMP>
bool SortedSequence<KEY, INFO, CMP>::operator==(const SortedSequence<KEY, INFO, CMP>& S) {
    if (m_size != S.m_size) {
        return false;
    }
 
    Element *p = m_dummy->m_next[0], *pS = S.m_dummy->m_next[0];
    while (p != m_dummy) {
        if (!m_comparer.equal(p->m_key, pS->m_key)) {
            return false;
        }
        p = p->m_next[0];
        pS = pS->m_next[0];
    }
 
    return true;
}
 
template<class KEY, class INFO, class CMP>
const typename SortedSequence<KEY, INFO, CMP>::Element* SortedSequence<KEY, INFO, CMP>::_lookup(
        const KEY& key) const {
    int h = m_height - 1;
    Element** pElement = m_dummy->m_next;
 
    while (true) {
        if (pElement[h] != m_dummy && m_comparer.less(pElement[h]->m_key, key)) {
            pElement = pElement[h]->m_next;
        } else if (--h < 0) {
            if (pElement[0] != m_dummy && m_comparer.equal(pElement[0]->m_key, key)) {
                return pElement[0];
            }
            return nullptr;
        }
    }
}
 
template<class KEY, class INFO, class CMP>
typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::lookup(
        const KEY& key) {
    return iterator(const_cast<Element*>(_lookup(key)));
}
 
template<class KEY, class INFO, class CMP>
typename SortedSequence<KEY, INFO, CMP>::const_iterator SortedSequence<KEY, INFO, CMP>::lookup(
        const KEY& key) const {
    return const_iterator(_lookup(key));
}
 
template<class KEY, class INFO, class CMP>
const typename SortedSequence<KEY, INFO, CMP>::Element* SortedSequence<KEY, INFO, CMP>::_locate(
        const KEY& key) const {
    int h = m_height - 1;
    Element** pElement = m_dummy->m_next;
 
    while (true) {
        if (pElement[h] != m_dummy && m_comparer.less(pElement[h]->m_key, key)) {
            pElement = pElement[h]->m_next;
        } else if (--h < 0) {
            Element* p = (pElement[0] != m_dummy) ? pElement[0] : nullptr;
            return p;
        }
    }
}
 
template<class KEY, class INFO, class CMP>
typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::locate(
        const KEY& key) {
    return iterator(const_cast<Element*>(_locate(key)));
}
 
template<class KEY, class INFO, class CMP>
typename SortedSequence<KEY, INFO, CMP>::const_iterator SortedSequence<KEY, INFO, CMP>::locate(
        const KEY& key) const {
    return const_iterator(_locate(key));
}
 
template<class KEY, class INFO, class CMP>
void SortedSequence<KEY, INFO, CMP>::grow(int newHeight) {
    if (newHeight > m_realHeight) {
        m_realHeight = newHeight;
        m_dummy->grow(newHeight);
    }
 
    for (int i = newHeight; i-- > m_height;) {
        m_dummy->m_next[i] = m_dummy;
        m_dummy->m_prev[i] = m_dummy;
    }
    m_height = newHeight;
}
 
template<class KEY, class INFO, class CMP>
int SortedSequence<KEY, INFO, CMP>::randomHeightAndGrow() {
    int h = 1;
    while (m_randomBits(m_rng) == 1) {
        h++;
    }
 
    if (h > m_height) {
        grow(h);
    }
 
    return h;
}
 
template<class KEY, class INFO, class CMP>
typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::insert(
        const KEY& key, const INFO& info) {
    int h = m_height - 1;
    Element* pCurrent = m_dummy;
 
    while (true) {
        if (pCurrent->m_next[h] != m_dummy && m_comparer.less(pCurrent->m_next[h]->m_key, key)) {
            pCurrent = pCurrent->m_next[h];
 
        } else {
            if (--h < 0) {
                // found element?
                if (pCurrent->m_next[0] != m_dummy
                        && m_comparer.equal(pCurrent->m_next[0]->m_key, key)) {
                    pCurrent->m_next[0]->m_info = info;
                    return iterator(pCurrent->m_next[0]);
                }
                break;
            }
        }
    }
 
    // add new element (key,inf)
    m_size++;
 
    int nh = randomHeightAndGrow();
 
    Element* pNewElement = new Element(key, info, nh);
    insertElementAfterElement(pNewElement, pCurrent);
 
    return iterator(pNewElement);
}
 
template<class KEY, class INFO, class CMP>
void SortedSequence<KEY, INFO, CMP>::del(const KEY& key) {
    iterator it = lookup(key);
    if (it.valid()) {
        delItem(it);
    }
}
 
template<class KEY, class INFO, class CMP>
typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::insertAfter(
        iterator it, const KEY& key, const INFO& info) {
    m_size++;
 
    int nh = randomHeightAndGrow();
 
    Element* pNewElement = new Element(key, info, nh);
    insertElementAfterElement(pNewElement, it.m_pElement);
 
    return pNewElement;
}
 
template<class KEY, class INFO, class CMP>
void SortedSequence<KEY, INFO, CMP>::insertElementAfterElement(Element* p, Element* q) {
    OGDF_ASSERT(p->m_height <= m_height);
 
    for (int h = 0; h < p->m_height; ++h) {
        while (q != m_dummy && q->m_height <= h) {
            q = q->m_prev[h - 1];
        }
 
        Element* r = q->m_next[h];
        p->m_next[h] = r;
        p->m_prev[h] = q;
        q->m_next[h] = r->m_prev[h] = p;
    }
}
 
template<class KEY, class INFO, class CMP>
void SortedSequence<KEY, INFO, CMP>::reverseElements(Element* p, Element* q) {
    while (p != q) {
        Element* r = p;
        p = p->m_next[0];
        removeElement(r);
        insertElementAfterElement(r, q);
    }
}
 
template<class KEY, class INFO, class CMP>
void SortedSequence<KEY, INFO, CMP>::removeElement(Element* p) {
    OGDF_ASSERT(p != nullptr);
    OGDF_ASSERT(p != m_dummy);
 
    for (int h = 0; h < p->m_height; ++h) {
        Element *pPred = p->m_prev[h], *pSucc = p->m_next[h];
        pPred->m_next[h] = pSucc;
        pSucc->m_prev[h] = pPred;
    }
}
 
template<class KEY, class INFO, class CMP>
void SortedSequence<KEY, INFO, CMP>::delItem(typename SortedSequence<KEY, INFO, CMP>::iterator it) {
    Element* p = it.m_pElement;
    removeElement(p);
 
    m_size--;
    delete p;
}
 
template<class KEY, class INFO, class CMP>
inline typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::begin() {
    return (m_dummy->m_next[0] != m_dummy) ? m_dummy->m_next[0] : nullptr;
}
 
template<class KEY, class INFO, class CMP>
inline typename SortedSequence<KEY, INFO, CMP>::const_iterator
SortedSequence<KEY, INFO, CMP>::begin() const {
    return (m_dummy->m_next[0] != m_dummy) ? m_dummy->m_next[0] : 0;
}
 
template<class KEY, class INFO, class CMP>
inline typename SortedSequence<KEY, INFO, CMP>::iterator SortedSequence<KEY, INFO, CMP>::end() {
    return SortedSequence<KEY, INFO, CMP>::iterator();
}
 
template<class KEY, class INFO, class CMP>
inline typename SortedSequence<KEY, INFO, CMP>::const_iterator
SortedSequence<KEY, INFO, CMP>::end() const {
    return SortedSequence<KEY, INFO, CMP>::const_iterator();
}
 
template<class KEY, class INFO, class CMP>
inline typename SortedSequence<KEY, INFO, CMP>::reverse_iterator
SortedSequence<KEY, INFO, CMP>::rbegin() {
    return (m_dummy->m_prev[0] != m_dummy) ? m_dummy->m_prev[0] : 0;
}
 
template<class KEY, class INFO, class CMP>
inline typename SortedSequence<KEY, INFO, CMP>::const_reverse_iterator
SortedSequence<KEY, INFO, CMP>::rbegin() const {
    return (m_dummy->m_prev[0] != m_dummy) ? m_dummy->m_prev[0] : 0;
}
 
template<class KEY, class INFO, class CMP>
inline typename SortedSequence<KEY, INFO, CMP>::reverse_iterator SortedSequence<KEY, INFO, CMP>::rend() {
    return SortedSequence<KEY, INFO, CMP>::iterator();
}
 
template<class KEY, class INFO, class CMP>
inline typename SortedSequence<KEY, INFO, CMP>::const_reverse_iterator
SortedSequence<KEY, INFO, CMP>::rend() const {
    return SortedSequence<KEY, INFO, CMP>::const_iterator();
}
 
}