Anti-Grain Geometry - AGG (libagg)
2.5
|
00001 //---------------------------------------------------------------------------- 00002 // Anti-Grain Geometry (AGG) - Version 2.5 00003 // A high quality rendering engine for C++ 00004 // Copyright (C) 2002-2006 Maxim Shemanarev 00005 // Contact: mcseem@antigrain.com 00006 // mcseemagg@yahoo.com 00007 // http://antigrain.com 00008 // 00009 // AGG is free software; you can redistribute it and/or 00010 // modify it under the terms of the GNU General Public License 00011 // as published by the Free Software Foundation; either version 2 00012 // of the License, or (at your option) any later version. 00013 // 00014 // AGG is distributed in the hope that it will be useful, 00015 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00016 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00017 // GNU General Public License for more details. 00018 // 00019 // You should have received a copy of the GNU General Public License 00020 // along with AGG; if not, write to the Free Software 00021 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, 00022 // MA 02110-1301, USA. 00023 //---------------------------------------------------------------------------- 00024 00025 #ifndef AGG_ARRAY_INCLUDED 00026 #define AGG_ARRAY_INCLUDED 00027 00028 #include <stddef.h> 00029 #include <string.h> 00030 #include "agg_basics.h" 00031 00032 namespace agg 00033 { 00034 00035 //-------------------------------------------------------pod_array_adaptor 00036 template<class T> class pod_array_adaptor 00037 { 00038 public: 00039 typedef T value_type; 00040 pod_array_adaptor(T* array, unsigned size) : 00041 m_array(array), m_size(size) {} 00042 00043 unsigned size() const { return m_size; } 00044 const T& operator [] (unsigned i) const { return m_array[i]; } 00045 T& operator [] (unsigned i) { return m_array[i]; } 00046 const T& at(unsigned i) const { return m_array[i]; } 00047 T& at(unsigned i) { return m_array[i]; } 00048 T value_at(unsigned i) const { return m_array[i]; } 00049 00050 private: 00051 T* m_array; 00052 unsigned m_size; 00053 }; 00054 00055 00056 //---------------------------------------------------------pod_auto_array 00057 template<class T, unsigned Size> class pod_auto_array 00058 { 00059 public: 00060 typedef T value_type; 00061 typedef pod_auto_array<T, Size> self_type; 00062 00063 pod_auto_array() {} 00064 explicit pod_auto_array(const T* c) 00065 { 00066 memcpy(m_array, c, sizeof(T) * Size); 00067 } 00068 00069 const self_type& operator = (const T* c) 00070 { 00071 memcpy(m_array, c, sizeof(T) * Size); 00072 return *this; 00073 } 00074 00075 static unsigned size() { return Size; } 00076 const T& operator [] (unsigned i) const { return m_array[i]; } 00077 T& operator [] (unsigned i) { return m_array[i]; } 00078 const T& at(unsigned i) const { return m_array[i]; } 00079 T& at(unsigned i) { return m_array[i]; } 00080 T value_at(unsigned i) const { return m_array[i]; } 00081 00082 private: 00083 T m_array[Size]; 00084 }; 00085 00086 00087 //--------------------------------------------------------pod_auto_vector 00088 template<class T, unsigned Size> class pod_auto_vector 00089 { 00090 public: 00091 typedef T value_type; 00092 typedef pod_auto_vector<T, Size> self_type; 00093 00094 pod_auto_vector() : m_size(0) {} 00095 00096 void remove_all() { m_size = 0; } 00097 void clear() { m_size = 0; } 00098 void add(const T& v) { m_array[m_size++] = v; } 00099 void push_back(const T& v) { m_array[m_size++] = v; } 00100 void inc_size(unsigned size) { m_size += size; } 00101 00102 unsigned size() const { return m_size; } 00103 const T& operator [] (unsigned i) const { return m_array[i]; } 00104 T& operator [] (unsigned i) { return m_array[i]; } 00105 const T& at(unsigned i) const { return m_array[i]; } 00106 T& at(unsigned i) { return m_array[i]; } 00107 T value_at(unsigned i) const { return m_array[i]; } 00108 00109 private: 00110 T m_array[Size]; 00111 unsigned m_size; 00112 }; 00113 00114 00115 //---------------------------------------------------------------pod_array 00116 template<class T> class pod_array 00117 { 00118 public: 00119 typedef T value_type; 00120 typedef pod_array<T> self_type; 00121 00122 ~pod_array() { pod_allocator<T>::deallocate(m_array, m_size); } 00123 pod_array() : m_array(0), m_size(0) {} 00124 00125 pod_array(unsigned size) : 00126 m_array(pod_allocator<T>::allocate(size)), 00127 m_size(size) 00128 {} 00129 00130 pod_array(const self_type& v) : 00131 m_array(pod_allocator<T>::allocate(v.m_size)), 00132 m_size(v.m_size) 00133 { 00134 memcpy(m_array, v.m_array, sizeof(T) * m_size); 00135 } 00136 00137 void resize(unsigned size) 00138 { 00139 if(size != m_size) 00140 { 00141 pod_allocator<T>::deallocate(m_array, m_size); 00142 m_array = pod_allocator<T>::allocate(m_size = size); 00143 } 00144 } 00145 const self_type& operator = (const self_type& v) 00146 { 00147 resize(v.size()); 00148 memcpy(m_array, v.m_array, sizeof(T) * m_size); 00149 return *this; 00150 } 00151 00152 unsigned size() const { return m_size; } 00153 const T& operator [] (unsigned i) const { return m_array[i]; } 00154 T& operator [] (unsigned i) { return m_array[i]; } 00155 const T& at(unsigned i) const { return m_array[i]; } 00156 T& at(unsigned i) { return m_array[i]; } 00157 T value_at(unsigned i) const { return m_array[i]; } 00158 00159 const T* data() const { return m_array; } 00160 T* data() { return m_array; } 00161 private: 00162 T* m_array; 00163 unsigned m_size; 00164 }; 00165 00166 00167 00168 //--------------------------------------------------------------pod_vector 00169 // A simple class template to store Plain Old Data, a vector 00170 // of a fixed size. The data is continous in memory 00171 //------------------------------------------------------------------------ 00172 template<class T> class pod_vector 00173 { 00174 public: 00175 typedef T value_type; 00176 00177 ~pod_vector() { pod_allocator<T>::deallocate(m_array, m_capacity); } 00178 pod_vector() : m_size(0), m_capacity(0), m_array(0) {} 00179 pod_vector(unsigned cap, unsigned extra_tail=0); 00180 00181 // Copying 00182 pod_vector(const pod_vector<T>&); 00183 const pod_vector<T>& operator = (const pod_vector<T>&); 00184 00185 // Set new capacity. All data is lost, size is set to zero. 00186 void capacity(unsigned cap, unsigned extra_tail=0); 00187 unsigned capacity() const { return m_capacity; } 00188 00189 // Allocate n elements. All data is lost, 00190 // but elements can be accessed in range 0...size-1. 00191 void allocate(unsigned size, unsigned extra_tail=0); 00192 00193 // Resize keeping the content. 00194 void resize(unsigned new_size); 00195 00196 void zero() 00197 { 00198 memset(m_array, 0, sizeof(T) * m_size); 00199 } 00200 00201 void add(const T& v) { m_array[m_size++] = v; } 00202 void push_back(const T& v) { m_array[m_size++] = v; } 00203 void insert_at(unsigned pos, const T& val); 00204 void inc_size(unsigned size) { m_size += size; } 00205 unsigned size() const { return m_size; } 00206 unsigned byte_size() const { return m_size * sizeof(T); } 00207 void serialize(int8u* ptr) const; 00208 void deserialize(const int8u* data, unsigned byte_size); 00209 const T& operator [] (unsigned i) const { return m_array[i]; } 00210 T& operator [] (unsigned i) { return m_array[i]; } 00211 const T& at(unsigned i) const { return m_array[i]; } 00212 T& at(unsigned i) { return m_array[i]; } 00213 T value_at(unsigned i) const { return m_array[i]; } 00214 00215 const T* data() const { return m_array; } 00216 T* data() { return m_array; } 00217 00218 void remove_all() { m_size = 0; } 00219 void clear() { m_size = 0; } 00220 void cut_at(unsigned num) { if(num < m_size) m_size = num; } 00221 00222 private: 00223 unsigned m_size; 00224 unsigned m_capacity; 00225 T* m_array; 00226 }; 00227 00228 //------------------------------------------------------------------------ 00229 template<class T> 00230 void pod_vector<T>::capacity(unsigned cap, unsigned extra_tail) 00231 { 00232 m_size = 0; 00233 if(cap > m_capacity) 00234 { 00235 pod_allocator<T>::deallocate(m_array, m_capacity); 00236 m_capacity = cap + extra_tail; 00237 m_array = m_capacity ? pod_allocator<T>::allocate(m_capacity) : 0; 00238 } 00239 } 00240 00241 //------------------------------------------------------------------------ 00242 template<class T> 00243 void pod_vector<T>::allocate(unsigned size, unsigned extra_tail) 00244 { 00245 capacity(size, extra_tail); 00246 m_size = size; 00247 } 00248 00249 00250 //------------------------------------------------------------------------ 00251 template<class T> 00252 void pod_vector<T>::resize(unsigned new_size) 00253 { 00254 if(new_size > m_size) 00255 { 00256 if(new_size > m_capacity) 00257 { 00258 T* data = pod_allocator<T>::allocate(new_size); 00259 memcpy(data, m_array, m_size * sizeof(T)); 00260 pod_allocator<T>::deallocate(m_array, m_capacity); 00261 m_array = data; 00262 } 00263 } 00264 else 00265 { 00266 m_size = new_size; 00267 } 00268 } 00269 00270 //------------------------------------------------------------------------ 00271 template<class T> pod_vector<T>::pod_vector(unsigned cap, unsigned extra_tail) : 00272 m_size(0), 00273 m_capacity(cap + extra_tail), 00274 m_array(pod_allocator<T>::allocate(m_capacity)) {} 00275 00276 //------------------------------------------------------------------------ 00277 template<class T> pod_vector<T>::pod_vector(const pod_vector<T>& v) : 00278 m_size(v.m_size), 00279 m_capacity(v.m_capacity), 00280 m_array(v.m_capacity ? pod_allocator<T>::allocate(v.m_capacity) : 0) 00281 { 00282 memcpy(m_array, v.m_array, sizeof(T) * v.m_size); 00283 } 00284 00285 //------------------------------------------------------------------------ 00286 template<class T> const pod_vector<T>& 00287 pod_vector<T>::operator = (const pod_vector<T>&v) 00288 { 00289 allocate(v.m_size); 00290 if(v.m_size) memcpy(m_array, v.m_array, sizeof(T) * v.m_size); 00291 return *this; 00292 } 00293 00294 //------------------------------------------------------------------------ 00295 template<class T> void pod_vector<T>::serialize(int8u* ptr) const 00296 { 00297 if(m_size) memcpy(ptr, m_array, m_size * sizeof(T)); 00298 } 00299 00300 //------------------------------------------------------------------------ 00301 template<class T> 00302 void pod_vector<T>::deserialize(const int8u* data, unsigned byte_size) 00303 { 00304 byte_size /= sizeof(T); 00305 allocate(byte_size); 00306 if(byte_size) memcpy(m_array, data, byte_size * sizeof(T)); 00307 } 00308 00309 //------------------------------------------------------------------------ 00310 template<class T> 00311 void pod_vector<T>::insert_at(unsigned pos, const T& val) 00312 { 00313 if(pos >= m_size) 00314 { 00315 m_array[m_size] = val; 00316 } 00317 else 00318 { 00319 memmove(m_array + pos + 1, m_array + pos, (m_size - pos) * sizeof(T)); 00320 m_array[pos] = val; 00321 } 00322 ++m_size; 00323 } 00324 00325 //---------------------------------------------------------------pod_bvector 00326 // A simple class template to store Plain Old Data, similar to std::deque 00327 // It doesn't reallocate memory but instead, uses blocks of data of size 00328 // of (1 << S), that is, power of two. The data is NOT contiguous in memory, 00329 // so the only valid access method is operator [] or curr(), prev(), next() 00330 // 00331 // There reallocs occure only when the pool of pointers to blocks needs 00332 // to be extended (it happens very rarely). You can control the value 00333 // of increment to reallocate the pointer buffer. See the second constructor. 00334 // By default, the incremeent value equals (1 << S), i.e., the block size. 00335 //------------------------------------------------------------------------ 00336 template<class T, unsigned S=6> class pod_bvector 00337 { 00338 public: 00339 enum block_scale_e 00340 { 00341 block_shift = S, 00342 block_size = 1 << block_shift, 00343 block_mask = block_size - 1 00344 }; 00345 00346 typedef T value_type; 00347 00348 ~pod_bvector(); 00349 pod_bvector(); 00350 pod_bvector(unsigned block_ptr_inc); 00351 00352 // Copying 00353 pod_bvector(const pod_bvector<T, S>& v); 00354 const pod_bvector<T, S>& operator = (const pod_bvector<T, S>& v); 00355 00356 void remove_all() { m_size = 0; } 00357 void clear() { m_size = 0; } 00358 void free_all() { free_tail(0); } 00359 void free_tail(unsigned size); 00360 void add(const T& val); 00361 void push_back(const T& val) { add(val); } 00362 void modify_last(const T& val); 00363 void remove_last(); 00364 00365 int allocate_continuous_block(unsigned num_elements); 00366 00367 void add_array(const T* ptr, unsigned num_elem) 00368 { 00369 while(num_elem--) 00370 { 00371 add(*ptr++); 00372 } 00373 } 00374 00375 template<class DataAccessor> void add_data(DataAccessor& data) 00376 { 00377 while(data.size()) 00378 { 00379 add(*data); 00380 ++data; 00381 } 00382 } 00383 00384 void cut_at(unsigned size) 00385 { 00386 if(size < m_size) m_size = size; 00387 } 00388 00389 unsigned size() const { return m_size; } 00390 00391 const T& operator [] (unsigned i) const 00392 { 00393 return m_blocks[i >> block_shift][i & block_mask]; 00394 } 00395 00396 T& operator [] (unsigned i) 00397 { 00398 return m_blocks[i >> block_shift][i & block_mask]; 00399 } 00400 00401 const T& at(unsigned i) const 00402 { 00403 return m_blocks[i >> block_shift][i & block_mask]; 00404 } 00405 00406 T& at(unsigned i) 00407 { 00408 return m_blocks[i >> block_shift][i & block_mask]; 00409 } 00410 00411 T value_at(unsigned i) const 00412 { 00413 return m_blocks[i >> block_shift][i & block_mask]; 00414 } 00415 00416 const T& curr(unsigned idx) const 00417 { 00418 return (*this)[idx]; 00419 } 00420 00421 T& curr(unsigned idx) 00422 { 00423 return (*this)[idx]; 00424 } 00425 00426 const T& prev(unsigned idx) const 00427 { 00428 return (*this)[(idx + m_size - 1) % m_size]; 00429 } 00430 00431 T& prev(unsigned idx) 00432 { 00433 return (*this)[(idx + m_size - 1) % m_size]; 00434 } 00435 00436 const T& next(unsigned idx) const 00437 { 00438 return (*this)[(idx + 1) % m_size]; 00439 } 00440 00441 T& next(unsigned idx) 00442 { 00443 return (*this)[(idx + 1) % m_size]; 00444 } 00445 00446 const T& last() const 00447 { 00448 return (*this)[m_size - 1]; 00449 } 00450 00451 T& last() 00452 { 00453 return (*this)[m_size - 1]; 00454 } 00455 00456 unsigned byte_size() const; 00457 void serialize(int8u* ptr) const; 00458 void deserialize(const int8u* data, unsigned byte_size); 00459 void deserialize(unsigned start, const T& empty_val, 00460 const int8u* data, unsigned byte_size); 00461 00462 template<class ByteAccessor> 00463 void deserialize(ByteAccessor data) 00464 { 00465 remove_all(); 00466 unsigned elem_size = data.size() / sizeof(T); 00467 00468 for(unsigned i = 0; i < elem_size; ++i) 00469 { 00470 int8u* ptr = (int8u*)data_ptr(); 00471 for(unsigned j = 0; j < sizeof(T); ++j) 00472 { 00473 *ptr++ = *data; 00474 ++data; 00475 } 00476 ++m_size; 00477 } 00478 } 00479 00480 template<class ByteAccessor> 00481 void deserialize(unsigned start, const T& empty_val, ByteAccessor data) 00482 { 00483 while(m_size < start) 00484 { 00485 add(empty_val); 00486 } 00487 00488 unsigned elem_size = data.size() / sizeof(T); 00489 for(unsigned i = 0; i < elem_size; ++i) 00490 { 00491 int8u* ptr; 00492 if(start + i < m_size) 00493 { 00494 ptr = (int8u*)(&((*this)[start + i])); 00495 } 00496 else 00497 { 00498 ptr = (int8u*)data_ptr(); 00499 ++m_size; 00500 } 00501 for(unsigned j = 0; j < sizeof(T); ++j) 00502 { 00503 *ptr++ = *data; 00504 ++data; 00505 } 00506 } 00507 } 00508 00509 const T* block(unsigned nb) const { return m_blocks[nb]; } 00510 00511 private: 00512 void allocate_block(unsigned nb); 00513 T* data_ptr(); 00514 00515 unsigned m_size; 00516 unsigned m_num_blocks; 00517 unsigned m_max_blocks; 00518 T** m_blocks; 00519 unsigned m_block_ptr_inc; 00520 }; 00521 00522 00523 //------------------------------------------------------------------------ 00524 template<class T, unsigned S> pod_bvector<T, S>::~pod_bvector() 00525 { 00526 if(m_num_blocks) 00527 { 00528 T** blk = m_blocks + m_num_blocks - 1; 00529 while(m_num_blocks--) 00530 { 00531 pod_allocator<T>::deallocate(*blk, block_size); 00532 --blk; 00533 } 00534 } 00535 pod_allocator<T*>::deallocate(m_blocks, m_max_blocks); 00536 } 00537 00538 00539 //------------------------------------------------------------------------ 00540 template<class T, unsigned S> 00541 void pod_bvector<T, S>::free_tail(unsigned size) 00542 { 00543 if(size < m_size) 00544 { 00545 unsigned nb = (size + block_mask) >> block_shift; 00546 while(m_num_blocks > nb) 00547 { 00548 pod_allocator<T>::deallocate(m_blocks[--m_num_blocks], block_size); 00549 } 00550 if(m_num_blocks == 0) 00551 { 00552 pod_allocator<T*>::deallocate(m_blocks, m_max_blocks); 00553 m_blocks = 0; 00554 m_max_blocks = 0; 00555 } 00556 m_size = size; 00557 } 00558 } 00559 00560 00561 //------------------------------------------------------------------------ 00562 template<class T, unsigned S> pod_bvector<T, S>::pod_bvector() : 00563 m_size(0), 00564 m_num_blocks(0), 00565 m_max_blocks(0), 00566 m_blocks(0), 00567 m_block_ptr_inc(block_size) 00568 { 00569 } 00570 00571 00572 //------------------------------------------------------------------------ 00573 template<class T, unsigned S> 00574 pod_bvector<T, S>::pod_bvector(unsigned block_ptr_inc) : 00575 m_size(0), 00576 m_num_blocks(0), 00577 m_max_blocks(0), 00578 m_blocks(0), 00579 m_block_ptr_inc(block_ptr_inc) 00580 { 00581 } 00582 00583 00584 //------------------------------------------------------------------------ 00585 template<class T, unsigned S> 00586 pod_bvector<T, S>::pod_bvector(const pod_bvector<T, S>& v) : 00587 m_size(v.m_size), 00588 m_num_blocks(v.m_num_blocks), 00589 m_max_blocks(v.m_max_blocks), 00590 m_blocks(v.m_max_blocks ? 00591 pod_allocator<T*>::allocate(v.m_max_blocks) : 00592 0), 00593 m_block_ptr_inc(v.m_block_ptr_inc) 00594 { 00595 unsigned i; 00596 for(i = 0; i < v.m_num_blocks; ++i) 00597 { 00598 m_blocks[i] = pod_allocator<T>::allocate(block_size); 00599 memcpy(m_blocks[i], v.m_blocks[i], block_size * sizeof(T)); 00600 } 00601 } 00602 00603 00604 //------------------------------------------------------------------------ 00605 template<class T, unsigned S> 00606 const pod_bvector<T, S>& 00607 pod_bvector<T, S>::operator = (const pod_bvector<T, S>& v) 00608 { 00609 unsigned i; 00610 for(i = m_num_blocks; i < v.m_num_blocks; ++i) 00611 { 00612 allocate_block(i); 00613 } 00614 for(i = 0; i < v.m_num_blocks; ++i) 00615 { 00616 memcpy(m_blocks[i], v.m_blocks[i], block_size * sizeof(T)); 00617 } 00618 m_size = v.m_size; 00619 return *this; 00620 } 00621 00622 00623 //------------------------------------------------------------------------ 00624 template<class T, unsigned S> 00625 void pod_bvector<T, S>::allocate_block(unsigned nb) 00626 { 00627 if(nb >= m_max_blocks) 00628 { 00629 T** new_blocks = pod_allocator<T*>::allocate(m_max_blocks + m_block_ptr_inc); 00630 00631 if(m_blocks) 00632 { 00633 memcpy(new_blocks, 00634 m_blocks, 00635 m_num_blocks * sizeof(T*)); 00636 00637 pod_allocator<T*>::deallocate(m_blocks, m_max_blocks); 00638 } 00639 m_blocks = new_blocks; 00640 m_max_blocks += m_block_ptr_inc; 00641 } 00642 m_blocks[nb] = pod_allocator<T>::allocate(block_size); 00643 m_num_blocks++; 00644 } 00645 00646 00647 00648 //------------------------------------------------------------------------ 00649 template<class T, unsigned S> 00650 inline T* pod_bvector<T, S>::data_ptr() 00651 { 00652 unsigned nb = m_size >> block_shift; 00653 if(nb >= m_num_blocks) 00654 { 00655 allocate_block(nb); 00656 } 00657 return m_blocks[nb] + (m_size & block_mask); 00658 } 00659 00660 00661 00662 //------------------------------------------------------------------------ 00663 template<class T, unsigned S> 00664 inline void pod_bvector<T, S>::add(const T& val) 00665 { 00666 *data_ptr() = val; 00667 ++m_size; 00668 } 00669 00670 00671 //------------------------------------------------------------------------ 00672 template<class T, unsigned S> 00673 inline void pod_bvector<T, S>::remove_last() 00674 { 00675 if(m_size) --m_size; 00676 } 00677 00678 00679 //------------------------------------------------------------------------ 00680 template<class T, unsigned S> 00681 void pod_bvector<T, S>::modify_last(const T& val) 00682 { 00683 remove_last(); 00684 add(val); 00685 } 00686 00687 00688 //------------------------------------------------------------------------ 00689 template<class T, unsigned S> 00690 int pod_bvector<T, S>::allocate_continuous_block(unsigned num_elements) 00691 { 00692 if(num_elements < block_size) 00693 { 00694 data_ptr(); // Allocate initial block if necessary 00695 unsigned rest = block_size - (m_size & block_mask); 00696 unsigned index; 00697 if(num_elements <= rest) 00698 { 00699 // The rest of the block is good, we can use it 00700 //----------------- 00701 index = m_size; 00702 m_size += num_elements; 00703 return index; 00704 } 00705 00706 // New block 00707 //--------------- 00708 m_size += rest; 00709 data_ptr(); 00710 index = m_size; 00711 m_size += num_elements; 00712 return index; 00713 } 00714 return -1; // Impossible to allocate 00715 } 00716 00717 00718 //------------------------------------------------------------------------ 00719 template<class T, unsigned S> 00720 unsigned pod_bvector<T, S>::byte_size() const 00721 { 00722 return m_size * sizeof(T); 00723 } 00724 00725 00726 //------------------------------------------------------------------------ 00727 template<class T, unsigned S> 00728 void pod_bvector<T, S>::serialize(int8u* ptr) const 00729 { 00730 unsigned i; 00731 for(i = 0; i < m_size; i++) 00732 { 00733 memcpy(ptr, &(*this)[i], sizeof(T)); 00734 ptr += sizeof(T); 00735 } 00736 } 00737 00738 //------------------------------------------------------------------------ 00739 template<class T, unsigned S> 00740 void pod_bvector<T, S>::deserialize(const int8u* data, unsigned byte_size) 00741 { 00742 remove_all(); 00743 byte_size /= sizeof(T); 00744 for(unsigned i = 0; i < byte_size; ++i) 00745 { 00746 T* ptr = data_ptr(); 00747 memcpy(ptr, data, sizeof(T)); 00748 ++m_size; 00749 data += sizeof(T); 00750 } 00751 } 00752 00753 00754 // Replace or add a number of elements starting from "start" position 00755 //------------------------------------------------------------------------ 00756 template<class T, unsigned S> 00757 void pod_bvector<T, S>::deserialize(unsigned start, const T& empty_val, 00758 const int8u* data, unsigned byte_size) 00759 { 00760 while(m_size < start) 00761 { 00762 add(empty_val); 00763 } 00764 00765 byte_size /= sizeof(T); 00766 for(unsigned i = 0; i < byte_size; ++i) 00767 { 00768 if(start + i < m_size) 00769 { 00770 memcpy(&((*this)[start + i]), data, sizeof(T)); 00771 } 00772 else 00773 { 00774 T* ptr = data_ptr(); 00775 memcpy(ptr, data, sizeof(T)); 00776 ++m_size; 00777 } 00778 data += sizeof(T); 00779 } 00780 } 00781 00782 00783 //---------------------------------------------------------block_allocator 00784 // Allocator for arbitrary POD data. Most usable in different cache 00785 // systems for efficient memory allocations. 00786 // Memory is allocated with blocks of fixed size ("block_size" in 00787 // the constructor). If required size exceeds the block size the allocator 00788 // creates a new block of the required size. However, the most efficient 00789 // use is when the average reqired size is much less than the block size. 00790 //------------------------------------------------------------------------ 00791 class block_allocator 00792 { 00793 struct block_type 00794 { 00795 int8u* data; 00796 unsigned size; 00797 }; 00798 00799 public: 00800 void remove_all() 00801 { 00802 if(m_num_blocks) 00803 { 00804 block_type* blk = m_blocks + m_num_blocks - 1; 00805 while(m_num_blocks--) 00806 { 00807 pod_allocator<int8u>::deallocate(blk->data, blk->size); 00808 --blk; 00809 } 00810 pod_allocator<block_type>::deallocate(m_blocks, m_max_blocks); 00811 } 00812 m_num_blocks = 0; 00813 m_max_blocks = 0; 00814 m_blocks = 0; 00815 m_buf_ptr = 0; 00816 m_rest = 0; 00817 } 00818 00819 ~block_allocator() 00820 { 00821 remove_all(); 00822 } 00823 00824 block_allocator(unsigned block_size, unsigned block_ptr_inc=256-8) : 00825 m_block_size(block_size), 00826 m_block_ptr_inc(block_ptr_inc), 00827 m_num_blocks(0), 00828 m_max_blocks(0), 00829 m_blocks(0), 00830 m_buf_ptr(0), 00831 m_rest(0) 00832 { 00833 } 00834 00835 00836 int8u* allocate(unsigned size, unsigned alignment=1) 00837 { 00838 if(size == 0) return 0; 00839 if(size <= m_rest) 00840 { 00841 int8u* ptr = m_buf_ptr; 00842 if(alignment > 1) 00843 { 00844 unsigned align = 00845 (alignment - unsigned((size_t)ptr) % alignment) % alignment; 00846 00847 size += align; 00848 ptr += align; 00849 if(size <= m_rest) 00850 { 00851 m_rest -= size; 00852 m_buf_ptr += size; 00853 return ptr; 00854 } 00855 allocate_block(size); 00856 return allocate(size - align, alignment); 00857 } 00858 m_rest -= size; 00859 m_buf_ptr += size; 00860 return ptr; 00861 } 00862 allocate_block(size + alignment - 1); 00863 return allocate(size, alignment); 00864 } 00865 00866 00867 private: 00868 void allocate_block(unsigned size) 00869 { 00870 if(size < m_block_size) size = m_block_size; 00871 if(m_num_blocks >= m_max_blocks) 00872 { 00873 block_type* new_blocks = 00874 pod_allocator<block_type>::allocate(m_max_blocks + m_block_ptr_inc); 00875 00876 if(m_blocks) 00877 { 00878 memcpy(new_blocks, 00879 m_blocks, 00880 m_num_blocks * sizeof(block_type)); 00881 pod_allocator<block_type>::deallocate(m_blocks, m_max_blocks); 00882 } 00883 m_blocks = new_blocks; 00884 m_max_blocks += m_block_ptr_inc; 00885 } 00886 00887 m_blocks[m_num_blocks].size = size; 00888 m_blocks[m_num_blocks].data = 00889 m_buf_ptr = 00890 pod_allocator<int8u>::allocate(size); 00891 00892 m_num_blocks++; 00893 m_rest = size; 00894 } 00895 00896 unsigned m_block_size; 00897 unsigned m_block_ptr_inc; 00898 unsigned m_num_blocks; 00899 unsigned m_max_blocks; 00900 block_type* m_blocks; 00901 int8u* m_buf_ptr; 00902 unsigned m_rest; 00903 }; 00904 00905 00906 00907 00908 00909 00910 00911 00912 //------------------------------------------------------------------------ 00913 enum quick_sort_threshold_e 00914 { 00915 quick_sort_threshold = 9 00916 }; 00917 00918 00919 //-----------------------------------------------------------swap_elements 00920 template<class T> inline void swap_elements(T& a, T& b) 00921 { 00922 T temp = a; 00923 a = b; 00924 b = temp; 00925 } 00926 00927 00928 //--------------------------------------------------------------quick_sort 00929 template<class Array, class Less> 00930 void quick_sort(Array& arr, Less less) 00931 { 00932 if(arr.size() < 2) return; 00933 00934 typename Array::value_type* e1; 00935 typename Array::value_type* e2; 00936 00937 int stack[80]; 00938 int* top = stack; 00939 int limit = arr.size(); 00940 int base = 0; 00941 00942 for(;;) 00943 { 00944 int len = limit - base; 00945 00946 int i; 00947 int j; 00948 int pivot; 00949 00950 if(len > quick_sort_threshold) 00951 { 00952 // we use base + len/2 as the pivot 00953 pivot = base + len / 2; 00954 swap_elements(arr[base], arr[pivot]); 00955 00956 i = base + 1; 00957 j = limit - 1; 00958 00959 // now ensure that *i <= *base <= *j 00960 e1 = &(arr[j]); 00961 e2 = &(arr[i]); 00962 if(less(*e1, *e2)) swap_elements(*e1, *e2); 00963 00964 e1 = &(arr[base]); 00965 e2 = &(arr[i]); 00966 if(less(*e1, *e2)) swap_elements(*e1, *e2); 00967 00968 e1 = &(arr[j]); 00969 e2 = &(arr[base]); 00970 if(less(*e1, *e2)) swap_elements(*e1, *e2); 00971 00972 for(;;) 00973 { 00974 do i++; while( less(arr[i], arr[base]) ); 00975 do j--; while( less(arr[base], arr[j]) ); 00976 00977 if( i > j ) 00978 { 00979 break; 00980 } 00981 00982 swap_elements(arr[i], arr[j]); 00983 } 00984 00985 swap_elements(arr[base], arr[j]); 00986 00987 // now, push the largest sub-array 00988 if(j - base > limit - i) 00989 { 00990 top[0] = base; 00991 top[1] = j; 00992 base = i; 00993 } 00994 else 00995 { 00996 top[0] = i; 00997 top[1] = limit; 00998 limit = j; 00999 } 01000 top += 2; 01001 } 01002 else 01003 { 01004 // the sub-array is small, perform insertion sort 01005 j = base; 01006 i = j + 1; 01007 01008 for(; i < limit; j = i, i++) 01009 { 01010 for(; less(*(e1 = &(arr[j + 1])), *(e2 = &(arr[j]))); j--) 01011 { 01012 swap_elements(*e1, *e2); 01013 if(j == base) 01014 { 01015 break; 01016 } 01017 } 01018 } 01019 if(top > stack) 01020 { 01021 top -= 2; 01022 base = top[0]; 01023 limit = top[1]; 01024 } 01025 else 01026 { 01027 break; 01028 } 01029 } 01030 } 01031 } 01032 01033 01034 01035 01036 //------------------------------------------------------remove_duplicates 01037 // Remove duplicates from a sorted array. It doesn't cut the 01038 // tail of the array, it just returns the number of remaining elements. 01039 //----------------------------------------------------------------------- 01040 template<class Array, class Equal> 01041 unsigned remove_duplicates(Array& arr, Equal equal) 01042 { 01043 if(arr.size() < 2) return arr.size(); 01044 01045 unsigned i, j; 01046 for(i = 1, j = 1; i < arr.size(); i++) 01047 { 01048 typename Array::value_type& e = arr[i]; 01049 if(!equal(e, arr[i - 1])) 01050 { 01051 arr[j++] = e; 01052 } 01053 } 01054 return j; 01055 } 01056 01057 //--------------------------------------------------------invert_container 01058 template<class Array> void invert_container(Array& arr) 01059 { 01060 int i = 0; 01061 int j = arr.size() - 1; 01062 while(i < j) 01063 { 01064 swap_elements(arr[i++], arr[j--]); 01065 } 01066 } 01067 01068 //------------------------------------------------------binary_search_pos 01069 template<class Array, class Value, class Less> 01070 unsigned binary_search_pos(const Array& arr, const Value& val, Less less) 01071 { 01072 if(arr.size() == 0) return 0; 01073 01074 unsigned beg = 0; 01075 unsigned end = arr.size() - 1; 01076 01077 if(less(val, arr[0])) return 0; 01078 if(less(arr[end], val)) return end + 1; 01079 01080 while(end - beg > 1) 01081 { 01082 unsigned mid = (end + beg) >> 1; 01083 if(less(val, arr[mid])) end = mid; 01084 else beg = mid; 01085 } 01086 01087 //if(beg <= 0 && less(val, arr[0])) return 0; 01088 //if(end >= arr.size() - 1 && less(arr[end], val)) ++end; 01089 01090 return end; 01091 } 01092 01093 //----------------------------------------------------------range_adaptor 01094 template<class Array> class range_adaptor 01095 { 01096 public: 01097 typedef typename Array::value_type value_type; 01098 01099 range_adaptor(Array& array, unsigned start, unsigned size) : 01100 m_array(array), m_start(start), m_size(size) 01101 {} 01102 01103 unsigned size() const { return m_size; } 01104 const value_type& operator [] (unsigned i) const { return m_array[m_start + i]; } 01105 value_type& operator [] (unsigned i) { return m_array[m_start + i]; } 01106 const value_type& at(unsigned i) const { return m_array[m_start + i]; } 01107 value_type& at(unsigned i) { return m_array[m_start + i]; } 01108 value_type value_at(unsigned i) const { return m_array[m_start + i]; } 01109 01110 private: 01111 Array& m_array; 01112 unsigned m_start; 01113 unsigned m_size; 01114 }; 01115 01116 //---------------------------------------------------------------int_less 01117 inline bool int_less(int a, int b) { return a < b; } 01118 01119 //------------------------------------------------------------int_greater 01120 inline bool int_greater(int a, int b) { return a > b; } 01121 01122 //----------------------------------------------------------unsigned_less 01123 inline bool unsigned_less(unsigned a, unsigned b) { return a < b; } 01124 01125 //-------------------------------------------------------unsigned_greater 01126 inline bool unsigned_greater(unsigned a, unsigned b) { return a > b; } 01127 } 01128 01129 #endif