slist.hxx

Go to the documentation of this file.

/*
 *   xyzzy
 *   Copyright (C) 2007    Karl W. Pfalzer
 *
 *   This program is free software; you can redistribute it and/or
 *   modify it under the terms of the GNU General Public License
 *   as published by the Free Software Foundation; either version 2
 *   of the License, or (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program; if not, write to the
 *   Free Software Foundation, Inc.
 *   51 Franklin Street, Fifth Floor
 *   Boston, MA  02110-1301, USA.
 */

#if !defined(_xyzzy_slist_hxx_)
#    define  _xyzzy_slist_hxx_

namespace xyzzy
{
    class TSlist
    {
    public:
        unsigned length() const
        {
            return m_len;
        }

        bool isEmpty() const
        {
            return (0 == m_len);
        }

        bool hasMore() const
        {
            return !isEmpty();
        }

    protected:
        TSlist()
        :   m_len(0)
        {}

        virtual ~TSlist()
        {}

        unsigned    m_len;
    };

    template<typename T>
    class PTSlist : public TSlist
    {
    public:
        PTSlist()
        :   TSlist(),
            mp_head(0),
            mp_tail(0)
        {}

    private:
        struct Ele
        {
            Ele(T dat, Ele *pnext = 0)
            :   m_dat(dat), mp_next(pnext)
            {}

            T   m_dat;
            Ele *mp_next;
        };

    public:
        T peek() const
        {
            return mp_head->m_dat;
        }

        T pop()
        {
            T rval = peek();
            Ele *p = mp_head;
            mp_head = mp_head->mp_next;
            if (0 == --m_len)
            {
                mp_tail = 0;
            }
            delete p;
            return rval;
        }

        void append(T dat)
        {
            Ele *p = new Ele(dat);      
            if (0 != mp_tail)
            {
                mp_tail->mp_next = p;
                mp_tail = p;
            }
            else
            {
                mp_head = mp_tail = p;
            }
            m_len++;
        }

        void prepend(T dat)
        {
            Ele *p = new Ele(dat, mp_head);     
            mp_head = p;
            if (0 == mp_tail)
            {
                mp_tail = p;
            }
            m_len++;
        }

        void push(T dat)
        {
            prepend(dat);
        }

        ~PTSlist()
        {
            erase(mp_head);
            delete mp_head;
        }

    private:
        Ele *mp_head;
        Ele *mp_tail;

        void erase(Ele *start)
        {
            if (0 == start)
            {
                return;
            }
            Ele *p, *q = start->mp_next;
            while (q != 0)
            {
                p = q;
                q = q->mp_next;
                delete p;
                m_len--;
            }
            mp_tail = start;
            mp_tail->mp_next = 0;
        }

        friend class Iterator;

    public:
        class Iterator
        {
        public:
            Iterator(PTSlist &list)
            :   mp_curr(list.mp_head)
            {}

            Iterator(const Iterator &iter)
            :   mp_curr(iter.mp_curr)
            {}

            const Iterator& operator=(const Iterator &iter)
            {
                mp_curr = iter.mp_curr;
                return *this;
            }

            T& operator*() const
            {
                return mp_curr->m_dat;
            }

            T* operator->() const
            {
                return &(operator*());
            }

            const Ele* operator()() const
            {
                return mp_curr;
            }

            bool hasMore() const
            {
                return (0 != mp_curr);
            }

            // pre-incr
            Iterator& operator++()
            {
                incr();
                return *this;
            }

            // NOTE: post-incr requires copy constructor.
            Iterator operator++(int)
            {
                Iterator rval(*this);
                incr();
                return rval;
            }

        private:
            void incr()
            {
                if (0 != mp_curr)
                {
                    mp_curr = mp_curr->mp_next;
                }
            }

            Iterator(Ele *where)
            :   mp_curr(where)
            {}

            Ele     *mp_curr;       

            friend class PTSlist;
        };

        void erase(const Iterator &start)
        {
            erase(start.mp_curr);
        }

        Iterator last()
        {
            Iterator rval(mp_tail);
            return rval;
        }

        void insert(Iterator &after, T dat)
        {
            Ele *q = const_cast<Ele*>(after());
            if (mp_tail == q)
            {
                append(dat);
            }
            else
            {
                Ele *p = new Ele(dat, q->mp_next);
                q->mp_next = p;
                m_len++;
            }
        }
    };
};

#endif  //_xyzzy_slist_hxx_

---