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