git.cworth.org Git - vogl/blob - src/voglcore/vogl_vector.h

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 // File: vogl_vector.h
  28 #pragma once
  29
  30 #include "vogl_core.h"
  31
  32 namespace vogl
  33 {
  34     struct elemental_vector
  35     {
  36         void *m_p;
  37         uint m_size;
  38         uint m_capacity;
  39
  40         typedef void (*object_mover)(void *pDst, void *pSrc, uint num);
  41
  42         bool increase_capacity(uint min_new_capacity, bool grow_hint, uint element_size, object_mover pRelocate, bool nofail);
  43     };
  44
  45     template <typename T>
  46     class vector : public helpers::rel_ops<vector<T> >
  47     {
  48     public:
  49         typedef T *iterator;
  50         typedef const T *const_iterator;
  51         typedef T value_type;
  52         typedef T &reference;
  53         typedef const T &const_reference;
  54         typedef T *pointer;
  55         typedef const T *const_pointer;
  56
  57         inline vector()
  58             : m_p(NULL),
  59               m_size(0),
  60               m_capacity(0)
  61         {
  62         }
  63
  64         inline vector(uint n, const T &init)
  65             : m_p(NULL),
  66               m_size(0),
  67               m_capacity(0)
  68         {
  69             increase_capacity(n, false);
  70             helpers::construct_array(m_p, n, init);
  71             m_size = n;
  72         }
  73
  74         inline vector(const vector &other)
  75             : m_p(NULL),
  76               m_size(0),
  77               m_capacity(0)
  78         {
  79             increase_capacity(other.m_size, false);
  80
  81             m_size = other.m_size;
  82
  83             if (type_is_bitwise_copyable())
  84                 memcpy(reinterpret_cast<void *>(m_p), reinterpret_cast<const void *>(other.m_p), m_size * sizeof(T));
  85             else
  86             {
  87                 T *pDst = m_p;
  88                 const T *pSrc = other.m_p;
  89                 for (uint i = m_size; i > 0; i--)
  90                     helpers::construct(pDst++, *pSrc++);
  91             }
  92         }
  93
  94         inline explicit vector(uint size)
  95             : m_p(NULL),
  96               m_size(0),
  97               m_capacity(0)
  98         {
  99             resize(size);
 100         }
 101
 102         inline ~vector()
 103         {
 104             if (m_p)
 105             {
 106                 scalar_type<T>::destruct_array(m_p, m_size);
 107                 vogl_free(m_p);
 108             }
 109         }
 110
 111         inline vector &operator=(const vector &other)
 112         {
 113             if (this == &other)
 114                 return *this;
 115
 116             if (m_capacity >= other.m_size)
 117                 resize(0);
 118             else
 119             {
 120                 clear();
 121                 increase_capacity(other.m_size, false);
 122             }
 123
 124             if (type_is_bitwise_copyable())
 125                 memcpy(reinterpret_cast<void *>(m_p), reinterpret_cast<const void *>(other.m_p), other.m_size * sizeof(T));
 126             else
 127             {
 128                 T *pDst = m_p;
 129                 const T *pSrc = other.m_p;
 130                 for (uint i = other.m_size; i > 0; i--)
 131                     helpers::construct(pDst++, *pSrc++);
 132             }
 133
 134             m_size = other.m_size;
 135
 136             return *this;
 137         }
 138
 139         inline const T *begin() const
 140         {
 141             return m_p;
 142         }
 143         T *begin()
 144         {
 145             return m_p;
 146         }
 147
 148         inline const T *end() const
 149         {
 150             return m_p + m_size;
 151         }
 152         T *end()
 153         {
 154             return m_p + m_size;
 155         }
 156
 157         inline bool is_empty() const
 158         {
 159             return !m_size;
 160         }
 161         inline uint size() const
 162         {
 163             return m_size;
 164         }
 165         inline uint size_in_bytes() const
 166         {
 167             return m_size * sizeof(T);
 168         }
 169         inline uint capacity() const
 170         {
 171             return m_capacity;
 172         }
 173
 174         // operator[] will assert on out of range indices, but in final builds there is (and will never be) any range checking on this method.
 175         inline const T &operator[](uint i) const
 176         {
 177             VOGL_ASSERT(i < m_size);
 178             return m_p[i];
 179         }
 180         inline T &operator[](uint i)
 181         {
 182             VOGL_ASSERT(i < m_size);
 183             return m_p[i];
 184         }
 185
 186         // at() always includes range checking, even in final builds, unlike operator [].
 187         // The first element is returned if the index is out of range.
 188         inline const T &at(uint i) const
 189         {
 190             VOGL_ASSERT(i < m_size);
 191             return (i >= m_size) ? m_p[0] : m_p[i];
 192         }
 193         inline T &at(uint i)
 194         {
 195             VOGL_ASSERT(i < m_size);
 196             return (i >= m_size) ? m_p[0] : m_p[i];
 197         }
 198
 199         inline const T &front() const
 200         {
 201             VOGL_ASSERT(m_size);
 202             return m_p[0];
 203         }
 204         inline T &front()
 205         {
 206             VOGL_ASSERT(m_size);
 207             return m_p[0];
 208         }
 209
 210         inline const T &back() const
 211         {
 212             VOGL_ASSERT(m_size);
 213             return m_p[m_size - 1];
 214         }
 215         inline T &back()
 216         {
 217             VOGL_ASSERT(m_size);
 218             return m_p[m_size - 1];
 219         }
 220
 221         inline const T *get_ptr() const
 222         {
 223             return m_p;
 224         }
 225         inline T *get_ptr()
 226         {
 227             return m_p;
 228         }
 229
 230         inline const T *get_const_ptr() const
 231         {
 232             return m_p;
 233         }
 234
 235         // clear() sets the container to empty, then frees the allocated block.
 236         inline void clear()
 237         {
 238             if (m_p)
 239             {
 240                 scalar_type<T>::destruct_array(m_p, m_size);
 241                 vogl_free(m_p);
 242                 m_p = NULL;
 243                 m_size = 0;
 244                 m_capacity = 0;
 245             }
 246         }
 247
 248         inline void clear_no_destruction()
 249         {
 250             if (m_p)
 251             {
 252                 vogl_free(m_p);
 253                 m_p = NULL;
 254                 m_size = 0;
 255                 m_capacity = 0;
 256             }
 257         }
 258
 259         inline void reserve(uint new_capacity)
 260         {
 261             if (new_capacity > m_capacity)
 262                 increase_capacity(new_capacity, false);
 263             else if (new_capacity < m_capacity)
 264             {
 265                 // Must work around the lack of a "decrease_capacity()" method.
 266                 // This case is rare enough in practice that it's probably not worth implementing an optimized in-place resize.
 267                 vector tmp;
 268                 tmp.increase_capacity(math::maximum(m_size, new_capacity), false);
 269                 tmp = *this;
 270                 swap(tmp);
 271             }
 272         }
 273
 274         inline bool try_reserve(uint new_capacity)
 275         {
 276             return increase_capacity(new_capacity, true, true);
 277         }
 278
 279         // resize() will never shrink the array's capacity, only enlarge it.
 280         // resize(0) empties the container, but does not free the allocated block.
 281         // If grow_hint is true, the capacity will at least double on resizes (it will also double if you're only enlarging by 1 element, assuming you're push_back'ing).
 282         inline void resize(uint new_size, bool grow_hint = false)
 283         {
 284             if (m_size != new_size)
 285             {
 286                 if (new_size < m_size)
 287                     scalar_type<T>::destruct_array(m_p + new_size, m_size - new_size);
 288                 else
 289                 {
 290                     if (new_size > m_capacity)
 291                         increase_capacity(new_size, (new_size == (m_size + 1)) || grow_hint);
 292
 293                     scalar_type<T>::construct_array(m_p + m_size, new_size - m_size);
 294                 }
 295
 296                 m_size = new_size;
 297             }
 298         }
 299
 300         inline bool try_resize(uint new_size, bool grow_hint = false)
 301         {
 302             if (m_size != new_size)
 303             {
 304                 if (new_size < m_size)
 305                     scalar_type<T>::destruct_array(m_p + new_size, m_size - new_size);
 306                 else
 307                 {
 308                     if (new_size > m_capacity)
 309                     {
 310                         if (!increase_capacity(new_size, (new_size == (m_size + 1)) || grow_hint, true))
 311                             return false;
 312                     }
 313
 314                     scalar_type<T>::construct_array(m_p + m_size, new_size - m_size);
 315                 }
 316
 317                 m_size = new_size;
 318             }
 319
 320             return true;
 321         }
 322
 323         // Ensures array is large enough for element at index to be accessed.
 324         inline void ensure_element_is_valid(uint index)
 325         {
 326             if (index >= m_size)
 327                 resize(index + 1, true);
 328         }
 329
 330         // If size >= capacity/2, reset() sets the container's size to 0 but doesn't free the allocated block (because the container may be similarly loaded in the future).
 331         // Otherwise it blows away the allocated block. See http://www.codercorner.com/blog/?p=494
 332         inline void reset()
 333         {
 334             if (m_size >= (m_capacity >> 1))
 335                 resize(0);
 336             else
 337                 clear();
 338         }
 339
 340         inline T *enlarge(uint i)
 341         {
 342             uint cur_size = m_size;
 343             resize(cur_size + i, true);
 344             return get_ptr() + cur_size;
 345         }
 346
 347         inline T *try_enlarge(uint i)
 348         {
 349             uint cur_size = m_size;
 350             if (!try_resize(cur_size + i, true))
 351                 return NULL;
 352             return get_ptr() + cur_size;
 353         }
 354
 355         inline void push_back(const T &obj)
 356         {
 357             VOGL_ASSERT(!m_p || (&obj < m_p) || (&obj >= (m_p + m_size)));
 358
 359             if (m_size >= m_capacity)
 360                 increase_capacity(m_size + 1, true);
 361
 362             scalar_type<T>::construct(m_p + m_size, obj);
 363             m_size++;
 364         }
 365
 366         inline bool try_push_back(const T &obj)
 367         {
 368             VOGL_ASSERT(!m_p || (&obj < m_p) || (&obj >= (m_p + m_size)));
 369
 370             if (m_size >= m_capacity)
 371             {
 372                 if (!increase_capacity(m_size + 1, true, true))
 373                     return false;
 374             }
 375
 376             scalar_type<T>::construct(m_p + m_size, obj);
 377             m_size++;
 378
 379             return true;
 380         }
 381
 382         inline void push_back_value(T obj)
 383         {
 384             if (m_size >= m_capacity)
 385                 increase_capacity(m_size + 1, true);
 386
 387             scalar_type<T>::construct(m_p + m_size, obj);
 388             m_size++;
 389         }
 390
 391         inline void pop_back()
 392         {
 393             VOGL_ASSERT(m_size);
 394
 395             if (m_size)
 396             {
 397                 m_size--;
 398                 scalar_type<T>::destruct(&m_p[m_size]);
 399             }
 400         }
 401
 402         inline void insert(uint index, const T *p, uint n)
 403         {
 404             VOGL_ASSERT(index <= m_size);
 405             if (!n)
 406                 return;
 407
 408             const uint orig_size = m_size;
 409             resize(m_size + n, true);
 410
 411             const uint num_to_move = orig_size - index;
 412
 413             if (type_is_bitwise_copyable())
 414             {
 415                 // This overwrites the destination object bits, but bitwise copyable means we don't need to worry about destruction.
 416                 memmove(reinterpret_cast<void *>(m_p + index + n), reinterpret_cast<const void *>(m_p + index), sizeof(T) * num_to_move);
 417             }
 418             else
 419             {
 420                 const T *pSrc = m_p + orig_size - 1;
 421                 T *pDst = const_cast<T *>(pSrc) + n;
 422
 423                 for (uint i = 0; i < num_to_move; i++)
 424                 {
 425                     VOGL_ASSERT((pDst - m_p) < (int)m_size);
 426                     *pDst-- = *pSrc--;
 427                 }
 428             }
 429
 430             T *pDst = m_p + index;
 431
 432             if (type_is_bitwise_copyable())
 433             {
 434                 // This copies in the new bits, overwriting the existing objects, which is OK for copyable types that don't need destruction.
 435                 memcpy(reinterpret_cast<void *>(pDst), reinterpret_cast<const void *>(p), sizeof(T) * n);
 436             }
 437             else
 438             {
 439                 for (uint i = 0; i < n; i++)
 440                 {
 441                     VOGL_ASSERT((pDst - m_p) < (int)m_size);
 442                     *pDst++ = *p++;
 443                 }
 444             }
 445         }
 446
 447         inline void insert(uint index, const T &obj)
 448         {
 449             VOGL_ASSERT(!m_p || (&obj < m_p) || (&obj >= (m_p + m_size)));
 450             insert(index, &obj, 1);
 451         }
 452
 453         // push_front() isn't going to be very fast - it's only here for usability.
 454         inline void push_front(const T &obj)
 455         {
 456             insert(0, &obj, 1);
 457         }
 458
 459         vector &append(const vector &other)
 460         {
 461             VOGL_ASSERT(this != &other);
 462             if (other.m_size)
 463                 insert(m_size, &other[0], other.m_size);
 464             return *this;
 465         }
 466
 467         vector &append(const T *p, uint n)
 468         {
 469             if (n)
 470                 insert(m_size, p, n);
 471             return *this;
 472         }
 473
 474         inline void erase(uint start, uint n)
 475         {
 476             VOGL_ASSERT((start + n) <= m_size);
 477             if ((start + n) > m_size)
 478                 return;
 479
 480             if (!n)
 481                 return;
 482
 483             const uint num_to_move = m_size - (start + n);
 484
 485             T *pDst = m_p + start;
 486
 487             const T *pSrc = m_p + start + n;
 488
 489             if (type_is_bitwise_copyable_or_movable())
 490             {
 491                 // This test is overly cautious.
 492                 if ((!type_is_bitwise_copyable()) || type_has_destructor())
 493                 {
 494                     // Type has been marked explictly as bitwise movable, which means we can move them around but they may need to be destructed.
 495                     // First destroy the erased objects.
 496                     scalar_type<T>::destruct_array(pDst, n);
 497                 }
 498
 499                 // Copy "down" the objects to preserve, filling in the empty slots.
 500                 memmove(pDst, pSrc, num_to_move * sizeof(T));
 501             }
 502             else
 503             {
 504                 // Type is not bitwise copyable or movable.
 505                 // Move them down one at a time by using the equals operator, and destroying anything that's left over at the end.
 506                 T *pDst_end = pDst + num_to_move;
 507                 while (pDst != pDst_end)
 508                     *pDst++ = *pSrc++;
 509
 510                 scalar_type<T>::destruct_array(pDst_end, n);
 511             }
 512
 513             m_size -= n;
 514         }
 515
 516         inline void erase(uint index)
 517         {
 518             erase(index, 1);
 519         }
 520
 521         inline void erase(T *p)
 522         {
 523             VOGL_ASSERT((p >= m_p) && (p < (m_p + m_size)));
 524             erase(static_cast<uint>(p - m_p));
 525         }
 526
 527         void erase_unordered(uint index)
 528         {
 529             VOGL_ASSERT(index < m_size);
 530
 531             if ((index + 1) < m_size)
 532                 (*this)[index] = back();
 533
 534             pop_back();
 535         }
 536
 537         inline bool operator==(const vector &rhs) const
 538         {
 539             if (this == &rhs)
 540                 return true;
 541
 542             if (m_size != rhs.m_size)
 543                 return false;
 544             else if (m_size)
 545             {
 546                 if (scalar_type<T>::cFlag)
 547                     return memcmp(m_p, rhs.m_p, sizeof(T) * m_size) == 0;
 548                 else
 549                 {
 550                     const T *pSrc = m_p;
 551                     const T *pDst = rhs.m_p;
 552                     for (uint i = m_size; i; i--)
 553                         if (!(*pSrc++ == *pDst++))
 554                             return false;
 555                 }
 556             }
 557
 558             return true;
 559         }
 560
 561         // lexicographical order
 562         inline bool operator<(const vector &rhs) const
 563         {
 564             const uint min_size = math::minimum(m_size, rhs.m_size);
 565
 566             const T *pSrc = m_p;
 567             const T *pSrc_end = m_p + min_size;
 568             const T *pDst = rhs.m_p;
 569
 570             while ((pSrc < pSrc_end) && (*pSrc == *pDst))
 571             {
 572                 pSrc++;
 573                 pDst++;
 574             }
 575
 576             if (pSrc < pSrc_end)
 577                 return *pSrc < *pDst;
 578
 579             return m_size < rhs.m_size;
 580         }
 581
 582         inline void swap(vector &other)
 583         {
 584             utils::swap(m_p, other.m_p);
 585             utils::swap(m_size, other.m_size);
 586             utils::swap(m_capacity, other.m_capacity);
 587         }
 588
 589         inline void sort()
 590         {
 591             introsort(begin(), end());
 592         }
 593
 594         template <typename Comp>
 595         inline void sort(Comp compare_obj)
 596         {
 597             introsort(begin(), end(), compare_obj);
 598         }
 599
 600         inline bool is_sorted() const
 601         {
 602             for (uint i = 1; i < m_size; ++i)
 603                 if (m_p[i] < m_p[i - 1])
 604                     return false;
 605             return true;
 606         }
 607
 608         inline void unique()
 609         {
 610             if (!is_empty())
 611             {
 612                 sort();
 613
 614                 resize(static_cast<uint>(std::unique(begin(), end()) - begin()));
 615             }
 616         }
 617
 618         template <typename EqComp>
 619         inline void unique(EqComp comp)
 620         {
 621             if (!is_empty())
 622             {
 623                 sort();
 624
 625                 resize(static_cast<uint>(std::unique(begin(), end(), comp) - begin()));
 626             }
 627         }
 628
 629         inline void reverse()
 630         {
 631             uint j = m_size >> 1;
 632             for (uint i = 0; i < j; i++)
 633                 utils::swap(m_p[i], m_p[m_size - 1 - i]);
 634         }
 635
 636         inline int find(const T &key) const
 637         {
 638             VOGL_ASSERT(m_size <= static_cast<uint>(cINT32_MAX));
 639
 640             const T *p = m_p;
 641             const T *p_end = m_p + m_size;
 642
 643             uint index = 0;
 644
 645             while (p != p_end)
 646             {
 647                 if (key == *p)
 648                     return index;
 649
 650                 p++;
 651                 index++;
 652             }
 653
 654             return cInvalidIndex;
 655         }
 656
 657         template <typename Q>
 658         inline int find(const T &key, Q equal_to) const
 659         {
 660             VOGL_ASSERT(m_size <= static_cast<uint>(cINT32_MAX));
 661
 662             const T *p = m_p;
 663             const T *p_end = m_p + m_size;
 664
 665             uint index = 0;
 666
 667             while (p != p_end)
 668             {
 669                 if (equal_to(key, *p))
 670                     return index;
 671
 672                 p++;
 673                 index++;
 674             }
 675
 676             return cInvalidIndex;
 677         }
 678
 679         inline int find_last(const T &key) const
 680         {
 681             VOGL_ASSERT(m_size <= static_cast<uint>(cINT32_MAX));
 682
 683             for (int i = m_size - 1; i >= 0; --i)
 684                 if (m_p[i] == key)
 685                     return i;
 686
 687             return cInvalidIndex;
 688         }
 689
 690         template <typename Q>
 691         inline int find_last(const T &key, Q equal_to) const
 692         {
 693             VOGL_ASSERT(m_size <= static_cast<uint>(cINT32_MAX));
 694
 695             for (int i = m_size - 1; i >= 0; --i)
 696                 if (equal_to(m_p[i], key))
 697                     return i;
 698
 699             return cInvalidIndex;
 700         }
 701
 702         inline int find_sorted(const T &key) const
 703         {
 704             VOGL_ASSERT(m_size <= static_cast<uint>(cINT32_MAX));
 705
 706             if (m_size)
 707             {
 708                 // Uniform binary search - Knuth Algorithm 6.2.1 U, unrolled twice.
 709                 // TODO: OK, is this worth it vs the usual algorithm?
 710                 int i = ((m_size + 1) >> 1) - 1;
 711                 int m = m_size;
 712
 713                 for (;;)
 714                 {
 715                     VOGL_ASSERT_OPEN_RANGE(i, 0, (int)m_size);
 716                     const T *pKey_i = m_p + i;
 717                     int cmp = key < *pKey_i;
 718 #ifdef VOGL_BUILD_DEBUG
 719                     int cmp2 = *pKey_i < key;
 720                     VOGL_ASSERT((cmp != cmp2) || (key == *pKey_i));
 721 #endif
 722                     if ((!cmp) && (key == *pKey_i))
 723                         return i;
 724                     m >>= 1;
 725                     if (!m)
 726                         break;
 727                     cmp = -cmp;
 728                     i += (((m + 1) >> 1) ^ cmp) - cmp;
 729                     if (i < 0)
 730                         break;
 731
 732                     VOGL_ASSERT_OPEN_RANGE(i, 0, (int)m_size);
 733                     pKey_i = m_p + i;
 734                     cmp = key < *pKey_i;
 735 #ifdef VOGL_BUILD_DEBUG
 736                     cmp2 = *pKey_i < key;
 737                     VOGL_ASSERT((cmp != cmp2) || (key == *pKey_i));
 738 #endif
 739                     if ((!cmp) && (key == *pKey_i))
 740                         return i;
 741                     m >>= 1;
 742                     if (!m)
 743                         break;
 744                     cmp = -cmp;
 745                     i += (((m + 1) >> 1) ^ cmp) - cmp;
 746                     if (i < 0)
 747                         break;
 748                 }
 749             }
 750
 751             return cInvalidIndex;
 752         }
 753
 754         template <typename Q>
 755         inline int find_sorted(const T &key, Q less_than) const
 756         {
 757             if (m_size)
 758             {
 759                 // Uniform binary search - Knuth Algorithm 6.2.1 U, unrolled twice.
 760                 // TODO: OK, is this worth it vs the usual algorithm?
 761                 int i = ((m_size + 1) >> 1) - 1;
 762                 int m = m_size;
 763
 764                 for (;;)
 765                 {
 766                     VOGL_ASSERT_OPEN_RANGE(i, 0, (int)m_size);
 767                     const T *pKey_i = m_p + i;
 768                     int cmp = less_than(key, *pKey_i);
 769 #ifdef VOGL_BUILD_DEBUG
 770                     int cmp2 = less_than(*pKey_i, key);
 771                     VOGL_ASSERT((cmp != cmp2) || (key == *pKey_i));
 772 #endif
 773                     if ((!cmp) && (!less_than(*pKey_i, key)))
 774                         return i;
 775                     m >>= 1;
 776                     if (!m)
 777                         break;
 778                     cmp = -cmp;
 779                     i += (((m + 1) >> 1) ^ cmp) - cmp;
 780                     if (i < 0)
 781                         break;
 782
 783                     VOGL_ASSERT_OPEN_RANGE(i, 0, (int)m_size);
 784                     pKey_i = m_p + i;
 785                     cmp = less_than(key, *pKey_i);
 786 #ifdef VOGL_BUILD_DEBUG
 787                     cmp2 = less_than(*pKey_i, key);
 788                     VOGL_ASSERT((cmp != cmp2) || (key == *pKey_i));
 789 #endif
 790                     if ((!cmp) && (!less_than(*pKey_i, key)))
 791                         return i;
 792                     m >>= 1;
 793                     if (!m)
 794                         break;
 795                     cmp = -cmp;
 796                     i += (((m + 1) >> 1) ^ cmp) - cmp;
 797                     if (i < 0)
 798                         break;
 799                 }
 800             }
 801
 802             return cInvalidIndex;
 803         }
 804
 805         inline uint count_occurences(const T &key) const
 806         {
 807             uint c = 0;
 808
 809             const T *p = m_p;
 810             const T *p_end = m_p + m_size;
 811
 812             while (p != p_end)
 813             {
 814                 if (key == *p)
 815                     c++;
 816
 817                 p++;
 818             }
 819
 820             return c;
 821         }
 822
 823         inline void set_all(const T &o)
 824         {
 825             if ((sizeof(T) == 1) && (scalar_type<T>::cFlag))
 826                 memset(m_p, *reinterpret_cast<const uint8 *>(&o), m_size);
 827             else
 828             {
 829                 T *pDst = m_p;
 830                 T *pDst_end = pDst + m_size;
 831                 while (pDst != pDst_end)
 832                     *pDst++ = o;
 833             }
 834         }
 835
 836         // Caller assumes ownership of the heap block associated with the container. Container is cleared.
 837         inline void *assume_ownership()
 838         {
 839             T *p = m_p;
 840             m_p = NULL;
 841             m_size = 0;
 842             m_capacity = 0;
 843             return p;
 844         }
 845
 846         // Caller is granting ownership of the indicated heap block.
 847         // Block must have size constructed elements, and have enough room for capacity elements.
 848         inline bool grant_ownership(T *p, uint size, uint capacity)
 849         {
 850             // To to prevent the caller from obviously shooting themselves in the foot.
 851             if (((p + capacity) > m_p) && (p < (m_p + m_capacity)))
 852             {
 853                 // Can grant ownership of a block inside the container itself!
 854                 VOGL_ASSERT_ALWAYS;
 855                 return false;
 856             }
 857
 858             if (size > capacity)
 859             {
 860                 VOGL_ASSERT_ALWAYS;
 861                 return false;
 862             }
 863
 864             if (!p)
 865             {
 866                 if (capacity)
 867                 {
 868                     VOGL_ASSERT_ALWAYS;
 869                     return false;
 870                 }
 871             }
 872             else if (!capacity)
 873             {
 874                 VOGL_ASSERT_ALWAYS;
 875                 return false;
 876             }
 877
 878             clear();
 879             m_p = p;
 880             m_size = size;
 881             m_capacity = capacity;
 882             return true;
 883         }
 884
 885         // Fisher–Yates shuffle
 886         template <typename R>
 887         inline void shuffle(R &rm)
 888         {
 889             VOGL_ASSERT(m_size < static_cast<uint>(cINT32_MAX));
 890
 891             if ((m_size <= 1U) || (m_size >= static_cast<uint>(cINT32_MAX)))
 892                 return;
 893
 894             for (uint i = m_size - 1; i >= 1; --i)
 895             {
 896                 uint j = rm.irand_inclusive(0, i);
 897                 std::swap(m_p[j], m_p[i]);
 898             }
 899         }
 900
 901     private:
 902         T *m_p;
 903         uint m_size;
 904         uint m_capacity;
 905
 906         template <typename Q>
 907         struct is_vector
 908         {
 909             enum
 910             {
 911                 cFlag = false
 912             };
 913         };
 914         template <typename Q>
 915         struct is_vector<vector<Q> >
 916         {
 917             enum
 918             {
 919                 cFlag = true
 920             };
 921         };
 922
 923         static void object_mover(void *pDst_void, void *pSrc_void, uint num)
 924         {
 925             T *pSrc = static_cast<T *>(pSrc_void);
 926             T *const pSrc_end = pSrc + num;
 927             T *pDst = static_cast<T *>(pDst_void);
 928
 929             while (pSrc != pSrc_end)
 930             {
 931                 // placement new
 932                 new (static_cast<void *>(pDst)) T(*pSrc);
 933                 pSrc->~T();
 934                 ++pSrc;
 935                 ++pDst;
 936             }
 937         }
 938
 939         inline bool increase_capacity(uint min_new_capacity, bool grow_hint, bool nofail = false)
 940         {
 941             return reinterpret_cast<elemental_vector *>(this)->increase_capacity(
 942                 min_new_capacity, grow_hint, sizeof(T),
 943                 (type_is_bitwise_copyable_or_movable() || (is_vector<T>::cFlag)) ? NULL : object_mover, nofail);
 944         }
 945
 946         static inline bool type_is_bitwise_copyable()
 947         {
 948             return VOGL_IS_BITWISE_COPYABLE(T);
 949         }
 950
 951         static inline bool type_is_bitwise_copyable_or_movable()
 952         {
 953             return VOGL_IS_BITWISE_COPYABLE_OR_MOVABLE(T);
 954         }
 955
 956         static inline bool type_has_destructor()
 957         {
 958             return VOGL_HAS_DESTRUCTOR(T);
 959         }
 960     };
 961
 962     typedef vogl::vector<uint8> uint8_vec;
 963     typedef vogl::vector<char> char_vec;
 964     typedef vogl::vector<int> int_vec;
 965     typedef vogl::vector<uint> uint_vec;
 966     typedef vogl::vector<int32> int32_vec;
 967     typedef vogl::vector<uint32> uint32_vec;
 968     typedef vogl::vector<int64_t> int64_vec;
 969     typedef vogl::vector<uint64_t> uint64_vec;
 970     typedef vogl::vector<float> float_vec;
 971     typedef vogl::vector<double> double_vec;
 972     typedef vogl::vector<void *> void_ptr_vec;
 973     typedef vogl::vector<const void *> const_void_ptr_vec;
 974
 975     template <typename T>
 976     struct bitwise_movable<vector<T> >
 977     {
 978         enum
 979         {
 980             cFlag = true
 981         };
 982     };
 983
 984     template <typename T>
 985     inline void swap(vector<T> &a, vector<T> &b)
 986     {
 987         a.swap(b);
 988     }
 989
 990 #if 0
 991 inline void vector_test()
 992 {
 993         vogl::random r;
 994         for (uint i = 0; i < 100000; i++)
 995         {
 996                 uint n = r.irand(0, 1000);
 997                 vogl::vector<int> xx(n);
 998
 999                 for (int i = 0; i < n; i++)
1000                         xx[i] = i * 2;
1001                 VOGL_VERIFY(xx.find_sorted(-1) < 0);
1002                 for (uint i = 0; i < n; i++)
1003                 {
1004                         VOGL_VERIFY(xx.find_sorted(2 * i) == i);
1005                         VOGL_VERIFY(xx.find_sorted(2 * i + 1) < 0);
1006                 }
1007                 VOGL_VERIFY(xx.find_sorted(n * 2) < 0);
1008                 VOGL_VERIFY(xx.find_sorted(99999) < 0);
1009         }
1010 }
1011 #endif
1012
1013 } // namespace vogl
1014
1015 namespace std
1016 {
1017     template <typename T>
1018     inline void swap(vogl::vector<T> &a, vogl::vector<T> &b)
1019     {
1020         a.swap(b);
1021     }
1022 }