Saf/Collection/List.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_LIST_H
#define SAF_COLLECTION_LIST_H

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

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

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

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

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

            protected:
                Node *m_node;

                // The list can access the protected members
                friend class List<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;
                }

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

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

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

                bool operator!=(const ConstIterator& ci) const
                {
                    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;
                }

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

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

        private:
            Node *m_head;

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

        public:
            List()
            {
                Init();
            }

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

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

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

                while (n != m_head)
                {
                    n = n->m_next;
                    Mem::Delete(n->m_prev);
                }

                m_head->m_next = m_head;
                m_head->m_prev = 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 != l.m_head)
                    {
                        ndst = SAF_NEW Node(nsrc->m_val);
                        ndst->m_prev = nprev;
                        nprev->m_next = ndst;
                        nprev = ndst;
                        nsrc = nsrc->m_next;
                    }

                    nprev->m_next = m_head;
                    m_head->m_prev = nprev;
                }

                return *this;
            }

            MyType& Swap(MyType& l)
            {
                Algo::Swap(m_head, l.m_head);
                return *this;
            }

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

            MyType& PushFront(const T &val)
            {
                InsertBefore(Front(), val);
                return *this;
            }

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

            MyType& PopFront()
            {
                if (!IsEmpty())
                {
                    Erase(Front());
                }
                return *this;
            }

            MyType& PopBack()
            {
                if (!IsEmpty())
                {
                    Erase(Back());
                }
                return *this;
            }

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

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

                return Iterator(n);
            }

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

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

                return Iterator(n);
            }

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

                n->m_prev->m_next = r;
                r->m_prev = n->m_prev;
                Mem::Delete(n);

                return Iterator(r);
            }

            MyType& SpliceBefore(Iterator el, MyType& list)
            {
                return SpliceBefore(el, list.Begin(), list.End());
            }

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

            MyType& SpliceBefore(Iterator el, Iterator first, Iterator last)
            {
                Node *nw = el.m_node;
                Node *nf = first.m_node, *nl = last.m_node;

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

                Node *nt = nw->m_prev;
                nw->m_prev = nl->m_prev;
                nl->m_prev = nf->m_prev;
                nf->m_prev = nt;

                return *this;
            }

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

                while (ncur != m_head)
                {
                    if (pred(ncur->m_val))
                    {
                        // Predicate holds -> remove element.
                        Node *nerase = ncur, *nprev = ncur->m_prev;
                        ncur = ncur->m_next;

                        nprev->m_next = ncur;
                        ncur->m_prev = nprev;
                        Mem::Delete(nerase);

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

                return removed;
            }

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

                while (ncur != m_head)
                {
                    if (pred(nlast->m_val, ncur->m_val))
                    {
                        // Match -> remove element.
                        Node *nerase = ncur;
                        ncur = ncur->m_next;

                        nlast->m_next = ncur;
                        ncur->m_prev = nlast;
                        Mem::Delete(nerase);

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

                return removed;
            }

            template <class Comp>
            MyType& Merge(MyType& list, Comp comp)
            {
                if (this != &list)
                {
                    Iterator nf1 = Begin(), nl1 = End();
                    Iterator nf2 = list.Begin(), nl2 = list.End();

                    while (nf1 != nl1 && nf2 != nl2)
                    {
                        if (comp(*nf2, *nf1))
                        {
                            do
                            {
                                ++nf2;
                            } while (nf2 != nl2 && comp(*nf2, *nf1));

                            SpliceBefore(nf1, list.Begin(), nf2);
                        }

                        ++nf1;
                    }

                    if (nf2 != nl2)
                    {
                        SpliceBefore(nl1, nf2, nl2);
                    }
                }

                return *this;
            }

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

                    while (!IsEmpty())
                    {
                        lcarry.SpliceBefore(lcarry.Begin(), Begin());

                        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()
            {
                Node *nc = m_head, *nn;

                do
                {
                    nn = nc->m_next;
                    nc->m_next = nc->m_prev;
                    nc->m_prev = nn;
                    nc = nn;
                } while (nc != m_head);

                return *this;
            }

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

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

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

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

            Iterator Front()
            {
                return Begin();
            }

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

            Iterator Back()
            {
                return Iterator(m_head->m_prev);
            }

            ConstIterator Back() const
            {
                return ConstIterator(m_head->m_prev);
            }
        };
    }

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

#endif