src/kitemviews/kitemset.h

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