include/wx/vector.h

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // Name:        wx/vector.h
   3 // Purpose:     STL vector clone
   4 // Author:      Lindsay Mathieson
   5 // Modified by: Vaclav Slavik - make it a template
   6 // Created:     30.07.2001
   7 // Copyright:   (c) 2001 Lindsay Mathieson <lindsay@mathieson.org>,
   8 //                  2007 Vaclav Slavik <vslavik@fastmail.fm>
   9 // Licence:     wxWindows licence
  10 ///////////////////////////////////////////////////////////////////////////////
  11
  12 #ifndef _WX_VECTOR_H_
  13 #define _WX_VECTOR_H_
  14
  15 #include "wx/defs.h"
  16
  17 #if wxUSE_STL
  18
  19 #include <vector>
  20 #define wxVector std::vector
  21
  22 #else // !wxUSE_STL
  23
  24 #include "wx/utils.h"
  25
  26 template<typename T>
  27 class wxVector
  28 {
  29 public:
  30     typedef size_t size_type;
  31     typedef T value_type;
  32     typedef value_type* iterator;
  33     typedef const value_type* const_iterator;
  34     typedef value_type& reference;
  35
  36     wxVector() : m_size(0), m_capacity(0), m_values(NULL) {}
  37
  38     wxVector(const wxVector& c)
  39     {
  40         Copy(c);
  41     }
  42
  43     ~wxVector()
  44     {
  45         clear();
  46     }
  47
  48     void clear()
  49     {
  50         delete[] m_values;
  51         m_values = NULL;
  52         m_size = m_capacity = 0;
  53     }
  54
  55     void reserve(size_type n)
  56     {
  57         if ( n <= m_capacity )
  58             return;
  59
  60         // increase the size twice, unless we're already too big or unless
  61         // more is requested
  62         const size_type increment = (m_size > 0)
  63                                      ? wxMin(m_size, ALLOC_MAX_SIZE)
  64                                      : ALLOC_INITIAL_SIZE;
  65         if ( m_capacity + increment > n )
  66             n = m_capacity + increment;
  67
  68         value_type *mem = new value_type[n];
  69
  70         if ( m_values )
  71         {
  72             for ( size_type i = 0; i < m_size; ++i )
  73                 mem[i] = m_values[i];
  74             delete[] m_values;
  75         }
  76
  77         m_values = mem;
  78         m_capacity = n;
  79     }
  80
  81     size_type size() const
  82     {
  83         return m_size;
  84     }
  85
  86     size_type capacity() const
  87     {
  88         return m_capacity;
  89     }
  90
  91     bool empty() const
  92     {
  93         return size() == 0;
  94     }
  95
  96     wxVector& operator=(const wxVector& vb)
  97     {
  98         Copy(vb);
  99         return *this;
 100     }
 101
 102     void push_back(const value_type& v)
 103     {
 104         reserve(size() + 1);
 105         m_values[m_size++] = v;
 106     }
 107
 108     void pop_back()
 109     {
 110         erase(end() - 1);
 111     }
 112
 113     const value_type& at(size_type idx) const
 114     {
 115         wxASSERT(idx < m_size);
 116         return m_values[idx];
 117     }
 118
 119     value_type& at(size_type idx)
 120     {
 121         wxASSERT(idx < m_size);
 122         return m_values[idx];
 123     }
 124
 125     const value_type& operator[](size_type idx) const  { return at(idx); }
 126     value_type& operator[](size_type idx) { return at(idx); }
 127     const value_type& front() const { return at(0); }
 128     value_type& front() { return at(0); }
 129     const value_type& back() const { return at(size() - 1); }
 130     value_type& back() { return at(size() - 1); }
 131
 132     const_iterator begin() const { return m_values; }
 133     iterator begin() { return m_values; }
 134     const_iterator end() const { return m_values + size(); }
 135     iterator end() { return m_values + size(); }
 136
 137     iterator insert(iterator it, const value_type& v = value_type())
 138     {
 139         size_t idx = it - begin();
 140
 141         reserve(size() + 1);
 142
 143         // unless we're inserting at the end, move following values out of
 144         // the way:
 145         for ( size_t n = m_size; n != idx; --n )
 146             m_values[n] = m_values[n-1];
 147
 148         m_values[idx] = v;
 149         m_size++;
 150
 151         return begin() + idx;
 152     }
 153
 154     iterator erase(iterator it)
 155     {
 156         return erase(it, it + 1);
 157     }
 158
 159     iterator erase(iterator first, iterator last)
 160     {
 161         if ( first == last )
 162             return first;
 163         wxASSERT( first < end() && last <= end() );
 164
 165         size_type index = first - begin();
 166         size_type count = last - first;
 167
 168         // move the remaining values over to the freed space:
 169         for ( iterator i = last; i < end(); ++i )
 170             *(i - count) = *i;
 171
 172         // erase items behind the new end of m_values:
 173         for ( iterator i = end() - count; i < end(); ++i )
 174             *i = value_type();
 175
 176         m_size -= count;
 177
 178         return begin() + index;
 179     }
 180
 181 #if WXWIN_COMPATIBILITY_2_8
 182     wxDEPRECATED( size_type erase(size_type n) );
 183 #endif // WXWIN_COMPATIBILITY_2_8
 184
 185 private:
 186     static const size_type ALLOC_INITIAL_SIZE = 16;
 187     static const size_type ALLOC_MAX_SIZE = 4096;
 188
 189     void Copy(const wxVector& vb)
 190     {
 191         clear();
 192         reserve(vb.size());
 193
 194         for ( const_iterator i = vb.begin(); i != vb.end(); ++i )
 195             push_back(*i);
 196     }
 197
 198 private:
 199     size_type m_size,
 200               m_capacity;
 201     value_type *m_values;
 202 };
 203
 204 #if WXWIN_COMPATIBILITY_2_8
 205 template<typename T>
 206 typename wxVector<T>::size_type wxVector<T>::erase(size_type n)
 207 {
 208     erase(begin() + n);
 209     return n;
 210 }
 211 #endif // WXWIN_COMPATIBILITY_2_8
 212
 213 #endif // wxUSE_STL/!wxUSE_STL
 214
 215 #if WXWIN_COMPATIBILITY_2_8
 216     #define WX_DECLARE_VECTORBASE(obj, cls) typedef wxVector<obj> cls
 217     #define _WX_DECLARE_VECTOR(obj, cls, exp) WX_DECLARE_VECTORBASE(obj, cls)
 218     #define WX_DECLARE_VECTOR(obj, cls) WX_DECLARE_VECTORBASE(obj, cls)
 219 #endif // WXWIN_COMPATIBILITY_2_8
 220
 221 #endif // _WX_VECTOR_H_