symlist.h

Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file symlist.h

/* This software is distributed under the GNU Lesser General Public License */
//==========================================================================
//
//   symlist.h
//
//==========================================================================
// $Id: symlist.h,v 1.17 2002/12/20 08:26:08 chris Exp $

#ifndef SYMLIST_H
#define SYMLIST_H

#include <GTL/GTL.h> 

#include <cassert>

__GTL_BEGIN_NAMESPACE

template <class T>
struct symnode 
{
    symnode()
    {
    }

    symnode(const T& n) : data(n)
    {
    }

    symnode* adj[2];

    T data;
};

template <class T, class Ref>
struct symlist_iterator 
{
    typedef symlist_iterator<T, Ref> self;

    typedef symnode<T>* linktype;

    symlist_iterator() : act (0)
    {
    }

    symlist_iterator(const self& it) : act(it.act), dir(it.dir)
    {
    }

    symlist_iterator(linktype _act, int _dir) : act(_act), dir(_dir)
    {
    }
    
    symlist_iterator(linktype _act, linktype _prev) :
        act(_act),
        dir (where_not (_act, _prev))
    {
    }

    self& operator=(const self& it)
    {
        act = it.act;
        dir = it.dir;
        return *this;
    }

    bool operator==(const self& it) const
    {
        return act == it.act;
    }
    
    bool operator!=(const self& it) const
    {
        return act != it.act;
    }
    
    Ref operator*() 
    {
        return act->data;
    }

    self& operator++();

    self& operator--();
    
    static int where(linktype _act, linktype _prev) 
    {
        return _prev == _act->adj[0] ? 0 : 1;
    }

    static int where_not(linktype _act, linktype _prev)
    {
        return _prev == _act->adj[1] ? 0 : 1;
    }

    void reverse()
    {
        dir = 1 - dir;
    }
        
    linktype& next()
    {
        return act->adj[dir];
    }

    linktype& prev()
    {
        return act->adj[1 - dir];
    }

    linktype act;

    int dir;
};

template <class T>
class symlist 
{
public:
    typedef symlist_iterator<T, T&> iterator;

    typedef symlist_iterator<T, const T&> const_iterator;

    symlist()
    {
        link = new symnode<T>;
        link->adj[0] = link->adj[1] = link;
    }

    symlist(const symlist<T>& li);

    symlist<T>& operator=(const symlist<T>& li);

    ~symlist();

    bool empty() const
    {
        return link->adj[0] == link && link->adj[1] == link;
    }

    T& front()
    {
        return link->adj[0]->data;
    }

    T& back()
    {
        return link->adj[1]->data;
    }

    iterator begin()
    {
        return ++end();
    }

    iterator end()
    {
        return iterator(link, 0);
    }

    const_iterator begin() const
    {
        return ++end();
    }

    const_iterator end () const
    {
        return const_iterator (link, 0);
    }

    iterator rbegin()
    {
        return ++rend();
    }

    iterator rend()
    {
        return iterator (link, 1);
    }

    const_iterator rbegin() const
    {
        return ++rend();
    }

    const_iterator rend() const
    {
        return const_iterator(link, 1);
    }

    iterator insert (iterator pos, const T& data);

    void splice (iterator pos, iterator it);

    void splice (iterator pos, iterator it, iterator end);

    iterator erase (iterator pos);

    iterator erase (iterator it, iterator end);

    void attach_sublist (iterator, iterator);

    void detach_sublist ();

    void reverse ();
private:
    symnode<T>* link;

    iterator _prev;

    iterator _next;
};


// Implementation Begin

template <class T, class Ref>
symlist_iterator<T, Ref>& symlist_iterator<T, Ref>::operator++()
{
    symnode<T>* prev = act; 
    act = act->adj[dir];
    dir = where_not(act, prev);
    return *this;
}


template <class T, class Ref>
symlist_iterator<T, Ref>& symlist_iterator<T, Ref>::operator--()
{
    symnode<T>* prev = act;
    act = act->adj[1 - dir];
    dir = where(act, prev); 
    return *this;
}


template <class T>
symlist<T>::symlist (const symlist<T>& l)
{
    link = new symnode<T>;
    link->adj[0] = link->adj[1] = link;    
    
    const_iterator it = l.begin();
    const_iterator e = l.end();

    while (it != e)
    {
        insert(end(), *it);
        ++it;
    }
}


template <class T>
symlist<T>::~symlist()
{
    if (_next == iterator())
    {
        erase (begin(), end());
    }
    else
    {
        detach_sublist();
    }
    
    delete link;
}


template <class T>
symlist<T>& symlist<T>::operator=(const symlist<T>& l) 
{
    erase(begin(), end());

    const_iterator it = l.begin();
    const_iterator e = l.end();

    while (it != e)
    {
        insert(end(), *it);
        ++it;
    }
    
    return *this;
}


template <class T>
symlist_iterator<T, T&> symlist<T>::insert(
    symlist_iterator<T,T&> pos,
    const T& ins)
{
    iterator prev = pos;
    --prev;
    symnode<T>* n = new symnode<T>(ins);
    n->adj[0] = pos.act;
    n->adj[1] = prev.act;

    if (pos == prev)
    {
        pos = prev;
    }

    pos.prev() = n;
    prev.next() = n;

    return iterator(n, 0);
}


template <class T>
void symlist<T>::splice(symlist_iterator<T, T&> pos,
                        symlist_iterator<T, T&> beg,
                        symlist_iterator<T, T&> end) 
{
    if (beg != end)
    {
        iterator prev = beg;
        --prev;
        iterator last = end;
        --last;

        //
        // The following seems to be rather senseless, but it is required
        // since two iterator are equal, iff the point to the same element.
        // This implies that they might have different directions. Suppose
        // that prev == end is true and they have different directions,
        // than prev.next() and end.prev() return the same element !! Thus
        // the assignment prev = end corrects this, since the direction
        // gets copied, too.
        //
        if (prev == end)
        {
            prev = end;
        }
            
        prev.next() = end.act;
        end.prev() = prev.act;

        prev = pos;
        --prev;

        if (pos == prev)
        {
            pos = prev;
        }

        if (last == beg)
        {
            last = beg;
        }
        
        prev.next() = beg.act;
        beg.prev() = prev.act;
        pos.prev() = last.act;
        last.next() = pos.act;
    }
}


template <class T>
void symlist<T>::splice(symlist_iterator<T,T&> pos, 
                        symlist_iterator<T,T&> beg)
{
    iterator tmp = beg;
    ++tmp;
    splice(pos, beg, tmp);
}


template <class T>
symlist_iterator<T,T&> symlist<T>::erase(symlist_iterator<T,T&> pos) 
{
    assert (pos.act != link);
    iterator prev = pos;
    --prev;
    iterator next = pos;
    ++next;
    
    if (next == prev)
    {
        next = prev;
    }

    next.prev() = prev.act;
    prev.next() = next.act;

    delete (pos.act);

    return next;
}

template <class T>
symlist_iterator<T,T&> symlist<T>::erase(symlist_iterator<T,T&> beg, 
                                         symlist_iterator<T,T&> end)
{
    iterator prev = beg;
    --prev;
    iterator it = beg;
    symnode<T>* act;

    while (it != end)
    {
        assert (it.act != link);
        act = it.act;
        ++it;
        delete (act);
    }

    if (prev == end)
    {
        prev = end;
    }   
    
    end.prev() = prev.act;
    prev.next() = end.act;
   
    return end;
}    


template <class T>
void symlist<T>::attach_sublist(symlist_iterator<T,T&> it, 
                                symlist_iterator<T,T&> end) 
{ 
    assert (empty());
    iterator last = end;
    --last;
    _prev = it;
    --_prev;
    _next = end;

    if (it == last)
    {
        it = last;
    }

    link->adj[0] = it.act;
    it.prev() = link;
    link->adj[1] = last.act;
    last.next() = link;
}   

    
template <class T>
void symlist<T>::detach_sublist() 
{
    if (_next != iterator())
    {
        iterator it(begin());
        iterator e(end());
        
        --e;
        
        if (e == it)
        {
            e = it;
        }

        _prev.next() = it.act;
        it.prev() = _prev.act;
        _next.prev() = e.act;
        e.next() = _next.act;
        link->adj[0] = link->adj[1] = link;

        _next = iterator();
        _prev = iterator();
    }
}


template <class T>
inline void symlist<T>::reverse()
{
    symnode<T>* tmp = link->adj[0];
    link->adj[0] = link->adj[1];
    link->adj[1] = tmp;
}

// Implementation End

__GTL_END_NAMESPACE

#endif // SYMLIST_H

//--------------------------------------------------------------------------
//   end of file
//--------------------------------------------------------------------------