git.cworth.org Git - vogl/blob - src/voglcore/vogl_sparse_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_sparse_vector.h
  28 #pragma once
  29
  30 #include "vogl_core.h"
  31 #include "vogl_rand.h"
  32 #include "vogl_strutils.h"
  33 #include <vector>
  34
  35 namespace vogl
  36 {
  37     template <typename T, uint Log2N>
  38     class sparse_vector_traits
  39     {
  40     public:
  41         static inline void *alloc_space(uint size)
  42         {
  43             return vogl_malloc(size);
  44         }
  45
  46         static inline void free_space(void *p)
  47         {
  48             vogl_free(p);
  49         }
  50
  51         static inline void construct_group(T *p)
  52         {
  53             scalar_type<T>::construct_array(p, 1U << Log2N);
  54         }
  55
  56         static inline void destruct_group(T *p)
  57         {
  58             scalar_type<T>::destruct_array(p, 1U << Log2N);
  59         }
  60
  61         static inline void construct_element(T *p)
  62         {
  63             scalar_type<T>::construct(p);
  64         }
  65
  66         static inline void destruct_element(T *p)
  67         {
  68             scalar_type<T>::destruct(p);
  69         }
  70
  71         static inline void copy_group(T *pDst, const T *pSrc)
  72         {
  73             for (uint j = 0; j < (1U << Log2N); j++)
  74                 pDst[j] = pSrc[j];
  75         }
  76     };
  77
  78     template <typename T, uint Log2N, template <typename, uint> class Traits = sparse_vector_traits>
  79     class sparse_vector : public Traits<T, Log2N>
  80     {
  81     public:
  82         typedef Traits<T, Log2N> base;
  83
  84         enum
  85         {
  86             N = 1U << Log2N
  87         };
  88         typedef vogl::vector<T *> group_ptr_vec;
  89
  90         inline sparse_vector()
  91             : m_size(0), m_num_active_groups(0)
  92         {
  93             init_default();
  94         }
  95
  96         inline sparse_vector(uint size)
  97             : m_size(0), m_num_active_groups(0)
  98         {
  99             init_default();
 100
 101             resize(size);
 102         }
 103
 104         inline sparse_vector(const sparse_vector &other)
 105             : m_size(0), m_num_active_groups(0)
 106         {
 107             init_default();
 108
 109             *this = other;
 110         }
 111
 112         template <uint OtherLogN, template <typename, uint> class OtherTraits>
 113         inline sparse_vector(const sparse_vector<T, OtherLogN, OtherTraits> &other)
 114             : m_size(0), m_num_active_groups(0)
 115         {
 116             init_default();
 117
 118             default_element() = other.default_element();
 119
 120             *this = other;
 121         }
 122
 123         inline sparse_vector(const vogl::vector<T> &other)
 124             : m_size(0), m_num_active_groups(0)
 125         {
 126             init_default();
 127
 128             *this = other;
 129         }
 130
 131         inline ~sparse_vector()
 132         {
 133             for (uint i = 0; (i < m_groups.size()) && m_num_active_groups; i++)
 134                 free_group(m_groups[i]);
 135
 136             deinit_default();
 137         }
 138
 139         // Get/set the default object returned by operator [] on non-present elements.
 140         inline const T &default_element() const
 141         {
 142             return *reinterpret_cast<const T *>(m_default);
 143         }
 144         inline T &default_element()
 145         {
 146             return *reinterpret_cast<T *>(m_default);
 147         }
 148
 149         inline bool assign(const sparse_vector &other)
 150         {
 151             if (this == &other)
 152                 return true;
 153
 154             if (!try_resize(other.size()))
 155                 return false;
 156
 157             for (uint i = 0; i < other.m_groups.size(); i++)
 158             {
 159                 const T *p = other.m_groups[i];
 160
 161                 T *q = m_groups[i];
 162
 163                 if (p)
 164                 {
 165                     if (!q)
 166                     {
 167                         q = alloc_group(true);
 168                         if (!q)
 169                             return false;
 170
 171                         m_groups[i] = q;
 172                     }
 173
 174                     base::copy_group(q, p);
 175                 }
 176                 else if (q)
 177                 {
 178                     free_group(q);
 179                     m_groups[i] = NULL;
 180                 }
 181             }
 182
 183             return true;
 184         }
 185
 186         sparse_vector &operator=(const sparse_vector &other)
 187         {
 188             if (!assign(other))
 189             {
 190                 VOGL_FAIL("Out of memory");
 191             }
 192
 193             return *this;
 194         }
 195
 196         template <uint OtherLogN, template <typename, uint> class OtherTraits>
 197         inline bool assign(const sparse_vector<T, OtherLogN, OtherTraits> &other)
 198         {
 199             if ((void *)this == (void *)&other)
 200                 return true;
 201
 202             if (!try_resize(other.size()))
 203                 return true;
 204
 205             for (uint i = 0; i < other.size(); ++i)
 206                 if (other.is_present(i))
 207                     set(i, *other.get_ptr(i));
 208
 209             return true;
 210         }
 211
 212         template <uint OtherLogN, template <typename, uint> class OtherTraits>
 213         inline sparse_vector &operator=(const sparse_vector<T, OtherLogN, OtherTraits> &other)
 214         {
 215             if (!assign(other))
 216             {
 217                 VOGL_FAIL("Out of memory");
 218             }
 219
 220             return *this;
 221         }
 222
 223         inline bool assign(const vogl::vector<T> &other, bool default_element_check)
 224         {
 225             if (!try_resize(other.size()))
 226                 return true;
 227
 228             if (default_element_check)
 229             {
 230                 allocate_all_groups();
 231
 232                 const T *pSrc = other.get_ptr();
 233                 const uint n = other.size();
 234                 for (uint i = 0; i < n; ++i)
 235                     m_groups[i >> Log2N][i & (N - 1)] = *pSrc++;
 236             }
 237             else
 238             {
 239                 for (uint i = 0; i < other.size(); ++i)
 240                     if (other[i] != default_element())
 241                         set(i, other[i]);
 242             }
 243
 244             return true;
 245         }
 246
 247         inline bool operator=(const vogl::vector<T> &other)
 248         {
 249             if (!assign(other, true))
 250             {
 251                 VOGL_FAIL("Out of memory");
 252             }
 253             return true;
 254         }
 255
 256         bool operator==(const sparse_vector &other) const
 257         {
 258             if (this == &other)
 259                 return true;
 260
 261             if (m_size != other.m_size)
 262                 return false;
 263
 264             for (uint i = 0; i < m_size; i++)
 265                 if (!((*this)[i] == other[i]))
 266                     return false;
 267
 268             return true;
 269         }
 270
 271         bool operator!=(const sparse_vector &other) const
 272         {
 273             return !(*this == other);
 274         }
 275
 276         bool operator<(const sparse_vector &rhs) const
 277         {
 278             const uint min_size = math::minimum(m_size, rhs.m_size);
 279
 280             uint i;
 281             for (i = 0; i < min_size; i++)
 282                 if (!((*this)[i] == rhs[i]))
 283                     break;
 284
 285             if (i < min_size)
 286                 return (*this)[i] < rhs[i];
 287
 288             return m_size < rhs.m_size;
 289         }
 290
 291         void clear()
 292         {
 293             if (m_groups.size())
 294             {
 295                 for (uint i = 0; (i < m_groups.size()) && m_num_active_groups; i++)
 296                     free_group(m_groups[i]);
 297
 298                 m_groups.clear();
 299             }
 300
 301             m_size = 0;
 302
 303             VOGL_ASSERT(!m_num_active_groups);
 304         }
 305
 306         bool get_vector(vogl::vector<T> &dst) const
 307         {
 308             if (!dst.try_resize(size()))
 309                 return false;
 310
 311             const T *const *ppGroups = m_groups.get_ptr();
 312             const uint num_groups = m_groups.size();
 313             for (uint group_iter = 0; group_iter < num_groups; ++group_iter)
 314             {
 315                 const T *pGroup = ppGroups[group_iter];
 316                 if (!pGroup)
 317                     continue;
 318
 319                 const uint n = get_num_valid_elements_in_group(group_iter);
 320                 T *pDst = &dst[group_iter << Log2N];
 321
 322                 for (uint i = 0; i < n; ++i)
 323                     *pDst++ = *pGroup++;
 324             }
 325
 326             return true;
 327         }
 328
 329         bool try_resize(uint new_size)
 330         {
 331             if (m_size == new_size)
 332                 return true;
 333
 334             uint new_last_group_index = 0;
 335             uint prev_num_valid_elements_in_new_last_group = 0;
 336             bool shrinking = ((new_size) && (new_size < m_size));
 337             if (shrinking)
 338             {
 339                 new_last_group_index = (new_size - 1) >> Log2N;
 340                 prev_num_valid_elements_in_new_last_group = get_num_valid_elements_in_group(new_last_group_index);
 341                 VOGL_ASSERT(prev_num_valid_elements_in_new_last_group);
 342             }
 343
 344             const uint new_num_groups = (new_size + N - 1) >> Log2N;
 345             if (new_num_groups != m_groups.size())
 346             {
 347                 for (uint i = new_num_groups; i < m_groups.size(); i++)
 348                     free_group(m_groups[i]);
 349
 350                 if (!m_groups.try_resize(new_num_groups))
 351                     return false;
 352             }
 353
 354             m_size = new_size;
 355
 356             if (shrinking)
 357             {
 358                 T *pLast_group = m_groups[new_last_group_index];
 359                 if (pLast_group)
 360                 {
 361                     uint cur_num_valid_elements_in_new_last_group = get_num_valid_elements_in_group(new_last_group_index);
 362                     VOGL_ASSERT(cur_num_valid_elements_in_new_last_group);
 363
 364                     if (cur_num_valid_elements_in_new_last_group < prev_num_valid_elements_in_new_last_group)
 365                     {
 366                         for (uint i = cur_num_valid_elements_in_new_last_group; i < prev_num_valid_elements_in_new_last_group; i++)
 367                             pLast_group[i] = default_element();
 368                     }
 369                 }
 370             }
 371
 372             return true;
 373         }
 374
 375         void resize(uint size)
 376         {
 377             if (!try_resize(size))
 378             {
 379                 VOGL_FAIL("Out of memory");
 380             }
 381         }
 382
 383         inline uint size() const
 384         {
 385             return m_size;
 386         }
 387         inline bool is_empty() const
 388         {
 389             return 0 == m_size;
 390         }
 391
 392         inline uint capacity() const
 393         {
 394             return m_groups.size() << Log2N;
 395         }
 396         inline uint actual_capacity() const
 397         {
 398             return m_num_active_groups << Log2N;
 399         }
 400
 401         // Returns the default object if the element does not yet exist.
 402         // at() will not force elements to be allocated if they don't exist, preventing accidents.
 403         inline const T &at(uint i) const
 404         {
 405             VOGL_ASSERT(i < m_size);
 406             const T *p = m_groups[i >> Log2N];
 407             return p ? p[i & (N - 1)] : *reinterpret_cast<const T *>(m_default);
 408         }
 409
 410         // Returns the default object if the element does not yet exist.
 411         // operator [] is read only, i.e. will not force elements to be allocated if they don't exist, preventing accidents.
 412         inline const T &operator[](uint i) const
 413         {
 414             return at(i);
 415         }
 416
 417         class sparse_vector_object_accessor
 418         {
 419             sparse_vector &m_array;
 420             uint m_index;
 421
 422         public:
 423             inline sparse_vector_object_accessor(sparse_vector &array, uint index)
 424                 : m_array(array), m_index(index)
 425             {
 426             }
 427             inline sparse_vector_object_accessor(const sparse_vector_object_accessor &other)
 428                 : m_array(other.m_array), m_index(other.m_index)
 429             {
 430             }
 431
 432             // Returns const ref to element, or the default element if it's not allocated.
 433             inline operator const T &() const
 434             {
 435                 return m_array.get_element(m_index);
 436             }
 437
 438             // Taking the address always forces the element to be allocated.
 439             inline T *operator&() const
 440             {
 441                 T *p = m_array.get_ptr(m_index);
 442                 if (!p)
 443                     p = m_array.ensure_present(m_index);
 444                 return p;
 445             }
 446
 447             // Assigns element, forcing it to be allocated if it doesn't exist.
 448             inline T &operator=(const T &other) const
 449             {
 450                 T *p = m_array.get_ptr(m_index);
 451                 if (!p)
 452                     p = m_array.ensure_present(m_index);
 453                 *p = other;
 454                 return *p;
 455             }
 456         };
 457
 458         // Yes this is ugly, but it works around the fact that we can't overload operator "." in C++.
 459         // So operator[] and at() are read-only (and never force elements to be allocated, preventing silly accidents), and operator () is read/write (it will write on operator =).
 460         // I'm torn about this guy, it's probably too confusing vs. just calling get_or_create_element(), get_ptr(), etc.
 461         inline const sparse_vector_object_accessor operator()(uint i)
 462         {
 463             VOGL_ASSERT(i < m_size);
 464             return sparse_vector_object_accessor(*this, i);
 465         }
 466
 467         //      Returns a ref to the element (allocating it if necessary).
 468         inline T &get_or_create_element(uint i)
 469         {
 470             VOGL_ASSERT(i < m_size);
 471
 472             T *p = m_groups[i >> Log2N];
 473             if (!p)
 474                 return *ensure_present(i);
 475
 476             return p[i & (N - 1)];
 477         }
 478
 479         // Returns NULL if element does not yet exist.
 480         inline const T *get_ptr(uint i) const
 481         {
 482             VOGL_ASSERT(i < m_size);
 483             const T *p = m_groups[i >> Log2N];
 484             return p ? &p[i & (N - 1)] : NULL;
 485         }
 486
 487         // Returns NULL if element does not yet exist.
 488         inline T *get_ptr(uint i)
 489         {
 490             VOGL_ASSERT(i < m_size);
 491             T *p = m_groups[i >> Log2N];
 492             return p ? &p[i & (N - 1)] : NULL;
 493         }
 494
 495         // Returns true if the element exists.
 496         inline bool is_present(uint i) const
 497         {
 498             VOGL_ASSERT(i < m_size);
 499             return m_groups[i >> Log2N] != NULL;
 500         }
 501
 502         // Ensures element is allocated/present (enlarging the entire array if needed).
 503         inline T *ensure_present(uint index)
 504         {
 505             const uint group_index = index >> Log2N;
 506             if (group_index >= m_groups.size())
 507             {
 508                 if (!try_resize(index + 1))
 509                     return NULL;
 510             }
 511
 512             T *p = m_groups[group_index];
 513             if (!p)
 514             {
 515                 p = alloc_group(true);
 516                 if (!p)
 517                     return NULL;
 518
 519                 m_groups[group_index] = p;
 520             }
 521
 522             m_size = math::maximum(index + 1, m_size);
 523
 524             return p + (index & (N - 1));
 525         }
 526
 527         inline bool set(uint index, const T &obj)
 528         {
 529             T *p = ensure_present(index);
 530             if (!p)
 531                 return false;
 532
 533             *p = obj;
 534
 535             return true;
 536         }
 537
 538         inline void push_back(const T &obj)
 539         {
 540             if (!set(m_size, obj))
 541             {
 542                 VOGL_FAIL("Out of memory");
 543             }
 544         }
 545
 546         inline bool try_push_back(const T &obj)
 547         {
 548             return set(m_size, obj);
 549         }
 550
 551         inline T *enlarge(uint n)
 552         {
 553             uint orig_size = m_size;
 554             for (uint i = 0; i < n; i++)
 555             {
 556                 if (!ensure_present(m_size))
 557                 {
 558                     VOGL_FAIL("Out of memory");
 559                 }
 560             }
 561             return get_ptr(orig_size);
 562         }
 563
 564         inline void pop_back()
 565         {
 566             VOGL_ASSERT(m_size);
 567             if (m_size)
 568                 resize(m_size - 1);
 569         }
 570
 571         // Sets range [start, start + num) to the default object, freeing any groups that it can
 572         inline void invalidate_range(uint start, uint num)
 573         {
 574             if (!num)
 575                 return;
 576
 577             if ((start + num) > m_size)
 578             {
 579                 VOGL_ASSERT_ALWAYS;
 580                 return;
 581             }
 582
 583             const uint num_to_skip = math::minimum(math::get_align_up_value_delta(start, N), num);
 584
 585             for (uint i = 0; i < num_to_skip; i++)
 586             {
 587                 if (is_present(start + i))
 588                     set(start + i, default_element());
 589             }
 590
 591             start += num_to_skip;
 592             num -= num_to_skip;
 593
 594             const uint first_group_to_free = start >> Log2N;
 595             const uint num_groups_to_free = num >> Log2N;
 596
 597             free_groups(first_group_to_free, num_groups_to_free);
 598
 599             const uint total_elements_freed = num_groups_to_free << Log2N;
 600             start += total_elements_freed;
 601             num -= total_elements_freed;
 602
 603             for (uint i = 0; i < num; i++)
 604             {
 605                 if (is_present(start + i))
 606                     set(start + i, default_element());
 607             }
 608         }
 609
 610         inline void invalidate_all()
 611         {
 612             for (uint i = 0; i < m_groups.size(); i++)
 613             {
 614                 T *p = m_groups[i];
 615                 if (p)
 616                 {
 617                     free_group(p);
 618                     m_groups[i] = NULL;
 619                 }
 620             }
 621         }
 622
 623         inline void swap(sparse_vector &other)
 624         {
 625             utils::swap(m_size, other.m_size);
 626             m_groups.swap(other.m_groups);
 627             utils::swap(m_num_active_groups, other.m_num_active_groups);
 628         }
 629
 630         inline bool set_all(const T &val)
 631         {
 632             if (is_empty())
 633                 return true;
 634
 635             const bool is_default = (val == default_element());
 636
 637             for (uint group_iter = 0; group_iter < m_groups.size(); ++group_iter)
 638             {
 639                 const T *pGroup = m_groups[group_iter];
 640                 if (!pGroup)
 641                 {
 642                     if (is_default)
 643                         continue;
 644
 645                     pGroup = alloc_group(true);
 646                     if (!pGroup)
 647                         return false;
 648
 649                     m_groups[group_iter] = pGroup;
 650                 }
 651
 652                 const uint n = get_num_valid_elements_in_group(group_iter);
 653                 for (uint i = 0; i < n; i++)
 654                     pGroup[i] = val;
 655             }
 656
 657             return true;
 658         }
 659
 660         inline int find(const T &key) const
 661         {
 662             if (is_empty())
 663                 return cInvalidIndex;
 664
 665             const bool is_default = (key == default_element());
 666
 667             for (uint group_iter = 0; group_iter < m_groups.size(); ++group_iter)
 668             {
 669                 const T *pGroup = m_groups[group_iter];
 670                 if (!pGroup)
 671                 {
 672                     if (is_default)
 673                         return group_iter << Log2N;
 674                     continue;
 675                 }
 676
 677                 const uint n = get_num_valid_elements_in_group(group_iter);
 678                 for (uint i = 0; i < n; i++)
 679                     if (pGroup[i] == key)
 680                         return (group_iter << Log2N) + i;
 681             }
 682
 683             return cInvalidIndex;
 684         }
 685
 686         inline uint allocate_all_groups()
 687         {
 688             if (m_num_active_groups == m_groups.size())
 689                 return 0;
 690
 691             uint num_groups_allocated = 0;
 692
 693             for (uint group_iter = 0; group_iter < m_groups.size(); ++group_iter)
 694             {
 695                 T *pGroup = m_groups[group_iter];
 696                 if (pGroup)
 697                     continue;
 698
 699                 m_groups[group_iter] = alloc_group();
 700                 num_groups_allocated++;
 701             }
 702
 703             return num_groups_allocated;
 704         }
 705
 706         inline uint optimize_groups()
 707         {
 708             if (!m_num_active_groups)
 709                 return 0;
 710
 711             uint num_groups_freed = 0;
 712
 713             for (uint group_iter = 0; group_iter < m_groups.size(); ++group_iter)
 714             {
 715                 T *pGroup = m_groups[group_iter];
 716                 if (!pGroup)
 717                     continue;
 718
 719                 const uint n = get_num_valid_elements_in_group(group_iter);
 720
 721                 uint i;
 722                 for (i = 0; i < n; i++)
 723                     if (!(pGroup[i] == default_element()))
 724                         break;
 725
 726                 if (i == n)
 727                 {
 728                     free_group(pGroup);
 729                     m_groups[group_iter] = NULL;
 730
 731                     ++num_groups_freed;
 732                 }
 733             }
 734
 735             return num_groups_freed;
 736         }
 737
 738         inline bool check() const
 739         {
 740             if (m_groups.size() != ((m_size + (N - 1)) >> Log2N))
 741                 return false;
 742
 743             vogl::vector<T *> group_ptrs;
 744             uint total_active_groups = 0;
 745             for (uint group_iter = 0; group_iter < m_groups.size(); ++group_iter)
 746             {
 747                 T *pGroup = m_groups[group_iter];
 748                 if (reinterpret_cast<intptr_t>(pGroup) & (VOGL_MIN_ALLOC_ALIGNMENT - 1))
 749                     return false;
 750
 751                 if (pGroup)
 752                 {
 753                     total_active_groups++;
 754                     group_ptrs.push_back(pGroup);
 755                 }
 756             }
 757
 758             if (total_active_groups != m_num_active_groups)
 759                 return false;
 760
 761             group_ptrs.sort();
 762             group_ptrs.unique();
 763             if (group_ptrs.size() != total_active_groups)
 764                 return false;
 765
 766             if (m_groups.size())
 767             {
 768                 uint t = 0;
 769                 for (uint i = 0; i < (m_groups.size() - 1); i++)
 770                 {
 771                     uint n = get_num_valid_elements_in_group(i);
 772                     if (n != N)
 773                         return false;
 774                     t += n;
 775                 }
 776
 777                 uint num_valid_in_last_group = get_num_valid_elements_in_group(m_groups.size() - 1);
 778                 t += num_valid_in_last_group;
 779                 if (t != m_size)
 780                     return false;
 781
 782                 if (!num_valid_in_last_group)
 783                     return false;
 784                 if (num_valid_in_last_group > N)
 785                     return false;
 786
 787                 const T *pLast_group = m_groups.back();
 788                 if (pLast_group)
 789                 {
 790                     for (uint i = num_valid_in_last_group; i < N; i++)
 791                     {
 792                         if (!(pLast_group[i] == default_element()))
 793                             return false;
 794                     }
 795                 }
 796             }
 797
 798             return true;
 799         }
 800
 801         inline void copy_element(uint dst_index, uint src_index)
 802         {
 803             if (!is_present(src_index))
 804             {
 805                 if (is_present(dst_index))
 806                     set(dst_index, default_element());
 807             }
 808             else
 809             {
 810                 set(dst_index, *get_ptr(src_index));
 811             }
 812         }
 813
 814         inline void erase(uint start, uint n)
 815         {
 816             VOGL_ASSERT((start + n) <= m_size);
 817             if ((start + n) > m_size)
 818                 return;
 819
 820             if (!n)
 821                 return;
 822
 823             const uint orig_num_groups = m_groups.size();
 824
 825             uint num_to_move = m_size - (start + n);
 826             uint dst_index = start;
 827             uint src_index = start + n;
 828
 829             while ((num_to_move) && ((dst_index & (N - 1)) != 0))
 830             {
 831                 copy_element(dst_index, src_index);
 832
 833                 ++src_index;
 834                 ++dst_index;
 835                 --num_to_move;
 836             }
 837
 838             if (num_to_move)
 839             {
 840                 // dst_index must be aligned to the beginning of a group here.
 841                 VOGL_ASSERT((dst_index & (N - 1)) == 0);
 842
 843                 const uint move_gap_size = src_index - dst_index;
 844
 845                 // If the move gap is >= the group size, then we can just free all the groups in the middle of the move gap that are overridden (and bulk erase the group ptrs array).
 846                 if (move_gap_size >= N)
 847                 {
 848                     uint first_full_group, num_full_groups;
 849                     get_full_group_range(dst_index, math::minimum(num_to_move, move_gap_size), first_full_group, num_full_groups);
 850
 851                     if (num_full_groups)
 852                     {
 853                         const uint total_elements_to_free = num_full_groups << Log2N;
 854
 855                         VOGL_ASSERT(total_elements_to_free <= num_to_move);
 856                         VOGL_ASSERT(dst_index <= (first_full_group << Log2N));
 857                         VOGL_ASSERT(src_index >= total_elements_to_free);
 858
 859                         free_groups(first_full_group, num_full_groups);
 860
 861                         m_groups.erase(first_full_group, num_full_groups);
 862                         m_groups.resize(orig_num_groups);
 863
 864                         //VOGL_ASSERT(check());
 865
 866                         src_index -= total_elements_to_free;
 867                     }
 868                 }
 869
 870                 while (num_to_move)
 871                 {
 872                     if (!is_present(src_index))
 873                     {
 874                         if ((src_index & (N - 1)) == 0)
 875                         {
 876                             uint num_not_present = math::minimum<uint>(num_to_move, N);
 877
 878                             // We know up to the next N src elements are not present, so there's no need to check them.
 879                             VOGL_ASSERT(!is_present(src_index + num_not_present - 1));
 880
 881                             src_index += num_not_present;
 882                             num_to_move -= num_not_present;
 883
 884                             while (num_not_present)
 885                             {
 886                                 if (is_present(dst_index))
 887                                     set(dst_index, default_element());
 888
 889                                 ++dst_index;
 890                                 --num_not_present;
 891                             }
 892                             continue;
 893                         }
 894
 895                         if (is_present(dst_index))
 896                             set(dst_index, default_element());
 897                     }
 898                     else
 899                     {
 900                         set(dst_index, *get_ptr(src_index));
 901                     }
 902
 903                     ++src_index;
 904                     ++dst_index;
 905                     --num_to_move;
 906                 }
 907             }
 908
 909             resize(m_size - n);
 910         }
 911
 912         inline void insert(uint index, const T *p, uint n, bool check_for_default_elements_while_copying = true)
 913         {
 914             VOGL_ASSERT(index <= m_size);
 915             if (!n)
 916                 return;
 917
 918             const uint orig_size = m_size;
 919             resize(m_size + n);
 920
 921             uint num_to_copy = orig_size - index;
 922
 923             uint src_index = orig_size - 1;
 924             uint dst_index = src_index + n;
 925
 926             while (num_to_copy)
 927             {
 928                 copy_element(dst_index, src_index);
 929
 930                 --src_index;
 931                 --dst_index;
 932                 --num_to_copy;
 933             }
 934
 935             dst_index = index;
 936
 937             if (check_for_default_elements_while_copying)
 938             {
 939                 while (n)
 940                 {
 941                     if (!(*p == default_element()))
 942                         set(dst_index, *p);
 943
 944                     ++dst_index;
 945                     ++p;
 946                     --n;
 947                 }
 948             }
 949             else
 950             {
 951                 while (n)
 952                 {
 953                     set(dst_index++, *p++);
 954                     --n;
 955                 }
 956             }
 957         }
 958
 959         inline void insert(uint index, const T &obj)
 960         {
 961             insert(index, &obj, 1);
 962         }
 963
 964         inline void push_front(const T &obj)
 965         {
 966             insert(0, &obj, 1);
 967         }
 968
 969         sparse_vector &append(const sparse_vector &other)
 970         {
 971             VOGL_ASSERT(this != &other);
 972
 973             if (other.m_size)
 974                 insert(m_size, &other[0], other.m_size);
 975             return *this;
 976         }
 977
 978         sparse_vector &append(const T *p, uint n)
 979         {
 980             insert(m_size, p, n);
 981             return *this;
 982         }
 983
 984         // low-level element group access
 985         inline uint get_num_groups() const
 986         {
 987             return m_groups.size();
 988         }
 989         inline uint get_num_active_groups() const
 990         {
 991             return m_num_active_groups;
 992         }
 993         inline uint get_group_size() const
 994         {
 995             return N;
 996         }
 997
 998         inline bool is_last_group(uint group_index) const
 999         {
1000             return (static_cast<int>(group_index) == (static_cast<int>(m_groups.size()) - 1));
1001         }
1002
1003         inline uint get_group_index(uint element_index)
1004         {
1005             return element_index >> Log2N;
1006         }
1007         inline uint get_group_offset(uint element_index)
1008         {
1009             return element_index & (N - 1);
1010         }
1011
1012         inline const T *get_group_ptr(uint group_index) const
1013         {
1014             return m_groups[group_index];
1015         }
1016         inline T *get_group_ptr(uint group_index)
1017         {
1018             return m_groups[group_index];
1019         }
1020
1021         const group_ptr_vec &get_group_ptr_vec() const
1022         {
1023             return m_groups;
1024         }
1025         group_ptr_vec &get_group_ptr_vec()
1026         {
1027             return m_groups;
1028         }
1029
1030         inline bool is_group_present(uint group_index) const
1031         {
1032             return get_group_ptr(group_index) != NULL;
1033         }
1034
1035         inline uint get_num_valid_elements_in_group(uint group_index) const
1036         {
1037             VOGL_ASSERT(group_index < m_groups.size());
1038
1039             if (!m_groups.size())
1040                 return 0;
1041
1042             uint n = 0;
1043             if (static_cast<int>(group_index) == (static_cast<int>(m_groups.size()) - 1))
1044                 n = m_size & (N - 1);
1045
1046             return n ? n : static_cast<uint>(N);
1047         }
1048
1049     private:
1050         uint m_size;
1051         uint m_num_active_groups;
1052
1053         group_ptr_vec m_groups;
1054
1055         uint64_t m_default[(sizeof(T) + sizeof(uint64_t) - 1) / sizeof(uint64_t)];
1056
1057         inline T *alloc_group(bool nofail = false)
1058         {
1059             T *p = static_cast<T *>(base::alloc_space(N * sizeof(T)));
1060
1061             if (!p)
1062             {
1063                 if (nofail)
1064                     return NULL;
1065
1066                 VOGL_FAIL("Out of memory");
1067             }
1068
1069             base::construct_group(p);
1070
1071             m_num_active_groups++;
1072
1073             return p;
1074         }
1075
1076         inline void free_group(T *p)
1077         {
1078             if (p)
1079             {
1080                 VOGL_ASSERT(m_num_active_groups);
1081                 m_num_active_groups--;
1082
1083                 base::destruct_group(p);
1084
1085                 base::free_space(p);
1086             }
1087         }
1088
1089         inline void free_groups(uint first_group_to_free, uint num_groups_to_free)
1090         {
1091             for (uint i = 0; i < num_groups_to_free; i++)
1092             {
1093                 T *p = m_groups[first_group_to_free + i];
1094                 if (p)
1095                 {
1096                     free_group(p);
1097                     m_groups[first_group_to_free + i] = NULL;
1098                 }
1099             }
1100         }
1101
1102         // assumes [start, start + num) is a valid group range
1103         inline void get_full_group_range(uint start, uint num, uint &first_full_group, uint &num_full_groups)
1104         {
1105             const uint num_to_skip = math::minimum(math::get_align_up_value_delta(start, N), num);
1106
1107             start += num_to_skip;
1108             num -= num_to_skip;
1109
1110             first_full_group = start >> Log2N;
1111             num_full_groups = num >> Log2N;
1112         }
1113
1114         inline void init_default()
1115         {
1116             base::construct_element(reinterpret_cast<T *>(m_default));
1117         }
1118
1119         inline void deinit_default()
1120         {
1121             base::destruct_element(reinterpret_cast<T *>(m_default));
1122         }
1123     };
1124
1125     extern uint g_sparse_vector_test_counters[2];
1126
1127     template <uint counter>
1128     class sparse_vector_test_obj
1129     {
1130     public:
1131         sparse_vector_test_obj()
1132         {
1133             g_sparse_vector_test_counters[counter]++;
1134         }
1135
1136         sparse_vector_test_obj(const sparse_vector_test_obj &)
1137         {
1138             g_sparse_vector_test_counters[counter]--;
1139         }
1140
1141         ~sparse_vector_test_obj()
1142         {
1143             VOGL_ASSERT(g_sparse_vector_test_counters[counter]);
1144             g_sparse_vector_test_counters[counter]--;
1145         }
1146
1147         bool operator==(const sparse_vector_test_obj &other) const
1148         {
1149             return this == &other;
1150         }
1151     };
1152
1153     inline bool sparse_vector_test(uint seed = 15)
1154     {
1155         uint num_failures = 0;
1156         random r;
1157         r.seed(seed);
1158
1159 #define VOGL_SPARSE_VECTOR_CHECK(x)          \
1160     do                                         \
1161     {                                          \
1162         if (!(x))                              \
1163         {                                      \
1164             num_failures++;                    \
1165             vogl_debug_break_if_debugging(); \
1166         }                                      \
1167     } while (0)
1168
1169         printf("\n");
1170         for (uint t = 0; t < 10; t++)
1171         {
1172             {
1173                 printf("std::vector: ");
1174                 timed_scope stopwatch;
1175                 {
1176                     std::vector<dynamic_string> t1;
1177                     //t1.reserve(100000);
1178                     for (uint i = 0; i < 100000; i++)
1179                     {
1180                         char buf[256];
1181                         vogl_sprintf_s(buf, sizeof(buf), "%u", i);
1182                         t1.push_back(buf);
1183                     }
1184                 }
1185             }
1186
1187             {
1188                 printf("std::vector with reserve: ");
1189                 timed_scope stopwatch;
1190                 {
1191                     std::vector<dynamic_string> t1;
1192                     t1.reserve(100000);
1193                     for (uint i = 0; i < 100000; i++)
1194                     {
1195                         char buf[256];
1196                         vogl_sprintf_s(buf, sizeof(buf), "%u", i);
1197                         t1.push_back(buf);
1198                     }
1199                 }
1200             }
1201
1202             {
1203                 printf("vogl::vector: ");
1204                 timed_scope stopwatch;
1205                 {
1206                     vogl::vector<dynamic_string> t1;
1207                     //t1.reserve(100000);
1208                     for (uint i = 0; i < 100000; i++)
1209                     {
1210                         char buf[256];
1211                         vogl_sprintf_s(buf, sizeof(buf), "%u", i);
1212                         t1.push_back(buf);
1213                     }
1214                 }
1215             }
1216
1217             {
1218                 printf("vogl::vector with reserve: ");
1219                 timed_scope stopwatch;
1220                 {
1221                     vogl::vector<dynamic_string> t1;
1222                     t1.reserve(100000);
1223                     for (uint i = 0; i < 100000; i++)
1224                     {
1225                         char buf[256];
1226                         vogl_sprintf_s(buf, sizeof(buf), "%u", i);
1227                         t1.push_back(buf);
1228                     }
1229                 }
1230             }
1231
1232 #define SPARSE_VECTOR_PUSH_BACK_TEST(x)                                                                         \
1233     {                                                                                                           \
1234         printf("vogl::sparse_vector %u, group size %u bytes: ", x, (1U << x) * (uint)sizeof(dynamic_string)); \
1235         timed_scope stopwatch;                                                                                  \
1236         {                                                                                                       \
1237             sparse_vector<dynamic_string, x> t2;                                                                \
1238             for (uint i = 0; i < 100000; i++)                                                                   \
1239             {                                                                                                   \
1240                 char buf[256];                                                                                  \
1241                 vogl_sprintf_s(buf, sizeof(buf), "%u", i);                                                       \
1242                 t2.push_back(buf);                                                                              \
1243             }                                                                                                   \
1244         }                                                                                                       \
1245     }
1246
1247             SPARSE_VECTOR_PUSH_BACK_TEST(0);
1248             SPARSE_VECTOR_PUSH_BACK_TEST(1);
1249             SPARSE_VECTOR_PUSH_BACK_TEST(2);
1250             SPARSE_VECTOR_PUSH_BACK_TEST(3);
1251             SPARSE_VECTOR_PUSH_BACK_TEST(4);
1252             SPARSE_VECTOR_PUSH_BACK_TEST(5);
1253             SPARSE_VECTOR_PUSH_BACK_TEST(6);
1254             SPARSE_VECTOR_PUSH_BACK_TEST(7);
1255             SPARSE_VECTOR_PUSH_BACK_TEST(8);
1256             SPARSE_VECTOR_PUSH_BACK_TEST(9);
1257             SPARSE_VECTOR_PUSH_BACK_TEST(10);
1258             SPARSE_VECTOR_PUSH_BACK_TEST(11);
1259             SPARSE_VECTOR_PUSH_BACK_TEST(12);
1260             SPARSE_VECTOR_PUSH_BACK_TEST(13);
1261             SPARSE_VECTOR_PUSH_BACK_TEST(14);
1262 #undef SPARSE_VECTOR_PUSH_BACK_TEST
1263         }
1264
1265         {
1266             sparse_vector<uint, 2> a1;
1267
1268             VOGL_SPARSE_VECTOR_CHECK(a1.check());
1269
1270             for (uint i = 0; i < 16; i++)
1271                 a1.push_back(i);
1272
1273             const uint *q = &a1[0];
1274             VOGL_NOTE_UNUSED(q);
1275             uint *p = &a1(0);
1276             VOGL_NOTE_UNUSED(p);
1277             const uint &x1 = a1[0];
1278             VOGL_NOTE_UNUSED(x1);
1279             uint &x2 = a1.get_or_create_element(0);
1280             VOGL_NOTE_UNUSED(x2);
1281
1282             for (uint i = 0; i < 16; i++)
1283                 a1(i) = i;
1284
1285             VOGL_SPARSE_VECTOR_CHECK(a1.check());
1286
1287             VOGL_SPARSE_VECTOR_CHECK(a1.size() == 16);
1288             VOGL_SPARSE_VECTOR_CHECK(a1.get_num_active_groups() == 4);
1289
1290             for (uint i = 0; i < 16; i++)
1291                 VOGL_SPARSE_VECTOR_CHECK(a1[i] == i);
1292
1293             const sparse_vector<uint, 2> a1_const(a1);
1294             for (uint i = 0; i < 16; i++)
1295                 VOGL_SPARSE_VECTOR_CHECK(a1_const[i] == i);
1296             for (uint i = 0; i < 16; i++)
1297                 VOGL_SPARSE_VECTOR_CHECK(a1_const.at(i) == i);
1298
1299             a1.invalidate_range(1, 9);
1300             VOGL_SPARSE_VECTOR_CHECK(a1.get_num_active_groups() == 3);
1301             VOGL_SPARSE_VECTOR_CHECK(a1.check());
1302
1303             for (uint i = 0; i < 16; i++)
1304             {
1305                 if ((i >= 1) && (i <= 9))
1306                     VOGL_SPARSE_VECTOR_CHECK(a1[i] == a1.default_element());
1307                 else
1308                     VOGL_SPARSE_VECTOR_CHECK(a1[i] == i);
1309             }
1310
1311             a1.invalidate_all();
1312             VOGL_SPARSE_VECTOR_CHECK(a1.get_num_active_groups() == 0);
1313             VOGL_SPARSE_VECTOR_CHECK(a1.check());
1314
1315             for (uint i = 0; i < 16; i++)
1316                 VOGL_SPARSE_VECTOR_CHECK(a1[i] == a1.default_element());
1317         }
1318
1319         {
1320             sparse_vector<uint, 0> a1;
1321
1322             VOGL_SPARSE_VECTOR_CHECK(a1.check());
1323
1324             for (uint i = 0; i < 16; i++)
1325                 a1.push_back(i);
1326
1327             const uint *q = &a1[0];
1328             VOGL_NOTE_UNUSED(q);
1329             uint *p = &a1(0);
1330             VOGL_NOTE_UNUSED(p);
1331             const uint &x1 = a1[0];
1332             VOGL_NOTE_UNUSED(x1);
1333             uint &x2 = a1.get_or_create_element(0);
1334             VOGL_NOTE_UNUSED(x2);
1335
1336             for (uint i = 0; i < 16; i++)
1337                 a1(i) = i;
1338
1339             VOGL_SPARSE_VECTOR_CHECK(a1.check());
1340
1341             VOGL_SPARSE_VECTOR_CHECK(a1.size() == 16);
1342             VOGL_SPARSE_VECTOR_CHECK(a1.get_num_active_groups() == 16);
1343
1344             for (uint i = 0; i < 16; i++)
1345                 VOGL_SPARSE_VECTOR_CHECK(a1[i] == i);
1346
1347             const sparse_vector<uint, 0> a1_const(a1);
1348             for (uint i = 0; i < 16; i++)
1349                 VOGL_SPARSE_VECTOR_CHECK(a1_const[i] == i);
1350             for (uint i = 0; i < 16; i++)
1351                 VOGL_SPARSE_VECTOR_CHECK(a1_const.at(i) == i);
1352
1353             a1.invalidate_range(1, 9);
1354             VOGL_SPARSE_VECTOR_CHECK(a1.get_num_active_groups() == 7);
1355             VOGL_SPARSE_VECTOR_CHECK(a1.check());
1356
1357             for (uint i = 0; i < 16; i++)
1358             {
1359                 if ((i >= 1) && (i <= 9))
1360                     VOGL_SPARSE_VECTOR_CHECK(a1[i] == a1.default_element());
1361                 else
1362                     VOGL_SPARSE_VECTOR_CHECK(a1[i] == i);
1363             }
1364
1365             a1.invalidate_all();
1366             VOGL_SPARSE_VECTOR_CHECK(a1.get_num_active_groups() == 0);
1367             VOGL_SPARSE_VECTOR_CHECK(a1.check());
1368
1369             for (uint i = 0; i < 16; i++)
1370                 VOGL_SPARSE_VECTOR_CHECK(a1[i] == a1.default_element());
1371         }
1372
1373         {
1374             sparse_vector<sparse_vector_test_obj<0>, 2> blah;
1375
1376             VOGL_SPARSE_VECTOR_CHECK(g_sparse_vector_test_counters[0] == 1);
1377
1378             blah.resize(16);
1379             for (uint i = 0; i < 16; i++)
1380                 blah.set(i, sparse_vector_test_obj<0>());
1381
1382             VOGL_SPARSE_VECTOR_CHECK(g_sparse_vector_test_counters[0] == 17);
1383
1384             blah.erase(4, 4);
1385
1386             VOGL_SPARSE_VECTOR_CHECK(g_sparse_vector_test_counters[0] == 13);
1387
1388             for (uint i = 4; i < 8; i++)
1389                 blah.set(i, blah.default_element());
1390             blah.optimize_groups();
1391             VOGL_SPARSE_VECTOR_CHECK(g_sparse_vector_test_counters[0] == 13);
1392
1393             blah.insert(4, sparse_vector_test_obj<0>());
1394             VOGL_SPARSE_VECTOR_CHECK(g_sparse_vector_test_counters[0] == 17); // 17, because the sparse_vector had to add a new group to the end and groups are always fully constructed
1395
1396             blah.clear();
1397
1398             VOGL_SPARSE_VECTOR_CHECK(g_sparse_vector_test_counters[0] == 1);
1399
1400             blah.resize(256);
1401             blah.allocate_all_groups();
1402
1403             VOGL_SPARSE_VECTOR_CHECK(g_sparse_vector_test_counters[0] == 257);
1404
1405             blah.erase(0, blah.size());
1406
1407             VOGL_SPARSE_VECTOR_CHECK(g_sparse_vector_test_counters[0] == 1);
1408         }
1409
1410         for (uint iter = 0; iter < 10000; iter++)
1411         {
1412             uint n = r.irand_inclusive(0, 100000);
1413             uint j = r.irand_inclusive(0, math::clamp<uint>(n / 30, 1, n));
1414
1415             vogl::vector<uint> a1(n);
1416             sparse_vector<uint, 6> a2;
1417             sparse_vector<uint, 6> a4;
1418
1419             VOGL_SPARSE_VECTOR_CHECK(a2.check());
1420
1421             for (uint m = 0; m < j; m++)
1422             {
1423                 uint pos = r.irand(0, n);
1424                 a1[pos] = m;
1425                 a2.set(pos, m);
1426             }
1427
1428             VOGL_SPARSE_VECTOR_CHECK(a2.check());
1429
1430             a2.resize(n);
1431
1432             VOGL_SPARSE_VECTOR_CHECK(a2.check());
1433
1434             a2.optimize_groups();
1435
1436             VOGL_SPARSE_VECTOR_CHECK(a2.check());
1437
1438             a2.allocate_all_groups();
1439
1440             VOGL_SPARSE_VECTOR_CHECK(a2.check());
1441
1442             a2.optimize_groups();
1443
1444             VOGL_SPARSE_VECTOR_CHECK(a2.check());
1445
1446             a4 = a2;
1447
1448             vector<uint> k4;
1449             a2.get_vector(k4);
1450             sparse_vector<uint, 8> k5(k4);
1451             VOGL_SPARSE_VECTOR_CHECK(k5 == a4);
1452             k5.clear();
1453             k5.assign(k4, true);
1454             VOGL_SPARSE_VECTOR_CHECK(k5 == a4);
1455
1456             sparse_vector<uint, 6> a3(a2);
1457
1458             VOGL_SPARSE_VECTOR_CHECK(a2 == a3);
1459             VOGL_SPARSE_VECTOR_CHECK(!(a2 < a3));
1460             VOGL_SPARSE_VECTOR_CHECK(!(a3 < a2));
1461
1462             for (uint m = 0; m < n; m++)
1463             {
1464                 VOGL_SPARSE_VECTOR_CHECK(a1[m] == a2[m]);
1465             }
1466
1467             for (uint m = 0; m < n; m++)
1468             {
1469                 VOGL_SPARSE_VECTOR_CHECK(a1[a1.size() - 1] == a2[a2.size() - 1]);
1470                 a1.pop_back();
1471                 a2.pop_back();
1472
1473                 if (m == n / 2)
1474                 {
1475                     VOGL_SPARSE_VECTOR_CHECK(a2.check());
1476
1477                     a3.allocate_all_groups();
1478                     a3 = a2;
1479
1480                     VOGL_SPARSE_VECTOR_CHECK(a2 == a3);
1481                     VOGL_SPARSE_VECTOR_CHECK(!(a2 < a3));
1482                     VOGL_SPARSE_VECTOR_CHECK(!(a3 < a2));
1483
1484                     VOGL_SPARSE_VECTOR_CHECK(a3.check());
1485                 }
1486             }
1487
1488             VOGL_SPARSE_VECTOR_CHECK(a2.check());
1489
1490             a2.optimize_groups();
1491
1492             VOGL_SPARSE_VECTOR_CHECK(a2.check());
1493
1494             {
1495                 vogl::vector<uint> shadow(a4.size());
1496                 for (uint i = 0; i < a4.size(); i++)
1497                     shadow[i] = a4[i];
1498
1499                 for (uint m = 0; m < a4.size(); m++)
1500                 {
1501                     VOGL_SPARSE_VECTOR_CHECK(a4[m] == shadow[m]);
1502                 }
1503
1504                 vogl::vector<uint> vals;
1505                 vals.reserve(n);
1506
1507                 uint k = r.irand(0, math::minimum<uint>(16, n / 4));
1508                 while ((k) && (a4.size()))
1509                 {
1510                     uint s = r.irand(0, a4.size());
1511                     uint l = r.irand_inclusive(1, a4.size() - s);
1512
1513                     if (r.get_bit())
1514                     {
1515                         shadow.erase(s, l);
1516                         a4.erase(s, l);
1517                     }
1518                     else
1519                     {
1520                         vals.resize(l);
1521                         for (uint i = 0; i < l; i++)
1522                             vals[i] = r.urand32();
1523
1524                         shadow.insert(s, vals.get_ptr(), l);
1525                         a4.insert(s, vals.get_ptr(), l);
1526                     }
1527
1528                     VOGL_SPARSE_VECTOR_CHECK(a4.check());
1529                     VOGL_SPARSE_VECTOR_CHECK(shadow.size() == a4.size());
1530
1531                     for (uint m = 0; m < a4.size(); m++)
1532                     {
1533                         VOGL_SPARSE_VECTOR_CHECK(a4[m] == shadow[m]);
1534                     }
1535
1536                     k--;
1537                 }
1538             }
1539
1540             {
1541                 sparse_vector<uint, 0> a5(a4.size());
1542                 a5 = a4;
1543
1544                 vogl::vector<uint> shadow(a5.size());
1545                 for (uint i = 0; i < a5.size(); i++)
1546                     shadow[i] = a5[i];
1547
1548                 for (uint m = 0; m < a5.size(); m++)
1549                 {
1550                     VOGL_SPARSE_VECTOR_CHECK(a5[m] == shadow[m]);
1551                 }
1552
1553                 vogl::vector<uint> vals;
1554                 vals.reserve(n);
1555
1556                 uint k = r.irand(0, math::minimum<uint>(16, n / 4));
1557                 while ((k) && (a5.size()))
1558                 {
1559                     uint s = r.irand(0, a5.size());
1560                     uint l = r.irand_inclusive(1, a5.size() - s);
1561
1562                     if (r.get_bit())
1563                     {
1564                         shadow.erase(s, l);
1565                         a5.erase(s, l);
1566                     }
1567                     else
1568                     {
1569                         vals.resize(l);
1570                         for (uint i = 0; i < l; i++)
1571                             vals[i] = r.urand32();
1572
1573                         shadow.insert(s, vals.get_ptr(), l);
1574                         a5.insert(s, vals.get_ptr(), l);
1575                     }
1576
1577                     VOGL_SPARSE_VECTOR_CHECK(a5.check());
1578                     VOGL_SPARSE_VECTOR_CHECK(shadow.size() == a5.size());
1579
1580                     for (uint m = 0; m < a5.size(); m++)
1581                     {
1582                         VOGL_SPARSE_VECTOR_CHECK(a5[m] == shadow[m]);
1583                     }
1584
1585                     k--;
1586                 }
1587             }
1588
1589             uint k = 2;
1590             sparse_vector<uint *, 2> z1;
1591             z1.push_back(&k);
1592             *z1[0] = 5;
1593             z1(0) = &k;
1594             VOGL_SPARSE_VECTOR_CHECK(*z1[0] == 5);
1595
1596             sparse_vector<uint *, 4> z2(z1);
1597             sparse_vector<uint *, 4> z3;
1598             z3 = z1;
1599             z3 = z2;
1600
1601             sparse_vector<dynamic_string, 4> j1;
1602             j1.push_back("blah");
1603             const sparse_vector<dynamic_string, 4> &j2 = j1;
1604             j1.at(0).get_ptr();
1605             j1(0) = dynamic_string("cool");
1606             j1[0].get_ptr();
1607             j2[0].get_ptr();
1608
1609             if ((iter & 255) == 0)
1610                 printf("%u\n", iter);
1611         }
1612
1613 #undef VOGL_SPARSE_VECTOR_CHECK
1614
1615         return !num_failures;
1616     }
1617
1618 } // namespace vogl