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
  */
 
 #include "kitemset.h"
 
 KItemSet::iterator KItemSet::insert(int i)
 {
     if (m_itemRanges.empty()) {
         m_itemRanges.push_back(KItemRange(i, 1));
         return iterator(m_itemRanges.begin(), 0);
     }
 
     KItemRangeList::iterator rangeBegin = m_itemRanges.begin();
     if (i < rangeBegin->index) {
         // The inserted index is smaller than all existing items.
         if (i == rangeBegin->index - 1) {
             // Move the beginning of the first range one item to the front.
             --rangeBegin->index;
             ++rangeBegin->count;
         } else {
             // Insert a new range at the beginning.
             rangeBegin = m_itemRanges.insert(rangeBegin, KItemRange(i, 1));
         }
 
         return iterator(rangeBegin, 0);
     }
 
     KItemRangeList::iterator rangeEnd = m_itemRanges.end();
     KItemRangeList::iterator lastRange = rangeEnd - 1;
     if (i >= lastRange->index) {
         // i either belongs to the last range, or it is larger than all existing items.
         const int lastItemPlus1 = lastRange->index + lastRange->count;
         if (i == lastItemPlus1) {
             // Move the end of the last range one item to the back.
             ++lastRange->count;
         } else if (i > lastItemPlus1) {
             // Append a new range.
             lastRange = m_itemRanges.insert(rangeEnd, KItemRange(i, 1));
         }
 
         return iterator(lastRange, i - lastRange->index);
     }
 
     // We know that i is between the smallest existing item and the first item
     // of the last range. Find the lowest range whose 'index' is smaller than i.
     KItemRangeList::iterator low = rangeBegin;
     KItemRangeList::iterator high = lastRange;
 
     while (low + 1 != high) {
         const int span = high - low;
         Q_ASSERT(span >= 2);
 
         KItemRangeList::iterator mid = low + span / 2;
         if (mid->index > i) {
             high = mid;
         } else {
             low = mid;
         }
     }
 
     Q_ASSERT(low->index <= i && high->index > i);
 
     if (i == low->index + low->count) {
         // i is just one item behind the range low.
         if (i == high->index - 1) {
             // i closes the gap between low and high. Merge the two ranges.
             const int newRangeCount = low->count + 1 + high->count;
             KItemRangeList::iterator behindNewRange = m_itemRanges.erase(high);
             KItemRangeList::iterator newRange = behindNewRange - 1;
             newRange->count = newRangeCount;
             return iterator(newRange, i - newRange->index);
         } else {
             // Extend low by one item.
             ++low->count;
             return iterator(low, low->count - 1);
         }
     } else if (i > low->index + low->count) {
         if (i == high->index - 1) {
             // Extend high by one item to the front.
             --high->index;
             ++high->count;
             return iterator(high, 0);
         } else {
             // Insert a new range between low and high.
             KItemRangeList::iterator newRange = m_itemRanges.insert(high, KItemRange(i, 1));
             return iterator(newRange, 0);
         }
     } else {
         // The range low already contains i.
         return iterator(low, i - low->index);
     }
 }
 
 KItemSet::iterator KItemSet::erase(iterator it)
 {
     KItemRangeList::iterator rangeIt = it.m_rangeIt;
 
     if (it.m_offset == 0) {
         // Removed index is at the beginning of a range.
         if (rangeIt->count > 1) {
             ++rangeIt->index;
             --rangeIt->count;
         } else {
             // The range only contains the removed index.
             rangeIt = m_itemRanges.erase(rangeIt);
         }
         return iterator(rangeIt, 0);
     } else if (it.m_offset == rangeIt->count - 1) {
         // Removed index is at the end of a range.
         --rangeIt->count;
         ++rangeIt;
         return iterator(rangeIt, 0);
     } else {
         // The removed index is in the middle of a range.
         const int newRangeIndex = *it + 1;
         const int newRangeCount = rangeIt->count - it.m_offset - 1;
         const KItemRange newRange(newRangeIndex, newRangeCount);
 
         rangeIt->count = it.m_offset;
         ++rangeIt;
         rangeIt = m_itemRanges.insert(rangeIt, newRange);
 
         return iterator(rangeIt, 0);
     }
 }
 
 KItemSet KItemSet::operator+(const KItemSet &other) const
 {
     KItemSet sum;
 
     KItemRangeList::const_iterator it1 = m_itemRanges.constBegin();
     KItemRangeList::const_iterator it2 = other.m_itemRanges.constBegin();
 
     const KItemRangeList::const_iterator end1 = m_itemRanges.constEnd();
     const KItemRangeList::const_iterator end2 = other.m_itemRanges.constEnd();
 
     while (it1 != end1 || it2 != end2) {
         if (it1 == end1) {
             // We are past the end of 'this' already. Append all remaining
             // item ranges from 'other'.
             while (it2 != end2) {
                 sum.m_itemRanges.append(*it2);
                 ++it2;
             }
         } else if (it2 == end2) {
             // We are past the end of 'other' already. Append all remaining
             // item ranges from 'this'.
             while (it1 != end1) {
                 sum.m_itemRanges.append(*it1);
                 ++it1;
             }
         } else {
             // Find the beginning of the next range.
             int index = qMin(it1->index, it2->index);
             int count = 0;
 
             do {
                 if (it1 != end1 && it1->index <= index + count) {
                     // The next range from 'this' overlaps with the current range in the sum.
                     count = qMax(count, it1->index + it1->count - index);
                     ++it1;
                 }
 
                 if (it2 != end2 && it2->index <= index + count) {
                     // The next range from 'other' overlaps with the current range in the sum.
                     count = qMax(count, it2->index + it2->count - index);
                     ++it2;
                 }
             } while ((it1 != end1 && it1->index <= index + count) || (it2 != end2 && it2->index <= index + count));
 
             sum.m_itemRanges.append(KItemRange(index, count));
         }
     }
 
     return sum;
 }
 
 KItemSet KItemSet::operator^(const KItemSet &other) const
 {
     // We are looking for all ints which are either in *this or in other,
     // but not in both.
     KItemSet result;
 
     // When we go through all integers from INT_MIN to INT_MAX and start
     // in the state "do not add to result", every beginning/end of a range
     // of *this and other toggles the "add/do not add to result" state.
     // Therefore, we just have to put ints where any range starts/ends to
     // a sorted array, and then we can calculate the result quite easily.
     QVector<int> rangeBoundaries;
     rangeBoundaries.resize(2 * (m_itemRanges.count() + other.m_itemRanges.count()));
     const QVector<int>::iterator begin = rangeBoundaries.begin();
     const QVector<int>::iterator end = rangeBoundaries.end();
     QVector<int>::iterator it = begin;
 
     for (const KItemRange &range : std::as_const(m_itemRanges)) {
         *it++ = range.index;
         *it++ = range.index + range.count;
     }
 
     const QVector<int>::iterator middle = it;
 
     for (const KItemRange &range : std::as_const(other.m_itemRanges)) {
         *it++ = range.index;
         *it++ = range.index + range.count;
     }
     Q_ASSERT(it == end);
 
     std::inplace_merge(begin, middle, end);
 
     it = begin;
     while (it != end) {
         const int rangeBegin = *it;
         ++it;
 
         if (*it == rangeBegin) {
             // It seems that ranges from both *this and other start at
             // rangeBegin. Do not start a new range, but read the next int.
             //
             // Example: Consider the symmetric difference of the sets
             // {1, 2, 3, 4} and {1, 2}. The sorted list of range boundaries is
             // 1 1 3 5. Discarding the duplicate 1 yields the result
             // rangeBegin = 3, rangeEnd = 5, which corresponds to the set {3, 4}.
             ++it;
         } else {
             // The end of the current range is the next *single* int that we
             // find. If an int appears twice in rangeBoundaries, the range does
             // not end.
             //
             // Example: Consider the symmetric difference of the sets
             // {1, 2, 3, 4, 8, 9, 10} and {5, 6, 7}. The sorted list of range
             // boundaries is 1 5 5 8 8 11, and discarding all duplicates yields
             // the result rangeBegin = 1, rangeEnd = 11, which corresponds to
             // the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
             bool foundEndOfRange = false;
             int rangeEnd;
             do {
                 rangeEnd = *it;
                 ++it;
 
                 if (it == end || *it != rangeEnd) {
                     foundEndOfRange = true;
                 } else {
                     ++it;
                 }
             } while (!foundEndOfRange);
 
             result.m_itemRanges.append(KItemRange(rangeBegin, rangeEnd - rangeBegin));
         }
     }
 
     return result;
 }
 
 bool KItemSet::isValid() const
 {
     const KItemRangeList::const_iterator begin = m_itemRanges.constBegin();
     const KItemRangeList::const_iterator end = m_itemRanges.constEnd();
 
     for (KItemRangeList::const_iterator it = begin; it != end; ++it) {
         if (it->count <= 0) {
             return false;
         }
 
         if (it != begin) {
             const KItemRangeList::const_iterator previous = it - 1;
             if (previous->index + previous->count >= it->index) {
                 return false;
             }
         }
     }
 
     return true;
 }
 
 KItemRangeList::iterator KItemSet::rangeForItem(int i)
 {
     const KItemRangeList::iterator end = m_itemRanges.end();
     KItemRangeList::iterator low = m_itemRanges.begin();
     KItemRangeList::iterator high = end;
 
     if (low == end || low->index > i) {
         return end;
     }
 
     while (low != high && low + 1 != high) {
         KItemRangeList::iterator mid = low + (high - low) / 2;
         if (mid->index > i) {
             high = mid;
         } else {
             low = mid;
         }
     }
 
     Q_ASSERT(low->index <= i);
     if (low->index + low->count > i) {
         return low;
     }
 
     return end;
 }
 
 KItemRangeList::const_iterator KItemSet::constRangeForItem(int i) const
 {
     const KItemRangeList::const_iterator end = m_itemRanges.constEnd();
     KItemRangeList::const_iterator low = m_itemRanges.constBegin();
     KItemRangeList::const_iterator high = end;
 
     if (low == end || low->index > i) {
         return end;
     }
 
     while (low != high && low + 1 != high) {
         KItemRangeList::const_iterator mid = low + (high - low) / 2;
         if (mid->index > i) {
             high = mid;
         } else {
             low = mid;
         }
     }
 
     Q_ASSERT(low->index <= i);
     if (low->index + low->count > i) {
         return low;
     }
 
     return end;
 }