path: root/src/include/list

/* IBM_PROLOG_BEGIN_TAG                                                   */
/* This is an automatically generated prolog.                             */
/*                                                                        */
/* $Source: src/include/list $                                            */
/*                                                                        */
/* OpenPOWER HostBoot Project                                             */
/*                                                                        */
/* Contributors Listed Below - COPYRIGHT 2011,2016                        */
/* [+] International Business Machines Corp.                              */
/*                                                                        */
/*                                                                        */
/* Licensed under the Apache License, Version 2.0 (the "License");        */
/* you may not use this file except in compliance with the License.       */
/* You may obtain a copy of the License at                                */
/*                                                                        */
/*     http://www.apache.org/licenses/LICENSE-2.0                         */
/*                                                                        */
/* Unless required by applicable law or agreed to in writing, software    */
/* distributed under the License is distributed on an "AS IS" BASIS,      */
/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        */
/* implied. See the License for the specific language governing           */
/* permissions and limitations under the License.                         */
/*                                                                        */
/* IBM_PROLOG_END_TAG                                                     */
#ifndef stl_list
#define stl_list

#include <stddef.h>
#if !defined( __STDC_LIMIT_MACROS)
#define __STDC_LIMIT_MACROS
#endif
#include <stdint.h>
#include <new>
#include <algorithm>
#include <initializer_list>

namespace std
{

    /**
     * @class ListNode_t
     *
     * @note Non template dependent part of a list node. This code will not
     * get duplicated for each type T
     */
    struct ListNode_t
    {
        ListNode_t * iv_next;
        ListNode_t * iv_prev;


        /**
         * Reset the node to point to itself
         * @post iv_next == iv_post == this
         */
        void reset()
        {
            iv_next = this;
            iv_prev = this;
        }

        /**
         * Swap this node with another node
         * @param[in] i_otherNode The other node
         * @note This node is removed from it's chain and linked into the other nodes chain
         *       The other node is removed form it's chain and linked into where this node
         *       used to be.
         */
        void swap(ListNode_t & i_otherNode)
        {
            ListNode_t temp;
            temp.link(*this);           // put temp into this chain
            unlink();                   // take this node out of the chain

            link(i_otherNode);          // put this node into i_otherNode chain
            i_otherNode.unlink();       // take i_otherNode out of the chain

            i_otherNode.link(temp);     // put i_otherNode into temp chain
            temp.unlink();              // take temp out of chain
        }

        /**
         * link this node into the i_node chain just before i_node.
         * @param[in] A node in node chain to link this node into
         */
        void link(ListNode_t & i_node)
        {
            iv_next = &i_node;
            iv_prev = i_node.iv_prev;
            i_node.iv_prev = this;
            iv_prev->iv_next = this;
        }

        /**
         * Unlink this node from the chain
         * @post this node is orphaned.
         */
        void unlink()
        {
            iv_prev->iv_next = iv_next;
            iv_next->iv_prev = iv_prev;
            reset();
        }

        /**
         * Move given chain slice into this chain before this node
         * @param[in] pointer to first node in chain to merge it
         * @param[in] pointer to last node in chin to merge in
         * @pre i_first & i_last must be in the same chain
         * @post Given chain merged in before this node, including i_last
         *       The chain i_first,i_last was taken from is healed.
         */
        void merge(ListNode_t * i_first,ListNode_t * i_last)
        {
            ListNode_t * nodeP = iv_prev;

            // Remove the source slice from it's chain
            i_first->iv_prev->iv_next = i_last->iv_next;
            i_last->iv_next->iv_prev = i_first->iv_prev;

            // link in the new slice into this chain
            nodeP->iv_next = i_first;
            iv_prev = i_last;
            i_first->iv_prev = nodeP;
            i_last->iv_next = this;
        }

        /**
         * Query if node is part of a chain
         */
        bool empty() const
        {
            return (iv_next == this) && (iv_prev == this);
        }
    };

    /**
     * @class ListNodeData_t
     *
     * @note Template dependent part of a list node.
     */
    template <typename T>
    struct ListNodeData_t : public ListNode_t
    {
        T iv_data;
    };

    /**
     * @class ListIterator_t
     * @brief Forward list iterator.
     * @note Forward iterators support:
     * <ul>
     * <li> operator== </li>
     * <li> operator!= </li>
     * <li> operator * (both rvalue, and left of assignemnt operator) </li>
     * <li> operator-> </li>
     * <li> operator-- (pre and post) </li>
     * <li> operator++ (pre and post) </li>
     * </ul>
     * @note Forward iterators are not random access i.e. don't support operator+ operator-
     */
    template<typename T>
        struct  ListIterator_t
        {
            typedef ListIterator_t<T>        _This;
            typedef ListNodeData_t<T>       _Node;

            typedef T                       value_type;
            typedef ptrdiff_t               difference_type;
            typedef T*                      pointer;
            typedef T&                      reference;

            /**
             * Default constructior
             */
            __attribute__ ((always_inline)) inline
            ListIterator_t() : iv_node()
            {}


            /**
             * Construct from a node pointer
             * @pararm[in] i_ln ListNode_t to use
             */
            __attribute__ ((always_inline)) inline
            explicit ListIterator_t(ListNode_t* i_ln) : iv_node(i_ln)
            {}

            /**
             * Dereference
             * @return reference to node data
             */
            __attribute__ ((always_inline)) inline
            reference operator* () const
            {
                return  static_cast<_Node*>(iv_node)->iv_data;
            }

            /**
             * Dereference
             * @return pointer to node data
             */
            __attribute__ ((always_inline)) inline
            pointer   operator->() const
            {
                return &static_cast<_Node*>(iv_node)->iv_data;
            }

            /**
             * Pre Increment
             * @return reference to iterator
             */
            __attribute__ ((always_inline)) inline
            _This& operator++()
            {
                iv_node = iv_node->iv_next; return *this;
            }

            /**
             * Post Increment
             * @return reference to iterator
             */
            __attribute__ ((always_inline)) inline
            _This  operator++(int)
            {
                _This tmp = *this;
                iv_node = iv_node->iv_next;
                return tmp;
            }

            /**
             * Pre decrement
             * @return reference to iterator
             */
            __attribute__ ((always_inline)) inline
            _This& operator--()
            {
                iv_node = iv_node->iv_prev;
                return *this;
            }

            /**
             * Post decrement
             * @return reference to iterator
             */
            __attribute__ ((always_inline)) inline
            _This  operator--(int)
            {
                _This tmp = *this;
                iv_node = iv_node->iv_prev;
                return *this;
            }

            /**
             * Comparison
             * @param[in] Itertor to compare
             * @return true if ==, else false
             */
            __attribute__ ((always_inline)) inline
            bool operator==(const _This& i_ln) const
            {
                return iv_node == i_ln.iv_node;
            }

            /**
             * Negative Comparison
             * @param[in] Iterator to compare
             * @return true if !=, else false;
             */
            __attribute__ ((always_inline)) inline
            bool operator!=(const _This& i_ln) const
            {
                return iv_node != i_ln.iv_node;
            }

            ListNode_t * iv_node;  ///! pointer to a list node
        };

    /**
     * @class ListIterator_t
     * @brief const Forward list iterator.
     * @note Forward iterators support:
     * <ul>
     * <li> operator== </li>
     * <li> operator!= </li>
     * <li> operator * (rvalue only) </li>
     * <li> operator-> </li>
     * <li> operator-- (pre and post) </li>
     * <li> operator++ (pre and post) </li>
     * </ul>
     * @note Forward iterators are not random access i.e. don't support operator+ operator-
     */
    template<typename T>
        struct  ListConstIterator_t
        {
            typedef ListConstIterator_t<T>      _This;
            typedef const ListNodeData_t<T>     _Node;
            typedef const ListIterator_t<T>     const_iterator;

            typedef T                       value_type;
            typedef ptrdiff_t               difference_type;
            typedef const T*                pointer;
            typedef const T&                const_reference;

            /**
             * Default constructior
             */
            __attribute__ ((always_inline)) inline
            ListConstIterator_t() : iv_node()
            {}

            /**
             * Construct from a const node pointer
             * @pararm[i] ListNode_t to use
             */
            __attribute__ ((always_inline)) inline
            explicit ListConstIterator_t(const ListNode_t* i_ln) : iv_node(i_ln)
            {}

            /**
             * Construct from another const_iterator
             * @param[i] const_iterator reference
             */
            __attribute__ ((always_inline)) inline
            ListConstIterator_t(const_iterator& i_ln) : iv_node(i_ln.iv_node)
            {}

            /**
             * Dereference
             * @return const_reference to node data
             */
            __attribute__ ((always_inline)) inline
            const_reference operator* () const
            {
                return  static_cast<_Node*>(iv_node)->iv_data;
            }

            /**
             * Dereference
             * @return const pointer to node data
             */
            __attribute__ ((always_inline)) inline
            pointer   operator->() const
            {
                return &static_cast<_Node*>(iv_node)->iv_data;
            }

            /**
             * Pre Increment
             * @return reference to iterator
             */
            __attribute__ ((always_inline)) inline
            _This& operator++()
            {
                iv_node = iv_node->iv_next; return *this;
            }

            /**
             * Post Increment
             * @return reference to iterator
             */
            __attribute__ ((always_inline)) inline
            _This  operator++(int)
            {
                _This tmp = *this;
                iv_node = iv_node->iv_next;
                return tmp;
            }

            /**
             * Pre decrement
             * @return reference to iterator
             */
            __attribute__ ((always_inline)) inline
            _This& operator--()
            {
                iv_node = iv_node->iv_prev;
                return *this;
            }

            /**
             * Post decrement
             * @return reference to iterator
             */
            __attribute__ ((always_inline)) inline
            _This  operator--(int)
            {
                _This tmp = *this;
                iv_node = iv_node->iv_prev;
                return *this;
            }

            /**
             * Comparison
             * @param[in] Iterator to compare
             * @return true if ==, else false
             */
            __attribute__ ((always_inline)) inline
            bool operator==(const _This& i_ln) const
            {
                return iv_node == i_ln.iv_node;
            }

            /**
             * Negative Comparison
             * @param[in] Itertor to compare
             * @return true if !=, else false;
             */
            __attribute__ ((always_inline)) inline
            bool operator!=(const _This& i_ln) const
            {
                return iv_node != i_ln.iv_node;
            }

            public: // data

                const ListNode_t * iv_node;
        };

    // So const and non-const iterators can be compared
    template<typename VAL> __attribute__((always_inline)) inline
    bool
    operator==( const ListIterator_t<VAL>& i_ln,
                const ListConstIterator_t<VAL>& i_lm)
    {
        return i_ln.iv_node == i_lm.iv_node;
    }

    template<typename VAL> __attribute__((always_inline)) inline
    bool
    operator!=( const ListIterator_t<VAL>& i_ln,
                const ListConstIterator_t<VAL>& i_lm)
    {
        return i_ln.iv_node != i_lm.iv_node;
    }

    /**
     * @class std::list
     *
     * @note
     * <p>Does not support:
     * <ul>
     * <li> allocators </li>
     * <li> reverse iterators </li>
     * <li> rbegin() </li>
     * <li> rend() </li>
     * <li> unique() </li>
     * <li> merge() </li>
     * <li> sort() </li>
     * </ul>
     */
    template<typename T>
        class   list
        {
            public:
                typedef ListNodeData_t<T>       _Node;
                typedef size_t                  size_type;
                typedef T &                     reference;
                typedef const T&                const_reference;
                typedef ListIterator_t<T>       iterator;
                typedef ListConstIterator_t<T>  const_iterator;


            protected:

                ListNode_t iv_node;

            private:

                /**
                 * Allocate space for a node
                 * @return pointer to the space for the node
                 */
                _Node * allocate_node()
                {
                    return (_Node *) new uint8_t[sizeof(_Node)];
                }

                /** Free node space
                 * @param[in] pointer to the node
                 */
                void deallocate_node(ListNode_t * i_p)
                {
                    delete (uint8_t *)i_p;
                }

                /**
                 * Create a new node
                 * @pararm reference to data element to use
                 * @post Space allocated, element constructed
                 */
                _Node * makeNode(const T& i_x)
                {
                    _Node * np = allocate_node();
                    new (&(np->iv_data)) T(i_x);
                    return np;
                }

                /**
                 * Destroy a node
                 * @param pointer to node
                 * @post destructor on element called, space freed.
                 */
                void destroyNode(ListNode_t * i_ln)
                {
                    _Node * np = static_cast<_Node *>(i_ln);
                    (&(np->iv_data))->~T();
                    deallocate_node(i_ln);
                }

            public:

                /**
                 *  Default ctor
                 */
                __attribute__ ((always_inline)) inline
                list()
                {
                    iv_node.reset();
                }

                /**
                 * ctor list of size n
                 * @param[in] n element size
                 * @param[in] value element reference used to construct elements
                 */
                explicit list (size_type n, const T& value = T())
                {
                    iv_node.reset();
                    while(n--) push_back(value);
                }

                /**
                 * ctor with input initialization_list
                 * @param[in] init_list Initialization list to populate list with
                 */
                list(std::initializer_list<T> init_list)
                {
                    iv_node.reset();
                    for (auto&& i: init_list)
                    {
                        push_back(i);
                    }
                }

                /**
                 * ctor from InputTerator
                 * @param[i] first Iterator to first element to copy
                 * @param[i] last  Iterator to last element + 1 to copy.
                 */
                template <class InputIterator >
                list ( InputIterator first, InputIterator last)
                {
                    iv_node.reset();
                    while(first != last) push_back(*first++);
                }

                /**
                 * copy ctor
                 * @param Referece list to copy.
                 */
                list ( const list<T>& x)
                {
                    iv_node.reset();
                    for(const_iterator i = x.begin(); i != x.end(); ++i)
                        push_back(*i);
                }

                /**
                 * dtor
                 * @post Destructors called, storaged freed.
                 */
                __attribute__ ((always_inline)) inline
                ~list()
                {
                    clear();
                }

                /**
                 * Assignment
                 * @param[in] x reference list to copy.
                 * @post any previously obtained iterators are invalid
                 */
                __attribute__ ((always_inline)) inline
                list<T>& operator= (const list<T>& x)
                {
                    list<T> new_list(x);
                    swap(new_list);
                    return *this;
                }

                // --- iterators

                /**
                 * Get iterator to first element in the list
                 */
                __attribute__ ((always_inline)) inline
                iterator begin() { return iterator(iv_node.iv_next); }

                /**
                 * Get const_iterator to the first element in the list
                 */
                __attribute__ ((always_inline)) inline
                const_iterator begin() const { return const_iterator(iv_node.iv_next); }

                /**
                 * Get an iterator to the last element in the list + 1
                 */
                __attribute__ ((always_inline)) inline
                iterator end() { return iterator(&iv_node); }

                /**
                 * Get a const_iterator to the last element in the list + 1
                 */
                __attribute__ ((always_inline)) inline
                const_iterator end() const { return const_iterator(&iv_node); }

                //reverse_iterator rbegin();
                //const_reverse_iterator rbegin() const;

                //reverse_iterator rend();
                //const_reverse_iterator rend() const;

                // ---------------- Capacity

                /**
                 * Query for empty container
                 * @return bool, true if size()==0 else false.
                 * @pre none
                 * @post none
                 */
                __attribute__ ((always_inline)) inline
                bool empty() const
                {
                    return iv_node.empty();
                }

                /**
                 * Get the number of elements in the container
                 * @return number of elements in the container
                 */
                size_type size() const
                {
                    size_type size = 0;
                    for(const_iterator i = begin(); i != end(); ++i) ++size;
                    return(size);
                }

                /**
                 * Return the maximum potential size the container could reach.
                 * @return number of the maximum element count this container could reach
                 */
                __attribute__ ((always_inline)) inline
                size_type max_size() const  { return UINT64_MAX/sizeof(T); }

                /**
                 * Resize the vector to contain n elements
                 * @param n, new size
                 * @param object used to copy to any added elements if size() is increased
                 * @post All previously obtained iterators are invalid.
                 * @node if n < size(), vector is truncated.
                 *       if n > size(), vector is padded with copies of x
                 */
                void resize( size_type n, T x = T() )
                {
                    size_type sz = size();
                    if(n < sz)
                    {
                        while(n != sz--) pop_back();
                    }
                    else if(n > sz)
                    {
                        while(n != sz++) push_back(x);
                    }
                    // else n == size() do nothing
                }

                //---------------Element Access

                /**
                 * Get a reference to the first element in the list
                 */
                __attribute__ ((always_inline)) inline
                reference front()
                {
                    return *begin();
                }

                /**
                 * Get a const_reference to the first element in the list
                 */
                __attribute__ ((always_inline)) inline
                const_reference front() const
                {
                    return *begin();
                }

                /**
                 * Get a reference to the last element in the list
                 */
                __attribute__ ((always_inline)) inline
                reference back()
                {
                    iterator i = end();
                    --i;
                    return *i;
                }

                /**
                 * Get a const_reference to the last element in the list
                 */
                __attribute__ ((always_inline)) inline
                const_reference back() const
                {
                    const_iterator i = end();
                    --i;
                    return *i;
                }

                //---------- Modifiers

                /**
                 * Assign a slice of a container to this list
                 * @param[in] first InputIterator to the first element to assign
                 * @pararm[in] last InputIterator to the last element to assign
                 * @post any previously obtained iterators are invalid
                 */
                template <class InputIterator>
                __attribute__ ((always_inline)) inline
                void assign( InputIterator first, InputIterator last)
                {
                    list<T> new_list(first,last);
                    swap(new_list);
                }

                /**
                 * Assign a list of n elements of type T
                 * @param[in] n Number of elements to assign
                 * @param[in] x Reference to the element used to create elements.
                 * @post any previously obtained iterators are invalid
                 */
                __attribute__ ((always_inline)) inline
                void assign( size_type n, const T& x)
                {
                    list<T> new_list(n,x);
                    swap(new_list);
                }

                /**
                 * Add an element to the front fo the list
                 * @pararm Element to add
                 */
                __attribute__ ((always_inline)) inline
                void push_front (const T& x)
                {
                    insert(begin(),x);
                }

                /**
                 * Remove the element at the front of the container
                 */
                __attribute__ ((always_inline)) inline
                void pop_front ()
                {
                    erase(begin());
                }

                /**
                 * Add an element to the back of the container
                 * @param[in] x referece to element to add
                 * @post size()+= 1;
                 */
                __attribute__ ((always_inline)) inline
                void push_back (const T& x)
                {
                    insert(end(),x);
                }

                /**
                 * Remove the element at the back of the container
                 */
                __attribute__ ((always_inline)) inline
                void pop_back ()
                {
                    iterator i = end();
                    --i;
                    erase(i);
                }

                /**
                 * Instert an element into the container at the given position
                 * @param[in] pos Iterator position to insert element
                 * @return iterator to newly inserved element
                 */
                iterator insert ( iterator pos, const T& x)
                {
                    ListNode_t * node = makeNode(x);
                    node->link(*pos.iv_node);
                    return iterator(node);
                }

                /**
                 * Insert n elements at the given position
                 * @param[in] pos position to insert elements
                 * @param[in] n number of elements to insert
                 * @param[in] ref const_reference of element used to create elements
                 */
                void insert(iterator pos, size_type n, const T& ref)
                {
                    while(n--) insert ( pos, ref);
                }


                /**
                 * Insert a copy of a container slice into this container
                 * @param[in] pos iterator to postion to add elements in this list
                 * @param[in] first InputIterator to the first element to copy insert
                 * @param[in] last InputIterator to the last element+1 to copy insert
                 */
                template <class InputIterator>
                void insert (iterator pos, InputIterator first, InputIterator last)
                {
                    while(first != last)
                    {
                       pos = insert(pos,*first++);
                       ++pos;
                    }
                }

                /**
                 * Erase the element at the given postion
                 * @pararm[i] pos iterator to position to erase/remove
                 * @return iterator to the element following the one removed
                 */
                iterator erase (iterator pos)
                {
                    iterator ret = end();
                    if(!empty())
                    {
                        ret = pos;
                        ++ret;
                        (pos.iv_node)->unlink();
                        destroyNode(pos.iv_node);
                    }
                    return ret;
                }

                /**
                 * Erase a range of elements
                 * @param[in] first iterator to the first element to erase
                 * @param[in] last iterator to the last element+1 to erase
                 * @return iterator to the element following the last one removed
                 */
                iterator erase (iterator first, iterator last)
                {
                    while(first != last) first = erase(first);
                    return last;
                }

                /**
                 * Swap the elements of this containers with the one provided
                 * @param[in] reference to list container to swap elements with.
                 */
                void swap ( list<T>& i_that)
                {
                    iv_node.swap(i_that.iv_node);
                }

                 /**
                 * clear all elements from the ist.
                 * @post size() == 0; elements destroyed, space freed.
                 */
                void clear()
                {
                    iterator i = begin();
                    while( i != end() )
                    {
                        iterator j = i++;
                        destroyNode(j.iv_node);
                    }
                    iv_node.reset();
                 }


                // -------- operations

                /**
                 * Move elements from another list container to this list container at the given position.
                 * @param[in] pos position in this list to move elements to
                 * @param[in] list object of containing the same type of elements as this one.
                 * @pre x != *this
                 * @post this->size() += x.size();  x.empty() == true
                 */
                void splice ( iterator pos, list<T>& x)
                {
                    if(!x.empty())
                    {
                        pos.iv_node->merge(x.iv_node.iv_next,x.iv_node.iv_prev);
                    }
                }

                /**
                 * Move an element from another list into this list at the given position.
                 * @param[in] pos position destination in this list to move element to
                 * @param[in] x list object containing the same type of elements as this one.
                 * @param[in] i postion source in list x to move element from
                 * @pre x can be *this if pos != i
                 * @post Iterators pointing to moved elements are no longer valid.
                 *       this->size() += 1, if (x != *this) x.size() -= 1;
                 */
                void splice ( iterator pos, list<T>& x, iterator i)
                {
                    i.iv_node->unlink();
                    i.iv_node->link(*pos.iv_node);
                }

                /**
                 * Move elements from another list container to this list container at the given position.
                 * @param[in] pos postion in this list container to move elements to.
                 * @param[in] x list object containing the same type of elements as this one.
                 * @param[in] first iterator to first element to move.
                 * @param[in] last  iterator to last element to move + 1.
                 * @pre x can be *this as long as  pos < first || pos >= last
                 * @post x.size() is reduced by # of elements moved if x is not *this
                 *       size() is increased by # of elements moved.
                 *       Iterator pointing to moved elements are no longer valid.
                 * @note Moves all elements between first & last, including first, but not including last
                 */
                void splice ( iterator pos, list<T>& x, iterator first, iterator last)
                {
                    --last;
                    pos.iv_node->merge(first.iv_node,last.iv_node);
                }

                /**
                 * Remove all elements with the specific value.
                 * @param[in] value that must match to remove
                 * @post Matched objects destroyed and removed from list
                 */
                void remove ( const T& value )
                {
                    iterator i = begin();
                    while(i != end())
                    {
                        iterator j = i++;
                        if(*j == value) erase(j);
                    }
                }

                /**
                 * Removes from the list all the elements for which Predicate returns true.
                 * @param[in] predicate function or functor
                 * @post Matched objects destroyed and removed from list
                 * @note Predicate can be implemented as any typed expression taking one
                 *       argument of the same type as the list and returning bool.
                 *       This may either be a function pointer or an object whose class
                 *       implements operator().
                 */
                template <class Predicate>
                void remove_if ( Predicate pred )
                {
                    iterator i = begin();
                    while(i != end())
                    {
                        iterator j = i++;
                        if(pred(*j)) erase(j);
                    }
                }

                /**
                 * Remove all but the first element from every consecutive group of equal elements.
                 * @pre This container is sorted.
                 * @post All but the first element from every consecutive group of equal elements is removed
                 * @note An element is only removed from the list if it is equal to the element
                 *       immediately preceding it.
                 * @note Not implemented
                 */
                void unique( );

                /**
                 * Remove all but the first element from every consecutive group of unique elements
                 * where uniqueness is determined by the BinaryPredicate.
                 * @note The BinaryPredicate takes two values of the same type as in the list,
                 *       returns true to remove from the container the element passed as first
                 *       argument.
                 *       Not implmented
                 */
                template <class BinaryPredicate>
                    void unique ( BinaryPredicate binary_pred);

                /**
                 * Merges another list into this list, inserting elements into the list at their
                 * repective ordered positions.
                 * @param[in] x container of same type elements as this container.
                 * @pre The containers are sorted.
                 * @post x.size() == 0
                 * @note Not Implemented
                 */
                void merge( list<T>& x );

                /**
                 * Merges another list into this list, inserting elements into the list at their
                 * repective ordered positions.
                 * @post x.size() == 0
                 * @note The comparison function takes two values of the same type as the list
                 * elements, returns true of the first argument is less than the second, otherwise
                 * false
                 * @note Not Implemented
                 */
                template <class Compare>
                    void merge ( list<T>& x, Compare comp);

                /**
                 * Sort the elements in the list from lower to higher
                 * @pre Container element objects must implement operator<.
                 * @note Not Implemented
                 */
                void sort();

                /**
                 * Sort the elements in the list from lower to higher using compare function
                 * @param Compare function that takes two values the same type as contained in the
                 * list; returns true if first arg goes before second arg, otherwise false.
                 * @note Not Implemented.
                 */
                template <class Compare>
                    void sort (Compare comp);

                /**
                 * Reverse the order of the elements in the list.
                 */
                void reverse ()
                {
                    iterator i = begin();
                    while(i != end())
                    {
                        iterator j = i++;
                        std::swap(j.iv_node->iv_next,j.iv_node->iv_prev);
                    }
                    std::swap(iv_node.iv_next,iv_node.iv_prev);
                }


        };
};

#endif
/* vim: set filetype=cpp : */