diff options
| -rw-r--r-- | scripts/HeaderOrder.txt | 6 | ||||
| -rw-r--r-- | src/SparseVector.h | 186 | ||||
| -rw-r--r-- | test/unit/testSparseVector.cxx | 185 |
3 files changed, 377 insertions, 0 deletions
diff --git a/scripts/HeaderOrder.txt b/scripts/HeaderOrder.txt index df4f0f4a2..cbfdf6f3f 100644 --- a/scripts/HeaderOrder.txt +++ b/scripts/HeaderOrder.txt @@ -21,6 +21,7 @@ #include <cstring> #include <cctype> #include <cstdio> +#include <cstdarg> #include <cmath> // C++ standard library @@ -98,6 +99,7 @@ #include "SplitVector.h" #include "Partitioning.h" #include "RunStyles.h" +#include "SparseVector.h" #include "ContractionState.h" #include "CellBuffer.h" #include "PerLine.h" @@ -148,3 +150,7 @@ #import "ScintillaView.h" #import "ScintillaCocoa.h" #import "PlatCocoa.h" + +// Catch testing framework +#include "catch.hpp" + diff --git a/src/SparseVector.h b/src/SparseVector.h new file mode 100644 index 000000000..f96b36b8b --- /dev/null +++ b/src/SparseVector.h @@ -0,0 +1,186 @@ +// Scintilla source code edit control +/** @file SparseVector.h + ** Hold data sparsely associated with elements in a range. + **/ +// Copyright 2016 by Neil Hodgson <neilh@scintilla.org> +// The License.txt file describes the conditions under which this software may be distributed. + +#ifndef SPARSEVECTOR_H +#define SPARSEVECTOR_H + +#ifdef SCI_NAMESPACE +namespace Scintilla { +#endif + +// SparseVector is similar to RunStyles but is more efficient for cases where values occur +// for one position instead of over a range of positions. +template <typename T> +class SparseVector { +private: + Partitioning *starts; + SplitVector<T> *values; + // Private so SparseVector objects can not be copied + SparseVector(const SparseVector &); + void ClearValue(int partition) { + values->SetValueAt(partition, T()); + } + void CommonSetValueAt(int position, T value) { + // Do the work of setting the value to allow for specialization of SetValueAt. + assert(position < Length()); + const int partition = starts->PartitionFromPosition(position); + const int startPartition = starts->PositionFromPartition(partition); + if (value == T()) { + // Setting the empty value is equivalent to deleting the position + if (position == 0) { + ClearValue(partition); + } else if (position == startPartition) { + // Currently an element at this position, so remove + ClearValue(partition); + starts->RemovePartition(partition); + values->Delete(partition); + } + // Else element remains empty + } else { + if (position == startPartition) { + // Already a value at this position, so replace + ClearValue(partition); + values->SetValueAt(partition, value); + } else { + // Insert a new element + starts->InsertPartition(partition + 1, position); + values->InsertValue(partition + 1, 1, value); + } + } + } +public: + SparseVector() { + starts = new Partitioning(8); + values = new SplitVector<T>(); + values->InsertValue(0, 2, T()); + } + ~SparseVector() { + delete starts; + starts = NULL; + // starts dead here but not used by ClearValue. + for (int part = 0; part < values->Length(); part++) { + ClearValue(part); + } + delete values; + values = NULL; + } + int Length() const { + return starts->PositionFromPartition(starts->Partitions()); + } + int Elements() const { + return starts->Partitions(); + } + int PositionOfElement(int element) const { + return starts->PositionFromPartition(element); + } + T ValueAt(int position) const { + assert(position < Length()); + const int partition = starts->PartitionFromPosition(position); + const int startPartition = starts->PositionFromPartition(partition); + if (startPartition == position) { + return values->ValueAt(partition); + } else { + return T(); + } + } + void SetValueAt(int position, T value) { + CommonSetValueAt(position, value); + } + void InsertSpace(int position, int insertLength) { + assert(position <= Length()); // Only operation that works at end. + const int partition = starts->PartitionFromPosition(position); + const int startPartition = starts->PositionFromPartition(partition); + if (startPartition == position) { + T valueCurrent = values->ValueAt(partition); + // Inserting at start of run so make previous longer + if (partition == 0) { + // Inserting at start of document so ensure 0 + if (valueCurrent != T()) { + ClearValue(0); + starts->InsertPartition(1, 0); + values->InsertValue(1, 1, valueCurrent); + starts->InsertText(0, insertLength); + } else { + starts->InsertText(partition, insertLength); + } + } else { + if (valueCurrent != T()) { + starts->InsertText(partition - 1, insertLength); + } else { + // Insert at end of run so do not extend style + starts->InsertText(partition, insertLength); + } + } + } else { + starts->InsertText(partition, insertLength); + } + } + void DeletePosition(int position) { + assert(position < Length()); + int partition = starts->PartitionFromPosition(position); + const int startPartition = starts->PositionFromPartition(partition); + if (startPartition == position) { + if (partition == 0) { + ClearValue(0); + } else if (partition == starts->Partitions()) { + // This should not be possible + ClearValue(partition); + throw std::runtime_error("SparseVector: deleting end partition."); + } else { + ClearValue(partition); + starts->RemovePartition(partition); + values->Delete(partition); + // Its the previous partition now that gets smaller + partition--; + } + } + starts->InsertText(partition, -1); + } + void Check() const { + if (Length() < 0) { + throw std::runtime_error("SparseVector: Length can not be negative."); + } + if (starts->Partitions() < 1) { + throw std::runtime_error("SparseVector: Must always have 1 or more partitions."); + } + if (starts->Partitions() != values->Length() - 1) { + throw std::runtime_error("SparseVector: Partitions and values different lengths."); + } + // The final element can not be set + if (values->ValueAt(values->Length() - 1) != T()) { + throw std::runtime_error("SparseVector: Unused style at end changed."); + } + } +}; + +// The specialization for const char * makes copies and deletes them as needed. + +template<> +inline void SparseVector<const char *>::ClearValue(int partition) { + const char *value = values->ValueAt(partition); + delete []value; + values->SetValueAt(partition, NULL); +} + +template<> +inline void SparseVector<const char *>::SetValueAt(int position, const char *value) { + // Make a copy of the string + if (value) { + const size_t len = strlen(value); + char *valueCopy = new char[len + 1](); + std::copy(value, value + len, valueCopy); + CommonSetValueAt(position, valueCopy); + } else { + CommonSetValueAt(position, NULL); + } +} + +#ifdef SCI_NAMESPACE +} +#endif + +#endif diff --git a/test/unit/testSparseVector.cxx b/test/unit/testSparseVector.cxx new file mode 100644 index 000000000..11960163e --- /dev/null +++ b/test/unit/testSparseVector.cxx @@ -0,0 +1,185 @@ +// Unit Tests for Scintilla internal data structures + +#include <string.h> + +#include <cassert> + +#include <stdexcept> +#include <algorithm> + +#include "Platform.h" + +#include "Position.h" +#include "SplitVector.h" +#include "Partitioning.h" +#include "SparseVector.h" + +#include "catch.hpp" + +// Test SparseVector. + +// Helper to produce a string representation of a SparseVector<const char *> +// to simplify checks. +static std::string Representation(const SparseVector<const char *> &st) { + std::string ret; + for (int i = 0;i < st.Length();i++) { + const char *value = st.ValueAt(i); + if (value) + ret += value; + else + ret += "-"; + } + return ret; +} + +TEST_CASE("SparseVector") { + + SparseVector<const char *> st; + + SECTION("IsEmptyInitially") { + REQUIRE(1 == st.Elements()); + REQUIRE(0 == st.Length()); + st.Check(); + } + + SECTION("InsertSpace") { + st.InsertSpace(0, 5); + REQUIRE(1 == st.Elements()); + REQUIRE(static_cast<const char *>(NULL) == st.ValueAt(0)); + REQUIRE(static_cast<const char *>(NULL) == st.ValueAt(1)); + REQUIRE(static_cast<const char *>(NULL) == st.ValueAt(4)); + st.Check(); + } + + SECTION("InsertValue") { + st.InsertSpace(0, 5); + st.SetValueAt(3, "3"); + REQUIRE(2 == st.Elements()); + REQUIRE("---3-" == Representation(st)); + st.Check(); + } + + SECTION("InsertAndDeleteValue") { + st.InsertSpace(0, 5); + REQUIRE(5 == st.Length()); + st.SetValueAt(3, "3"); + REQUIRE(2 == st.Elements()); + st.DeletePosition(3); + REQUIRE(1 == st.Elements()); + REQUIRE(4 == st.Length()); + REQUIRE("----" == Representation(st)); + st.Check(); + } + + SECTION("InsertAndDeleteAtStart") { + REQUIRE(1 == st.Elements()); + st.InsertSpace(0, 5); + st.SetValueAt(0, "3"); + REQUIRE(1 == st.Elements()); + REQUIRE("3----" == Representation(st)); + st.DeletePosition(0); + REQUIRE(1 == st.Elements()); + REQUIRE("----" == Representation(st)); + st.SetValueAt(0, "4"); + REQUIRE(1 == st.Elements()); + REQUIRE("4---" == Representation(st)); + st.DeletePosition(0); + REQUIRE(1 == st.Elements()); + REQUIRE("---" == Representation(st)); + st.Check(); + } + + SECTION("InsertAndDeleteAtEnd") { + REQUIRE(1 == st.Elements()); + st.InsertSpace(0, 5); + st.SetValueAt(4, "5"); + REQUIRE(2 == st.Elements()); + REQUIRE("----5" == Representation(st)); + st.DeletePosition(4); + REQUIRE(1 == st.Elements()); + REQUIRE("----" == Representation(st)); + st.Check(); + } + + SECTION("SetNULL") { + REQUIRE(1 == st.Elements()); + st.InsertSpace(0, 5); + st.SetValueAt(4, "5"); + REQUIRE(2 == st.Elements()); + REQUIRE("----5" == Representation(st)); + st.SetValueAt(4, NULL); + REQUIRE(1 == st.Elements()); + REQUIRE("-----" == Representation(st)); + st.Check(); + } + + SECTION("DeleteAll") { + REQUIRE(1 == st.Elements()); + st.InsertSpace(0, 10); + st.SetValueAt(9, "9"); + st.SetValueAt(7, "7"); + st.SetValueAt(4, "4"); + st.SetValueAt(3, "3"); + REQUIRE(5 == st.Elements()); + REQUIRE("---34--7-9" == Representation(st)); + st.Check(); + } + +} + +TEST_CASE("SparseTextInt") { + + SparseVector<int> st; + + SECTION("InsertAndDeleteValue") { + st.InsertSpace(0, 5); + st.SetValueAt(3, 3); + REQUIRE(2 == st.Elements()); + REQUIRE(0 == st.ValueAt(0)); + REQUIRE(0 == st.ValueAt(1)); + REQUIRE(0 == st.ValueAt(2)); + REQUIRE(3 == st.ValueAt(3)); + REQUIRE(0 == st.ValueAt(4)); + st.SetValueAt(3, -3); + REQUIRE(2 == st.Elements()); + REQUIRE(0 == st.ValueAt(0)); + REQUIRE(0 == st.ValueAt(1)); + REQUIRE(0 == st.ValueAt(2)); + REQUIRE(-3 == st.ValueAt(3)); + REQUIRE(0 == st.ValueAt(4)); + st.SetValueAt(3, 0); + REQUIRE(1 == st.Elements()); + REQUIRE(0 == st.ValueAt(0)); + REQUIRE(0 == st.ValueAt(1)); + REQUIRE(0 == st.ValueAt(2)); + REQUIRE(0 == st.ValueAt(3)); + REQUIRE(0 == st.ValueAt(4)); + st.Check(); + } +} + +TEST_CASE("SparseTextString") { + + SparseVector<std::string> st; + + SECTION("InsertAndDeleteValue") { + st.InsertSpace(0, 5); + REQUIRE(5 == st.Length()); + st.SetValueAt(3, "3"); + REQUIRE(2 == st.Elements()); + REQUIRE("" == st.ValueAt(0)); + REQUIRE("" == st.ValueAt(2)); + REQUIRE("3" == st.ValueAt(3)); + REQUIRE("" == st.ValueAt(4)); + st.DeletePosition(0); + REQUIRE(4 == st.Length()); + REQUIRE("3" == st.ValueAt(2)); + st.DeletePosition(2); + REQUIRE(1 == st.Elements()); + REQUIRE(3 == st.Length()); + REQUIRE("" == st.ValueAt(0)); + REQUIRE("" == st.ValueAt(1)); + REQUIRE("" == st.ValueAt(2)); + st.Check(); + } +} |