Saf/Collection/ForwardList.h

Go to the documentation of this file.

/*
    This file is part of Simple Application Framework (Saf) library.
    Copyright (C) 2010 - 2012 Ondrej Danek <ondrej.danek@gmail.com>

    This library 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 3 of the License, or
    (at your option) any later version.

    Saf 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 Simple Application Framework library. If not, 
    see <http://www.gnu.org/licenses/>.
*/

#ifndef SAF_COLLECTION_FORWARDLIST_H
#define SAF_COLLECTION_FORWARDLIST_H

#include "../Type.h"
#include "../Mem/Alloc.h"
#include "../Algo/Swap.h"
#include "../Type/IteratorCategory.h"

namespace Saf
{
    namespace Collection
    {        
        template <class T> 
        class ForwardList
        {
        protected:
            typedef ForwardList<T> MyType;

        protected:
            class Node
            {
            public:
                Node *m_next;
                T m_val;

            public:
                Node(const T& val)
                    : m_val(val)
                {}
            };

        public:
            class ConstIterator
            {
            public:
                typedef T ValType;
                typedef Type::IteratorCategory::ForwardCategory CategoryType;

            protected:
                Node *m_node;

                // The list can access the protected members
                friend class ForwardList<T>;

            public:
                ConstIterator()
                {}

                explicit ConstIterator(Node *node)
                    : m_node(node)
                {}

                ConstIterator(const ConstIterator& iter)
                    : m_node(iter.m_node)
                {}
                    
                ConstIterator& operator=(const ConstIterator& iter)
                {
                    m_node = iter.m_node;
                    return *this;
                }

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

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

                ConstIterator& operator++()
                {
                    m_node = m_node->m_next;
                    return *this;
                }

                ConstIterator operator++(int)
                {
                    ConstIterator ci(*this);
                    ++(*this);
                    return ci;
                }

                bool operator==(const ConstIterator& ci)
                {
                    return (m_node == ci.m_node);
                }

                bool operator!=(const ConstIterator& ci)
                {
                    return (m_node != ci.m_node);
                }
            };

            class Iterator
                : public ConstIterator
            {
            public:
                Iterator()
                    : ConstIterator()
                {}

                explicit Iterator(Node *node)
                    : ConstIterator(node)
                {}

                Iterator(const Iterator& iter)
                    : ConstIterator(iter)
                {}
                    
                Iterator& operator=(const Iterator& iter)
                {
                    ConstIterator::operator=(iter);
                    return *this;
                }

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

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

                Iterator& operator++()
                {
                    this->m_node = this->m_node->m_next;
                    return *this;
                }

                Iterator operator++(int)
                {
                    Iterator it(*this);
                    ++(*this);
                    return it;
                }
            };

        private:
            Node *m_head;
            Node *m_last;

        private:
            void Init()
            {
                Mem::OperatorNew(m_head, SAF_SOURCE_LOCATION);
                m_head->m_next = nullptr;
                m_last = m_head;
            }

        public:
            ForwardList()
            {
                Init();
            }

            ForwardList(const MyType& list)
            {
                Init();
                *this = list;
            }

            ~ForwardList()
            {
                Free();
                Mem::OperatorDelete(m_head);
            }

            void Free()
            {
                Node *n = m_head->m_next, *nprev;

                while (n != nullptr)
                {
                    nprev = n;
                    n = n->m_next;
                    Mem::Delete(nprev);
                }

                m_head->m_next = nullptr;
                m_last = m_head;
            }

            MyType& operator=(const MyType& l)
            {
                if (&l != this)
                {
                    Free();

                    // Copy
                    Node *nprev = m_head, *ndst, *nsrc = l.m_head->m_next;

                    while (nsrc != nullptr)
                    {
                        ndst = SAF_NEW Node(nsrc->m_val);
                        nprev->m_next = ndst;
                        nprev = ndst;
                        nsrc = nsrc->m_next;
                    }

                    nprev->m_next = nullptr;
                    m_last = nprev;
                }

                return *this;
            }

            MyType& Swap(MyType& fl)
            {
                Algo::Swap(m_head, fl.m_head);
                Algo::Swap(m_last, fl.m_last);

                return *this;
            }

            bool IsEmpty() const
            {
                return (m_head->m_next == nullptr);
            }

            MyType& PushFront(const T &val)
            {
                InsertAfter(BeforeBegin(), val);
                return *this;
            }

            MyType& PushBack(const T &val)
            {
                InsertAfter(Back(), val);
                return *this;
            }

            MyType& PopFront()
            {
                if (!IsEmpty())
                {
                    EraseAfter(BeforeBegin());
                }

                return *this;
            }

            Iterator InsertAfter(Iterator iter, const T &val)
            {
                Node *b = iter.m_node, *n = SAF_NEW Node(val);

                n->m_next = b->m_next;
                b->m_next = n;

                if (b == m_last)
                {
                    m_last = n;
                }

                return Iterator(n);
            }

            Iterator EraseAfter(Iterator iter)
            {
                Node *n = iter.m_node, *nsucc = n->m_next;

                if (nsucc == m_last)
                {
                    m_last = n;
                }

                n->m_next = nsucc->m_next;
                Mem::Delete(nsucc);

                return Iterator(n->m_next);
            }

            MyType& SpliceAfter(Iterator el, MyType& list)
            {
                return SpliceAfter(el, list, list.BeforeBegin(), list.Back());
            }

            MyType& SpliceAfter(Iterator el, MyType& list, Iterator first)
            {
                Iterator last = first;
                return SpliceAfter(el, list, first, ++last);
            }

            MyType& SpliceAfter(Iterator el, MyType& list, 
                Iterator first, Iterator last)
            {
                Node *nw = el.m_node, *nws = nw->m_next;
                Node *nf = first.m_node, *nl = last.m_node;

                nw->m_next = nf->m_next;
                nf->m_next = nl->m_next;
                nl->m_next = nws;

                if (nl == list.m_last)
                {
                    list.m_last = nf;
                }

                if (nw == m_last)
                {
                    m_last = nl;
                }

                return *this;
            }

            template <class Pred>
            Size RemoveIf(Pred pred)
            {
                Node *ncur = m_head->m_next, *nlast = m_head;
                Size removed = 0;

                while (ncur != nullptr)
                {
                    if (pred(ncur->m_val))
                    {
                        // Predicate holds -> remove element.
                        nlast->m_next = ncur->m_next;
                        Mem::Delete(ncur);
                        ncur = nlast->m_next;

                        ++removed;
                    }
                    else
                    {
                        // Advance.
                        nlast = ncur;
                        ncur = ncur->m_next;
                    }   
                }

                m_last = nlast;

                return removed;
            }

            template <class Pred>
            Size Unique(Pred pred)
            {
                Size removed = 0;

                if (!IsEmpty())
                {
                    Node *nlast = m_head->m_next;
                    Node *ncur = nlast->m_next;                

                    while (ncur != nullptr)
                    {
                        if (pred(nlast->m_val, ncur->m_val))
                        {
                            // Match -> remove element.
                            nlast->m_next = ncur->m_next;
                            Mem::Delete(ncur);
                            ncur = nlast->m_next;

                            ++removed;
                        }
                        else
                        {
                            // No match -> advance.
                            nlast = ncur;
                            ncur = ncur->m_next;
                        }
                    }

                    m_last = nlast;
                }

                return removed;
            }

            template <class Comp>
            MyType& Merge(MyType& list, Comp comp)
            {
                if (this != &list)
                {
                    Iterator nb1 = BeforeBegin(), nc1 = Begin(), ne1 = End();
                    Iterator nc2 = list.Begin(), ne2 = list.End();

                    while (nc1 != ne1 && nc2 != ne2)
                    {
                        if (comp(*nc2, *nc1))
                        {
                            Iterator nb2 = list.BeforeBegin();

                            do
                            {
                                ++nb2;
                                ++nc2;
                            } while (nc2 != ne2 && comp(*nc2, *nc1));

                            SpliceAfter(nb1, list, list.BeforeBegin(), nb2);
                            nb1 = nb2;
                        }

                        ++nb1;
                        ++nc1;
                    }

                    if (nc2 != ne2)
                    {
                        SpliceAfter(nb1, list);
                    }
                }

                return *this;
            }

            template <class Comp>
            MyType& Sort(Comp comp)
            {
                // Sort only if at least two elements present
                if (m_head->m_next != nullptr && m_head->m_next->m_next != nullptr)
                {
                    const Size MaxBin = 40;
                    ForwardList<T> lcarry, lbin[MaxBin + 1];
                    Size lastBin = 0, curBin;

                    while (!IsEmpty())
                    {
                        lcarry.SpliceAfter(lcarry.BeforeBegin(), *this, BeforeBegin());

                        for (curBin = 0; curBin < lastBin && !lbin[curBin].IsEmpty(); ++curBin)
                        {
                            lbin[curBin].Merge(lcarry, comp);
                            lbin[curBin].Swap(lcarry);
                        }

                        if (curBin == MaxBin)
                        {
                            lbin[curBin - 1].Merge(lcarry, comp);
                        }
                        else
                        {
                            lbin[curBin].Swap(lcarry);
                            if (curBin == lastBin)
                            {
                                lastBin++;
                            }
                        }
                    }

                    for (curBin = 1; curBin < lastBin; ++curBin)
                    {
                        lbin[curBin].Merge(lbin[curBin - 1], comp);
                    }

                    Swap(lbin[lastBin - 1]);
                }

                return *this;
            }

            MyType& Reverse()
            {
                if (!IsEmpty())
                {
                    Node *nprev = nullptr, *nc = m_head->m_next, *nn;

                    m_last = nc;

                    while (nc != nullptr)
                    {
                        nn = nc->m_next;
                        nc->m_next = nprev;
                        nprev = nc;
                        nc = nn;
                    }

                    m_head->m_next = nprev;
                }

                return *this;
            }

            Iterator Begin()
            {
                return Iterator(m_head->m_next);
            }

            ConstIterator Begin() const
            {
                return ConstIterator(m_head->m_next);
            }

            Iterator End()
            {
                return Iterator(nullptr);
            }

            ConstIterator End() const
            {
                return ConstIterator(nullptr);
            }

            Iterator Front()
            {
                return Begin();
            }

            ConstIterator Front() const
            {
                return Begin();
            }

            Iterator Back()
            {
                return Iterator(m_last);
            }

            ConstIterator Back() const
            {
                return ConstIterator(m_last);
            }

            Iterator BeforeBegin()
            {
                return Iterator(m_head);
            }

            ConstIterator BeforeBegin() const
            {
                return ConstIterator(m_head);
            }
        };
    }

    namespace Algo
    {
        // Swap specialization for forward list container.
        template <class T>
        struct SwapFunc< Collection::ForwardList<T> >
        {
            void operator()(Collection::ForwardList<T>& x, Collection::ForwardList<T>& y)
            {
                x.Swap(y);
            }
        };
    }
}

#endif