GAList.hpp

/* ----------------------------------------------------------------------------
  mbwall 25feb95
  Copyright 1995 Massachusetts Institute of Technology
---------------------------------------------------------------------------- */
 
#pragma once
 
#include <GAListBASE.h>
#include <gaerror.h>
 
/* ----------------------------------------------------------------------------
 GAList
---------------------------------------------------------------------------- */
template <class T> class GAListIter;
 
extern GANodeBASE *_GAListTraverse(unsigned int index, unsigned int &cur,
                                   GANodeBASE *node);
 
template <class T> GANode<T> *_GAListCopy(GANode<T> *node, GANode<T> *head)
{
    if (!node)
        return nullptr;
    auto *newnode = new GANode<T>(node->contents);
    GANode<T> *lasttmp = newnode, *newtmp = nullptr;
    GANode<T> *tmp = DYN_CAST(GANode<T> *, node->next);
    while (tmp && tmp != head)
    {
        newtmp = new GANode<T>(tmp->contents);
        newtmp->prev = lasttmp;
        lasttmp->next = newtmp;
 
        lasttmp = newtmp;
        tmp = DYN_CAST(GANode<T> *, tmp->next);
    }
    if (newtmp)
    {
        newtmp->next = newnode;
        newnode->prev = newtmp;
    }
    else
    {
        newnode->next = newnode;
        newnode->prev = newnode;
    }
    return newnode;
}
 
template <class T> class GAList : public GAListBASE
{
  public:
    GAList() : GAListBASE() { iter(*this); }
    explicit GAList(const T &t) : GAListBASE(new GANode<T>(t)), iter(*this) {}
    GAList(const GAList<T> &orig)
    {
        iter(*this);
        copy(orig);
    }
    GAList<T> &operator=(const GAList<T> &orig)
    {
        if (&orig != this)
            copy(orig);
        return *this;
    }
 
    // The destructor just goes through the list and deletes every node.
    virtual ~GAList()
    {
        while (hd)
            delete GAListBASE::remove(DYN_CAST(GANode<T> *, hd));
        iter.node = nullptr;
    }
 
    GAList<T> *clone(unsigned int i = 0) const
    {
        auto *t = new GAList<T>;
        GANode<T> *node;
        unsigned int w = 0;
        if (i == 0)
            node = DYN_CAST(GANode<T> *, hd);
        else
            node = DYN_CAST(GANode<T> *, _GAListTraverse(i, w, hd));
        if (!node)
            return t;
 
        GANode<T> *newnode = _GAListCopy(node, DYN_CAST(GANode<T> *, hd));
 
        t->insert(newnode, nullptr, GAListBASE::HEAD);
 
        // need to set iterator to right spot in the clone!!  for now its at the
        // head
 
        return t;
    }
 
    // methods that modify the state of the list
 
    // Yes, this is really ugly.  We do a complete destruction of the existing
    // list
    // then we copy the new one.  No caching, no nothing.  Oh well.  We set the
    // iterator to the head node - it should be set to the corresponding node,
    // but I won't do that right now.  THIS IS A BUG!
    void copy(const GAList<T> &orig)
    {
        while (hd)
            delete GAListBASE::remove(DYN_CAST(GANode<T> *, hd));
        hd = _GAListCopy(DYN_CAST(GANode<T> *, orig.hd),
                         DYN_CAST(GANode<T> *, orig.hd));
        iter.node = hd;
        sz = orig.sz;
        csz = orig.csz;
    }
 
    // Destroy the specified node.  This uses the current node as the one to
    // destroy, so be sure to use the iteration methods to move to the node you
    // want to destroy.  Once the node is gone, we set the current node to the
    // prev node of the one that was destroyed.  If the node that was nuked was
    // the head node then we set the current node to the new head.
    int destroy()
    {
        GANodeBASE *node = iter.node;
        if (!node)
            return GAListBASE::NO_ERR;
        if (node->prev && node->prev != node)
            if (hd == node)
                iter.node = node->next;
            else
                iter.node = node->prev;
        else
            iter.node = nullptr;
        delete GAListBASE::remove(node);
        return GAListBASE::NO_ERR;
    }
 
    int swap(unsigned int a, unsigned int b)
    {
        if (a == b || a > (unsigned int)size() || b > (unsigned int)size())
            return GAListBASE::NO_ERR;
        GANodeBASE *tmp = hd, *anode = nullptr, *bnode = nullptr;
        unsigned int cur = 0;
        while (tmp && tmp->next != hd)
        {
            if (a == cur)
                anode = tmp;
            if (b == cur)
                bnode = tmp;
            tmp = tmp->next;
            cur++;
        }
        if (a == cur)
            anode = tmp;
        if (b == cur)
            bnode = tmp;
        return GAListBASE::swapnode(anode, bnode);
    }
 
    T *remove()
    {
        GANode<T> *node = DYN_CAST(GANode<T> *, iter.node);
        if (!node)
            return nullptr;
 
        if (node->prev != node)
            iter.node = node->prev;
        else
            iter.node = nullptr;
        node = DYN_CAST(GANode<T> *, GAListBASE::remove(node));
        T *contents = new T(node->contents);
        delete node;
        return contents;
    }
 
    int insert(GAList<T> *t, GAListBASE::Location where = GAListBASE::AFTER)
    {
        if (this == t)
        {
            GAErr(GA_LOC, "GAList", "insert", GAError::CannotInsertIntoSelf);
            return GAListBASE::ERR;
        }
        if (GAListBASE::insert(t->hd, iter.node, where) == GAListBASE::ERR)
        {
            return GAListBASE::ERR;
        }
        iter.node = (t->hd ? t->hd : iter.node);
        t->hd = nullptr;
        t->iter.node = nullptr;
        return GAListBASE::NO_ERR;
    }
 
    int insert(const T &t, GAListBASE::Location where = GAListBASE::AFTER)
    {
        auto *c = new GANode<T>(t);
        if (GAListBASE::insert(c, iter.node, where) == GAListBASE::ERR)
        {
            delete c;
            return GAListBASE::ERR;
        }
        iter.node = c;
        return GAListBASE::NO_ERR;
    }
 
    // typesafes on iteration methods.  These call the built-in iterator then
    // return the contents of the now-current node.  They do not affect the
    // state of the list.
    T *head() { return iter.head(); }
    T *tail() { return iter.tail(); }
    T *current() { return iter.current(); }
    T *next() { return iter.next(); }
    T *prev() { return iter.prev(); }
    T *warp(unsigned int i) { return iter.warp(i); }
    T *warp(const GAListIter<T> &i)
    {
        return ((i.list == this) ? iter.warp(i) : nullptr);
    }
    T *operator[](unsigned int i) { return iter.warp(i); }
 
  protected:
    int insert(GANode<T> *n, GANode<T> *idx,
               GAListBASE::Location where = GAListBASE::AFTER)
    {
        if (GAListBASE::insert(n, idx, where) == GAListBASE::ERR)
            return GAListBASE::ERR;
        iter.node = n;
        return GAListBASE::NO_ERR;
    }
    GAListIter<T> iter; // the embedded iterator
    friend class GAListIter<T>;
};
 
/* ----------------------------------------------------------------------------
 GAListIter
-------------------------------------------------------------------------------
  This is a type-safe derivation of the base ListIter object.  I copied the
methods from the base class (I know, a no-no) rather than doing calls to the
base class methods.
  We depend on the template-ized GAList, thus the declaration.
  Behaviour for the iterator methods is defined as follows.  If the current
node is null, attempts to access a derived position from the current position
will return NULL.  The only way to reset the current node is to call the head()
locater (you always have to start at the list head to navigate the list).  If
the current node is non-null and the derived node is null, the current node is
NOT changed, but NULL is returned.  You can also warp to a new position if you
have another iterator or a list with an embedded iterator.
  When we create a new list iterator, it defaults to the same node as the one
used to create it.  If it is created with a list as its argument, it defaults
to the list's iterator's current position.
---------------------------------------------------------------------------- */
template <class T> class GAList;
 
template <class T> class GAListIter : public GAListIterBASE
{
  public:
    GAListIter() : GAListIterBASE() {}
    explicit GAListIter(const GAList<T> &t) : GAListIterBASE(t)
    {
        node = t.iter.node;
    }
    GAListIter(const GAListIter<T> &i) : GAListIterBASE(i) {}
    T *current() { return (node ? &((GANode<T> *)node)->contents : nullptr); }
    T *head()
    {
        return (((node = GAListIterBASE::head()) != nullptr) ? &((GANode<T> *)GAListIterBASE::head())->contents : nullptr);
    }
    T *tail()
    {
        return (((node = GAListIterBASE::tail()) != nullptr) ? &((GANode<T> *)GAListIterBASE::tail())->contents : nullptr);
    }
    T *next()
    {
        return ((node && node->next) ? &((GANode<T> *)(node = node->next))->contents : nullptr);
    }
    T *prev()
    {
        return ((node && node->prev) ? &((GANode<T> *)(node = node->prev))->contents : nullptr);
    }
    T *warp(const GAList<T> &t)
    {
        list = &t;
        node = t.iter.node;
        return (t.iter.node ? &((GANode<T> *)(node = t.iter.node))->contents : nullptr);
    }
    T *warp(const GAListIter<T> &i)
    {
        list = i.list;
        node = i.node;
        return (i.node ? &((GANode<T> *)(node = i.node))->contents : nullptr);
    }
    T *warp(unsigned int i)
    {
        GANodeBASE *n = GAListIterBASE::warp(i);
        return (n != nullptr ? &((GANode<T> *)(node = n))->contents : nullptr);
    }
 
  private:
    friend class GAList<T>; // do I need to do this?
};