Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  1. /*      Copyright (C) 2004 Garrett A. Kajmowicz
  2.         This file is part of the uClibc++ Library.
  3.         This library is free software; you can redistribute it and/or
  4.         modify it under the terms of the GNU Lesser General Public
  5.         License as published by the Free Software Foundation; either
  6.         version 2.1 of the License, or (at your option) any later version.
  7.  
  8.         This library is distributed in the hope that it will be useful,
  9.         but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.         MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11.         Lesser General Public License for more details.
  12.        
  13.         You should have received a copy of the GNU Lesser General Public
  14.         License along with this library; if not, write to the Free Software
  15.         Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  16.  
  17. */
  18.  
  19.  
  20. #include <memory>
  21. #include <iterator>
  22. #include <stdexcept>
  23.  
  24. #pragma GCC visibility push(default)
  25.  
  26. #ifndef __STD_HEADER_DEQUE
  27. #define __STD_HEADER_DEQUE
  28.  
  29.  
  30. namespace std{
  31.         template <class T, class Allocator = allocator<T> > class deque;
  32.         template <class T, class Allocator> bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
  33.         template <class T, class Allocator> bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
  34.         template <class T, class Allocator> bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
  35.         template <class T, class Allocator> bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
  36.         template <class T, class Allocator> bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
  37.         template <class T, class Allocator> bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
  38.         template <class T, class Allocator> void swap(deque<T,Allocator>& x, deque<T,Allocator>& y);
  39.  
  40.         template <class T, class Allocator> class _UCXXEXPORT deque {
  41.         public:
  42.                 friend bool operator==<>(const deque<T, Allocator>& x, const deque<T, Allocator>& y);
  43.                 friend class deque_iter;
  44.                 friend class deque_citer;
  45.                 class deque_iter;
  46.                 class deque_citer;
  47.  
  48.                 typedef typename Allocator::reference           reference;
  49.                 typedef typename Allocator::const_reference     const_reference;
  50.                 typedef deque_iter                              iterator;
  51.                 typedef deque_citer                             const_iterator;
  52.                 typedef typename Allocator::size_type           size_type;
  53.                 typedef typename Allocator::difference_type     difference_type;
  54.                 typedef T                                       value_type;
  55.                 typedef Allocator                               allocator_type;
  56.                 typedef typename Allocator::pointer             pointer;
  57.                 typedef typename Allocator::const_pointer       const_pointer;
  58.                 typedef std::reverse_iterator<iterator>         reverse_iterator;
  59.                 typedef std::reverse_iterator<const_iterator>   const_reverse_iterator;
  60.  
  61.                 explicit deque(const Allocator& al = Allocator());
  62.                 explicit deque(size_type n, const T& value = T(), const Allocator& al = Allocator());
  63.                 template <class InputIterator> deque(InputIterator first, InputIterator last, const Allocator& = Allocator());
  64.                 deque(const deque<T,Allocator>& x);
  65.                 ~deque();
  66.  
  67.                 deque<T,Allocator>& operator=(const deque<T,Allocator>& x);
  68.                 template <class InputIterator> void assign(InputIterator first, InputIterator last);
  69.                 template <class Size, class U> void assign(Size n, const U& u = U());
  70.                 allocator_type get_allocator() const;
  71.  
  72.                 iterator                begin();
  73.                 const_iterator          begin() const;
  74.                 iterator                end();
  75.                 const_iterator          end() const;
  76.                 reverse_iterator        rbegin();
  77.                 const_reverse_iterator  rbegin() const;
  78.                 reverse_iterator        rend();
  79.                 const_reverse_iterator  rend() const;
  80.  
  81.                 size_type               size() const;
  82.                 size_type               max_size() const;
  83.                 void                    resize(size_type sz, T c = T());
  84.                 bool                    empty() const;
  85.  
  86.                 reference       operator[](size_type n);
  87.                 const_reference operator[](size_type n) const;
  88.                 reference       at(size_type n);
  89.                 const_reference at(size_type n) const;
  90.                 reference       front();
  91.                 const_reference front() const;
  92.                 reference       back();
  93.                 const_reference back() const;
  94.  
  95.                 void push_front(const T& x);
  96.                 void push_back(const T& x);
  97.                 iterator insert(iterator position, const T& x = T());
  98.                 void     insert(iterator position, size_type n, const T& x);
  99.                 template <class InputIterator> void insert (iterator position, InputIterator first, InputIterator last);
  100.                 void pop_front();
  101.                 void pop_back();
  102.  
  103.                 iterator erase(iterator position);
  104.                 iterator erase(iterator first, iterator last);
  105.                 void     swap(deque<T,Allocator>&);
  106.                 void     clear();
  107.  
  108.         protected:
  109.                 void reserve(size_type n);
  110.                 inline size_type array_element(size_type deque_element) const{
  111.                         if(deque_element < (data_size - first_element)){
  112.                                 return first_element + deque_element;
  113.                         }
  114.                         return deque_element - (data_size - first_element);
  115.                 }
  116.                 inline size_type first_subtract(size_type sub_size) const{
  117.                         if(sub_size > first_element){
  118.                                 return (data_size - first_element) - sub_size;
  119.                         }
  120.                         return first_element - sub_size;
  121.                 }
  122.  
  123.                 T * data;
  124.                 size_type data_size;            //Physical size of array
  125.                 size_type elements;             //Elements in array
  126.                 size_type first_element;        //Element number of array 0..n
  127.                 size_type last_element;         //Element number of array 0..n
  128.                 Allocator a;
  129.  
  130.         };
  131.  
  132.  
  133.         template<class T, class Allocator> class _UCXXEXPORT deque<T, Allocator>::deque_iter
  134.                 : public std::iterator<
  135.                         random_access_iterator_tag,
  136.                         T,
  137.                         typename Allocator::difference_type,
  138.                         typename Allocator::pointer,
  139.                         typename Allocator::reference
  140.                 >
  141.         {
  142.         friend class deque<T, Allocator>;
  143.         protected:
  144.                 deque<T, Allocator> * container;
  145.                 typename Allocator::size_type element;
  146.  
  147.         public:
  148.                 deque_iter() : container(0), element(0) {  }
  149.                 deque_iter(const deque_iter & d) : container (d.container), element(d.element) {  }
  150.                 deque_iter(deque<T, Allocator> * c, typename Allocator::size_type e)
  151.                         : container(c), element(e)
  152.                 {
  153.                         return;
  154.                 }
  155.                 ~deque_iter() {  }
  156.                 deque_iter & operator=(const deque_iter & d){
  157.                         container = d.container;
  158.                         element = d.element;
  159.                         return *this;
  160.                 }
  161.                 T & operator*(){
  162.                         return container->data[container->array_element(element)];
  163.                 }
  164.                 T * operator->(){
  165.                         return container->data + container->array_element(element);
  166.                 }
  167.                 const T & operator*() const{
  168.                         return container->data[container->array_element(element)];
  169.                 }
  170.                 const T * operator->() const{
  171.                         return container->data + container->array_element(element);
  172.                 }
  173.                 bool operator==(const deque_iter & d) const{
  174.                         if(container == d.container && element == d.element){
  175.                                 return true;
  176.                         }
  177.                         return false;
  178.                 }
  179.                 bool operator==(const deque_citer & d) const{
  180.                         if(container == d.container && element == d.element){
  181.                                 return true;
  182.                         }
  183.                         return false;
  184.                 }
  185.                 bool operator!=(const deque_iter & d) const{
  186.                         if(container != d.container || element  != d.element){
  187.                                 return true;
  188.                         }
  189.                         return false;
  190.                 }
  191.                 bool operator!=(const deque_citer & d) const{
  192.                         if(container != d.container || element  != d.element){
  193.                                 return true;
  194.                         }
  195.                         return false;
  196.                 }
  197.                 bool operator<(const deque_iter & d) const{
  198.                         if(element < d.element){
  199.                                 return true;
  200.                         }
  201.                         return false;
  202.                 }
  203.                 bool operator<(const deque_citer & d) const{
  204.                         if(element < d.element){
  205.                                 return true;
  206.                         }
  207.                         return false;
  208.                 }
  209.                 bool operator<=(const deque_iter & d) const{
  210.                         if(element <= d.element){
  211.                                 return true;
  212.                         }
  213.                         return false;
  214.                 }
  215.                 bool operator<=(const deque_citer & d) const{
  216.                         if(element <= d.element){
  217.                                 return true;
  218.                         }
  219.                         return false;
  220.                 }
  221.                 bool operator>(const deque_iter & d) const{
  222.                         if(element > d.element){
  223.                                 return true;
  224.                         }
  225.                         return false;
  226.                 }
  227.                 bool operator>(const deque_citer & d) const{
  228.                         if(element > d.element){
  229.                                 return true;
  230.                         }
  231.                         return false;
  232.                 }
  233.                 bool operator>=(const deque_iter & d) const{
  234.                         if(element >= d.element){
  235.                                 return true;
  236.                         }
  237.                         return false;
  238.                 }
  239.                 bool operator>=(const deque_citer & d) const{
  240.                         if(element >= d.element){
  241.                                 return true;
  242.                         }
  243.                         return false;
  244.                 }
  245.                 deque_iter & operator++(){
  246.                         ++element;
  247.                         return *this;
  248.                 }
  249.                 deque_iter operator++(int){
  250.                         deque_iter temp(container, element);
  251.                         ++element;
  252.                         return temp;
  253.                 }
  254.                 deque_iter operator+(typename Allocator::size_type n){
  255.                         deque_iter temp(container, element + n);
  256.                         return temp;
  257.                 }
  258.                 deque_iter & operator+=(typename Allocator::size_type n){
  259.                         element += n;
  260.                         return *this;
  261.                 }
  262.                 deque_iter & operator--(){
  263.                         --element;
  264.                         return *this;
  265.                 }
  266.                 deque_iter operator--(int){
  267.                         deque_iter temp(container, element);
  268.                         --element;
  269.                         return temp;
  270.                 }
  271.                 deque_iter operator-(typename Allocator::size_type n){
  272.                         deque_iter temp(container, element - n);
  273.                         return temp;
  274.                 }
  275.                 deque_iter & operator-=(typename Allocator::size_type n){
  276.                         element -= n;
  277.                         return *this;
  278.                 }
  279.                 typename Allocator::size_type operator-(const deque_iter & d){
  280.                         return element - d.element;
  281.                 }
  282.  
  283.         };
  284.  
  285.         template<class T, class Allocator> class _UCXXEXPORT deque<T, Allocator>::deque_citer
  286.                 : public std::iterator<
  287.                         random_access_iterator_tag,
  288.                         T,
  289.                         typename Allocator::difference_type,
  290.                         typename Allocator::const_pointer,
  291.                         typename Allocator::const_reference
  292.                 >
  293.         {
  294.         friend class deque<T, Allocator>;
  295.         protected:
  296.                 const deque<T, Allocator> * container;
  297.                 typename Allocator::size_type element;
  298.  
  299.         public:
  300.                 deque_citer() : container(0), element(0) {  }
  301.                 deque_citer(const deque_citer & d) : container (d.container), element(d.element) {  }
  302.                 deque_citer(const deque_iter & d) : container (d.container), element(d.element) {  }
  303.                 deque_citer(const deque<T, Allocator> * c, typename Allocator::size_type e)
  304.                         : container(c), element(e)
  305.                 {
  306.                         return;
  307.                 }
  308.                 ~deque_citer() {  }
  309.                 deque_citer & operator=(const deque_iter & d){
  310.                         container = d.container;
  311.                         element = d.element;
  312.                         return *this;
  313.                 }
  314.                 const T & operator*() const{
  315.                         return container->data[container->array_element(element)];
  316.                 }
  317.                 const T * operator->() const{
  318.                         return container->data + container->array_element(element);
  319.                 }
  320.                 bool operator==(const deque_citer & d) const{
  321.                         if(container == d.container && element == d.element){
  322.                                 return true;
  323.                         }
  324.                         return false;
  325.                 }
  326.                 bool operator==(const deque_iter & d) const{
  327.                         if(container == d.container && element == d.element){
  328.                                 return true;
  329.                         }
  330.                         return false;
  331.                 }
  332.                 bool operator!=(const deque_citer & d) const{
  333.                         if(container != d.container || element  != d.element){
  334.                                 return true;
  335.                         }
  336.                         return false;
  337.                 }
  338.                 bool operator!=(const deque_iter & d) const{
  339.                         if(container != d.container || element  != d.element){
  340.                                 return true;
  341.                         }
  342.                         return false;
  343.                 }
  344.                 bool operator<(const deque_citer & d) const{
  345.                         if(element < d.element){
  346.                                 return true;
  347.                         }
  348.                         return false;
  349.                 }
  350.                 bool operator<(const deque_iter & d) const{
  351.                         if(element < d.element){
  352.                                 return true;
  353.                         }
  354.                         return false;
  355.                 }
  356.                 bool operator<=(const deque_citer & d) const{
  357.                         if(element <= d.element){
  358.                                 return true;
  359.                         }
  360.                         return false;
  361.                 }
  362.                 bool operator<=(const deque_iter & d) const{
  363.                         if(element <= d.element){
  364.                                 return true;
  365.                         }
  366.                         return false;
  367.                 }
  368.                 bool operator>(const deque_citer & d) const{
  369.                         if(element > d.element){
  370.                                 return true;
  371.                         }
  372.                         return false;
  373.                 }
  374.                 bool operator>(const deque_iter & d) const{
  375.                         if(element > d.element){
  376.                                 return true;
  377.                         }
  378.                         return false;
  379.                 }
  380.                 bool operator>=(const deque_citer & d){
  381.                         if(element >= d.element){
  382.                                 return true;
  383.                         }
  384.                         return false;
  385.                 }
  386.                 bool operator>=(const deque_iter & d){
  387.                         if(element >= d.element){
  388.                                 return true;
  389.                         }
  390.                         return false;
  391.                 }
  392.                 deque_citer & operator++(){
  393.                         ++element;
  394.                         return *this;
  395.                 }
  396.                 deque_citer operator++(int){
  397.                         deque_citer temp(container, element);
  398.                         ++element;
  399.                         return temp;
  400.                 }
  401.                 deque_citer operator+(typename Allocator::size_type n){
  402.                         deque_citer temp(container, element + n);
  403.                         return temp;
  404.                 }
  405.                 deque_citer & operator+=(typename Allocator::size_type n){
  406.                         element += n;
  407.                         return *this;
  408.                 }
  409.                 deque_citer & operator--(){
  410.                         --element;
  411.                         return *this;
  412.                 }
  413.                 deque_citer operator--(int){
  414.                         deque_citer temp(container, element);
  415.                         --element;
  416.                         return temp;
  417.                 }
  418.                 deque_citer operator-(typename Allocator::size_type n){
  419.                         deque_citer temp(container, element - n);
  420.                         return temp;
  421.                 }
  422.                 deque_citer & operator-=(typename Allocator::size_type n){
  423.                         element -= n;
  424.                         return *this;
  425.                 }
  426.                 typename Allocator::size_type operator-(const deque_citer & d){
  427.                         return element - d.element;
  428.                 }
  429.  
  430.         };
  431.  
  432.         template<class T, class Allocator> deque<T, Allocator>::deque(const Allocator& al)
  433.                 : data(0),
  434.                 data_size(0), elements(0), first_element(0), last_element(0), a(al)
  435.         {
  436.                 data_size = __UCLIBCXX_STL_BUFFER_SIZE__;
  437.                 data = a.allocate(data_size);
  438.                 first_element = data_size /2;
  439.                 last_element = first_element;
  440.         }
  441.  
  442.  
  443.         template<class T, class Allocator> deque<T, Allocator>::deque(
  444.                 size_type n, const T& value, const Allocator& al)
  445.                 : data(0),
  446.                 elements(n), first_element(0), last_element(0), a(al)
  447.         {
  448.                 data_size = elements + __UCLIBCXX_STL_BUFFER_SIZE__;
  449.                 data = a.allocate(data_size);
  450.                 first_element = (data_size - elements) / 2;
  451.                 last_element = first_element;
  452.  
  453.                 for(n=first_element ; n < last_element; ++n ){
  454.                         a.construct(data+n, value);
  455.                 }
  456.         }
  457.  
  458.  
  459.         template<class T, class Allocator> template <class InputIterator>
  460.                 deque<T, Allocator>::deque(InputIterator first, InputIterator last, const Allocator& al)
  461.                 : data(0),
  462.                 data_size(0), elements(0), first_element(0), last_element(0), a(al)
  463.         {
  464.                 data_size = __UCLIBCXX_STL_BUFFER_SIZE__;
  465.                 data = a.allocate(data_size);
  466.                 first_element = data_size / 4;  //Note sure how big, but let's add a little space...
  467.                 last_element = first_element;
  468.                 while(first != last){
  469.                         push_back(*first);
  470.                         ++first;
  471.                 }
  472.         }
  473.  
  474.  
  475.         template<class T, class Allocator> deque<T, Allocator>::deque(const deque<T,Allocator>& x)
  476.                 : data(0),
  477.                 elements(0), first_element(0), last_element(0), a(x.a)
  478.         {
  479.                 data_size = x.elements + __UCLIBCXX_STL_BUFFER_SIZE__;
  480.                 data = a.allocate(data_size);
  481.                 first_element = (data_size - x.elements) / 2;
  482.                 last_element = first_element;
  483.                 for(size_type i=0; i < x.elements; ++i){
  484.                         push_back(x[i]);
  485.                 }
  486.         }
  487.  
  488.  
  489.         template<class T, class Allocator> deque<T, Allocator>::~deque(){
  490.                 clear();
  491.                 a.deallocate(data, data_size);
  492.         }
  493.  
  494.         template<class T, class Allocator> deque<T,Allocator>& deque<T, Allocator>::
  495.                 operator=(const deque<T,Allocator>& x)
  496.         {
  497.                 if(&x == this){
  498.                         return *this;
  499.                 }
  500.                 resize(x.elements);
  501.                 for(size_t i = 0; i < elements; ++i){
  502.                         data[array_element(i)] = x[i];
  503.                 }
  504.                 return *this;
  505.         }
  506.  
  507.  
  508.         template<class T, class Allocator> template <class InputIterator> void
  509.                 deque<T, Allocator>::assign(InputIterator first, InputIterator last)
  510.         {
  511.                 clear();
  512.                 while(first !=last){
  513.                         push_back(*first);
  514.                         ++first;
  515.                 }
  516.         }
  517.  
  518.  
  519.         template<class T, class Allocator> template <class Size, class U> void
  520.                 deque<T, Allocator>::assign(Size n, const U& u)
  521.         {
  522.                 if(&u == this){
  523.                         return;
  524.                 }
  525.                 clear();
  526.                 for(size_type i = 0; i < n; ++i){
  527.                         push_back(u);
  528.                 }
  529.         }
  530.  
  531.  
  532.         template<class T, class Allocator> typename deque<T, Allocator>::allocator_type
  533.                 deque<T, Allocator>::get_allocator() const
  534.         {
  535.                 return a;
  536.         }
  537.  
  538.         template<class T, class Allocator> typename
  539.                 deque<T, Allocator>::iterator deque<T, Allocator>::begin()
  540.         {
  541.                 return deque_iter(this, 0);
  542.         }
  543.  
  544.  
  545.         template<class T, class Allocator> typename deque<T, Allocator>::const_iterator
  546.                 deque<T, Allocator>::begin() const
  547.         {
  548.                 return deque_citer(this, 0);
  549.         }
  550.  
  551.         template<class T, class Allocator> typename
  552.                 deque<T, Allocator>::iterator deque<T, Allocator>::end()
  553.         {
  554.                 return deque_iter(this, elements);
  555.         }
  556.  
  557.         template<class T, class Allocator> typename
  558.                 deque<T, Allocator>::const_iterator deque<T, Allocator>::end() const
  559.         {
  560.                 return deque_citer(this, elements);
  561.         }
  562.        
  563.         template<class T, class Allocator> typename
  564.                 deque<T, Allocator>::reverse_iterator deque<T, Allocator>::rbegin()
  565.         {
  566.                 return reverse_iterator(end());
  567.         }
  568.  
  569.         template<class T, class Allocator> typename
  570.                 deque<T, Allocator>::const_reverse_iterator deque<T, Allocator>::rbegin() const
  571.         {
  572.                 return const_reverse_iterator(end());
  573.         }
  574.  
  575.         template<class T, class Allocator> typename
  576.                 deque<T, Allocator>::reverse_iterator deque<T, Allocator>::rend()
  577.         {
  578.                 return reverse_iterator(begin());
  579.         }
  580.  
  581.         template<class T, class Allocator> typename
  582.                 deque<T, Allocator>::const_reverse_iterator deque<T, Allocator>::rend() const
  583.         {
  584.                 return const_reverse_iterator(begin());
  585.         }
  586.  
  587.         template<class T, class Allocator> typename
  588.                 deque<T, Allocator>::size_type deque<T, Allocator>::size() const
  589.         {
  590.                 return elements;
  591.         }
  592.  
  593.         template<class T, class Allocator> typename
  594.                 deque<T, Allocator>::size_type deque<T, Allocator>::max_size() const
  595.         {
  596.                 return ((size_type)(-1)) / sizeof(T);
  597.         }
  598.  
  599.         template<class T, class Allocator> void deque<T, Allocator>::resize(size_type sz, T c){
  600.                 reserve(sz);
  601.                 while(sz > size()){
  602.                         push_back(c);
  603.                 }
  604.                 while(sz < size()){
  605.                         pop_back();
  606.                 }
  607.         }
  608.  
  609.         template<class T, class Allocator> bool deque<T, Allocator>::empty() const{
  610.                 return (elements == 0);
  611.         }
  612.  
  613.         template<class T, class Allocator> typename
  614.                 deque<T, Allocator>::reference deque<T, Allocator>::operator[](size_type n)
  615.         {
  616.                 return data[array_element(n)];
  617.         }
  618.  
  619.         template<class T, class Allocator> typename
  620.                 deque<T, Allocator>::const_reference deque<T, Allocator>::operator[](size_type n) const
  621.         {
  622.                 return data[array_element(n)];
  623.         }
  624.  
  625.         template<class T, class Allocator> typename
  626.                 deque<T, Allocator>::reference deque<T, Allocator>::at(size_type n)
  627.         {
  628.                 if(n > elements){
  629.                         __throw_out_of_range("Out of deque range");
  630.                 }
  631.                 return data[array_element(n)];
  632.         }
  633.  
  634.         template<class T, class Allocator> typename
  635.                 deque<T, Allocator>::const_reference deque<T, Allocator>::at(size_type n) const
  636.         {
  637.                 if(n > elements){
  638.                         __throw_out_of_range("Out of deque range");
  639.                 }
  640.                 return data[array_element(n)];
  641.         }
  642.  
  643.         template<class T, class Allocator> typename
  644.                 deque<T, Allocator>::reference deque<T, Allocator>::front()
  645.         {
  646.                 return data[first_element];
  647.         }
  648.  
  649.         template<class T, class Allocator> typename
  650.                 deque<T, Allocator>::const_reference deque<T, Allocator>::front() const
  651.         {
  652.                 return data[first_element];
  653.         }
  654.  
  655.         template<class T, class Allocator> typename
  656.                 deque<T, Allocator>::reference deque<T, Allocator>::back()
  657.         {
  658.                 return data[array_element(elements-1)];
  659.         }
  660.  
  661.         template<class T, class Allocator> typename
  662.                 deque<T, Allocator>::const_reference deque<T, Allocator>::back() const
  663.         {
  664.                 return data[array_element(elements-1)];
  665.         }
  666.        
  667.         template<class T, class Allocator> void deque<T, Allocator>::push_front(const T& x){
  668.                 reserve(elements + 1);
  669.                 first_element = first_subtract(1);
  670.                 a.construct(data + first_element, x);
  671.                 ++elements;
  672.         }
  673.  
  674.         template<class T, class Allocator> void deque<T, Allocator>::push_back(const T& x){
  675.                 reserve(elements + 1);
  676.                 a.construct(data + last_element, x);
  677.                 ++elements;
  678.                 last_element = array_element(elements);
  679.         }
  680.  
  681.         template<class T, class Allocator> typename
  682.                 deque<T, Allocator>::iterator deque<T, Allocator>::insert(iterator position, const T& x)
  683.         {
  684.                 reserve(elements+1);
  685.                 if(position.element > (elements/2)){
  686.                         //Push all elements back 1
  687.                         push_back(x);
  688.                         for(size_type i = elements-1; i > position.element; --i){
  689.                                 at(i) = at(i-1);
  690.                         }
  691.                 }else{
  692.                         //Push all elements forward 1
  693.                         push_front(x);
  694.                         for(size_type i = 0; i < position.element; ++i){
  695.                                 at(i) = at(i+1);
  696.                         }
  697.                 }
  698.                 at(position.element) = x;
  699.                 return deque_iter(this, position.element);
  700.         }
  701.  
  702.         template<class T, class Allocator> void deque<T, Allocator>::
  703.                 insert(typename deque<T, Allocator>::iterator position, size_type n, const T& x)
  704.         {
  705.                 reserve(elements + n);
  706.                 for(size_t i =0; i < n; ++i){
  707.                         position = insert(position, x);
  708.                 }
  709.         }
  710.  
  711.         template<class T, class Allocator> template <class InputIterator>
  712.                 void deque<T, Allocator>::insert (iterator position, InputIterator first, InputIterator last)
  713.         {
  714.                 while(first != last){
  715.                         position = insert(position, *first);
  716.                         ++first;
  717.                 }
  718.         }
  719.  
  720.         template<class T, class Allocator> void deque<T, Allocator>::pop_front(){
  721.                 if(elements == 0){
  722.                         __throw_out_of_range("deque pop_front");
  723.                 }
  724.                 a.destroy(data + first_element);
  725.                 first_element = array_element(1);
  726.                 --elements;
  727.         }
  728.  
  729.         template<class T, class Allocator> void deque<T, Allocator>::pop_back(){
  730.                 last_element = array_element(elements - 1);
  731.                 a.destroy(data + last_element);
  732.                 --elements;
  733.         }
  734.  
  735.         template<class T, class Allocator> typename
  736.                 deque<T, Allocator>::iterator deque<T, Allocator>::erase(typename deque<T, Allocator>::iterator position)
  737.         {
  738.                 if(position.element > (elements /2)){
  739.                         for(size_type i = position.element; i < elements - 1; ++i){
  740.                                 at(i) = at(i+1);
  741.                         }
  742.                         pop_back();
  743.                 }else{
  744.                         for(size_type i = position.element; i > 0; --i){
  745.                                 at(i) = at(i-1);
  746.                         }
  747.                         pop_front();
  748.                 }
  749.                 return deque_iter(this, position.element);
  750.         }
  751.  
  752.         template<class T, class Allocator> typename deque<T, Allocator>::iterator
  753.                 deque<T, Allocator>::
  754.                 erase(typename deque<T, Allocator>::iterator first, typename deque<T, Allocator>::iterator last)
  755.         {
  756.                 //Shift backwards
  757.                 size_type num_move = last.element - first.element;
  758.                 if( first.element > (elements - last.element) ){
  759.                         for(size_type i = last.element; i < elements ; ++i){
  760.                                 at(i-num_move) = at(i);
  761.                         }
  762.                         for(size_type i = 0; i < num_move ; ++i){
  763.                                 pop_back();
  764.                         }
  765.                 }else{
  766.                         for(size_type i = 0; i < first.element ; ++i){
  767.                                 at(last.element - i - 1) = at(first.element - i - 1);
  768.                         }
  769.                         for(size_type i = 0; i < num_move ; ++i){
  770.                                 pop_front();
  771.                         }
  772.                 }
  773.                 return deque_iter(this, first.element);
  774.         }
  775.  
  776.         template<class T, class Allocator> void deque<T, Allocator>::swap(deque<T,Allocator>& x)
  777.         {
  778.                 T * temp_data;
  779.                 typename deque<T,Allocator>::size_type temp_size;
  780.  
  781.                 //Swap data pointers
  782.                 temp_data = x.data;
  783.                 x.data = data;
  784.                 data = temp_data;
  785.  
  786.                 //Swap array sizes
  787.                 temp_size = x.data_size;
  788.                 x.data_size = data_size;
  789.                 data_size = temp_size;
  790.  
  791.                 //Swap num array elements
  792.                 temp_size  = x.elements;
  793.                 x.elements = elements;
  794.                 elements = temp_size;
  795.  
  796.                 //Swap first_pointer
  797.                 temp_size = x.first_element;
  798.                 x.first_element = first_element;
  799.                 first_element = temp_size;
  800.  
  801.                 //Swap last_pointer
  802.                 temp_size = x.last_element;
  803.                 x.last_element = last_element;
  804.                 last_element = temp_size;
  805.         }
  806.  
  807.         template<class T, class Allocator> void deque<T, Allocator>::clear()
  808.         {
  809.                 while(elements > 0 ){
  810.                         pop_back();
  811.                 }
  812.         }
  813.  
  814.  
  815.         template<class T, class Allocator> void deque<T, Allocator>::reserve(typename deque<T, Allocator>::size_type n)
  816.         {
  817.                 if(data_size >= n){
  818.                         return;
  819.                 }
  820.  
  821.                 size_type size_temp;
  822.                 size_type first_temp;
  823.                 T * data_temp;
  824.                 size_temp = n + __UCLIBCXX_STL_BUFFER_SIZE__;           //Reserve extra 'cause we can
  825.                 data_temp = a.allocate(size_temp);
  826.        
  827.                 first_temp = (size_temp - elements) / 2;
  828.                 for(size_type i = 0; i < elements; ++i){
  829.                         a.construct(data_temp + first_temp + i, data[array_element(i)]);
  830.                         a.destroy(data + array_element(i));
  831.                 }
  832.  
  833.                 //Now shuffle pointers
  834.                 a.deallocate(data, data_size);
  835.                 data = data_temp;
  836.                 data_size = size_temp;
  837.                 first_element = first_temp;
  838.                 last_element = first_element + elements;
  839.         }
  840.  
  841.  
  842.         template <class T, class Allocator> _UCXXEXPORT
  843.                 bool
  844.                 operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y)
  845.         {
  846.                 if(x.elements != y.elements){
  847.                         return false;
  848.                 }
  849.                 for(typename deque<T,Allocator>::size_type i = 0; i < x.elements; ++i){
  850.                         if(x[i] < y[i] || y[i] < x[i]){
  851.                                 return false;
  852.                         }
  853.                 }
  854.                 return true;
  855.         }
  856.  
  857.         template <class T, class Allocator> bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
  858.         template <class T, class Allocator> _UCXXEXPORT
  859.                 bool
  860.                 operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y)
  861.         {
  862.                 if(x == y){
  863.                         return false;
  864.                 }
  865.                 return true;
  866.         }
  867.         template <class T, class Allocator> bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
  868.         template <class T, class Allocator> bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
  869.         template <class T, class Allocator> bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);
  870.         template <class T, class Allocator> _UCXXEXPORT void swap(deque<T,Allocator>& x, deque<T,Allocator>& y){
  871.                 x.swap(y);
  872.         }
  873.  
  874.  
  875.  
  876. }
  877.  
  878. #pragma GCC visibility pop
  879.  
  880. #endif
  881.  
  882.  
  883.  
  884.  
  885.