AtomicGameEngine/Source/ThirdParty/TurboBadger/tb_linklist.h

// ================================================================================
// ==      This file is a part of Turbo Badger. (C) 2011-2014, Emil Segerås      ==
// ==                     See tb_core.h for more information.                    ==
// ================================================================================

#ifndef TB_LINKLIST_H
#define TB_LINKLIST_H

#include "tb_core.h"
#include <assert.h>

namespace tb {

class TBLinkList;
class TBLink;

/** TBLinkListIterator - The backend class for a safe iteration of a TBLinkList.

    You would normally recieve a typed iterator from a TBLinkListOf::IterateForward
    or TBLinkListOf::IterateBackward, instead of creating this object directly.

    Safe iteration means that if a link is removed from a linked list, _all_ iterators that currently
    point to that link will automatically step to the next link in the iterators direction. */

class TBLinkListIterator
{
public:
    TBLinkListIterator(const TBLinkListIterator &iter);
    TBLinkListIterator(TBLinkList *linklist, TBLink *current_link, bool forward);
    ~TBLinkListIterator();

    /** Set the iterator to the first link in we iterate forward,
        or set it to the last link if we iterate backward.  */
    void Reset();

    /** Get the current link or nullptr if out of bounds. */
    TBLink *Get() const { return m_current_link; }

    /** Get the current link and step the iterator to the next (forward or backward). */
    TBLink *GetAndStep();

    operator TBLink *() const { return m_current_link; }

    const TBLinkListIterator& operator = (const TBLinkListIterator &iter);
private:
    TBLinkList *m_linklist;			///< The linklist we are iterating.
    TBLink *m_current_link;			///< The current link, or nullptr.
    bool m_forward;					///< true if we iterate from first to last item.

    TBLinkListIterator *m_prev;		///< Link in list of iterators for m_linklist
    TBLinkListIterator *m_next;		///< Link in list of iterators for m_linklist

    /** RemoveLink is called when removing/deleting links in the target linklist.
        This will make sure iterators skip the deleted item. */
    void RemoveLink(TBLink *link);
    friend class TBLinkList;

    /** Add ourself to the chain of iterators in the linklist. */
    void Register();

    /** Unlink ourself from the chain of iterators in the linklist. */
    void Unregister();
    void UnregisterAndClear();
};

/** TBLink - The backend class to be inserted in TBLinkList.
    Use the typed TBLinkOf for object storing! */

class TBLink
{
public:
    TBLink() : prev(nullptr), next(nullptr), linklist(nullptr) {}

    /** Return true if the link is currently added to a list. */
    bool IsInList() const { return linklist ? true : false; }
public:
    TBLink *prev;
    TBLink *next;
    TBLinkList *linklist;
};

template<class T>
class TBLinkOf : public TBLink
{
public:
    inline T *GetPrev() const { return (T *) prev; }
    inline T *GetNext() const { return (T *) next; }
};

/** TBLinkList - This is the backend for TBLinkListOf and TBLinkListAutoDeleteOf.
    You should use the typed TBLinkListOf or TBLinkListAutoDeleteOf for object storing! */

class TBLinkList
{
public:
    TBLinkList() : first(nullptr), last(nullptr), first_iterator(nullptr) {}
    ~TBLinkList();

    void Remove(TBLink *link);
    void RemoveAll();

    void AddFirst(TBLink *link);
    void AddLast(TBLink *link);

    void AddBefore(TBLink *link, TBLink *reference);
    void AddAfter(TBLink *link, TBLink *reference);

    bool ContainsLink(TBLink *link) const { return link->linklist == this; }

    bool HasLinks() const { return first ? true : false; }

    int CountLinks() const;
public:
    TBLink *first;
    TBLink *last;
    TBLinkListIterator *first_iterator;
};

/** TBLinkListOf is a double linked linklist. */

template<class T>
class TBLinkListOf
{
public:
    /** Remove link from this linklist. */
    void Remove(T *link)			{ m_linklist.Remove(static_cast<TBLinkOf<T>*>(link)); }

    /** Remove link from this linklist and delete it. */
    void Delete(T *link)			{ m_linklist.Remove(static_cast<TBLinkOf<T>*>(link)); delete link; }

    /** Remove all links without deleting them. */
    void RemoveAll()				{ m_linklist.RemoveAll(); }

    /** Delete all links in this linklist. */
    void DeleteAll()				{ while (T *t = GetFirst()) Delete(t); }

    /** Add link first in this linklist. */
    void AddFirst(T *link)			{ m_linklist.AddFirst(static_cast<TBLinkOf<T>*>(link)); }

    /** Add link last in this linklist. */
    void AddLast(T *link)			{ m_linklist.AddLast(static_cast<TBLinkOf<T>*>(link)); }

    /** Add link before the reference link (which must be added to this linklist). */
    void AddBefore(T *link, T *reference) { m_linklist.AddBefore(static_cast<TBLinkOf<T>*>(link), reference); }

    /** Add link after the reference link (which must be added to this linklist). */
    void AddAfter(T *link, T *reference) { m_linklist.AddAfter(static_cast<TBLinkOf<T>*>(link), reference); }

    /** Return true if the link is currently added to this linklist. */
    bool ContainsLink(T *link) const { return m_linklist.ContainsLink(static_cast<TBLinkOf<T>*>(link)); }

    /** Get the first link, or nullptr. */
    T *GetFirst() const { return (T *) static_cast<TBLinkOf<T>*>(m_linklist.first); }

    /** Get the last link, or nullptr. */
    T *GetLast() const { return (T *) static_cast<TBLinkOf<T>*>(m_linklist.last); }

    /** Return true if this linklist contains any links. */
    bool HasLinks() const { return m_linklist.HasLinks(); }

    /** Count the number of links in this list by iterating through all links. */
    int CountLinks() const { return m_linklist.CountLinks(); }

    /** Typed iterator for safe iteration. For more info, see TBLinkListIterator. */
    class Iterator : public TBLinkListIterator
    {
    public:
        Iterator(TBLinkListOf<T> *linklistof, bool forward)
            : TBLinkListIterator(&linklistof->m_linklist, forward ? linklistof->m_linklist.first : linklistof->m_linklist.last, forward) {}
        Iterator(TBLinkListOf<T> *linklistof, T *link, bool forward) : TBLinkListIterator(&linklistof->m_linklist, link, forward) {}
        inline T *Get() const { return (T *) static_cast<TBLinkOf<T>*>(TBLinkListIterator::Get()); }
        inline T *GetAndStep() { return (T *) static_cast<TBLinkOf<T>*>(TBLinkListIterator::GetAndStep()); }
        inline operator T *() const { return (T *) static_cast<TBLinkOf<T>*>(Get()); }
    };

    /** Get a forward iterator that starts with the first link. */
    Iterator IterateForward() { return Iterator(this, true); }

    /** Get a forward iterator that starts with the given link. */
    Iterator IterateForward(T *link) { return Iterator(this, link, true); }

    /** Get a backward iterator that starts with the last link. */
    Iterator IterateBackward() { return Iterator(this, false); }

    /** Get a backward iterator that starts with the given link. */
    Iterator IterateBackward(T *link) { return Iterator(this, link, false); }
private:
    TBLinkList m_linklist;
};

/** TBLinkListAutoDeleteOf is a double linked linklist that deletes all links on destruction. */

template<class T>
class TBLinkListAutoDeleteOf : public TBLinkListOf<T>
{
public:
    ~TBLinkListAutoDeleteOf() { TBLinkListOf<T>::DeleteAll(); }
};

}; // namespace tb

#endif // TB_LINKLIST_H