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