home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / lib270b.zip / emx / include / cpp / vector.h < prev    next >
C/C++ Source or Header  |  1995-05-17  |  11KB  |  357 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  */
  15.  
  16. #ifndef VECTOR_H
  17. #define VECTOR_H
  18.  
  19. #include <function.h>
  20. #include <algobase.h>
  21. #include <bool.h>
  22.  
  23. #ifndef Allocator
  24. #define Allocator allocator
  25. #include <defalloc.h>
  26. #endif
  27.  
  28. #ifndef vector
  29. #define vector vector
  30. #endif
  31.  
  32. template <class T>
  33. class vector {
  34. public:
  35.     
  36.     typedef Allocator<T> vector_allocator;
  37.     typedef T value_type;
  38.     typedef vector_allocator::pointer pointer;
  39.     typedef vector_allocator::pointer iterator;
  40.     typedef vector_allocator::const_pointer const_iterator;
  41.     typedef vector_allocator::reference reference;
  42.     typedef vector_allocator::const_reference const_reference;
  43.     typedef vector_allocator::size_type size_type;
  44.     typedef vector_allocator::difference_type difference_type;
  45.     typedef reverse_iterator<const_iterator, value_type, const_reference, 
  46.                              difference_type>  const_reverse_iterator;
  47.     typedef reverse_iterator<iterator, value_type, reference, difference_type>
  48.         reverse_iterator;
  49. protected:
  50.     static Allocator<T> static_allocator;
  51.     iterator start;
  52.     iterator finish;
  53.     iterator end_of_storage;
  54. #ifdef __GNUG__
  55.     void insert_aux(iterator position, const T& x) {
  56.     insert_aux(vector_iterator<T>(position), x);
  57.     }
  58.     void insert_aux(vector_iterator<T> position, const T& x);
  59. #else
  60.     void insert_aux(iterator position, const T& x);
  61. #endif
  62. public:
  63.     iterator begin() { return start; }
  64.     const_iterator begin() const { return start; }
  65.     iterator end() { return finish; }
  66.     const_iterator end() const { return finish; }
  67.     reverse_iterator rbegin() { return reverse_iterator(end()); }
  68.     const_reverse_iterator rbegin() const { 
  69.         return const_reverse_iterator(end()); 
  70.     }
  71.     reverse_iterator rend() { return reverse_iterator(begin()); }
  72.     const_reverse_iterator rend() const { 
  73.         return const_reverse_iterator(begin()); 
  74.     }
  75.     size_type size() const { return size_type(end() - begin()); }
  76.     size_type max_size() const { return static_allocator.max_size(); }
  77.     size_type capacity() const { return size_type(end_of_storage - begin()); }
  78.     bool empty() const { return begin() == end(); }
  79.     reference operator[](size_type n) { return *(begin() + n); }
  80.     const_reference operator[](size_type n) const { return *(begin() + n); }
  81.     vector() : start(0), finish(0), end_of_storage(0) {}
  82.     vector(size_type n, const T& value = T()) {
  83.     start = static_allocator.allocate(n);
  84.     uninitialized_fill_n(start, n, value);
  85.     finish = start + n;
  86.     end_of_storage = finish;
  87.     }
  88.     vector(const vector<T>& x) {
  89.     start = static_allocator.allocate(x.end() - x.begin());
  90.     finish = uninitialized_copy(x.begin(), x.end(), start);
  91.     end_of_storage = finish;
  92.     }
  93.     vector(const_iterator first, const_iterator last) {
  94.     size_type n = 0;
  95.     distance(first, last, n);
  96.     start = static_allocator.allocate(n);
  97.     finish = uninitialized_copy(first, last, start);
  98.     end_of_storage = finish;
  99.     }
  100.     ~vector() { 
  101.     destroy(start, finish);
  102.     static_allocator.deallocate(start);
  103.     }
  104.     vector<T>& operator=(const vector<T>& x);
  105.     void reserve(size_type n) {
  106.     if (capacity() < n) {
  107.         iterator tmp = static_allocator.allocate(n);
  108.         uninitialized_copy(begin(), end(), tmp);
  109.         destroy(start, finish);
  110.         static_allocator.deallocate(start);
  111.         finish = tmp + size();
  112.         start = tmp;
  113.         end_of_storage = begin() + n;
  114.     }
  115.     }
  116.     reference front() { return *begin(); }
  117.     const_reference front() const { return *begin(); }
  118.     reference back() { return *(end() - 1); }
  119.     const_reference back() const { return *(end() - 1); }
  120.     void push_back(const T& x) {
  121.     if (finish != end_of_storage) {
  122.         /* Borland bug */
  123.         construct(finish, x);
  124.         finish++;
  125.     } else
  126.         insert_aux(end(), x);
  127.     }
  128.     void swap(vector<T>& x) {
  129.     ::swap(start, x.start);
  130.     ::swap(finish, x.finish);
  131.     ::swap(end_of_storage, x.end_of_storage);
  132.     }
  133.     iterator insert(iterator position, const T& x) {
  134.     size_type n = position - begin();
  135.     if (finish != end_of_storage && position == end()) {
  136.         /* Borland bug */
  137.         construct(finish, x);
  138.         finish++;
  139.     } else
  140.         insert_aux(position, x);
  141.     return begin() + n;
  142.     }
  143. #ifdef __GNUG__
  144.     void insert (iterator position, const_iterator first, 
  145.          const_iterator last) {
  146.         insert(vector_iterator<T>(position),
  147.            vector_const_iterator<T>(first),
  148.            vector_const_iterator<T>(last));
  149.     }
  150.     void insert (vector_iterator<T> position, vector_const_iterator<T> first, 
  151.          vector_const_iterator<T> last);
  152.     void insert (iterator position, size_type n, const T& x) {
  153.     insert(vector_iterator<T>(position), n, x);
  154.     }
  155.     void insert (vector_iterator<T> position, size_type n, const T& x);
  156. #else
  157.     void insert (iterator position, const_iterator first, 
  158.          const_iterator last);
  159.     void insert (iterator position, size_type n, const T& x);
  160. #endif
  161.     void pop_back() {
  162.     /* Borland bug */
  163.         --finish;
  164.         destroy(finish);
  165.     }
  166.     void erase(iterator position) {
  167.     if (position + 1 != end())
  168.         copy(position + 1, end(), position);
  169.     /* Borland bug */
  170.     --finish;
  171.     destroy(finish);
  172.     }
  173.     void erase(iterator first, iterator last) {
  174.     vector<T>::iterator i = copy(last, end(), first);
  175.     destroy(i, finish);
  176.     // work around for destroy(copy(last, end(), first), finish);
  177.     finish = finish - (last - first); 
  178.     }
  179. #ifdef __GNUG__
  180.     friend T* value_type(const iterator&) { return (T*)(0); }
  181. #endif
  182. };
  183.  
  184. #ifdef __GNUG__
  185. template <class T>
  186. struct vector_iterator {
  187.     vector<T>::iterator it;
  188.     vector_iterator(vector<T>::iterator i) : it(i) {}
  189.     operator vector<T>::iterator() {
  190.     return it;
  191.     }
  192. };
  193.  
  194. template <class T>
  195. inline T* value_type(const vector_iterator<T>&) {
  196.     return (T*)(0);
  197. }
  198.  
  199.  
  200. template <class T>
  201. struct vector_const_iterator {
  202.     vector<T>::const_iterator it;
  203.     vector_const_iterator(vector<T>::const_iterator i) : it(i) {}
  204.     operator vector<T>::const_iterator() {
  205.     return it;
  206.     }
  207. };
  208. #endif
  209.  
  210. template <class T>
  211. inline bool operator==(const vector<T>& x, const vector<T>& y) {
  212.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  213. }
  214.  
  215. template <class T>
  216. inline bool operator<(const vector<T>& x, const vector<T>& y) {
  217.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  218. }
  219.  
  220. #ifndef __GNUG__
  221. template <class T>
  222. vector<T>::vector_allocator vector<T>::static_allocator;
  223. #endif
  224.  
  225. template <class T>
  226. vector<T>& vector<T>::operator=(const vector<T>& x) {
  227.     if (&x == this) return *this;
  228.     if (x.size() > capacity()) {
  229.     destroy(start, finish);
  230.     static_allocator.deallocate(start);
  231.     start = static_allocator.allocate(x.end() - x.begin());
  232.     end_of_storage = uninitialized_copy(x.begin(), x.end(), start);
  233.     } else if (size() >= x.size()) {
  234.     vector<T>::iterator i = copy(x.begin(), x.end(), begin());
  235.     destroy(i, finish);
  236.     // work around for destroy(copy(x.begin(), x.end(), begin()), finish);
  237.     } else {
  238.     copy(x.begin(), x.begin() + size(), begin());
  239.     uninitialized_copy(x.begin() + size(), x.end(), begin() + size());
  240.     }
  241.     finish = begin() + x.size();
  242.     return *this;
  243. }
  244.  
  245. template <class T>
  246. #ifdef __GNUG__
  247. void vector<T>::insert_aux(vector_iterator<T> posn, const T& x) {
  248.     iterator position = posn;
  249. #else
  250. void vector<T>::insert_aux(iterator position, const T& x) {
  251. #endif
  252.     if (finish != end_of_storage) {
  253.     construct(finish, *(finish - 1));
  254.     copy_backward(position, finish - 1, finish);
  255.     *position = x;
  256.     ++finish;
  257.     } else {
  258.     size_type len = size() ? 2 * size() 
  259.         : static_allocator.init_page_size();
  260.     iterator tmp = static_allocator.allocate(len);
  261.     uninitialized_copy(begin(), position, tmp);
  262.     construct(tmp + (position - begin()), x);
  263.     uninitialized_copy(position, end(), tmp + (position - begin()) + 1); 
  264.     destroy(begin(), end());
  265.     static_allocator.deallocate(begin());
  266.     end_of_storage = tmp + len;
  267.     finish = tmp + size() + 1;
  268.     start = tmp;
  269.     }
  270. }
  271.  
  272. template <class T>
  273. #ifdef __GNUG__
  274. void vector<T>::insert(vector_iterator<T> posn,
  275.                size_t n,
  276.                const T& x) {
  277.     iterator position = posn;
  278. #else
  279. void vector<T>::insert(iterator position, size_type n, const T& x) {
  280. #endif
  281.     if (n == 0) return;
  282.     if ((size_type) (end_of_storage - finish) >= n) {
  283.     if ((size_type) (end() - position) > n) {
  284.         uninitialized_copy(end() - n, end(), end());
  285.         copy_backward(position, end() - n, end());
  286.         fill(position, position + n, x);
  287.     } else {
  288.         uninitialized_copy(position, end(), position + n);
  289.         fill(position, end(), x);
  290.         uninitialized_fill_n(end(), n - (end() - position), x);
  291.     }
  292.     finish += n;
  293.     } else {
  294.     size_type len = size() + max(size(), n);
  295.     iterator tmp = static_allocator.allocate(len);
  296.     uninitialized_copy(begin(), position, tmp);
  297.     uninitialized_fill_n(tmp + (position - begin()), n, x);
  298.     uninitialized_copy(position, end(), tmp + (position - begin() + n));
  299.     destroy(begin(), end());
  300.     static_allocator.deallocate(begin());
  301.     end_of_storage = tmp + len;
  302.     finish = tmp + size() + n;
  303.     start = tmp;
  304.     }
  305. }
  306.  
  307. template <class T>
  308. #ifdef __GNUG__
  309. void vector<T>::insert(vector_iterator<T> posn, 
  310.                vector_const_iterator<T> fi, 
  311.                vector_const_iterator<T> la) {
  312.     iterator position = posn;
  313.     const_iterator first = fi;
  314.     const_iterator last = la;
  315. #else
  316. void vector<T>::insert(iterator position, 
  317.                const_iterator first, 
  318.                const_iterator last) {
  319. #endif
  320.     if (first == last) return;
  321.     size_type n = 0;
  322.     distance(first, last, n);
  323.     if ((size_type) (end_of_storage - finish) >= n) {
  324.     if ((size_type) (end() - position) > n) {
  325.         uninitialized_copy(end() - n, end(), end());
  326.         copy_backward(position, end() - n, end());
  327.         copy(first, last, position);
  328.     } else {
  329.         uninitialized_copy(position, end(), position + n);
  330.         copy(first, first + (end() - position), position);
  331.         uninitialized_copy(first + (end() - position), last, end());
  332.     }
  333.     finish += n;
  334.     } else {
  335.     size_type len = size() + max(size(), n);
  336.     iterator tmp = static_allocator.allocate(len);
  337.     uninitialized_copy(begin(), position, tmp);
  338.     uninitialized_copy(first, last, tmp + (position - begin()));
  339.     uninitialized_copy(position, end(), tmp + (position - begin() + n));
  340.     destroy(begin(), end());
  341.     static_allocator.deallocate(begin());
  342.     end_of_storage = tmp + len;
  343.     finish = tmp + size() + n;
  344.     start = tmp;
  345.     }
  346. }
  347.  
  348. #undef Allocator
  349. #undef vector
  350.  
  351. #endif
  352.  
  353.  
  354.  
  355.  
  356.  
  357.