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>

3 files changed, 1957 insertions, 0 deletions

diff --git a/src/include/algorithm b/src/include/algorithm
new file mode 100644
index 000000000..9bf0aa006
--- /dev/null
+++ b/src/include/algorithm
@@ -0,0 +1,132 @@
+#ifndef ALGORITHM
+#define ALGORITHM
+
+#ifdef __cplusplus
+namespace std
+{
+    /**
+     * Copy a range of elements
+     * @param[in] first InputIterator to the initial position in the source sequence.
+     * @param[in] last  InputIterator to last position + 1 in the source sequence.
+     * @param[in] result OutputIterator to initial position in the destination sequence.
+     * @return an iterator to the last element in the destination range
+     * @note If both ranges overlap in such a way that result points to an elmenent in the source
+     * range then fuction copy_backward should be used.
+     */
+    template <class InputIterator, class OutputIterator>
+    inline OutputIterator
+    copy (InputIterator first, InputIterator last, OutputIterator result )
+    {
+        while(first!=last)
+        {
+            *result = *first;
+            ++result;
+            ++first;
+        }
+        return result;
+    }
+
+    /**
+     * Copy a range of elements backwards
+     * @param[in] first Bidirectional iterator to the initial source position
+     * @param[in] last  Bidirectional iterator to the final source position + 1
+     * @param[in] result Bidirectional iterator to end of the destination sequence + 1.
+     * @return an iterator to the first element in the destination sequence.
+     * @note If both ranges overlap in such a way that result points to an element in the  source
+     * range, the function copy should be used instead.
+     */
+    template <class BidirectionalIterator1, class BidirectionalIterator2>
+    inline BidirectionalIterator2 
+    copy_backward (  BidirectionalIterator1 first,
+                     BidirectionalIterator1 last,
+                     BidirectionalIterator2 result )
+    {
+        while(last!=first)
+        {
+            --result;
+            --last;
+            *result = *last;
+        }
+        return result;
+    }
+
+    /**
+     * Exchange values of two objects
+     * @param[in] a reference to an object to be swaped with b
+     * @param[in] b reference to an object to be swaped with a
+     * @note this function may not be an efficient way to swap large objects.
+     */
+    template <class T> 
+        inline void 
+        swap(T& a, T&b )
+    {
+        T c(a);
+        a=b;
+        b=c;
+    }
+
+    /**
+     * Fill a range with value
+     * @param[in] first ForwardIterator to the first position in the source range.
+     * @param[in] last  ForwardIterator to the last position +1 in the source range.
+     * @param[in] value reference to the object used to fill the sequence.
+     */
+    template < class ForwardIterator, class T >
+    inline void
+    fill (ForwardIterator first, ForwardIterator last, const T& value )
+    {
+        while (first != last)
+        {
+            *first = value;
+            ++first;
+        }
+    }
+
+    /**
+     * Fill a sequence with value
+     * @param[in] first OutputIterator to the first position in the sequence.
+     * @param[in] n number of elements in the sequence
+     * @param[in] value reference to the value used to fill the sequence.
+     */
+    template < class OutputIterator, class Size, class T >
+    inline void
+    fill_n( OutputIterator first, Size n, const T& value )
+    {
+        for(; n>0; --n)
+        {
+            *first = value;
+            ++first;
+        }
+    }
+
+    /**
+     * Return the lesser of two arguments
+     * @param[in] a object reference
+     * @param[in] b object reference
+     * @return reference to te lesser object
+     */
+    template <class T>
+    inline const T& 
+    min(const T& a, const T& b)
+    {
+        if( b < a) return b;
+        return a;
+    }
+
+    /**
+     * Return the greater of two arguments
+     * @param[in] a object reference
+     * @param[in] b object reference
+     * @return reference to te greater object
+     */    
+    template <class T>
+    inline const T&
+    max(const T& a, const T& b)
+    {
+        if(a < b) return b;
+        return a;
+    }
+};
+#endif
+
+#endif
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
diff --git a/src/include/vector b/src/include/vector
new file mode 100644
index 000000000..fe6efec06
--- /dev/null
+++ b/src/include/vector
@@ -0,0 +1,820 @@
+#ifndef stl_vector
+#define stl_vector
+
+/**
+ * @file vector
+ * @brief simple stl vector template class declaration.
+ */
+
+#include <stddef.h>
+
+#if !defined( __STDC_LIMIT_MACROS)
+#define __STDC_LIMIT_MACROS
+#endif
+#include <stdint.h>
+#include <new>
+#include <algorithm>
+#include <assert.h>
+
+namespace std
+{
+
+    /**
+     * @class vector
+     * subset of stl vector
+     * @note Does not support allocators, reverse iterators.
+     */
+    template <class T>
+        class vector
+        {
+            public:
+
+                typedef T * iterator;
+                typedef const T * const_iterator;
+                typedef T & reference;
+                typedef const T & const_reference;
+                typedef size_t size_type;
+                typedef size_t difference_type;
+                //  typedef ptrdiff_t difference_type;
+                typedef T value_type;
+                typedef T * pointer;
+                typedef const T * const_pointer;
+
+
+            protected:
+
+                pointer iv_start;
+                pointer iv_finish;
+                pointer iv_end_of_storage;
+
+            public:
+
+                /**
+                 * Constructor default
+                 * @post     The vector is created with no elements. size() == 0, capacity() == 0
+                 */
+                __attribute__ ((always_inline))
+                explicit vector(void)
+                   :
+                        iv_start(NULL),
+                        iv_finish(NULL),
+                        iv_end_of_storage(NULL)
+                {}
+
+
+                /**
+                 * Constructor to create a vector of size n elements of value.
+                 * @param[in] n number of elements to create
+                 * @param[in] value used to create the n elements
+                 * @post     The vector is created with n elements of value.
+                 *           Storage allocated. size() == n, capacity() == n
+                 */
+                explicit vector(size_type n, const T& value = T())
+                    :
+                        iv_start(NULL),
+                        iv_finish(NULL),
+                        iv_end_of_storage(NULL)
+                {
+                    reserve(n);
+                    iv_finish = iv_start+n;
+                    ctor_fill(iv_start,iv_finish,value);
+                }
+
+
+                /**
+                 * COPY CTOR create a vector from another vector
+                 * @param[in] x  source vector
+                 * @post     vector of x.size() is created from x with same # nodes
+                 *           size() == capacity() == x.size()
+                 */
+                vector(const vector<T>& x)
+                    :
+                        iv_start(NULL),
+                        iv_finish(NULL),
+                        iv_end_of_storage(NULL)
+                {
+                    reserve(x.size());
+                    iv_finish = ctor_copy(x.iv_start, x.iv_finish, iv_start);
+                }
+
+                /**
+                 * CTOR create a vector from a container slice
+                 * @param[in] first iterator first in source sequence
+                 * @param[in] last  iterator one past end of source sequence
+                 * @returns  None.
+                 * @pre      last > first; first,last contained within source vector
+                 * @post     vector is created from slice given
+                 */
+                template<typename InputIterator>
+                    vector(InputIterator first, InputIterator last)
+                    :
+                        iv_start(NULL),
+                        iv_finish(NULL),
+                        iv_end_of_storage(NULL)
+                {
+                    //    assert(last >= first);
+                    // input iterators only support operator ( ++i, i++,==,!=,*,->,=)
+                    size_type n = 0;
+                    for(InputIterator i = first; i != last; ++i) ++n;
+                    reserve(n);
+                    iv_finish = ctor_copy(first,last,iv_start);
+                }
+
+                /**
+                 * DTOR
+                 * @post     Storage released
+                 */
+                __attribute__ ((always_inline))
+                ~vector()
+                {
+                    clear();  // call dtors
+                    free_storage(iv_start);
+                }
+
+                /**
+                 * Assignment operator.
+                 * @param[in] x   A vector.
+                 * @return  A vector (for the purpose of multiple assigns). 
+                 * @pre     None.
+                 * @post    *this == x, this->capacity() == x.size().
+                 *           All previously obtained iterators are invalid.
+                 */
+                vector<T>& operator=(const vector<T>& x)
+                {
+                    clear();
+                    reserve(x.size());
+                    iv_finish = ctor_copy(x.iv_start, x.iv_finish, iv_start);
+                    return(*this); 
+                }
+                
+                // Iterators --------------------
+                
+                /**
+                 * Get iterator to the first vector element
+                 * @return iterator of rist vector element
+                 * @pre None.
+                 * @post None.
+                 */
+                __attribute__ ((always_inline))
+                iterator begin()
+                { 
+                    return (iv_start);
+                }
+
+                /**
+                 * Get const_iterator to the first vector element
+                 * @return const_iterator of rist vector element
+                 * @pre None.
+                 * @post None.
+                 */
+                __attribute__ ((always_inline))
+                const_iterator begin() const
+                { 
+                    return (iv_start);
+                }
+
+                /**
+                 * Get iterator to the last vector element + 1
+                 * @return iterator
+                 * @pre None.
+                 * @post None.
+                 */
+                __attribute__ ((always_inline))
+                iterator end()
+                { 
+                    return (iv_finish);
+                }
+
+                /**
+                 * Get const_iterator to the last vector element + 1
+                 * @return const_iterator
+                 * @pre None.
+                 * @post None.
+                 */
+                __attribute__ ((always_inline))
+                const_iterator end() const
+                { 
+                    return (iv_finish);
+                }
+
+                /* TODO - Implement only if needed
+                reverse_iterator rbegin()
+                {
+                    return(iv_finish -1);
+                }
+
+                const_reverse_iterator rend()
+                {
+                    return (iv_start - 1);
+                }
+                */
+
+                //  Capacity -----------------------------------------------
+
+                /**
+                 * Get the number of elements in the container
+                 * @return number of elements in the container
+                 */
+                __attribute__ ((always_inline))
+                size_type size() const
+                {
+                    return(iv_finish - iv_start);
+                }
+
+                /**
+                 * 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[in]  n new size
+                 * @param[in] x 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());
+
+                /**
+                 * Get the number of elements the vector can hold before needing to reallocate storage.
+                 * @return element capacity of the vector 
+                 * @pre   None.
+                 * @post  None.
+                 */
+                __attribute__ ((always_inline))
+                size_type capacity() const
+                {
+                    return(iv_end_of_storage - iv_start);
+                }
+
+                /**
+                 * Query for empty container
+                 * @return bool, true if size()==0 else false.
+                 * @pre none
+                 * @post none
+                 */
+                __attribute__ ((always_inline))
+                bool empty() const
+                {
+                    return(size() == 0);
+                }
+
+                 /**
+                  * Reserve storage for a given number of elements
+                  * @param[in] n The requested capacity of the vector
+                  * @pre  None
+                  * @post If current cpacity() < n then new capcity == n; else no change.
+                  *       All previously obtained iterators are invalid
+                  */
+                void reserve(size_type n);
+
+                // - Element Access -----------------------------------
+
+                /**
+                 * Access a mutable reference to an element in the container
+                 * @param An index into the vector
+                 * @return A reference to an element
+                 * @pre    0 <= n < size()
+                 * @post   None.
+                 */
+                __attribute__ ((always_inline))
+                reference operator[](size_type n)
+                {
+                    return(*(iv_start + n)); 
+                }
+
+                /**
+                 * Access a mutable reference to an element in the container
+                 * @param[in] index An index into the vector
+                 * @return A reference to an element
+                 * @pre    0 <= n < size()
+                 * @post   None.
+                 * @note no exception handling
+                 */
+                __attribute__ ((always_inline))
+                reference at(size_type index)
+                {
+                    assert(index < size());
+                    return(*(iv_start + index));
+                }
+
+                /**
+                 * Get an immutable reference to an element in the container
+                 * @param[in] index An index into the vector
+                 * @return A const_reference to an object or type T
+                 * @pre    0 <= n < size()
+                 * @post   None.
+                 */
+                __attribute__ ((always_inline))
+                const_reference operator[](size_type index) const
+                {
+                    assert(index < size());
+                    return(*(iv_start + index)); 
+                }
+
+                /**
+                 * Get an immutable reference to an element in the container
+                 * @param[in] index An index into the vector
+                 * @return A const_reference to an object or type T
+                 * @pre    0 <= n < size()
+                 * @post   None.
+                 * @note no exception handling
+                 */
+                __attribute__ ((always_inline))
+                const_reference at(size_type index) const
+                {
+                    assert(index < size());
+                    return(*(iv_start + index));
+                }
+
+                /**
+                 * Get a mutable reference to the first element in the container
+                 * @return reference to first element
+                 * @pre none
+                 * @post None
+                 */
+                __attribute__ ((always_inline))
+                reference front()
+                {
+                    return *iv_start;
+                }
+
+                /**
+                 * Get an Immutable reference to the first element in the container
+                 * @return const_reference to first element
+                 * @pre none
+                 * @post None
+                 */
+                __attribute__ ((always_inline))
+                const_reference front() const
+                {
+                    return *iv_start;
+                }
+
+                /**
+                 * Get a mutable reference to the last element in the container
+                 * @return reference to last element
+                 * @pre none
+                 * @post None
+                 */
+                __attribute__ ((always_inline))
+                reference back()
+                {
+                    return *(iv_finish-1);
+                }
+
+                /**
+                 * Get an Immutable reference to the last element in the container
+                 * @return reference to last element
+                 * @pre none
+                 * @post None
+                 */
+                __attribute__ ((always_inline))
+                const_reference back() const
+                {
+                    return *(iv_finish-1);
+                }
+
+                // -- Modifiers -----------------------------
+
+                /*
+                 * Assign new content to the vector object
+                 * @param[n] first iterator to first element to copy in
+                 * @param[n] last  iterator to last element + 1 to copy in
+                 */
+                template <class InputIterator>
+                    void assign (InputIterator first, InputIterator last)
+                {
+                    clear();
+                    size_type n = 0;
+                    for(InputIterator i = first; i != last; ++i) ++n;
+                    reserve(n);
+                    iv_finish = ctor_copy(first,last,iv_start);
+                }
+
+
+                /*
+                 * Assign new content to the vector object
+                 * @param[in] n number of elements to assign
+                 * @param[in] x reference to element to copy in 
+                 */
+                void assign ( size_type n, const T& x)
+                {
+                    clear();
+                    reserve(n);
+                    ctor_fill_n(iv_start,n,x);
+                    iv_finish = iv_start + n;
+                }
+
+
+                /**
+                 * Add element to the back of the container
+                 * @param[in] x reference to object used to create new element
+                 * @pre none
+                 * @post All previously obtained iterators are invalid.
+                 */
+                __attribute__ ((always_inline))
+                void push_back(const T& x) 
+                {
+                    reserve(size() + 1);
+                    new (iv_finish++) T(x);
+                }
+
+                /**
+                 * Remove the last element in the container
+                 * @return nothing
+                 * @pre size() > 0
+                 * @post size() decreased by one
+                 */
+                __attribute__ ((always_inline))
+                void pop_back()
+                {
+                    erase(iv_finish-1,iv_finish);
+                }
+
+                /**
+                 * Insert an element into the container at a given position
+                 * @param[in] position iterator to position to insert
+                 * @param[in] x reference of element to insert
+                 * @pre  begin() <= position < end()
+                 * @post Element inserted at position, storage adjusted as needed.
+                 *       All previously obtained iterators are invalid.
+                 */
+                iterator insert(iterator position, const T& x)
+                {
+                    // iv_start will change if the vector gets resized - so save the offset for
+                    // return.
+                    difference_type offset = position - iv_start;
+                    insert(position, 1, x);
+                    return (iv_start + offset);
+                }
+
+                /**
+                 * Insert a number of copies of a given elements at a given position
+                 * @param[in] postion iterator, postion to insert elements
+                 * @param[in] n number of elements to insert
+                 * @param[in] x A reference to the object to uses to create the new elements
+                 * @pre   begin() <= postion < end()
+                 * @post  All previously obtained iterators are invalid.
+                 */
+                void insert (iterator position, size_type n, const T& x);
+
+                /**
+                 * Insert a slice into the current container at a given position
+                 * @param[in] position iterator, position to insert slice
+                 * @param[in] first iterator to first element of slice insert
+                 * @param[in] last  iterator to last element + 1 of slice to insert
+                 * @pre   begin() <= postion <= end(), first < last.
+                 * @post Elements inserted at postition. Storage adjusted as needed.
+                 *       All previously obtained iterators are invalid.
+                 * @note element pointed to by last is not inserted.
+                 */
+                template <class InputIterator>
+                    void insert (iterator position, InputIterator first, 
+                                 InputIterator last);
+
+
+                /**
+                 * Remove an element from the container
+                 * @param[in] position iterator, position of element to remove
+                 * @pre begin() <= position < end()
+                 * @post All previously obtained iterators are invalid.
+                 */
+                __attribute__ ((always_inline))
+                void erase(iterator position)
+                {
+                    erase(position,position+1);
+                }
+
+                /**
+                 * Remove a slice of elements from the container
+                 * @param[in] first iterator, postion of the first element to remove
+                 * @param[in] last iterator, postion of the last element + 1 to remove
+                 * @pre begin() <= first,last <= end(), first < last.
+                 * @post  All previously obtained iterators are invalid.
+                 * @note The element pointed to be last is not deleted.
+                 */
+                void erase(iterator first, iterator last) 
+                {
+                    assert(last >= first);
+                    assert(first >= iv_start);
+                    assert(first < iv_finish);
+                    assert(last > iv_start);
+                    assert(last <= iv_finish);
+
+                    first = copy(last,iv_finish,first);
+                    while(first != iv_finish)
+                    {
+                        --iv_finish;
+                        iv_finish->~T();
+                    }
+                }  
+
+
+                /**
+                 * Swap this vector with another
+                 * @param reference to another vector of this type
+                 */
+                void swap(vector<T>& x)
+                {
+                    std::swap(iv_start,x.iv_start);
+                    std::swap(iv_finish,x.iv_finish);
+                    std::swap(iv_end_of_storage,x.iv_end_of_storage);
+                }
+
+                /**
+                 * Clear the vector
+                 * @pre none.
+                 * @post size() = 0, All previously obtained iterators are invalid
+                 * @note capacity unchanged
+                 */
+                void clear ()
+                {
+                    while(iv_finish != iv_start)
+                    {
+                        --iv_finish;
+                        (iv_finish)->~T();
+                    }
+                }
+
+            private:
+
+                /**
+                 * Copy constructs elements into raw storage
+                 * @param[in] first iterator of first element to copy
+                 * @pararm[in] last iterator of last element + 1 to copy
+                 * @param[in] destination iterator of destination
+                 * @post elements moved
+                 */
+                template <class InputIterator, class OutputIterator>
+                    OutputIterator
+                    ctor_copy(InputIterator first,
+                              InputIterator last,
+                              OutputIterator destination)
+                    {
+                        while(first != last)
+                        {
+                            new (destination) T(*first);
+                            ++destination;
+                            ++first;
+                        }
+                        return(destination);
+                    }
+
+                /**
+                 * Copy constructs elements into raw storage
+                 * @param[in] first iterator of first element to copy
+                 * @param[in] last iterator of last element + 1 to copy
+                 * @param[in] destination iterator to end of destination + 1
+                 * @post elements moved
+                 */
+                template <class BidirectionalIterator1, class BidirectionalIterator2>
+                    BidirectionalIterator2
+                    ctor_copy_backward ( BidirectionalIterator1 first,
+                                         BidirectionalIterator1 last,
+                                         BidirectionalIterator2 destination)
+                    {
+                        while(last != first)
+                        {
+                            --destination;
+                            --last;
+                            new(destination) T(*last);
+                        }
+                        return destination;
+                    }
+
+                /**
+                 * fill by copy construct ino raw storage
+                 * @param[in] first itertor fo first element
+                 * @param[in] last iterator to last element + 1
+                 * @param[in] value to use to fill
+                 */
+                template < class ForwardIterator, class Tp >
+                    void
+                    ctor_fill (ForwardIterator first, ForwardIterator last, const Tp& value )
+                    {
+                        while (first != last)
+                        {
+                            new (first) T(value);
+                            ++first;
+                        }
+                    }
+
+                /**
+                 * fill by copy construct into raw storage
+                 * @param[in] first iterator first location to fill
+                 * @param[in] n number of elements to fill
+                 * @param[in] value to use to fill
+                 */
+                template < class OutputIterator, class Size, class Tp >
+                    void
+                    ctor_fill_n( OutputIterator first, Size n, const Tp& value )
+                    {
+                        for(; n>0; --n)
+                        {
+                            new (first) T(value);
+                            ++first;
+                        }
+                    }
+                
+
+                /**
+                 * Free all the storage allocated to this vector
+                 * @param[in] i_start iterator to start of storage block
+                 */
+                 __attribute__ ((always_inline))
+                 void free_storage(iterator i_start)
+                 {
+                     delete [] (uint8_t *)i_start;
+                 }
+
+                 /**
+                  * Allocate storage for this vector
+                  * @param[in] n, number of elements required
+                  */
+                 __attribute__ ((always_inline))
+                 iterator allocate_storage(size_type n) 
+                 {
+                     return (iterator) new uint8_t[n * sizeof(T)];
+                 }
+
+                /**
+                 * debug dump
+                 */
+                //void dump(const char * msg = "")
+                //{
+                //    puts(msg);
+                //    printf("vector_dump::start 0x%016lx finish 0x%016lx eos 0x%016lx\n",
+                //           (uint64_t)iv_start, (uint64_t)iv_finish, (uint64_t)iv_end_of_storage);
+                //}
+        };
+
+}; // end namespace std
+
+// ------------------------------------------------------------------------------------------------
+
+template <class T>
+void std::vector<T>::reserve(size_type n)
+{
+    size_type c = capacity();
+    if(n > c)
+    {
+        // if requested new capacity < 10% of current capacity then increase by 10%
+        size_type dif = n - c;
+        size_type inc = 1 + (c/size_type(10));
+        if(dif < inc)
+        {
+            n += inc;
+        }
+
+        iterator newStart = allocate_storage(n);
+        if(NULL == iv_start)
+        {
+            iv_finish = newStart;
+        }
+        else
+        {
+            iterator newFinish = ctor_copy(iv_start, iv_finish, newStart);
+            clear();
+            iv_finish = newFinish;
+            free_storage(iv_start);
+        }
+        iv_end_of_storage = newStart + n;
+        iv_start = newStart;
+    }
+}
+
+
+// ------------------------------------------------------------------------------------------------
+
+template <class T>
+void std::vector<T>::insert (iterator position, size_type n, const T& x)
+{
+    //assert (position >= iv_start);
+    //assert (position <= iv_finish);
+    size_type new_size = size() + n;
+    if(position == end())
+    {
+        reserve(new_size);
+        while(n--) new (iv_finish++) T(x);
+    }
+    else if(new_size > capacity())
+    {
+        vector<T> new_vec;
+        new_vec.reserve(new_size);
+        for(const_iterator i = begin(); i != end(); ++i)
+        {
+            if(i == position)
+            {
+                while(n--) new_vec.push_back(x);
+            }
+            new_vec.push_back(*i);
+        }
+        swap(new_vec);  // swap this with new_vec
+    }
+    else  // already have enough space
+    {
+        size_type m = iv_finish - position;  // # of existing elements to move
+        pointer new_finish = iv_finish + n;
+        if(m < n)
+        {
+            ctor_copy_backward(position,iv_finish,new_finish);
+            while(n--)
+            {
+                if(position < iv_finish) *position = x;
+                else new (position) T(x);
+                ++position;
+            }
+        }
+        else // n <= m
+        {
+            ctor_copy_backward(iv_finish-n,iv_finish,new_finish);  // raw storage copy
+            copy_backward(position, iv_finish-n, iv_finish);       // operator= copy
+            fill_n(position,n,x);
+        }
+        iv_finish = new_finish;
+    }
+}
+
+// ------------------------------------------------------------------------------------------------
+
+template <class T>
+template <class InputIterator>
+void std::vector<T>::insert (iterator position,
+                             InputIterator first, 
+                             InputIterator last)
+// Should only move storage if there is not room
+// InputIterators are not random access  (eg. can't do diff = last - first)
+{
+    size_type n = 0;
+    for(InputIterator i = first; i != last; ++i) ++n;
+    size_type new_size = size() + n;
+
+    if(position == end())
+    {
+        reserve(new_size);
+        iv_finish = ctor_copy(first,last,iv_finish);
+    }
+    else if(new_size > capacity())  // make a new vector
+    {
+        vector<T> new_vec;
+        new_vec.reserve(new_size);
+        for(const_iterator i = begin(); i != end(); ++i)
+        {
+            if(i == position)
+            {
+                while(n--) new_vec.push_back(*first++);
+            }
+            new_vec.push_back(*i);
+        }
+        swap(new_vec);
+    }
+    else  // already have enough space
+    {
+        size_type m = iv_finish - position;  // # of exising elements to adjust
+        if(m < n)
+        {
+            ctor_copy_backward(position,iv_finish,iv_finish+n); // cp all existing elements to raw storage
+            while(first != last)
+            {
+                if(position < iv_finish) *position = *first; // cp new elements to existing element locations
+                else new (position) T(*first);               // cp remaining new elements to raw storage
+                ++position;
+                ++first;
+            }
+        }
+        else // n <= m
+        {
+            ctor_copy_backward(iv_finish-n, iv_finish, iv_finish+n); // cp existing elements to raw storage
+            copy_backward(position, iv_finish-n, iv_finish);  // cp rest of existing elements to existing locations
+            copy(first,last,position);                        // cp in new elements to existing locations
+        }
+        iv_finish += n;
+    }
+}
+
+// ------------------------------------------------------------------------------------------------
+
+template <class T>
+void std::vector<T>::resize(size_type n, T x)
+{
+    size_type sz = size();
+    if(n < sz)
+    {
+        erase(iv_start + n,iv_finish);
+    }
+    else if(n > sz)
+    {
+        insert(iv_finish,n-sz,x);
+    }
+    // else n == size() do nothing
+}
+
+#endif    
+