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)
  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)
 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     iterator begin();
 227     const_iterator begin() const;
 228     const_iterator constBegin() const;
 229     iterator end();
 230     const_iterator end() const;
 231     const_iterator constEnd() const;
 232
 233     int first() const;
 234     int last() const;
 235
 236     bool contains(int i) const;
 237     iterator insert(int i);
 238     iterator find(int i);
 239     const_iterator constFind(int i) const;
 240     bool remove(int i);
 241     iterator erase(iterator it);
 242
 243     /**
 244      * Returns a new set which contains all items that are contained in this
 245      * KItemSet, in \a other, or in both.
 246      */
 247     KItemSet operator+(const KItemSet &other) const;
 248
 249     /**
 250      * Returns a new set which contains all items that are contained either in
 251      * this KItemSet, or in \a other, but not in both (the symmetric difference
 252      * of both KItemSets).
 253      */
 254     KItemSet operator^(const KItemSet &other) const;
 255
 256     KItemSet &operator<<(int i);
 257
 258 private:
 259     /**
 260      * Returns true if the KItemSet is valid, and false otherwise.
 261      * A valid KItemSet must store the item ranges in ascending order, and
 262      * the ranges must not overlap.
 263      */
 264     bool isValid() const;
 265
 266     /**
 267      * This function returns an iterator that points to the KItemRange which
 268      * contains i, or m_itemRanges.end() if no such range exists.
 269      */
 270     KItemRangeList::iterator rangeForItem(int i);
 271
 272     /**
 273      * This function returns an iterator that points to the KItemRange which
 274      * contains i, or m_itemRanges.constEnd() if no such range exists.
 275      */
 276     KItemRangeList::const_iterator constRangeForItem(int i) const;
 277
 278     KItemRangeList m_itemRanges;
 279
 280     friend class KItemSetTest;
 281 };
 282
 283 inline KItemSet::KItemSet()
 284     : m_itemRanges()
 285 {
 286 }
 287
 288 inline KItemSet::KItemSet(const KItemSet &other)
 289     : m_itemRanges(other.m_itemRanges)
 290 {
 291 }
 292
 293 inline KItemSet::~KItemSet() = default;
 294
 295 inline KItemSet &KItemSet::operator=(const KItemSet &other)
 296 {
 297     m_itemRanges = other.m_itemRanges;
 298     return *this;
 299 }
 300
 301 inline int KItemSet::count() const
 302 {
 303     int result = 0;
 304     for (const KItemRange &range : qAsConst(m_itemRanges)) {
 305         result += range.count;
 306     }
 307     return result;
 308 }
 309
 310 inline bool KItemSet::isEmpty() const
 311 {
 312     return m_itemRanges.isEmpty();
 313 }
 314
 315 inline void KItemSet::clear()
 316 {
 317     m_itemRanges.clear();
 318 }
 319
 320 inline bool KItemSet::operator==(const KItemSet &other) const
 321 {
 322     return m_itemRanges == other.m_itemRanges;
 323 }
 324
 325 inline bool KItemSet::operator!=(const KItemSet &other) const
 326 {
 327     return m_itemRanges != other.m_itemRanges;
 328 }
 329
 330 inline bool KItemSet::contains(int i) const
 331 {
 332     const KItemRangeList::const_iterator it = constRangeForItem(i);
 333     return it != m_itemRanges.end();
 334 }
 335
 336 inline KItemSet::iterator KItemSet::find(int i)
 337 {
 338     const KItemRangeList::iterator it = rangeForItem(i);
 339     if (it != m_itemRanges.end()) {
 340         return iterator(it, i - it->index);
 341     } else {
 342         return end();
 343     }
 344 }
 345
 346 inline KItemSet::const_iterator KItemSet::constFind(int i) const
 347 {
 348     const KItemRangeList::const_iterator it = constRangeForItem(i);
 349     if (it != m_itemRanges.constEnd()) {
 350         return const_iterator(it, i - it->index);
 351     } else {
 352         return constEnd();
 353     }
 354 }
 355
 356 inline bool KItemSet::remove(int i)
 357 {
 358     iterator it = find(i);
 359     if (it != end()) {
 360         erase(it);
 361         return true;
 362     } else {
 363         return false;
 364     }
 365 }
 366
 367 inline KItemSet::iterator KItemSet::begin()
 368 {
 369     return iterator(m_itemRanges.begin(), 0);
 370 }
 371
 372 inline KItemSet::const_iterator KItemSet::begin() const
 373 {
 374     return const_iterator(m_itemRanges.begin(), 0);
 375 }
 376
 377 inline KItemSet::const_iterator KItemSet::constBegin() const
 378 {
 379     return const_iterator(m_itemRanges.constBegin(), 0);
 380 }
 381
 382 inline KItemSet::iterator KItemSet::end()
 383 {
 384     return iterator(m_itemRanges.end(), 0);
 385 }
 386
 387 inline KItemSet::const_iterator KItemSet::end() const
 388 {
 389     return const_iterator(m_itemRanges.end(), 0);
 390 }
 391
 392 inline KItemSet::const_iterator KItemSet::constEnd() const
 393 {
 394     return const_iterator(m_itemRanges.constEnd(), 0);
 395 }
 396
 397 inline int KItemSet::first() const
 398 {
 399     return m_itemRanges.first().index;
 400 }
 401
 402 inline int KItemSet::last() const
 403 {
 404     const KItemRange &lastRange = m_itemRanges.last();
 405     return lastRange.index + lastRange.count - 1;
 406 }
 407
 408 inline KItemSet &KItemSet::operator<<(int i)
 409 {
 410     insert(i);
 411     return *this;
 412 }
 413
 414 #endif