/*      Copyright (C) 2004 Garrett A. Kajmowicz

        This file is part of the uClibc++ Library.

        This library is free software; you can redistribute it and/or
        modify it under the terms of the GNU Lesser General Public
        License as published by the Free Software Foundation; either
        version 2.1 of the License, or (at your option) any later version.

        This library is distributed in the hope that it will be useful,
        but WITHOUT ANY WARRANTY; without even the implied warranty of
        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
        Lesser General Public License for more details.

        You should have received a copy of the GNU Lesser General Public
        License along with this library; if not, write to the Free Software
        Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

*/

#include "basic_definitions"
#include "memory"
#include "iterator"
#include "func_exception"
#include "algorithm"
#include "type_traits"

#pragma warning(push)
#pragma warning(disable:4127)

#ifndef __STD_HEADER_VECTOR
#define __STD_HEADER_VECTOR

namespace std{

        template <class T, class Allocator = allocator<T> > class vector;
        template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
        template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
        template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
        template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
        template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
        template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
        template <class T, class Allocator> void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);

//      template <class Allocator> bool operator==(const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
//      template <class Allocator> bool operator< (const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
//      template <class Allocator> bool operator!=(const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
//      template <class Allocator> bool operator> (const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
//      template <class Allocator> bool operator>=(const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
//      template <class Allocator> bool operator<=(const vector<bool,Allocator>& x, const vector<bool,Allocator>& y);
//      template <class Allocator> void swap(vector<bool,Allocator>& x, vector<bool,Allocator>& y);


        template <class T, class Allocator> class _UCXXEXPORT vector {
        private:
                enum {ispod=isPOD<T>::is};
        public:

                typedef typename Allocator::reference reference;
                typedef typename Allocator::const_reference const_reference;
                typedef typename Allocator::size_type size_type;
                typedef typename Allocator::difference_type difference_type;
                typedef typename Allocator::pointer pointer;
                typedef typename Allocator::const_pointer const_pointer;

                typedef T* iterator;
                typedef const T* const_iterator;
                typedef T value_type;
                typedef Allocator allocator_type;
                typedef std::reverse_iterator<iterator> reverse_iterator;
                typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

                explicit _UCXXEXPORT vector(): data(0), //defaultValue(T()), 
                        data_size(__UCLIBCXX_STL_BUFFER_SIZE__), elements(0), a(Allocator())
                {
                        data = a.allocate(data_size);
                }

                explicit _UCXXEXPORT vector(const Allocator& al): data(0), //defaultValue(T()), 
                        data_size(__UCLIBCXX_STL_BUFFER_SIZE__), elements(0), a(al)
                {
                        data = a.allocate(data_size);
                }

                explicit _UCXXEXPORT vector(size_type n, const T& value = T(), const Allocator& al= Allocator()) : 
                        data(0), 
                        data_size(0), elements(0), a(al)
                {
                        data_size = n + __UCLIBCXX_STL_BUFFER_SIZE__;
                        data = a.allocate(data_size);

                                resize(n, value);
                }

                template <class InputIterator> _UCXXEXPORT 
                        vector(InputIterator first, InputIterator last, const Allocator& al = Allocator()):
                        data(0), data_size(__UCLIBCXX_STL_BUFFER_SIZE__), elements(0), a(al)
                {
                        data = a.allocate(data_size);
                        assign(first, last);
                }

                _UCXXEXPORT vector(const vector<T,Allocator>& x){
                        a = x.a;

                        elements  = x.elements;
                        data_size = elements + __UCLIBCXX_STL_BUFFER_SIZE__;
                        data = a.allocate(data_size);

                        if (ispod)
                          memcpy(data,x.data,elements*sizeof(T));
                        else
                          for(size_type i = 0; i < elements; i++){
                                  a.construct(data+i, x.data[i]);
                          }
                }

                _UCXXEXPORT ~vector();  //Below

                _UCXXEXPORT vector<T,Allocator>& operator=(const vector<T,Allocator>& x){
                        if(&x == this){
                                return *this;
                        }

                        reserve(x.elements);    //Make sure that we have enough actual memory


                        //Copy as many elements as possible

                        size_t minElements = elements;
                        if(minElements > x.elements){
                                minElements = x.elements;
                        }
                        if (ispod)
                          memcpy(data,x.data,minElements*sizeof(T));
                        else
                          for(size_t i = 0; i < minElements; ++i){
                                  data[i] = x.data[i];
                          }

                        //If we need to add new elements
                        if(elements < x.elements){
                                for(size_t i = elements; i< x.elements; ++i){
                                        a.construct(data+i, x.data[i]);
                                        ++elements;
                                }
                        }

                        if(elements > x.elements){
                                downsize(x.elements);
                        }

                        return *this;
                }

                template <class InputIterator> _UCXXEXPORT void assign(InputIterator first, InputIterator last){
                        clear();
                        insert(begin(), first, last);
                }

                template <class Size, class U> _UCXXEXPORT void assign(Size n, const U& u = U()){
//              void assign(size_type n, const T& u ){
                        clear();
                        resize(n, u);
                }

                inline allocator_type get_allocator() const{
                        return a;
                }

                inline iterator begin(){
                        return data;
                }

                inline const_iterator begin() const{
                        return data;
                }

                inline iterator end(){
                        return (data + elements);
                }

                inline const_iterator end() const{
                        return (data + elements);
                }

                inline reverse_iterator rbegin(){
                        return reverse_iterator(end());
                }

                inline const_reverse_iterator rbegin() const{
                        return const_reverse_iterator(end());
                }

                inline reverse_iterator rend(){
                        return reverse_iterator(begin());
                }

                inline const_reverse_iterator rend() const{
                        return const_reverse_iterator(begin());
                }

                inline size_type size() const{
                        return elements;
                }

                _UCXXEXPORT size_type max_size() const{
                        return ((size_type)(-1)) / sizeof(T);
                }

                void downsize(size_type sz);
                void resize(size_type sz, const T & c=T());

                inline size_type capacity() const{
                        return data_size;
                }

                inline bool empty() const{
                        return (size() == 0);
                }

                void reserve(size_type n);

                inline reference operator[](size_type n){
                        return data[n];
                }

                inline const_reference operator[](size_type n) const{
                        return data[n];
                }

                _UCXXEXPORT const_reference at(size_type n) const{
                        if(n >= elements){
                                __throw_out_of_range("Invalid subscript");
                        }
                        return data[n];
                }

                _UCXXEXPORT reference at(size_type n){
                        if(n >= elements){
                                __throw_out_of_range("Invalid subscript");
                        }
                        return data[n];
                }

                inline reference front(){
                        return data[0];
                }

                inline const_reference front() const{
                        return data[0];
                }

                inline reference back(){
                        return data[ size() - 1];
                }

                inline const_reference back() const{
                        return data[ size() - 1 ];
                }

                inline void push_back(const T& x){
                        resize( size() + 1, x);
                }

                inline void pop_back(){
//                      resize(size() - 1, defaultValue);
                        downsize(size() - 1);
                }

                _UCXXEXPORT iterator insert(iterator position, const T& x = T()){
                        size_type index = position - data;
                        resize(size() + 1, x);
                        if (ispod){
                          if (elements-1>index)
                            memmove(data+index+1,data+(index+1)-1,((elements-1)-index)*sizeof(T));
                        }    
                        else  
                          for(size_type i = elements - 1; i > index; --i){
                                 data[i] = data[i-1];
                          }
                        data[index] = x;
                        return (data + index);
                }

                _UCXXEXPORT void _insert_fill(iterator position, size_type n, const T & x){
                        size_type index = position - data;
                        resize(size() + n, x);

                        for(size_type i = elements -1; (i > (index+n-1)); --i){
                                data[i] = data[i-n];
                        }
                        for(size_type i = 0; i < n; i++){
                                data[i + index]  = x;
                        }
                }

                template <class InputIterator> _UCXXEXPORT 
                        void _insert_from_iterator(iterator position, InputIterator first, InputIterator last)
                {
                        if (ispod && position==end()){
                          size_t sz=last-first;
                          reserve(size()+sz);
                          memcpy(end(),first,sz*sizeof(T));
                          elements+=sz;
                        }else{
                          while(first !=last){
                                  T temp = *first;
                                  position = insert(position, temp);
                                  ++position;
                                  ++first;
                          }
                        }  
                }

                template <class InputIterator>
                        inline void _dispatch_insert(iterator position, InputIterator first, InputIterator last, __true_type)
                {
                        _insert_fill(position, first, last);
                }

                template <class InputIterator>
                        inline void _dispatch_insert(iterator position, InputIterator first, InputIterator last, __false_type)
                {
                                _insert_from_iterator(position, first, last);
                }

                inline void insert(iterator position, size_type n, const T& x ){
                        _insert_fill(position, n, x);
                }

                template <class InputIterator> inline void insert(iterator position, InputIterator first, InputIterator last){
                        typedef typename __is_integer<InputIterator>::value __some_type;
                        _dispatch_insert(position, first, last, __some_type());
                }

                _UCXXEXPORT iterator erase(iterator position){
                        size_type index = position - data;
                        if (ispod){
                          if (index<elements-1)
                            memmove(data+index,data+index+1,((elements-1)-index)*sizeof(T));
                        }    
                        else  
                          for(size_type i = index; i < (elements - 1); ++i){
                                  data[i] = data[i+1];
                          }
                        downsize(size() - 1);
                        return (data + index);
                }

                _UCXXEXPORT iterator erase(iterator first, iterator last){
                        size_type index = first - data;
                        size_type width = last - first;
                        if (ispod){
                          if (index<elements-width)
                            memmove(data+index,data+index+width,((elements-width)-index)*sizeof(T));
                        }  
                        else
                          for(size_type i = index; i < (elements - width) ;++i){
                                  data[i] = data[i+width];
                          }
                        downsize(size() - width);
                        return (data + index);
                }

                _UCXXEXPORT void swap(vector<T,Allocator>& v){
                        if(this == &v){         //Avoid dv.swap(v)
                                return;
                        }
                        T* ptr;
                        size_type temp;

                        //Swap pointers first
                        ptr = data;
                        data = v.data;
                        v.data  = ptr;

                        //Swap element counts
                        temp = elements;
                        elements = v.elements;
                        v.elements = temp;

                        //Swap data size
                        temp = data_size;
                        data_size = v.data_size;
                        v.data_size = temp;
                }

                _UCXXEXPORT void clear(){
                        elements = 0;
                }

        protected:
                T* data;
                size_type data_size;
                size_type elements;
                Allocator a;
        };



        //Here go template instantiations

        template<class T, class Allocator> _UCXXEXPORT vector<T, Allocator>::~vector(){
                for(size_t i = 0; i < elements; ++i){
                        a.destroy(data + i);
                }
                a.deallocate(data, data_size);
                data = 0;
                elements = 0;
                data_size=0;
        }


        template<class T, class Allocator> _UCXXEXPORT void vector<T, Allocator>::reserve(size_type n){
              if (!allocator_traits<Allocator>::is_static)
               {
                if(n > data_size){              //We never shrink...
                        T * temp_ptr = data;
                        size_type temp_size = data_size;

                        data_size = n+n/2;//__UCLIBCXX_STL_BUFFER_SIZE__;
                        data = a.allocate(data_size);

                        if (ispod)
                          memcpy(data,temp_ptr,elements*sizeof(T));
                        else
                          for(size_type i = 0; i<elements; ++i){
                                  a.construct(data+i, temp_ptr[i]);
                                  a.destroy(temp_ptr+i);
                          }
                        a.deallocate(temp_ptr, temp_size);
                }
               }
              else
                data_size = n;  
        }

        template<class T, class Allocator> _UCXXEXPORT void vector<T, Allocator>::resize(size_type sz, const T & c){
                if(sz > elements){      //Need to actually call constructor
                        reserve(sz);

                        for(size_type i = elements; i<sz ; ++i){
                                a.construct(data+i, c);
                        }
                        elements = sz;
                }else{
                        downsize(sz);
                }
        }

        template<class T, class Allocator> _UCXXEXPORT void vector<T, Allocator>::downsize(size_type sz){
                if(sz < elements){      //Actually are downsizing
                        for(size_t i = sz; i< elements; ++i){
                                a.destroy(data+i);
                        }
                        elements = sz;
                }
        }


#ifndef __UCLIBCXX_COMPILE_VECTOR__
#ifdef __UCLIBCXX_EXPAND_VECTOR_BASIC__


#ifdef __UCLIBCXX_EXPAND_CONSTRUCTORS_DESTRUCTORS__
        template<> _UCXXEXPORT vector<char, allocator<char> >::vector(const allocator<char>& al);
        template<> _UCXXEXPORT vector<char, allocator<char> >::vector(size_type n, const char & value, const allocator<char> & al);

        template<> _UCXXEXPORT vector<char, allocator<char> >::~vector();
        template<> _UCXXEXPORT vector<unsigned char, allocator<unsigned char> >::~vector();

#endif //__UCLIBCXX_EXPAND_CONSTRUCTORS_DESTRUCTORS__
                
        template<> _UCXXEXPORT void vector<char, allocator<char> >::reserve(size_type n);
        template<> _UCXXEXPORT void vector<unsigned char, allocator<unsigned char> >::reserve(size_type n);
        template<> _UCXXEXPORT void vector<short int, allocator<short int> >::reserve(size_type n);
        template<> _UCXXEXPORT void vector<unsigned short int, allocator<unsigned short int> >::reserve(size_type n);
        template<> _UCXXEXPORT void vector<int, allocator<int> >::reserve(size_type n);
        template<> _UCXXEXPORT void vector<unsigned int, allocator<unsigned int> >::reserve(size_type n);
        template<> _UCXXEXPORT void vector<long int, allocator<long int> >::reserve(size_type n);
        template<> _UCXXEXPORT void vector<unsigned long int, allocator<unsigned long int> >::reserve(size_type n);
        template<> _UCXXEXPORT void vector<float, allocator<float> >::reserve(size_type n);
        template<> _UCXXEXPORT void vector<double, allocator<double> >::reserve(size_type n);
        template<> _UCXXEXPORT void vector<bool, allocator<bool> >::reserve(size_type n);

        template<> _UCXXEXPORT void vector<char, allocator<char> >::resize(size_type sz, const char & c);
        template<> _UCXXEXPORT void
                vector<unsigned char, allocator<unsigned char> >::resize(size_type sz, const unsigned char & c);
        template<> _UCXXEXPORT void vector<short int, allocator<short int> >::resize(size_type sz, const short & c);
        template<> _UCXXEXPORT void
                vector<unsigned short int, allocator<unsigned short int> >::resize(size_type sz, const unsigned short int & c);
        template<> _UCXXEXPORT void vector<int, allocator<int> >::resize(size_type sz, const int & c);
        template<> _UCXXEXPORT void vector<unsigned int, allocator<unsigned int> >::resize(size_type sz, const unsigned int & c);
        template<> _UCXXEXPORT void vector<long int, allocator<long int> >::resize(size_type sz, const long int & c);
        template<> _UCXXEXPORT void
                vector<unsigned long int, allocator<unsigned long int> >::resize(size_type sz, const unsigned long int & c);
        template<> _UCXXEXPORT void vector<float, allocator<float> >::resize(size_type sz, const float & c);
        template<> _UCXXEXPORT void vector<double, allocator<double> >::resize(size_type sz, const double & c);
        template<> _UCXXEXPORT void vector<bool, allocator<bool> >::resize(size_type sz, const bool & c);

#elif defined __UCLIBCXX_EXPAND_STRING_CHAR__

#ifdef __UCLIBCXX_EXPAND_CONSTRUCTORS_DESTRUCTORS__

        template<> _UCXXEXPORT vector<char, allocator<char> >::vector(const allocator<char>& al);
        template<> _UCXXEXPORT vector<char, allocator<char> >::vector(size_type n, const char & value, const allocator<char> & al);
        template<> _UCXXEXPORT vector<char, allocator<char> >::~vector();

#endif

        template<> _UCXXEXPORT void vector<char, allocator<char> >::reserve(size_type n);
        template<> _UCXXEXPORT void vector<char, allocator<char> >::resize(size_type sz, const char & c);

#endif
#endif



        template <class T, class Allocator> _UCXXEXPORT bool
                operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y)
        {
                if(x.size() !=y.size() ){
                        return false;
                }
                for(size_t i = 0; i < x.size(); ++i){
                        if(x[i] != y[i]){
                                return false;
                        }
                }
                return true;
        }

        template <class T, class Allocator> _UCXXEXPORT bool
                operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y)
        {
                less<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
                return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
        }
        template <class T, class Allocator> _UCXXEXPORT bool
                operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y)
        {
                return !(x == y);
        }
        template <class T, class Allocator> _UCXXEXPORT bool
                operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y)
        {
                greater<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
                return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
        }
        template <class T, class Allocator> _UCXXEXPORT bool
                operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y)
        {
                greater_equal<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
                return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
        }
        template <class T, class Allocator> _UCXXEXPORT bool
                operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y)
        {
                less_equal<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
                return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
        }

        template <class T, class Allocator> _UCXXEXPORT void swap(vector<T,Allocator>& x, vector<T,Allocator>& y){
                x.swap(y);
        }

}

#pragma warning(pop)

#endif

