src/stc/scintilla/src/Array.cpp

   1 /** file Array.cpp
   2 * This file is defining a kind of tool for simulating std::vector
   3 * for using wx on OS which are not supporting the STL
   4 * @author foldink (foldink@gmail.com)
   5 * @date 26-February-2010
   6 */
   7
   8 #include <string.h>
   9
  10 #include "Platform.h"
  11 #include "Scintilla.h"
  12 #include "Selection.h"
  13 #include "Array.h"
  14
  15 SelectionRange& ArrayIterator::operator*()
  16 {
  17         if ( m_idx >= m_parent->size() )
  18                 throw "Error access out of bounds";
  19
  20         return (*m_parent)[m_idx];
  21 }
  22
  23 ArrayIterator ArrayIterator::operator++(int)
  24 {
  25         ArrayIterator ret(*this);
  26         ret.m_idx++;
  27         return ret;
  28 }
  29
  30 ArrayIterator& ArrayIterator::operator++()
  31 {
  32         m_idx++;
  33         return (*this);
  34 }
  35
  36 ArrayIterator ArrayIterator::operator--(int)
  37 {
  38         if ( m_idx == 0 )
  39                 throw "Error access out of bounds";
  40
  41         ArrayIterator ret(*this);
  42         ret.m_idx--;
  43         return ret;
  44 }
  45
  46 ArrayIterator& ArrayIterator::operator--()
  47 {
  48         if ( m_idx == 0 )
  49
  50
  51                 m_idx--;
  52         return (*this);
  53 }
  54
  55 ArrayIterator ArrayIterator::operator+(size_t idx)
  56 {
  57         ArrayIterator ret(*this);
  58         ret.m_idx += idx;
  59         return ret;
  60 }
  61
  62 ArrayIterator ArrayIterator::operator-(size_t idx)
  63 {
  64         if ( idx > m_idx )
  65                 throw "Error access out of bounds";
  66
  67         ArrayIterator ret(*this);
  68         ret.m_idx -= idx;
  69         return ret;
  70 }
  71
  72 ArrayIterator& ArrayIterator::operator+=(size_t idx)
  73 {
  74         m_idx += idx;
  75         return (*this);
  76 }
  77
  78 ArrayIterator& ArrayIterator::operator-=(size_t idx)
  79 {
  80         if ( idx > m_idx )
  81                 throw "Error access out of bounds";
  82
  83         m_idx -= idx;
  84         return (*this);
  85 }
  86
  87 bool ArrayIterator::operator!=(const ArrayIterator& rhs)
  88 {
  89         if ( m_parent == rhs.m_parent && m_idx == rhs.m_idx )
  90                 return false;
  91
  92         return true;
  93 }
  94
  95 bool ArrayIterator::operator==(const ArrayIterator& rhs)
  96 {
  97         if ( m_parent == rhs.m_parent && m_idx == rhs.m_idx )
  98                 return true;
  99
 100         return false;
 101 }
 102
 103 Array::Array( size_t len ):
 104                 m_data(0L),
 105                 m_size(0)
 106 {
 107         if ( len == 0 )
 108                 return;
 109
 110         m_data = new SelectionRange[len];
 111         m_size = len;
 112 }
 113
 114 Array::Array( size_t len , const SelectionRange& val ):
 115                 m_data(0L),
 116                 m_size(0)
 117 {
 118         if ( len == 0 )
 119                 return;
 120
 121         m_data = new SelectionRange[len];
 122         m_size = len;
 123
 124         for ( size_t i = 0; i < len ; ++i )
 125                 *(m_data + i) = val;
 126 }
 127
 128 Array::Array( const Array& rhs ):
 129                 m_data(0L),
 130                 m_size(0)
 131 {
 132         if ( rhs.m_size == 0 )
 133                 return;
 134
 135         m_data = new SelectionRange[rhs.m_size];
 136         m_size = rhs.m_size;
 137         memcpy( m_data , rhs.m_data , m_size*sizeof(SelectionRange) );
 138 }
 139
 140 Array::~Array()
 141 {
 142         if ( m_data )
 143                 delete m_data;
 144 }
 145
 146 Array& Array::operator=( const Array& rhs )
 147 {
 148         if ( m_data )
 149                 delete m_data;
 150
 151         m_data = 0L;
 152         m_size = 0;
 153
 154         if ( rhs.m_size == 0 )
 155                 return (*this);
 156
 157         m_data = new SelectionRange[rhs.m_size];
 158         m_size = rhs.m_size;
 159         memcpy( m_data , rhs.m_data , m_size*sizeof(SelectionRange) );
 160
 161         return (*this);
 162 }
 163
 164 void Array::reserve( size_t len )
 165 {
 166         if ( len <= m_size || len == 0 )
 167                 return;
 168
 169         SelectionRange* data = 0L;
 170         data = new SelectionRange[len];
 171
 172         if ( m_data ) {
 173                 memcpy( data , m_data , m_size*sizeof(SelectionRange) );
 174                 delete m_data;
 175                 m_data = data;
 176         } else
 177                 m_data = data;
 178 }
 179
 180 void Array::push_back( const SelectionRange& val )
 181 {
 182         if ( !m_data ) {
 183                 m_data = new SelectionRange[1];
 184                 *m_data = val;
 185                 m_size = 1;
 186                 return;
 187         }
 188
 189         SelectionRange* data = 0L;
 190         data = new SelectionRange[m_size+1];
 191         memcpy( data , m_data , m_size*sizeof(SelectionRange) );
 192         m_data = data;
 193         *(m_data+m_size) = val;
 194         m_size++;
 195 }
 196
 197 void Array::pop_back( )
 198 {
 199         if ( !m_data )
 200                 throw "Error access out of bounds";
 201
 202         m_size--;
 203         SelectionRange* data = 0L;
 204
 205         if ( m_size > 0 ) {
 206                 data = new SelectionRange[m_size];
 207                 memcpy( data , m_data , m_size*sizeof(SelectionRange) );
 208         }
 209
 210         delete m_data;
 211         m_data = data;
 212 }
 213
 214 void Array::insert( ArrayIterator it , SelectionRange& val )
 215 {
 216         size_t idx = it.GetIdx();
 217         SelectionRange* data = 0L;
 218         if (!m_data) {
 219                 m_size = idx+1;
 220                 m_data = new SelectionRange[m_size];
 221         } else if ( idx >= m_size ) {
 222                 data = new SelectionRange[idx+1];
 223                 memcpy( data , m_data , m_size*sizeof(SelectionRange) );
 224                 m_size = idx+1;
 225                 delete m_data;
 226                 m_data = data;
 227         } else if ( idx == 0 ) {
 228                 data = new SelectionRange[m_size+1];
 229                 memcpy( data + 1 , m_data , m_size*sizeof(SelectionRange) );
 230                 delete m_data;
 231                 m_size++;
 232                 m_data = data;
 233         } else {
 234                 data = new SelectionRange[m_size+1];
 235                 memcpy( data , m_data , idx*sizeof(SelectionRange) );
 236                 memcpy( data + idx + 1 , m_data + idx , (m_size-idx)*sizeof(SelectionRange) );
 237                 delete m_data;
 238                 m_size++;
 239                 m_data = data;
 240         }
 241
 242         *(m_data + idx) = val;
 243 }
 244
 245 void Array::erase( ArrayIterator it )
 246 {
 247         size_t idx = it.GetIdx();
 248         if (!m_data || idx >= m_size )
 249                 throw "Error access out of bounds";
 250
 251         SelectionRange* data = 0L;
 252         if ( m_size == 1 ) {
 253                 delete m_data;
 254                 m_data = 0L;
 255                 return;
 256         } else if ( idx == 0) {
 257                 data = new SelectionRange[m_size-1];
 258                 memcpy( data , m_data + 1 , (m_size-1)*sizeof(SelectionRange) );
 259                 delete m_data;
 260                 m_size--;
 261                 m_data = data;
 262         } else {
 263                 data = new SelectionRange[m_size-1];
 264                 memcpy( data , m_data , (idx)*sizeof(SelectionRange) );
 265                 memcpy( data + idx , m_data + idx + 1 , (m_size-idx-1)*sizeof(SelectionRange) );
 266                 delete m_data;
 267                 m_size--;
 268                 m_data = data;
 269         }
 270 }
 271
 272 void Array::clear( )
 273 {
 274         if ( !m_data )
 275                 return;
 276
 277         delete m_data;
 278         m_data = 0L;
 279         m_size = 0;
 280 }
 281
 282 void Array::resize( size_t n , SelectionRange val )
 283 {
 284         if ( (n == 0 && !m_data) || n <= m_size )
 285                 return;
 286
 287         if ( n == 0 ) {
 288                 delete m_data;
 289                 m_data = 0L;
 290                 m_size = 0;
 291         }
 292
 293         SelectionRange* data = 0L;
 294         data = new SelectionRange[n];
 295         memcpy( data , m_data , m_size*sizeof(SelectionRange) );
 296         delete m_data;
 297         m_data = data;
 298
 299         for ( size_t i = m_size ; i < n ; ++i )
 300                 *( m_data + i ) = val;
 301
 302         m_size = n;
 303 }
 304
 305 bool Array::operator==(const Array& rhs)
 306 {
 307         if ( m_size != rhs.m_size )
 308                 return false;
 309
 310         if ( m_size == 0 && rhs.m_size == 0 )
 311                 return true;
 312
 313         for ( size_t i = 0 ; i < m_size ; ++i )
 314                 if ( ! ((*(m_data +i)) == (*(rhs.m_data+i))) )
 315                         return false;
 316
 317         return true;
 318 }
 319
 320 ArrayIterator Array::begin()
 321 {
 322         ArrayIterator ret(this,0);
 323         return ret;
 324 }
 325
 326 ArrayIterator Array::end()
 327 {
 328         ArrayIterator ret(this,m_size);
 329         return ret;
 330 }
 331
 332
 333 int partition(Array &array, int top, int bottom)
 334 {
 335         SelectionRange x = array[top];
 336         int i = top - 1;
 337         int j = bottom + 1;
 338         SelectionRange temp;
 339         do {
 340                 do {
 341                         j--;
 342                 } while (x < array[j]);
 343
 344                 do {
 345                         i++;
 346                 } while (array[j] < x);
 347
 348                 if (i < j) {
 349                         temp = array[i];
 350                         array[i] = array[j];
 351                         array[j] = temp;
 352                 }
 353         } while (i < j);
 354         return j;           // returns middle subscript
 355 }
 356
 357 void quicksort(Array &num, int top, int bottom)
 358 {
 359         // top = subscript of beginning of array
 360         // bottom = subscript of end of array
 361
 362         int middle;
 363         if (top < bottom) {
 364                 middle = partition(num, top, bottom);
 365                 quicksort(num, top, middle);   // sort first section
 366                 quicksort(num, middle+1, bottom);    // sort second section
 367         }
 368         return;
 369 }
 370
 371 void ArraySort( ArrayIterator start , ArrayIterator finish )
 372 {
 373         if ( start.m_parent != finish.m_parent )
 374                 throw "Invalid iterators parent mismatch";
 375
 376         if ( start.m_idx >= finish.m_idx-1 )
 377                 throw "Invalid iterators are refering to bad values";
 378
 379         quicksort( *(start.m_parent) , start.m_idx , finish.m_idx-1 );
 380 }