Method flatten

genericrange.h:114–145

	public:
		static void flatten(vector<GenericRange<T>>& intervals)
		{
			// Make a flat list of intervals, with each interval having all elements found in it
			// TODO: using a vector isn't ideal, since each modification not at front or back is O(n)
			std::sort(intervals.begin(), intervals.end());
			auto itr = intervals.begin();
			while (itr != intervals.end())
			{
				auto currentRange = *itr;
				auto nextRange = std::next(itr);
				if (nextRange == intervals.end()) // This is the last interval
					break;

				if (auto splitRanges = currentRange.split(*nextRange); splitRanges.size())
				{
					itr = intervals.erase(itr, std::next(nextRange)); // Remove the two source ranges that were split
					size_t resetIndex = intervals.size() + splitRanges.size() - 1; // This is where the iterator will be moved to after inserting new ranges
					for (const auto& range : splitRanges)
					{
						// For each split range, insert it in its sorted position
						auto rangeInsertItr = std::upper_bound(intervals.begin(), intervals.end(), range);
						size_t rangeInsertIndex = rangeInsertItr - intervals.begin();
						intervals.insert(rangeInsertItr, range);
						// Move the reset index to before the lowest inserted range's index; everything before is still sorted
						resetIndex = std::min(resetIndex, rangeInsertIndex == 0 ? 0 : rangeInsertIndex - 1);
					}
					itr = intervals.begin() + resetIndex;
				}
				else
					++itr;
			}
		}

		GenericRangeMap()
		{