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