1//---------------------------------------------------------------------------- 2// Anti-Grain Geometry - Version 2.4 3// Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com) 4// 5// Permission to copy, use, modify, sell and distribute this software 6// is granted provided this copyright notice appears in all copies. 7// This software is provided "as is" without express or implied 8// warranty, and with no claim as to its suitability for any purpose. 9// 10//---------------------------------------------------------------------------- 11// Contact: mcseem@antigrain.com 12// mcseemagg@yahoo.com 13// http://www.antigrain.com 14//---------------------------------------------------------------------------- 15#ifndef AGG_ARRAY_INCLUDED 16#define AGG_ARRAY_INCLUDED 17 18#include <stddef.h> 19#include <string.h> 20#include "agg_basics.h" 21 22namespace agg 23{ 24 25 //-------------------------------------------------------pod_array_adaptor 26 template<class T> class pod_array_adaptor 27 { 28 public: 29 typedef T value_type; 30 pod_array_adaptor(T* array, unsigned size) : 31 m_array(array), m_size(size) {} 32 33 unsigned size() const { return m_size; } 34 const T& operator [] (unsigned i) const { return m_array[i]; } 35 T& operator [] (unsigned i) { return m_array[i]; } 36 const T& at(unsigned i) const { return m_array[i]; } 37 T& at(unsigned i) { return m_array[i]; } 38 T value_at(unsigned i) const { return m_array[i]; } 39 40 private: 41 T* m_array; 42 unsigned m_size; 43 }; 44 45 46 //---------------------------------------------------------pod_auto_array 47 template<class T, unsigned Size> class pod_auto_array 48 { 49 public: 50 typedef T value_type; 51 typedef pod_auto_array<T, Size> self_type; 52 53 pod_auto_array() {} 54 explicit pod_auto_array(const T* c) 55 { 56 memcpy(m_array, c, sizeof(T) * Size); 57 } 58 59 const self_type& operator = (const T* c) 60 { 61 memcpy(m_array, c, sizeof(T) * Size); 62 return *this; 63 } 64 65 static unsigned size() { return Size; } 66 const T& operator [] (unsigned i) const { return m_array[i]; } 67 T& operator [] (unsigned i) { return m_array[i]; } 68 const T& at(unsigned i) const { return m_array[i]; } 69 T& at(unsigned i) { return m_array[i]; } 70 T value_at(unsigned i) const { return m_array[i]; } 71 72 private: 73 T m_array[Size]; 74 }; 75 76 77 //--------------------------------------------------------pod_auto_vector 78 template<class T, unsigned Size> class pod_auto_vector 79 { 80 public: 81 typedef T value_type; 82 typedef pod_auto_vector<T, Size> self_type; 83 84 pod_auto_vector() : m_size(0) {} 85 86 void remove_all() { m_size = 0; } 87 void clear() { m_size = 0; } 88 void add(const T& v) { m_array[m_size++] = v; } 89 void push_back(const T& v) { m_array[m_size++] = v; } 90 void inc_size(unsigned size) { m_size += size; } 91 92 unsigned size() const { return m_size; } 93 const T& operator [] (unsigned i) const { return m_array[i]; } 94 T& operator [] (unsigned i) { return m_array[i]; } 95 const T& at(unsigned i) const { return m_array[i]; } 96 T& at(unsigned i) { return m_array[i]; } 97 T value_at(unsigned i) const { return m_array[i]; } 98 99 private: 100 T m_array[Size]; 101 unsigned m_size; 102 }; 103 104 105 //---------------------------------------------------------------pod_array 106 template<class T> class pod_array 107 { 108 public: 109 typedef T value_type; 110 typedef pod_array<T> self_type; 111 112 ~pod_array() { pod_allocator<T>::deallocate(m_array, m_size); } 113 pod_array() : m_array(0), m_size(0) {} 114 115 pod_array(unsigned size) : 116 m_array(pod_allocator<T>::allocate(size)), 117 m_size(size) 118 {} 119 120 pod_array(const self_type& v) : 121 m_array(pod_allocator<T>::allocate(v.m_size)), 122 m_size(v.m_size) 123 { 124 memcpy(m_array, v.m_array, sizeof(T) * m_size); 125 } 126 127 void resize(unsigned size) 128 { 129 if(size != m_size) 130 { 131 pod_allocator<T>::deallocate(m_array, m_size); 132 m_array = pod_allocator<T>::allocate(m_size = size); 133 } 134 } 135 const self_type& operator = (const self_type& v) 136 { 137 resize(v.size()); 138 memcpy(m_array, v.m_array, sizeof(T) * m_size); 139 return *this; 140 } 141 142 unsigned size() const { return m_size; } 143 const T& operator [] (unsigned i) const { return m_array[i]; } 144 T& operator [] (unsigned i) { return m_array[i]; } 145 const T& at(unsigned i) const { return m_array[i]; } 146 T& at(unsigned i) { return m_array[i]; } 147 T value_at(unsigned i) const { return m_array[i]; } 148 149 const T* data() const { return m_array; } 150 T* data() { return m_array; } 151 private: 152 T* m_array; 153 unsigned m_size; 154 }; 155 156 157 158 //--------------------------------------------------------------pod_vector 159 // A simple class template to store Plain Old Data, a vector 160 // of a fixed size. The data is continous in memory 161 //------------------------------------------------------------------------ 162 template<class T> class pod_vector 163 { 164 public: 165 typedef T value_type; 166 167 ~pod_vector() { pod_allocator<T>::deallocate(m_array, m_capacity); } 168 pod_vector() : m_size(0), m_capacity(0), m_array(0) {} 169 pod_vector(unsigned cap, unsigned extra_tail=0); 170 171 // Copying 172 pod_vector(const pod_vector<T>&); 173 const pod_vector<T>& operator = (const pod_vector<T>&); 174 175 // Set new capacity. All data is lost, size is set to zero. 176 void capacity(unsigned cap, unsigned extra_tail=0); 177 unsigned capacity() const { return m_capacity; } 178 179 // Allocate n elements. All data is lost, 180 // but elements can be accessed in range 0...size-1. 181 void allocate(unsigned size, unsigned extra_tail=0); 182 183 // Resize keeping the content. 184 void resize(unsigned new_size); 185 186 void zero() 187 { 188 memset(m_array, 0, sizeof(T) * m_size); 189 } 190 191 void add(const T& v) { m_array[m_size++] = v; } 192 void push_back(const T& v) { m_array[m_size++] = v; } 193 void insert_at(unsigned pos, const T& val); 194 void inc_size(unsigned size) { m_size += size; } 195 unsigned size() const { return m_size; } 196 unsigned byte_size() const { return m_size * sizeof(T); } 197 void serialize(int8u* ptr) const; 198 void deserialize(const int8u* data, unsigned byte_size); 199 const T& operator [] (unsigned i) const { return m_array[i]; } 200 T& operator [] (unsigned i) { return m_array[i]; } 201 const T& at(unsigned i) const { return m_array[i]; } 202 T& at(unsigned i) { return m_array[i]; } 203 T value_at(unsigned i) const { return m_array[i]; } 204 205 const T* data() const { return m_array; } 206 T* data() { return m_array; } 207 208 void remove_all() { m_size = 0; } 209 void clear() { m_size = 0; } 210 void cut_at(unsigned num) { if(num < m_size) m_size = num; } 211 212 private: 213 unsigned m_size; 214 unsigned m_capacity; 215 T* m_array; 216 }; 217 218 //------------------------------------------------------------------------ 219 template<class T> 220 void pod_vector<T>::capacity(unsigned cap, unsigned extra_tail) 221 { 222 m_size = 0; 223 if(cap > m_capacity) 224 { 225 pod_allocator<T>::deallocate(m_array, m_capacity); 226 m_capacity = cap + extra_tail; 227 m_array = m_capacity ? pod_allocator<T>::allocate(m_capacity) : 0; 228 } 229 } 230 231 //------------------------------------------------------------------------ 232 template<class T> 233 void pod_vector<T>::allocate(unsigned size, unsigned extra_tail) 234 { 235 capacity(size, extra_tail); 236 m_size = size; 237 } 238 239 240 //------------------------------------------------------------------------ 241 template<class T> 242 void pod_vector<T>::resize(unsigned new_size) 243 { 244 if(new_size > m_size) 245 { 246 if(new_size > m_capacity) 247 { 248 T* data = pod_allocator<T>::allocate(new_size); 249 memcpy(data, m_array, m_size * sizeof(T)); 250 pod_allocator<T>::deallocate(m_array, m_capacity); 251 m_array = data; 252 } 253 } 254 else 255 { 256 m_size = new_size; 257 } 258 } 259 260 //------------------------------------------------------------------------ 261 template<class T> pod_vector<T>::pod_vector(unsigned cap, unsigned extra_tail) : 262 m_size(0), 263 m_capacity(cap + extra_tail), 264 m_array(pod_allocator<T>::allocate(m_capacity)) {} 265 266 //------------------------------------------------------------------------ 267 template<class T> pod_vector<T>::pod_vector(const pod_vector<T>& v) : 268 m_size(v.m_size), 269 m_capacity(v.m_capacity), 270 m_array(v.m_capacity ? pod_allocator<T>::allocate(v.m_capacity) : 0) 271 { 272 memcpy(m_array, v.m_array, sizeof(T) * v.m_size); 273 } 274 275 //------------------------------------------------------------------------ 276 template<class T> const pod_vector<T>& 277 pod_vector<T>::operator = (const pod_vector<T>&v) 278 { 279 allocate(v.m_size); 280 if(v.m_size) memcpy(m_array, v.m_array, sizeof(T) * v.m_size); 281 return *this; 282 } 283 284 //------------------------------------------------------------------------ 285 template<class T> void pod_vector<T>::serialize(int8u* ptr) const 286 { 287 if(m_size) memcpy(ptr, m_array, m_size * sizeof(T)); 288 } 289 290 //------------------------------------------------------------------------ 291 template<class T> 292 void pod_vector<T>::deserialize(const int8u* data, unsigned byte_size) 293 { 294 byte_size /= sizeof(T); 295 allocate(byte_size); 296 if(byte_size) memcpy(m_array, data, byte_size * sizeof(T)); 297 } 298 299 //------------------------------------------------------------------------ 300 template<class T> 301 void pod_vector<T>::insert_at(unsigned pos, const T& val) 302 { 303 if(pos >= m_size) 304 { 305 m_array[m_size] = val; 306 } 307 else 308 { 309 memmove(m_array + pos + 1, m_array + pos, (m_size - pos) * sizeof(T)); 310 m_array[pos] = val; 311 } 312 ++m_size; 313 } 314 315 //---------------------------------------------------------------pod_bvector 316 // A simple class template to store Plain Old Data, similar to std::deque 317 // It doesn't reallocate memory but instead, uses blocks of data of size 318 // of (1 << S), that is, power of two. The data is NOT contiguous in memory, 319 // so the only valid access method is operator [] or curr(), prev(), next() 320 // 321 // There reallocs occure only when the pool of pointers to blocks needs 322 // to be extended (it happens very rarely). You can control the value 323 // of increment to reallocate the pointer buffer. See the second constructor. 324 // By default, the incremeent value equals (1 << S), i.e., the block size. 325 //------------------------------------------------------------------------ 326 template<class T, unsigned S=6> class pod_bvector 327 { 328 public: 329 enum block_scale_e 330 { 331 block_shift = S, 332 block_size = 1 << block_shift, 333 block_mask = block_size - 1 334 }; 335 336 typedef T value_type; 337 338 ~pod_bvector(); 339 pod_bvector(); 340 pod_bvector(unsigned block_ptr_inc); 341 342 // Copying 343 pod_bvector(const pod_bvector<T, S>& v); 344 const pod_bvector<T, S>& operator = (const pod_bvector<T, S>& v); 345 346 void remove_all() { m_size = 0; } 347 void clear() { m_size = 0; } 348 void free_all() { free_tail(0); } 349 void free_tail(unsigned size); 350 void add(const T& val); 351 void push_back(const T& val) { add(val); } 352 void modify_last(const T& val); 353 void remove_last(); 354 355 int allocate_continuous_block(unsigned num_elements); 356 357 void add_array(const T* ptr, unsigned num_elem) 358 { 359 while(num_elem--) 360 { 361 add(*ptr++); 362 } 363 } 364 365 template<class DataAccessor> void add_data(DataAccessor& data) 366 { 367 while(data.size()) 368 { 369 add(*data); 370 ++data; 371 } 372 } 373 374 void cut_at(unsigned size) 375 { 376 if(size < m_size) m_size = size; 377 } 378 379 unsigned size() const { return m_size; } 380 381 const T& operator [] (unsigned i) const 382 { 383 return m_blocks[i >> block_shift][i & block_mask]; 384 } 385 386 T& operator [] (unsigned i) 387 { 388 return m_blocks[i >> block_shift][i & block_mask]; 389 } 390 391 const T& at(unsigned i) const 392 { 393 return m_blocks[i >> block_shift][i & block_mask]; 394 } 395 396 T& at(unsigned i) 397 { 398 return m_blocks[i >> block_shift][i & block_mask]; 399 } 400 401 T value_at(unsigned i) const 402 { 403 return m_blocks[i >> block_shift][i & block_mask]; 404 } 405 406 const T& curr(unsigned idx) const 407 { 408 return (*this)[idx]; 409 } 410 411 T& curr(unsigned idx) 412 { 413 return (*this)[idx]; 414 } 415 416 const T& prev(unsigned idx) const 417 { 418 return (*this)[(idx + m_size - 1) % m_size]; 419 } 420 421 T& prev(unsigned idx) 422 { 423 return (*this)[(idx + m_size - 1) % m_size]; 424 } 425 426 const T& next(unsigned idx) const 427 { 428 return (*this)[(idx + 1) % m_size]; 429 } 430 431 T& next(unsigned idx) 432 { 433 return (*this)[(idx + 1) % m_size]; 434 } 435 436 const T& last() const 437 { 438 return (*this)[m_size - 1]; 439 } 440 441 T& last() 442 { 443 return (*this)[m_size - 1]; 444 } 445 446 unsigned byte_size() const; 447 void serialize(int8u* ptr) const; 448 void deserialize(const int8u* data, unsigned byte_size); 449 void deserialize(unsigned start, const T& empty_val, 450 const int8u* data, unsigned byte_size); 451 452 template<class ByteAccessor> 453 void deserialize(ByteAccessor data) 454 { 455 remove_all(); 456 unsigned elem_size = data.size() / sizeof(T); 457 458 for(unsigned i = 0; i < elem_size; ++i) 459 { 460 int8u* ptr = (int8u*)data_ptr(); 461 for(unsigned j = 0; j < sizeof(T); ++j) 462 { 463 *ptr++ = *data; 464 ++data; 465 } 466 ++m_size; 467 } 468 } 469 470 template<class ByteAccessor> 471 void deserialize(unsigned start, const T& empty_val, ByteAccessor data) 472 { 473 while(m_size < start) 474 { 475 add(empty_val); 476 } 477 478 unsigned elem_size = data.size() / sizeof(T); 479 for(unsigned i = 0; i < elem_size; ++i) 480 { 481 int8u* ptr; 482 if(start + i < m_size) 483 { 484 ptr = (int8u*)(&((*this)[start + i])); 485 } 486 else 487 { 488 ptr = (int8u*)data_ptr(); 489 ++m_size; 490 } 491 for(unsigned j = 0; j < sizeof(T); ++j) 492 { 493 *ptr++ = *data; 494 ++data; 495 } 496 } 497 } 498 499 const T* block(unsigned nb) const { return m_blocks[nb]; } 500 501 private: 502 void allocate_block(unsigned nb); 503 T* data_ptr(); 504 505 unsigned m_size; 506 unsigned m_num_blocks; 507 unsigned m_max_blocks; 508 T** m_blocks; 509 unsigned m_block_ptr_inc; 510 }; 511 512 513 //------------------------------------------------------------------------ 514 template<class T, unsigned S> pod_bvector<T, S>::~pod_bvector() 515 { 516 if(m_num_blocks) 517 { 518 T** blk = m_blocks + m_num_blocks - 1; 519 while(m_num_blocks--) 520 { 521 pod_allocator<T>::deallocate(*blk, block_size); 522 --blk; 523 } 524 } 525 pod_allocator<T*>::deallocate(m_blocks, m_max_blocks); 526 } 527 528 529 //------------------------------------------------------------------------ 530 template<class T, unsigned S> 531 void pod_bvector<T, S>::free_tail(unsigned size) 532 { 533 if(size < m_size) 534 { 535 unsigned nb = (size + block_mask) >> block_shift; 536 while(m_num_blocks > nb) 537 { 538 pod_allocator<T>::deallocate(m_blocks[--m_num_blocks], block_size); 539 } 540 if(m_num_blocks == 0) 541 { 542 pod_allocator<T*>::deallocate(m_blocks, m_max_blocks); 543 m_blocks = 0; 544 m_max_blocks = 0; 545 } 546 m_size = size; 547 } 548 } 549 550 551 //------------------------------------------------------------------------ 552 template<class T, unsigned S> pod_bvector<T, S>::pod_bvector() : 553 m_size(0), 554 m_num_blocks(0), 555 m_max_blocks(0), 556 m_blocks(0), 557 m_block_ptr_inc(block_size) 558 { 559 } 560 561 562 //------------------------------------------------------------------------ 563 template<class T, unsigned S> 564 pod_bvector<T, S>::pod_bvector(unsigned block_ptr_inc) : 565 m_size(0), 566 m_num_blocks(0), 567 m_max_blocks(0), 568 m_blocks(0), 569 m_block_ptr_inc(block_ptr_inc) 570 { 571 } 572 573 574 //------------------------------------------------------------------------ 575 template<class T, unsigned S> 576 pod_bvector<T, S>::pod_bvector(const pod_bvector<T, S>& v) : 577 m_size(v.m_size), 578 m_num_blocks(v.m_num_blocks), 579 m_max_blocks(v.m_max_blocks), 580 m_blocks(v.m_max_blocks ? 581 pod_allocator<T*>::allocate(v.m_max_blocks) : 582 0), 583 m_block_ptr_inc(v.m_block_ptr_inc) 584 { 585 unsigned i; 586 for(i = 0; i < v.m_num_blocks; ++i) 587 { 588 m_blocks[i] = pod_allocator<T>::allocate(block_size); 589 memcpy(m_blocks[i], v.m_blocks[i], block_size * sizeof(T)); 590 } 591 } 592 593 594 //------------------------------------------------------------------------ 595 template<class T, unsigned S> 596 const pod_bvector<T, S>& 597 pod_bvector<T, S>::operator = (const pod_bvector<T, S>& v) 598 { 599 unsigned i; 600 for(i = m_num_blocks; i < v.m_num_blocks; ++i) 601 { 602 allocate_block(i); 603 } 604 for(i = 0; i < v.m_num_blocks; ++i) 605 { 606 memcpy(m_blocks[i], v.m_blocks[i], block_size * sizeof(T)); 607 } 608 m_size = v.m_size; 609 return *this; 610 } 611 612 613 //------------------------------------------------------------------------ 614 template<class T, unsigned S> 615 void pod_bvector<T, S>::allocate_block(unsigned nb) 616 { 617 if(nb >= m_max_blocks) 618 { 619 T** new_blocks = pod_allocator<T*>::allocate(m_max_blocks + m_block_ptr_inc); 620 621 if(m_blocks) 622 { 623 memcpy(new_blocks, 624 m_blocks, 625 m_num_blocks * sizeof(T*)); 626 627 pod_allocator<T*>::deallocate(m_blocks, m_max_blocks); 628 } 629 m_blocks = new_blocks; 630 m_max_blocks += m_block_ptr_inc; 631 } 632 m_blocks[nb] = pod_allocator<T>::allocate(block_size); 633 m_num_blocks++; 634 } 635 636 637 638 //------------------------------------------------------------------------ 639 template<class T, unsigned S> 640 inline T* pod_bvector<T, S>::data_ptr() 641 { 642 unsigned nb = m_size >> block_shift; 643 if(nb >= m_num_blocks) 644 { 645 allocate_block(nb); 646 } 647 return m_blocks[nb] + (m_size & block_mask); 648 } 649 650 651 652 //------------------------------------------------------------------------ 653 template<class T, unsigned S> 654 inline void pod_bvector<T, S>::add(const T& val) 655 { 656 *data_ptr() = val; 657 ++m_size; 658 } 659 660 661 //------------------------------------------------------------------------ 662 template<class T, unsigned S> 663 inline void pod_bvector<T, S>::remove_last() 664 { 665 if(m_size) --m_size; 666 } 667 668 669 //------------------------------------------------------------------------ 670 template<class T, unsigned S> 671 void pod_bvector<T, S>::modify_last(const T& val) 672 { 673 remove_last(); 674 add(val); 675 } 676 677 678 //------------------------------------------------------------------------ 679 template<class T, unsigned S> 680 int pod_bvector<T, S>::allocate_continuous_block(unsigned num_elements) 681 { 682 if(num_elements < block_size) 683 { 684 data_ptr(); // Allocate initial block if necessary 685 unsigned rest = block_size - (m_size & block_mask); 686 unsigned index; 687 if(num_elements <= rest) 688 { 689 // The rest of the block is good, we can use it 690 //----------------- 691 index = m_size; 692 m_size += num_elements; 693 return index; 694 } 695 696 // New block 697 //--------------- 698 m_size += rest; 699 data_ptr(); 700 index = m_size; 701 m_size += num_elements; 702 return index; 703 } 704 return -1; // Impossible to allocate 705 } 706 707 708 //------------------------------------------------------------------------ 709 template<class T, unsigned S> 710 unsigned pod_bvector<T, S>::byte_size() const 711 { 712 return m_size * sizeof(T); 713 } 714 715 716 //------------------------------------------------------------------------ 717 template<class T, unsigned S> 718 void pod_bvector<T, S>::serialize(int8u* ptr) const 719 { 720 unsigned i; 721 for(i = 0; i < m_size; i++) 722 { 723 memcpy(ptr, &(*this)[i], sizeof(T)); 724 ptr += sizeof(T); 725 } 726 } 727 728 //------------------------------------------------------------------------ 729 template<class T, unsigned S> 730 void pod_bvector<T, S>::deserialize(const int8u* data, unsigned byte_size) 731 { 732 remove_all(); 733 byte_size /= sizeof(T); 734 for(unsigned i = 0; i < byte_size; ++i) 735 { 736 T* ptr = data_ptr(); 737 memcpy(ptr, data, sizeof(T)); 738 ++m_size; 739 data += sizeof(T); 740 } 741 } 742 743 744 // Replace or add a number of elements starting from "start" position 745 //------------------------------------------------------------------------ 746 template<class T, unsigned S> 747 void pod_bvector<T, S>::deserialize(unsigned start, const T& empty_val, 748 const int8u* data, unsigned byte_size) 749 { 750 while(m_size < start) 751 { 752 add(empty_val); 753 } 754 755 byte_size /= sizeof(T); 756 for(unsigned i = 0; i < byte_size; ++i) 757 { 758 if(start + i < m_size) 759 { 760 memcpy(&((*this)[start + i]), data, sizeof(T)); 761 } 762 else 763 { 764 T* ptr = data_ptr(); 765 memcpy(ptr, data, sizeof(T)); 766 ++m_size; 767 } 768 data += sizeof(T); 769 } 770 } 771 772 773 //---------------------------------------------------------block_allocator 774 // Allocator for arbitrary POD data. Most usable in different cache 775 // systems for efficient memory allocations. 776 // Memory is allocated with blocks of fixed size ("block_size" in 777 // the constructor). If required size exceeds the block size the allocator 778 // creates a new block of the required size. However, the most efficient 779 // use is when the average reqired size is much less than the block size. 780 //------------------------------------------------------------------------ 781 class block_allocator 782 { 783 struct block_type 784 { 785 int8u* data; 786 unsigned size; 787 }; 788 789 public: 790 void remove_all() 791 { 792 if(m_num_blocks) 793 { 794 block_type* blk = m_blocks + m_num_blocks - 1; 795 while(m_num_blocks--) 796 { 797 pod_allocator<int8u>::deallocate(blk->data, blk->size); 798 --blk; 799 } 800 pod_allocator<block_type>::deallocate(m_blocks, m_max_blocks); 801 } 802 m_num_blocks = 0; 803 m_max_blocks = 0; 804 m_blocks = 0; 805 m_buf_ptr = 0; 806 m_rest = 0; 807 } 808 809 ~block_allocator() 810 { 811 remove_all(); 812 } 813 814 block_allocator(unsigned block_size, unsigned block_ptr_inc=256-8) : 815 m_block_size(block_size), 816 m_block_ptr_inc(block_ptr_inc), 817 m_num_blocks(0), 818 m_max_blocks(0), 819 m_blocks(0), 820 m_buf_ptr(0), 821 m_rest(0) 822 { 823 } 824 825 826 int8u* allocate(unsigned size, unsigned alignment=1) 827 { 828 if(size == 0) return 0; 829 if(size <= m_rest) 830 { 831 int8u* ptr = m_buf_ptr; 832 if(alignment > 1) 833 { 834 unsigned align = 835 (alignment - unsigned((size_t)ptr) % alignment) % alignment; 836 837 size += align; 838 ptr += align; 839 if(size <= m_rest) 840 { 841 m_rest -= size; 842 m_buf_ptr += size; 843 return ptr; 844 } 845 allocate_block(size); 846 return allocate(size - align, alignment); 847 } 848 m_rest -= size; 849 m_buf_ptr += size; 850 return ptr; 851 } 852 allocate_block(size + alignment - 1); 853 return allocate(size, alignment); 854 } 855 856 857 private: 858 void allocate_block(unsigned size) 859 { 860 if(size < m_block_size) size = m_block_size; 861 if(m_num_blocks >= m_max_blocks) 862 { 863 block_type* new_blocks = 864 pod_allocator<block_type>::allocate(m_max_blocks + m_block_ptr_inc); 865 866 if(m_blocks) 867 { 868 memcpy(new_blocks, 869 m_blocks, 870 m_num_blocks * sizeof(block_type)); 871 pod_allocator<block_type>::deallocate(m_blocks, m_max_blocks); 872 } 873 m_blocks = new_blocks; 874 m_max_blocks += m_block_ptr_inc; 875 } 876 877 m_blocks[m_num_blocks].size = size; 878 m_blocks[m_num_blocks].data = 879 m_buf_ptr = 880 pod_allocator<int8u>::allocate(size); 881 882 m_num_blocks++; 883 m_rest = size; 884 } 885 886 unsigned m_block_size; 887 unsigned m_block_ptr_inc; 888 unsigned m_num_blocks; 889 unsigned m_max_blocks; 890 block_type* m_blocks; 891 int8u* m_buf_ptr; 892 unsigned m_rest; 893 }; 894 895 896 897 898 899 900 901 902 //------------------------------------------------------------------------ 903 enum quick_sort_threshold_e 904 { 905 quick_sort_threshold = 9 906 }; 907 908 909 //-----------------------------------------------------------swap_elements 910 template<class T> inline void swap_elements(T& a, T& b) 911 { 912 T temp = a; 913 a = b; 914 b = temp; 915 } 916 917 918 //--------------------------------------------------------------quick_sort 919 template<class Array, class Less> 920 void quick_sort(Array& arr, Less less) 921 { 922 if(arr.size() < 2) return; 923 924 typename Array::value_type* e1; 925 typename Array::value_type* e2; 926 927 int stack[80]; 928 int* top = stack; 929 int limit = arr.size(); 930 int base = 0; 931 932 for(;;) 933 { 934 int len = limit - base; 935 936 int i; 937 int j; 938 int pivot; 939 940 if(len > quick_sort_threshold) 941 { 942 // we use base + len/2 as the pivot 943 pivot = base + len / 2; 944 swap_elements(arr[base], arr[pivot]); 945 946 i = base + 1; 947 j = limit - 1; 948 949 // now ensure that *i <= *base <= *j 950 e1 = &(arr[j]); 951 e2 = &(arr[i]); 952 if(less(*e1, *e2)) swap_elements(*e1, *e2); 953 954 e1 = &(arr[base]); 955 e2 = &(arr[i]); 956 if(less(*e1, *e2)) swap_elements(*e1, *e2); 957 958 e1 = &(arr[j]); 959 e2 = &(arr[base]); 960 if(less(*e1, *e2)) swap_elements(*e1, *e2); 961 962 for(;;) 963 { 964 do i++; while( less(arr[i], arr[base]) ); 965 do j--; while( less(arr[base], arr[j]) ); 966 967 if( i > j ) 968 { 969 break; 970 } 971 972 swap_elements(arr[i], arr[j]); 973 } 974 975 swap_elements(arr[base], arr[j]); 976 977 // now, push the largest sub-array 978 if(j - base > limit - i) 979 { 980 top[0] = base; 981 top[1] = j; 982 base = i; 983 } 984 else 985 { 986 top[0] = i; 987 top[1] = limit; 988 limit = j; 989 } 990 top += 2; 991 } 992 else 993 { 994 // the sub-array is small, perform insertion sort 995 j = base; 996 i = j + 1; 997 998 for(; i < limit; j = i, i++) 999 { 1000 for(; less(*(e1 = &(arr[j + 1])), *(e2 = &(arr[j]))); j--) 1001 { 1002 swap_elements(*e1, *e2); 1003 if(j == base) 1004 { 1005 break; 1006 } 1007 } 1008 } 1009 if(top > stack) 1010 { 1011 top -= 2; 1012 base = top[0]; 1013 limit = top[1]; 1014 } 1015 else 1016 { 1017 break; 1018 } 1019 } 1020 } 1021 } 1022 1023 1024 1025 1026 //------------------------------------------------------remove_duplicates 1027 // Remove duplicates from a sorted array. It doesn't cut the 1028 // tail of the array, it just returns the number of remaining elements. 1029 //----------------------------------------------------------------------- 1030 template<class Array, class Equal> 1031 unsigned remove_duplicates(Array& arr, Equal equal) 1032 { 1033 if(arr.size() < 2) return arr.size(); 1034 1035 unsigned i, j; 1036 for(i = 1, j = 1; i < arr.size(); i++) 1037 { 1038 typename Array::value_type& e = arr[i]; 1039 if(!equal(e, arr[i - 1])) 1040 { 1041 arr[j++] = e; 1042 } 1043 } 1044 return j; 1045 } 1046 1047 //--------------------------------------------------------invert_container 1048 template<class Array> void invert_container(Array& arr) 1049 { 1050 int i = 0; 1051 int j = arr.size() - 1; 1052 while(i < j) 1053 { 1054 swap_elements(arr[i++], arr[j--]); 1055 } 1056 } 1057 1058 //------------------------------------------------------binary_search_pos 1059 template<class Array, class Value, class Less> 1060 unsigned binary_search_pos(const Array& arr, const Value& val, Less less) 1061 { 1062 if(arr.size() == 0) return 0; 1063 1064 unsigned beg = 0; 1065 unsigned end = arr.size() - 1; 1066 1067 if(less(val, arr[0])) return 0; 1068 if(less(arr[end], val)) return end + 1; 1069 1070 while(end - beg > 1) 1071 { 1072 unsigned mid = (end + beg) >> 1; 1073 if(less(val, arr[mid])) end = mid; 1074 else beg = mid; 1075 } 1076 1077 //if(beg <= 0 && less(val, arr[0])) return 0; 1078 //if(end >= arr.size() - 1 && less(arr[end], val)) ++end; 1079 1080 return end; 1081 } 1082 1083 //----------------------------------------------------------range_adaptor 1084 template<class Array> class range_adaptor 1085 { 1086 public: 1087 typedef typename Array::value_type value_type; 1088 1089 range_adaptor(Array& array, unsigned start, unsigned size) : 1090 m_array(array), m_start(start), m_size(size) 1091 {} 1092 1093 unsigned size() const { return m_size; } 1094 const value_type& operator [] (unsigned i) const { return m_array[m_start + i]; } 1095 value_type& operator [] (unsigned i) { return m_array[m_start + i]; } 1096 const value_type& at(unsigned i) const { return m_array[m_start + i]; } 1097 value_type& at(unsigned i) { return m_array[m_start + i]; } 1098 value_type value_at(unsigned i) const { return m_array[m_start + i]; } 1099 1100 private: 1101 Array& m_array; 1102 unsigned m_start; 1103 unsigned m_size; 1104 }; 1105 1106 //---------------------------------------------------------------int_less 1107 inline bool int_less(int a, int b) { return a < b; } 1108 1109 //------------------------------------------------------------int_greater 1110 inline bool int_greater(int a, int b) { return a > b; } 1111 1112 //----------------------------------------------------------unsigned_less 1113 inline bool unsigned_less(unsigned a, unsigned b) { return a < b; } 1114 1115 //-------------------------------------------------------unsigned_greater 1116 inline bool unsigned_greater(unsigned a, unsigned b) { return a > b; } 1117} 1118 1119#endif 1120