Initial STL code delivery with code review changes.

Change-Id: Ib4226e1351acce15cacbe643eb2fb4f0dfb56855
Reviewed-on: http://gfwr801.rchland.ibm.com:8080/gerrit/68
Tested-by: Jenkins Server
Reviewed-by: A. Patrick Williams III <iawillia@us.ibm.com>

1 files changed, 1005 insertions, 0 deletions

diff --git a/src/include/list b/src/include/list
new file mode 100644
index 000000000..cd3a83f0a
--- /dev/null
+++ b/src/include/list
@@ -0,0 +1,1005 @@
+#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>
+
+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*                      pointer;
+            typedef T&                      reference;
+
+            /**
+             * Default constructior
+             */
+            __attribute__ ((always_inline))
+            ListIterator_t() : iv_node()
+            {}
+
+
+            /**
+             * Construct from a node pointer
+             * @pararm[in] i_ln ListNode_t to use
+             */
+            __attribute__ ((always_inline))
+            explicit ListIterator_t(ListNode_t* i_ln) : iv_node(i_ln)
+            {}
+
+            /**
+             * Dereference
+             * @return reference to node data
+             */
+            __attribute__ ((always_inline))
+            reference operator* () const
+            {
+                return  static_cast<_Node*>(iv_node)->iv_data;
+            }
+
+            /**
+             * Dereference
+             * @return pointer to node data
+             */
+            __attribute__ ((always_inline))
+            pointer   operator->() const
+            {
+                return &static_cast<_Node*>(iv_node)->iv_data;
+            }
+
+            /**
+             * Pre Increment
+             * @return reference to iterator
+             */
+            __attribute__ ((always_inline))
+            _This& operator++()
+            {
+                iv_node = iv_node->iv_next; return *this;
+            }
+
+            /**
+             * Post Increment
+             * @return reference to iterator
+             */
+            __attribute__ ((always_inline))
+            _This  operator++(int) 
+            {
+                _This tmp = *this; 
+                iv_node = iv_node->iv_next;
+                return tmp;
+            }
+
+            /**
+             * Pre decrement
+             * @return reference to iterator
+             */
+            __attribute__ ((always_inline))
+            _This& operator--()
+            {
+                iv_node = iv_node->iv_prev;
+                return *this;
+            }
+
+            /**
+             * Post decrement
+             * @return reference to iterator
+             */
+            __attribute__ ((always_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))
+            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))
+            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 const T*                pointer;
+            typedef const T&                const_reference;
+
+            /**
+             * Default constructior
+             */
+            __attribute__ ((always_inline))
+            ListConstIterator_t() : iv_node()
+            {} 
+
+            /**
+             * Construct from a const node pointer
+             * @pararm[i] ListNode_t to use
+             */
+            __attribute__ ((always_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))
+            ListConstIterator_t(const_iterator& i_ln) : iv_node(i_ln.iv_node)
+            {}
+
+            /**
+             * Dereference
+             * @return const_reference to node data
+             */
+            __attribute__ ((always_inline))
+            const_reference operator* () const
+            {
+                return  static_cast<_Node*>(iv_node)->iv_data;
+            }
+
+            /**
+             * Dereference
+             * @return const pointer to node data
+             */
+            __attribute__ ((always_inline))
+            pointer   operator->() const
+            { 
+                return &static_cast<_Node*>(iv_node)->iv_data;
+            }
+
+            /**
+             * Pre Increment
+             * @return reference to iterator
+             */
+            __attribute__ ((always_inline))
+            _This& operator++()
+            {
+                iv_node = iv_node->iv_next; return *this;
+            } 
+
+            /**
+             * Post Increment
+             * @return reference to iterator
+             */
+            __attribute__ ((always_inline))
+            _This  operator++(int) 
+            {
+                _This tmp = *this; 
+                iv_node = iv_node->iv_next;
+                return tmp;
+            } 
+
+            /**
+             * Pre decrement
+             * @return reference to iterator
+             */
+            __attribute__ ((always_inline))
+            _This& operator--()
+            {
+                iv_node = iv_node->iv_prev;
+                return *this;
+            } 
+            
+            /**
+             * Post decrement
+             * @return reference to iterator
+             */
+            __attribute__ ((always_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))
+            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))
+            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))
+    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))
+    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))
+                explicit 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 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))
+                ~list()
+                {
+                    clear();
+                }
+
+                /**
+                 * Assignment
+                 * @param[in] x reference list to copy.
+                 * @post any previously obtained iterators are invalid
+                 */
+                __attribute__ ((always_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))
+                iterator begin() { return iterator(iv_node.iv_next); }
+
+                /**
+                 * Get const_iterator to the first element in the list
+                 */
+                __attribute__ ((always_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))
+                iterator end() { return iterator(&iv_node); }
+
+                /**
+                 * Get a const_iterator to the last element in the list + 1
+                 */
+                __attribute__ ((always_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))
+                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))
+                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))
+                reference front()
+                {
+                    return *begin();
+                }
+
+                /**
+                 * Get a const_reference to the first element in the list
+                 */
+                __attribute__ ((always_inline))
+                const_reference front() const
+                {
+                    return *begin();
+                }
+
+                /**
+                 * Get a reference to the last element in the list
+                 */
+                __attribute__ ((always_inline))
+                reference back()
+                {
+                    iterator i = end();
+                    --i;
+                    return *i;
+                }
+
+                /**
+                 * Get a const_reference to the last element in the list
+                 */
+                __attribute__ ((always_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))
+                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))
+                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))
+                void push_front (const T& x)
+                {
+                    insert(begin(),x);
+                }
+
+                /**
+                 * Remove the element at the front of the container
+                 */
+                __attribute__ ((always_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))
+                void push_back (const T& x)
+                {
+                    insert(end(),x);
+                }
+
+                /**
+                 * Remove the element at the back of the container
+                 */
+                __attribute__ ((always_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