File indexing completed on 2024-04-28 05:45:10

 /*
  * SPDX-FileCopyrightText: 2013 Frank Reininghaus <frank78ac@googlemail.com>
  *
  * SPDX-License-Identifier: GPL-2.0-or-later
  */
 
 #ifndef KITEMSET_H
 #define KITEMSET_H
 
 #include "dolphin_export.h"
 #include "kitemviews/kitemrange.h"
 
 /**
  * @brief Stores a set of integer numbers in a space-efficient way.
  *
  * This class is similar to QSet<int>, but it has the following advantages:
  *
  * 1. It uses less memory than a QSet<int> if many consecutive numbers are
  *    stored. This is achieved by not storing each number separately, but
  *    "ranges" of numbers.
  *
  *    Example: The set {1, 2, 3, 4, 5} is represented by a single range which
  *    starts at 1 and has the length 5.
  *
  * 2. When iterating through a KItemSet using KItemSet::iterator or
  *    KItemSet::const_iterator, the numbers are traversed in ascending order.
  *
  * The complexity of most operations depends on the number of ranges.
  */
 
 class DOLPHIN_EXPORT KItemSet
 {
 public:
     KItemSet();
     KItemSet(const KItemSet &other);
     ~KItemSet();
     KItemSet &operator=(const KItemSet &other);
 
     /**
      * Returns the number of items in the set.
      * Complexity: O(log(number of ranges)).
      */
     int count() const;
 
     bool isEmpty() const;
     void clear();
 
     bool operator==(const KItemSet &other) const;
     bool operator!=(const KItemSet &other) const;
 
     class iterator
     {
         iterator(const KItemRangeList::iterator &rangeIt, int offset = 0)
             : m_rangeIt(rangeIt)
             , m_offset(offset)
         {
         }
 
     public:
         iterator(const iterator &other)
             : m_rangeIt(other.m_rangeIt)
             , m_offset(other.m_offset)
         {
         }
 
         iterator &operator=(const iterator &other)
         {
             m_rangeIt = other.m_rangeIt;
             m_offset = other.m_offset;
             return *this;
         }
 
         ~iterator() = default;
 
         int operator*() const
         {
             return m_rangeIt->index + m_offset;
         }
 
         inline bool operator==(const iterator &other) const
         {
             return m_rangeIt == other.m_rangeIt && m_offset == other.m_offset;
         }
 
         inline bool operator!=(const iterator &other) const
         {
             return !(*this == other);
         }
 
         inline iterator &operator++()
         {
             ++m_offset;
 
             if (m_offset == m_rangeIt->count) {
                 ++m_rangeIt;
                 m_offset = 0;
             }
 
             return *this;
         }
 
         inline iterator operator++(int)
         {
             iterator r = *this;
             ++(*this);
             return r;
         }
 
         inline iterator &operator--()
         {
             if (m_offset == 0) {
                 --m_rangeIt;
                 m_offset = m_rangeIt->count - 1;
             } else {
                 --m_offset;
             }
 
             return *this;
         }
 
         inline iterator operator--(int)
         {
             iterator r = *this;
             --(*this);
             return r;
         }
 
     private:
         KItemRangeList::iterator m_rangeIt;
         int m_offset;
 
         friend class const_iterator;
         friend class KItemSet;
     };
 
     class const_iterator
     {
         const_iterator(KItemRangeList::const_iterator rangeIt, int offset = 0)
             : m_rangeIt(rangeIt)
             , m_offset(offset)
         {
         }
 
     public:
         const_iterator(const const_iterator &other)
             : m_rangeIt(other.m_rangeIt)
             , m_offset(other.m_offset)
         {
         }
 
         explicit const_iterator(const iterator &other)
             : m_rangeIt(other.m_rangeIt)
             , m_offset(other.m_offset)
         {
         }
 
         const_iterator &operator=(const const_iterator &other)
         {
             m_rangeIt = other.m_rangeIt;
             m_offset = other.m_offset;
             return *this;
         }
 
         ~const_iterator() = default;
 
         int operator*() const
         {
             return m_rangeIt->index + m_offset;
         }
 
         inline bool operator==(const const_iterator &other) const
         {
             return m_rangeIt == other.m_rangeIt && m_offset == other.m_offset;
         }
 
         inline bool operator!=(const const_iterator &other) const
         {
             return !(*this == other);
         }
 
         inline const_iterator &operator++()
         {
             ++m_offset;
 
             if (m_offset == m_rangeIt->count) {
                 ++m_rangeIt;
                 m_offset = 0;
             }
 
             return *this;
         }
 
         inline const_iterator operator++(int)
         {
             const_iterator r = *this;
             ++(*this);
             return r;
         }
 
         inline const_iterator &operator--()
         {
             if (m_offset == 0) {
                 --m_rangeIt;
                 m_offset = m_rangeIt->count - 1;
             } else {
                 --m_offset;
             }
 
             return *this;
         }
 
         inline const_iterator operator--(int)
         {
             const_iterator r = *this;
             --(*this);
             return r;
         }
 
     private:
         KItemRangeList::const_iterator m_rangeIt;
         int m_offset;
 
         friend class KItemSet;
     };
 
     class const_reverse_iterator
     {
     public:
         const_reverse_iterator(KItemSet::const_iterator rangeIt)
             : m_current(rangeIt)
         {
         }
 
         const_reverse_iterator(const KItemSet::const_reverse_iterator &other)
             : m_current(other.base())
         {
         }
 
         int operator*() const
         {
             // analog to std::prev
             auto t = const_iterator(m_current);
             --t;
             return *t;
         }
 
         inline bool operator==(const const_reverse_iterator &other) const
         {
             return m_current == other.m_current;
         }
 
         bool operator!=(const const_reverse_iterator &other) const
         {
             return !(*this == other);
         }
 
         const_reverse_iterator &operator++()
         {
             --m_current;
             return *this;
         }
         const_reverse_iterator operator++(int)
         {
             auto tmp = *this;
             ++(*this);
             return tmp;
         }
 
         const_reverse_iterator &operator--()
         {
             ++m_current;
             return *this;
         }
         const_reverse_iterator operator--(int)
         {
             auto tmp = *this;
             --(*this);
             return tmp;
         }
 
         KItemSet::const_iterator base() const
         {
             return m_current;
         }
 
     private:
         KItemSet::const_iterator m_current;
     };
 
     iterator begin();
     const_iterator begin() const;
     const_iterator constBegin() const;
     iterator end();
     const_iterator end() const;
     const_iterator constEnd() const;
 
     const_reverse_iterator rend() const;
     const_reverse_iterator rbegin() const;
 
     int first() const;
     int last() const;
 
     bool contains(int i) const;
     iterator insert(int i);
     iterator find(int i);
     const_iterator constFind(int i) const;
     bool remove(int i);
     iterator erase(iterator it);
 
     /**
      * Returns a new set which contains all items that are contained in this
      * KItemSet, in \a other, or in both.
      */
     KItemSet operator+(const KItemSet &other) const;
 
     /**
      * Returns a new set which contains all items that are contained either in
      * this KItemSet, or in \a other, but not in both (the symmetric difference
      * of both KItemSets).
      */
     KItemSet operator^(const KItemSet &other) const;
 
     KItemSet &operator<<(int i);
 
 private:
     /**
      * Returns true if the KItemSet is valid, and false otherwise.
      * A valid KItemSet must store the item ranges in ascending order, and
      * the ranges must not overlap.
      */
     bool isValid() const;
 
     /**
      * This function returns an iterator that points to the KItemRange which
      * contains i, or m_itemRanges.end() if no such range exists.
      */
     KItemRangeList::iterator rangeForItem(int i);
 
     /**
      * This function returns an iterator that points to the KItemRange which
      * contains i, or m_itemRanges.constEnd() if no such range exists.
      */
     KItemRangeList::const_iterator constRangeForItem(int i) const;
 
     KItemRangeList m_itemRanges;
 
     friend class KItemSetTest;
 };
 
 inline KItemSet::KItemSet()
     : m_itemRanges()
 {
 }
 
 inline KItemSet::KItemSet(const KItemSet &other)
     : m_itemRanges(other.m_itemRanges)
 {
 }
 
 inline KItemSet::~KItemSet() = default;
 
 inline KItemSet &KItemSet::operator=(const KItemSet &other)
 {
     m_itemRanges = other.m_itemRanges;
     return *this;
 }
 
 inline int KItemSet::count() const
 {
     int result = 0;
     for (const KItemRange &range : std::as_const(m_itemRanges)) {
         result += range.count;
     }
     return result;
 }
 
 inline bool KItemSet::isEmpty() const
 {
     return m_itemRanges.isEmpty();
 }
 
 inline void KItemSet::clear()
 {
     m_itemRanges.clear();
 }
 
 inline bool KItemSet::operator==(const KItemSet &other) const
 {
     return m_itemRanges == other.m_itemRanges;
 }
 
 inline bool KItemSet::operator!=(const KItemSet &other) const
 {
     return m_itemRanges != other.m_itemRanges;
 }
 
 inline bool KItemSet::contains(int i) const
 {
     const KItemRangeList::const_iterator it = constRangeForItem(i);
     return it != m_itemRanges.end();
 }
 
 inline KItemSet::iterator KItemSet::find(int i)
 {
     const KItemRangeList::iterator it = rangeForItem(i);
     if (it != m_itemRanges.end()) {
         return iterator(it, i - it->index);
     } else {
         return end();
     }
 }
 
 inline KItemSet::const_iterator KItemSet::constFind(int i) const
 {
     const KItemRangeList::const_iterator it = constRangeForItem(i);
     if (it != m_itemRanges.constEnd()) {
         return const_iterator(it, i - it->index);
     } else {
         return constEnd();
     }
 }
 
 inline bool KItemSet::remove(int i)
 {
     iterator it = find(i);
     if (it != end()) {
         erase(it);
         return true;
     } else {
         return false;
     }
 }
 
 inline KItemSet::iterator KItemSet::begin()
 {
     return iterator(m_itemRanges.begin());
 }
 
 inline KItemSet::const_iterator KItemSet::begin() const
 {
     return const_iterator(m_itemRanges.begin());
 }
 
 inline KItemSet::const_iterator KItemSet::constBegin() const
 {
     return const_iterator(m_itemRanges.constBegin());
 }
 
 inline KItemSet::iterator KItemSet::end()
 {
     return iterator(m_itemRanges.end());
 }
 
 inline KItemSet::const_iterator KItemSet::end() const
 {
     return const_iterator(m_itemRanges.end());
 }
 
 inline KItemSet::const_iterator KItemSet::constEnd() const
 {
     return const_iterator(m_itemRanges.constEnd());
 }
 
 inline int KItemSet::first() const
 {
     return m_itemRanges.first().index;
 }
 
 inline int KItemSet::last() const
 {
     const KItemRange &lastRange = m_itemRanges.last();
     return lastRange.index + lastRange.count - 1;
 }
 
 inline KItemSet::const_reverse_iterator KItemSet::rend() const
 {
     return KItemSet::const_reverse_iterator(constBegin());
 }
 
 inline KItemSet::const_reverse_iterator KItemSet::rbegin() const
 {
     return KItemSet::const_reverse_iterator(constEnd());
 }
 
 inline KItemSet &KItemSet::operator<<(int i)
 {
     insert(i);
     return *this;
 }
 
 #endif