path: root/src/Partitioning.h

// Scintilla source code edit control
/** @file Partitioning.h
 ** Data structure used to partition an interval. Used for holding line start/end positions.
 **/
// Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
// The License.txt file describes the conditions under which this software may be distributed.

#ifndef PARTITIONING_H
#define PARTITIONING_H

namespace Scintilla {

/// A split vector of integers with a method for adding a value to all elements
/// in a range.
/// Used by the Partitioning class.

template <typename T>
class SplitVectorWithRangeAdd : public SplitVector<T> {
public:
	explicit SplitVectorWithRangeAdd(ptrdiff_t growSize_) {
		this->SetGrowSize(growSize_);
		this->ReAllocate(growSize_);
	}
	// Deleted so SplitVectorWithRangeAdd objects can not be copied.
	SplitVectorWithRangeAdd(const SplitVectorWithRangeAdd &) = delete;
	SplitVectorWithRangeAdd(SplitVectorWithRangeAdd &&) = delete;
	void operator=(const SplitVectorWithRangeAdd &) = delete;
	void operator=(SplitVectorWithRangeAdd &&) = delete;
	~SplitVectorWithRangeAdd() {
	}
	void RangeAddDelta(ptrdiff_t start, ptrdiff_t end, T delta) noexcept {
		// end is 1 past end, so end-start is number of elements to change
		ptrdiff_t i = 0;
		const ptrdiff_t rangeLength = end - start;
		ptrdiff_t range1Length = rangeLength;
		const ptrdiff_t part1Left = this->part1Length - start;
		if (range1Length > part1Left)
			range1Length = part1Left;
		while (i < range1Length) {
			this->body[start++] += delta;
			i++;
		}
		start += this->gapLength;
		while (i < rangeLength) {
			this->body[start++] += delta;
			i++;
		}
	}
};

/// Divide an interval into multiple partitions.
/// Useful for breaking a document down into sections such as lines.
/// A 0 length interval has a single 0 length partition, numbered 0
/// If interval not 0 length then each partition non-zero length
/// When needed, positions after the interval are considered part of the last partition
/// but the end of the last partition can be found with PositionFromPartition(last+1).

template <typename T>
class Partitioning {
private:
	// To avoid calculating all the partition positions whenever any text is inserted
	// there may be a step somewhere in the list.
	T stepPartition;
	T stepLength;
	std::unique_ptr<SplitVectorWithRangeAdd<T>> body;

	// Move step forward
	void ApplyStep(T partitionUpTo) noexcept {
		if (stepLength != 0) {
			body->RangeAddDelta(stepPartition+1, partitionUpTo + 1, stepLength);
		}
		stepPartition = partitionUpTo;
		if (stepPartition >= body->Length()-1) {
			stepPartition = Partitions();
			stepLength = 0;
		}
	}

	// Move step backward
	void BackStep(T partitionDownTo) noexcept {
		if (stepLength != 0) {
			body->RangeAddDelta(partitionDownTo+1, stepPartition+1, -stepLength);
		}
		stepPartition = partitionDownTo;
	}

	void Allocate(ptrdiff_t growSize) {
		body = std::make_unique<SplitVectorWithRangeAdd<T>>(growSize);
		stepPartition = 0;
		stepLength = 0;
		body->Insert(0, 0);	// This value stays 0 for ever
		body->Insert(1, 0);	// This is the end of the first partition and will be the start of the second
	}

public:
	explicit Partitioning(int growSize) : stepPartition(0), stepLength(0) {
		Allocate(growSize);
	}

	// Deleted so Partitioning objects can not be copied.
	Partitioning(const Partitioning &) = delete;
	Partitioning(Partitioning &&) = delete;
	void operator=(const Partitioning &) = delete;
	void operator=(Partitioning &&) = delete;

	~Partitioning() {
	}

	T Partitions() const noexcept {
		return static_cast<T>(body->Length())-1;
	}

	T Length() const noexcept {
		return PositionFromPartition(Partitions());
	}

	void InsertPartition(T partition, T pos) {
		if (stepPartition < partition) {
			ApplyStep(partition);
		}
		body->Insert(partition, pos);
		stepPartition++;
	}

	void InsertPartitions(T partition, const T *positions, size_t length) {
		if (stepPartition < partition) {
			ApplyStep(partition);
		}
		body->InsertFromArray(partition, positions, 0, length);
		stepPartition += static_cast<T>(length);
	}

	void InsertPartitionsWithCast(T partition, const ptrdiff_t *positions, size_t length) {
		// Used for 64-bit builds when T is 32-bits
		if (stepPartition < partition) {
			ApplyStep(partition);
		}
		T *pInsertion = body->InsertEmpty(partition, length);
		for (size_t i = 0; i < length; i++) {
			pInsertion[i] = static_cast<T>(positions[i]);
		}
		stepPartition += static_cast<T>(length);
	}

	void SetPartitionStartPosition(T partition, T pos) noexcept {
		ApplyStep(partition+1);
		if ((partition < 0) || (partition > body->Length())) {
			return;
		}
		body->SetValueAt(partition, pos);
	}

	void InsertText(T partitionInsert, T delta) noexcept {
		// Point all the partitions after the insertion point further along in the buffer
		if (stepLength != 0) {
			if (partitionInsert >= stepPartition) {
				// Fill in up to the new insertion point
				ApplyStep(partitionInsert);
				stepLength += delta;
			} else if (partitionInsert >= (stepPartition - body->Length() / 10)) {
				// Close to step but before so move step back
				BackStep(partitionInsert);
				stepLength += delta;
			} else {
				ApplyStep(Partitions());
				stepPartition = partitionInsert;
				stepLength = delta;
			}
		} else {
			stepPartition = partitionInsert;
			stepLength = delta;
		}
	}

	void RemovePartition(T partition) {
		if (partition > stepPartition) {
			ApplyStep(partition);
			stepPartition--;
		} else {
			stepPartition--;
		}
		body->Delete(partition);
	}

	T PositionFromPartition(T partition) const noexcept {
		PLATFORM_ASSERT(partition >= 0);
		PLATFORM_ASSERT(partition < body->Length());
		const ptrdiff_t lengthBody = body->Length();
		if ((partition < 0) || (partition >= lengthBody)) {
			return 0;
		}
		T pos = body->ValueAt(partition);
		if (partition > stepPartition)
			pos += stepLength;
		return pos;
	}

	/// Return value in range [0 .. Partitions() - 1] even for arguments outside interval
	T PartitionFromPosition(T pos) const noexcept {
		if (body->Length() <= 1)
			return 0;
		if (pos >= (PositionFromPartition(Partitions())))
			return Partitions() - 1;
		T lower = 0;
		T upper = Partitions();
		do {
			const T middle = (upper + lower + 1) / 2; 	// Round high
			T posMiddle = body->ValueAt(middle);
			if (middle > stepPartition)
				posMiddle += stepLength;
			if (pos < posMiddle) {
				upper = middle - 1;
			} else {
				lower = middle;
			}
		} while (lower < upper);
		return lower;
	}

	void DeleteAll() {
		Allocate(body->GetGrowSize());
	}

	void Check() const {
#ifdef CHECK_CORRECTNESS
		if (Length() < 0) {
			throw std::runtime_error("Partitioning: Length can not be negative.");
		}
		if (Partitions() < 1) {
			throw std::runtime_error("Partitioning: Must always have 1 or more partitions.");
		}
		if (Length() == 0) {
			if ((PositionFromPartition(0) != 0) || (PositionFromPartition(1) != 0)) {
				throw std::runtime_error("Partitioning: Invalid empty partitioning.");
			}
		} else {
			// Positions should be a strictly ascending sequence
			for (T i = 0; i < Partitions(); i++) {
				const T pos = PositionFromPartition(i);
				const T posNext = PositionFromPartition(i+1);
				if (pos > posNext) {
					throw std::runtime_error("Partitioning: Negative partition.");
				} else if (pos == posNext) {
					throw std::runtime_error("Partitioning: Empty partition.");
				}
			}
		}
#endif
	}

};


}

#endif