path: root/src/RunStyles.h

/** @file RunStyles.h
 ** Data structure used to store sparse styles.
 **/
// Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
// The License.txt file describes the conditions under which this software may be distributed.

/// Styling buffer using one element for each run rather than using
/// a filled buffer.

#ifndef RUNSTYLES_H
#define RUNSTYLES_H

namespace Scintilla::Internal {

// Return for RunStyles::FillRange reports if anything was changed and the
// range that was changed. This may be trimmed from the requested range
// when some of the requested range already had the requested value.
template <typename DISTANCE>
struct FillResult {
	bool changed;
	DISTANCE position;
	DISTANCE fillLength;
};

template <typename DISTANCE, typename STYLE>
class RunStyles {
private:
	Partitioning<DISTANCE> starts;
	SplitVector<STYLE> styles;

	// Find the first run at a position
	DISTANCE RunFromPosition(DISTANCE position) const noexcept {
		DISTANCE run = starts.PartitionFromPosition(position);
		// Go to first element with this position
		while ((run > 0) && (position == starts.PositionFromPartition(run-1))) {
			run--;
		}
		return run;
	}

	// If there is no run boundary at position, insert one continuing style.
	DISTANCE SplitRun(DISTANCE position) {
		DISTANCE run = RunFromPosition(position);
		const DISTANCE posRun = starts.PositionFromPartition(run);
		if (posRun < position) {
			STYLE runStyle = ValueAt(position);
			run++;
			starts.InsertPartition(run, position);
			styles.InsertValue(run, 1, runStyle);
		}
		return run;
	}

	void RemoveRun(DISTANCE run) {
		starts.RemovePartition(run);
		styles.DeleteRange(run, 1);
	}

	void RemoveRunIfEmpty(DISTANCE run) {
		if ((run < starts.Partitions()) && (starts.Partitions() > 1)) {
			if (starts.PositionFromPartition(run) == starts.PositionFromPartition(run+1)) {
				RemoveRun(run);
			}
		}
	}

	void RemoveRunIfSameAsPrevious(DISTANCE run) {
		if ((run > 0) && (run < starts.Partitions())) {
			const DISTANCE runBefore = run - 1;
			if (styles.ValueAt(runBefore) == styles.ValueAt(run)) {
				RemoveRun(run);
			}
		}
	}

public:
	RunStyles() {
		styles.InsertValue(0, 2, 0);
	}

	DISTANCE Length() const noexcept {
		return starts.PositionFromPartition(starts.Partitions());
	}

	STYLE ValueAt(DISTANCE position) const noexcept {
		return styles.ValueAt(starts.PartitionFromPosition(position));
	}

	DISTANCE FindNextChange(DISTANCE position, DISTANCE end) const noexcept {
		const DISTANCE run = starts.PartitionFromPosition(position);
		if (run < starts.Partitions()) {
			const DISTANCE runChange = starts.PositionFromPartition(run);
			if (runChange > position)
				return runChange;
			const DISTANCE nextChange = starts.PositionFromPartition(run + 1);
			if (nextChange > position) {
				return nextChange;
			} else if (position < end) {
				return end;
			} else {
				return end + 1;
			}
		} else {
			return end + 1;
		}
	}

	DISTANCE StartRun(DISTANCE position) const noexcept {
		return starts.PositionFromPartition(starts.PartitionFromPosition(position));
	}

	DISTANCE EndRun(DISTANCE position) const noexcept {
		return starts.PositionFromPartition(starts.PartitionFromPosition(position) + 1);
	}

	FillResult<DISTANCE> FillRange(DISTANCE position, STYLE value, DISTANCE fillLength) {
		const FillResult<DISTANCE> resultNoChange{false, position, fillLength};
		if (fillLength <= 0) {
			return resultNoChange;
		}
		DISTANCE end = position + fillLength;
		if (end > Length()) {
			return resultNoChange;
		}
		DISTANCE runEnd = RunFromPosition(end);
		const STYLE valueCurrent = styles.ValueAt(runEnd);
		if (valueCurrent == value) {
			// End already has value so trim range.
			end = starts.PositionFromPartition(runEnd);
			if (position >= end) {
				// Whole range is already same as value so no action
				return resultNoChange;
			}
			fillLength = end - position;
		} else {
			const DISTANCE startRun = starts.PositionFromPartition(runEnd);
			if (position > startRun) {
				const DISTANCE runNext = runEnd + 1;
				const DISTANCE endRun = starts.PositionFromPartition(runNext);
				if (end < endRun) {
					// New piece is completely inside a run with a different value so its a simple
					// insertion of two points [ (position, value), (end, valueCurrent) ]
					const DISTANCE range[] { position, end};
					starts.InsertPartitions(runEnd + 1, range, 2);
					// Temporary runEndIndex silences non-useful arithmetic overflow warnings
					const ptrdiff_t runEndIndex = runEnd;
					styles.Insert(runEndIndex + 1, value);
					styles.Insert(runEndIndex + 2, valueCurrent);
					return { true, position, fillLength };
				}
			}
			runEnd = SplitRun(end);
		}
		DISTANCE runStart = RunFromPosition(position);
		if (styles.ValueAt(runStart) == value) {
			// Start is in expected value so trim range.
			runStart++;
			position = starts.PositionFromPartition(runStart);
			fillLength = end - position;
		} else {
			if (starts.PositionFromPartition(runStart) < position) {
				runStart = SplitRun(position);
				runEnd++;
			}
		}
		if (runStart < runEnd) {
			const FillResult<DISTANCE> result{ true, position, fillLength };
			styles.SetValueAt(runStart, value);
			// Remove each old run over the range
			for (DISTANCE run=runStart+1; run<runEnd; run++) {
				RemoveRun(runStart+1);
			}
			runEnd = RunFromPosition(end);
			RemoveRunIfSameAsPrevious(runEnd);
			RemoveRunIfSameAsPrevious(runStart);
			runEnd = RunFromPosition(end);
			RemoveRunIfEmpty(runEnd);
			return result;
		}
		return resultNoChange;
	}

	void SetValueAt(DISTANCE position, STYLE value) {
		FillRange(position, value, 1);
	}

	void InsertSpace(DISTANCE position, DISTANCE insertLength) {
		DISTANCE runStart = RunFromPosition(position);
		if (starts.PositionFromPartition(runStart) == position) {
			STYLE runStyle = ValueAt(position);
			// Inserting at start of run so make previous longer
			if (runStart == 0) {
				// Inserting at start of document so ensure 0
				if (runStyle) {
					styles.SetValueAt(0, STYLE());
					starts.InsertPartition(1, 0);
					styles.InsertValue(1, 1, runStyle);
					starts.InsertText(0, insertLength);
				} else {
					starts.InsertText(runStart, insertLength);
				}
			} else {
				if (runStyle) {
					starts.InsertText(runStart-1, insertLength);
				} else {
					// Insert at end of run so do not extend style
					starts.InsertText(runStart, insertLength);
				}
			}
		} else {
			starts.InsertText(runStart, insertLength);
		}
	}

	void DeleteAll() {
		starts = Partitioning<DISTANCE>();
		styles = SplitVector<STYLE>();
		styles.InsertValue(0, 2, 0);
	}

	void DeleteRange(DISTANCE position, DISTANCE deleteLength) {
		DISTANCE end = position + deleteLength;
		DISTANCE runStart = RunFromPosition(position);
		DISTANCE runEnd = RunFromPosition(end);
		if (runStart == runEnd) {
			// Deleting from inside one run
			starts.InsertText(runStart, -deleteLength);
			RemoveRunIfEmpty(runStart);
		} else {
			runStart = SplitRun(position);
			runEnd = SplitRun(end);
			starts.InsertText(runStart, -deleteLength);
			// Remove each old run over the range
			for (DISTANCE run=runStart; run<runEnd; run++) {
				RemoveRun(runStart);
			}
			RemoveRunIfEmpty(runStart);
			RemoveRunIfSameAsPrevious(runStart);
		}
	}

	DISTANCE Runs() const noexcept {
		return starts.Partitions();
	}

	bool AllSame() const noexcept {
		for (DISTANCE run = 1; run < starts.Partitions(); run++) {
			const DISTANCE runBefore = run - 1;
			if (styles.ValueAt(run) != styles.ValueAt(runBefore))
				return false;
		}
		return true;
	}

	bool AllSameAs(STYLE value) const noexcept {
		return AllSame() && (styles.ValueAt(0) == value);
	}

	DISTANCE Find(STYLE value, DISTANCE start) const noexcept {
		if (start < Length()) {
			DISTANCE run = start ? RunFromPosition(start) : 0;
			if (styles.ValueAt(run) == value)
				return start;
			run++;
			while (run < starts.Partitions()) {
				if (styles.ValueAt(run) == value)
					return starts.PositionFromPartition(run);
				run++;
			}
		}
		return -1;
	}

	void Check() const {
		if (Length() < 0) {
			throw std::runtime_error("RunStyles: Length can not be negative.");
		}
		if (starts.Partitions() < 1) {
			throw std::runtime_error("RunStyles: Must always have 1 or more partitions.");
		}
		if (starts.Partitions() != styles.Length()-1) {
			throw std::runtime_error("RunStyles: Partitions and styles different lengths.");
		}
		DISTANCE start=0;
		while (start < Length()) {
			const DISTANCE end = EndRun(start);
			if (start >= end) {
				throw std::runtime_error("RunStyles: Partition is 0 length.");
			}
			start = end;
		}
		if (styles.ValueAt(styles.Length()-1) != 0) {
			throw std::runtime_error("RunStyles: Unused style at end changed.");
		}
		for (ptrdiff_t j=1; j<styles.Length()-1; j++) {
			if (styles.ValueAt(j) == styles.ValueAt(j-1)) {
				throw std::runtime_error("RunStyles: Style of a partition same as previous.");
			}
		}
	}
};

}

#endif