src/kitemviews/kitemset.h

   1 /*
   2  * SPDX-FileCopyrightText: 2013 Frank Reininghaus <frank78ac@googlemail.com>
   3  *
   4  * SPDX-License-Identifier: GPL-2.0-or-later
   5  */
   6
   7 #ifndef KITEMSET_H
   8 #define KITEMSET_H
   9
  10 #include "dolphin_export.h"
  11 #include "kitemviews/kitemrange.h"
  12
  13 /**
  14  * @brief Stores a set of integer numbers in a space-efficient way.
  15  *
  16  * This class is similar to QSet<int>, but it has the following advantages:
  17  *
  18  * 1. It uses less memory than a QSet<int> if many consecutive numbers are
  19  *    stored. This is achieved by not storing each number separately, but
  20  *    "ranges" of numbers.
  21  *
  22  *    Example: The set {1, 2, 3, 4, 5} is represented by a single range which
  23  *    starts at 1 and has the length 5.
  24  *
  25  * 2. When iterating through a KItemSet using KItemSet::iterator or
  26  *    KItemSet::const_iterator, the numbers are traversed in ascending order.
  27  *
  28  * The complexity of most operations depends on the number of ranges.
  29  */
  30
  31 class DOLPHIN_EXPORT KItemSet
  32 {
  33 public:
  34     KItemSet();
  35     KItemSet(const KItemSet &other);
  36     ~KItemSet();
  37     KItemSet &operator=(const KItemSet &other);
  38
  39     /**
  40      * Returns the number of items in the set.
  41      * Complexity: O(log(number of ranges)).
  42      */
  43     int count() const;
  44
  45     bool isEmpty() const;
  46     void clear();
  47
  48     bool operator==(const KItemSet &other) const;
  49     bool operator!=(const KItemSet &other) const;
  50
  51     class iterator
  52     {
  53         iterator(const KItemRangeList::iterator &rangeIt, int offset = 0)
  54             : m_rangeIt(rangeIt)
  55             , m_offset(offset)
  56         {
  57         }
  58
  59     public:
  60         iterator(const iterator &other)
  61             : m_rangeIt(other.m_rangeIt)
  62             , m_offset(other.m_offset)
  63         {
  64         }
  65
  66         iterator &operator=(const iterator &other)
  67         {
  68             m_rangeIt = other.m_rangeIt;
  69             m_offset = other.m_offset;
  70             return *this;
  71         }
  72
  73         ~iterator() = default;
  74
  75         int operator*() const
  76         {
  77             return m_rangeIt->index + m_offset;
  78         }
  79
  80         inline bool operator==(const iterator &other) const
  81         {
  82             return m_rangeIt == other.m_rangeIt && m_offset == other.m_offset;
  83         }
  84
  85         inline bool operator!=(const iterator &other) const
  86         {
  87             return !(*this == other);
  88         }
  89
  90         inline iterator &operator++()
  91         {
  92             ++m_offset;
  93
  94             if (m_offset == m_rangeIt->count) {
  95                 ++m_rangeIt;
  96                 m_offset = 0;
  97             }
  98
  99             return *this;
 100         }
 101
 102         inline iterator operator++(int)
 103         {
 104             iterator r = *this;
 105             ++(*this);
 106             return r;
 107         }
 108
 109         inline iterator &operator--()
 110         {
 111             if (m_offset == 0) {
 112                 --m_rangeIt;
 113                 m_offset = m_rangeIt->count - 1;
 114             } else {
 115                 --m_offset;
 116             }
 117
 118             return *this;
 119         }
 120
 121         inline iterator operator--(int)
 122         {
 123             iterator r = *this;
 124             --(*this);
 125             return r;
 126         }
 127
 128     private:
 129         KItemRangeList::iterator m_rangeIt;
 130         int m_offset;
 131
 132         friend class const_iterator;
 133         friend class KItemSet;
 134     };
 135
 136     class const_iterator
 137     {
 138         const_iterator(KItemRangeList::const_iterator rangeIt, int offset = 0)
 139             : m_rangeIt(rangeIt)
 140             , m_offset(offset)
 141         {
 142         }
 143
 144     public:
 145         const_iterator(const const_iterator &other)
 146             : m_rangeIt(other.m_rangeIt)
 147             , m_offset(other.m_offset)
 148         {
 149         }
 150
 151         explicit const_iterator(const iterator &other)
 152             : m_rangeIt(other.m_rangeIt)
 153             , m_offset(other.m_offset)
 154         {
 155         }
 156
 157         const_iterator &operator=(const const_iterator &other)
 158         {
 159             m_rangeIt = other.m_rangeIt;
 160             m_offset = other.m_offset;
 161             return *this;
 162         }
 163
 164         ~const_iterator() = default;
 165
 166         int operator*() const
 167         {
 168             return m_rangeIt->index + m_offset;
 169         }
 170
 171         inline bool operator==(const const_iterator &other) const
 172         {
 173             return m_rangeIt == other.m_rangeIt && m_offset == other.m_offset;
 174         }
 175
 176         inline bool operator!=(const const_iterator &other) const
 177         {
 178             return !(*this == other);
 179         }
 180
 181         inline const_iterator &operator++()
 182         {
 183             ++m_offset;
 184
 185             if (m_offset == m_rangeIt->count) {
 186                 ++m_rangeIt;
 187                 m_offset = 0;
 188             }
 189
 190             return *this;
 191         }
 192
 193         inline const_iterator operator++(int)
 194         {
 195             const_iterator r = *this;
 196             ++(*this);
 197             return r;
 198         }
 199
 200         inline const_iterator &operator--()
 201         {
 202             if (m_offset == 0) {
 203                 --m_rangeIt;
 204                 m_offset = m_rangeIt->count - 1;
 205             } else {
 206                 --m_offset;
 207             }
 208
 209             return *this;
 210         }
 211
 212         inline const_iterator operator--(int)
 213         {
 214             const_iterator r = *this;
 215             --(*this);
 216             return r;
 217         }
 218
 219     private:
 220         KItemRangeList::const_iterator m_rangeIt;
 221         int m_offset;
 222
 223         friend class KItemSet;
 224     };
 225
 226     class const_reverse_iterator
 227     {
 228     public:
 229         const_reverse_iterator(KItemSet::const_iterator rangeIt)
 230             : m_current(rangeIt)
 231         {
 232         }
 233
 234         const_reverse_iterator(const KItemSet::const_reverse_iterator &other)
 235             : m_current(other.base())
 236         {
 237         }
 238
 239         int operator*() const
 240         {
 241             // analog to std::prev
 242             auto t = const_iterator(m_current);
 243             --t;
 244             return *t;
 245         }
 246
 247         inline bool operator==(const const_reverse_iterator &other) const
 248         {
 249             return m_current == other.m_current;
 250         }
 251
 252         bool operator!=(const const_reverse_iterator &other) const
 253         {
 254             return !(*this == other);
 255         }
 256
 257         const_reverse_iterator &operator++()
 258         {
 259             --m_current;
 260             return *this;
 261         }
 262         const_reverse_iterator operator++(int)
 263         {
 264             auto tmp = *this;
 265             ++(*this);
 266             return tmp;
 267         }
 268
 269         const_reverse_iterator &operator--()
 270         {
 271             ++m_current;
 272             return *this;
 273         }
 274         const_reverse_iterator operator--(int)
 275         {
 276             auto tmp = *this;
 277             --(*this);
 278             return tmp;
 279         }
 280
 281         KItemSet::const_iterator base() const
 282         {
 283             return m_current;
 284         }
 285
 286     private:
 287         KItemSet::const_iterator m_current;
 288     };
 289
 290     iterator begin();
 291     const_iterator begin() const;
 292     const_iterator constBegin() const;
 293     iterator end();
 294     const_iterator end() const;
 295     const_iterator constEnd() const;
 296
 297     const_reverse_iterator rend() const;
 298     const_reverse_iterator rbegin() const;
 299
 300     int first() const;
 301     int last() const;
 302
 303     bool contains(int i) const;
 304     iterator insert(int i);
 305     iterator find(int i);
 306     const_iterator constFind(int i) const;
 307     bool remove(int i);
 308     iterator erase(iterator it);
 309
 310     /**
 311      * Returns a new set which contains all items that are contained in this
 312      * KItemSet, in \a other, or in both.
 313      */
 314     KItemSet operator+(const KItemSet &other) const;
 315
 316     /**
 317      * Returns a new set which contains all items that are contained either in
 318      * this KItemSet, or in \a other, but not in both (the symmetric difference
 319      * of both KItemSets).
 320      */
 321     KItemSet operator^(const KItemSet &other) const;
 322
 323     KItemSet &operator<<(int i);
 324
 325 private:
 326     /**
 327      * Returns true if the KItemSet is valid, and false otherwise.
 328      * A valid KItemSet must store the item ranges in ascending order, and
 329      * the ranges must not overlap.
 330      */
 331     bool isValid() const;
 332
 333     /**
 334      * This function returns an iterator that points to the KItemRange which
 335      * contains i, or m_itemRanges.end() if no such range exists.
 336      */
 337     KItemRangeList::iterator rangeForItem(int i);
 338
 339     /**
 340      * This function returns an iterator that points to the KItemRange which
 341      * contains i, or m_itemRanges.constEnd() if no such range exists.
 342      */
 343     KItemRangeList::const_iterator constRangeForItem(int i) const;
 344
 345     KItemRangeList m_itemRanges;
 346
 347     friend class KItemSetTest;
 348 };
 349
 350 inline KItemSet::KItemSet()
 351     : m_itemRanges()
 352 {
 353 }
 354
 355 inline KItemSet::KItemSet(const KItemSet &other)
 356     : m_itemRanges(other.m_itemRanges)
 357 {
 358 }
 359
 360 inline KItemSet::~KItemSet() = default;
 361
 362 inline KItemSet &KItemSet::operator=(const KItemSet &other)
 363 {
 364     m_itemRanges = other.m_itemRanges;
 365     return *this;
 366 }
 367
 368 inline int KItemSet::count() const
 369 {
 370     int result = 0;
 371     for (const KItemRange &range : std::as_const(m_itemRanges)) {
 372         result += range.count;
 373     }
 374     return result;
 375 }
 376
 377 inline bool KItemSet::isEmpty() const
 378 {
 379     return m_itemRanges.isEmpty();
 380 }
 381
 382 inline void KItemSet::clear()
 383 {
 384     m_itemRanges.clear();
 385 }
 386
 387 inline bool KItemSet::operator==(const KItemSet &other) const
 388 {
 389     return m_itemRanges == other.m_itemRanges;
 390 }
 391
 392 inline bool KItemSet::operator!=(const KItemSet &other) const
 393 {
 394     return m_itemRanges != other.m_itemRanges;
 395 }
 396
 397 inline bool KItemSet::contains(int i) const
 398 {
 399     const KItemRangeList::const_iterator it = constRangeForItem(i);
 400     return it != m_itemRanges.end();
 401 }
 402
 403 inline KItemSet::iterator KItemSet::find(int i)
 404 {
 405     const KItemRangeList::iterator it = rangeForItem(i);
 406     if (it != m_itemRanges.end()) {
 407         return iterator(it, i - it->index);
 408     } else {
 409         return end();
 410     }
 411 }
 412
 413 inline KItemSet::const_iterator KItemSet::constFind(int i) const
 414 {
 415     const KItemRangeList::const_iterator it = constRangeForItem(i);
 416     if (it != m_itemRanges.constEnd()) {
 417         return const_iterator(it, i - it->index);
 418     } else {
 419         return constEnd();
 420     }
 421 }
 422
 423 inline bool KItemSet::remove(int i)
 424 {
 425     iterator it = find(i);
 426     if (it != end()) {
 427         erase(it);
 428         return true;
 429     } else {
 430         return false;
 431     }
 432 }
 433
 434 inline KItemSet::iterator KItemSet::begin()
 435 {
 436     return iterator(m_itemRanges.begin());
 437 }
 438
 439 inline KItemSet::const_iterator KItemSet::begin() const
 440 {
 441     return const_iterator(m_itemRanges.begin());
 442 }
 443
 444 inline KItemSet::const_iterator KItemSet::constBegin() const
 445 {
 446     return const_iterator(m_itemRanges.constBegin());
 447 }
 448
 449 inline KItemSet::iterator KItemSet::end()
 450 {
 451     return iterator(m_itemRanges.end());
 452 }
 453
 454 inline KItemSet::const_iterator KItemSet::end() const
 455 {
 456     return const_iterator(m_itemRanges.end());
 457 }
 458
 459 inline KItemSet::const_iterator KItemSet::constEnd() const
 460 {
 461     return const_iterator(m_itemRanges.constEnd());
 462 }
 463
 464 inline int KItemSet::first() const
 465 {
 466     return m_itemRanges.first().index;
 467 }
 468
 469 inline int KItemSet::last() const
 470 {
 471     const KItemRange &lastRange = m_itemRanges.last();
 472     return lastRange.index + lastRange.count - 1;
 473 }
 474
 475 inline KItemSet::const_reverse_iterator KItemSet::rend() const
 476 {
 477     return KItemSet::const_reverse_iterator(constBegin());
 478 }
 479
 480 inline KItemSet::const_reverse_iterator KItemSet::rbegin() const
 481 {
 482     return KItemSet::const_reverse_iterator(constEnd());
 483 }
 484
 485 inline KItemSet &KItemSet::operator<<(int i)
 486 {
 487     insert(i);
 488     return *this;
 489 }
 490
 491 #endif