SparseVector.h

Go to the documentation of this file.

// 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
 
namespace Scintilla {
 
// SparseVector is similar to RunStyles but is more efficient for cases where values occur
// for one position instead of over a range of positions.
// There are always elements at the start and end, so the element type should have
// a reasonable empty value that will cause no problems.
// The element type should have a noexcept default constructor as that allows methods to
// be noexcept.
template <typename T>
class SparseVector {
private:
    std::unique_ptr<Partitioning<Sci::Position>> starts;
    std::unique_ptr<SplitVector<T>> values;
    T empty;    // Return from ValueAt when no element at a position.
    void ClearValue(Sci::Position partition) noexcept {
        values->SetValueAt(partition, T());
    }
public:
    SparseVector() : empty() {
        starts = Sci::make_unique<Partitioning<Sci::Position>>(8);
        values = Sci::make_unique<SplitVector<T>>();
        values->InsertEmpty(0, 2);
    }
    // Deleted so SparseVector objects can not be copied.
    SparseVector(const SparseVector &) = delete;
    SparseVector(SparseVector &&) = delete;
    void operator=(const SparseVector &) = delete;
    void operator=(SparseVector &&) = delete;
    ~SparseVector() {
        starts.reset();
        // starts dead here but not used by ClearValue.
        for (Sci::Position part = 0; part < values->Length(); part++) {
            ClearValue(part);
        }
        values.reset();
    }
    Sci::Position Length() const noexcept {
        return starts->Length();
    }
    Sci::Position Elements() const noexcept {
        return starts->Partitions();
    }
    Sci::Position PositionOfElement(Sci::Position element) const noexcept {
        return starts->PositionFromPartition(element);
    }
    Sci::Position ElementFromPosition(Sci::Position position) const noexcept {
        if (position < Length()) {
            return starts->PartitionFromPosition(position);
        } else {
            return starts->Partitions();
        }
    }
    const T& ValueAt(Sci::Position position) const noexcept {
        assert(position <= Length());
        const Sci::Position partition = ElementFromPosition(position);
        const Sci::Position startPartition = starts->PositionFromPartition(partition);
        if (startPartition == position) {
            return values->ValueAt(partition);
        } else {
            return empty;
        }
    }
    template <typename ParamType>
    void SetValueAt(Sci::Position position, ParamType &&value) {
        assert(position <= Length());
        const Sci::Position partition = ElementFromPosition(position);
        const Sci::Position 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, std::forward<ParamType>(value));
            } else {
                // Insert a new element
                starts->InsertPartition(partition + 1, position);
                values->Insert(partition + 1, std::forward<ParamType>(value));
            }
        }
    }
    void InsertSpace(Sci::Position position, Sci::Position insertLength) {
        assert(position <= Length());
        const Sci::Position partition = starts->PartitionFromPosition(position);
        const Sci::Position startPartition = starts->PositionFromPartition(partition);
        if (startPartition == position) {
            const bool positionOccupied = values->ValueAt(partition) != T();
            // Inserting at start of run so make previous longer
            if (partition == 0) {
                // Inserting at start of document so ensure start empty
                if (positionOccupied) {
                    starts->InsertPartition(1, 0);
                    values->InsertEmpty(0, 1);
                }
                starts->InsertText(partition, insertLength);
            } else {
                if (positionOccupied) {
                    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(Sci::Position position) {
        assert(position < Length());
        Sci::Position partition = starts->PartitionFromPosition(position);
        const Sci::Position startPartition = starts->PositionFromPartition(partition);
        if (startPartition == position) {
            if (partition == 0) {
                ClearValue(0);
                if (starts->PositionFromPartition(1) == 1) {
                    // Removing all space of first partition, so remove next partition
                    // and move value if not last
                    if (Elements() > 1) {
                        starts->RemovePartition(partition + 1);
                        values->Delete(partition);
                    }
                }
            } 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);
        Check();
    }
    void DeleteRange(Sci::Position position, Sci::Position deleteLength) {
        // For now, delete elements in range - may want to leave value at start
        // or combine onto position.
        if (position > Length() || (deleteLength == 0)) {
            return;
        }
        const Sci::Position positionEnd = position + deleteLength;
        assert(positionEnd <= Length());
        if (position == 0) {
            // Remove all partitions in range, moving values to start
            while ((Elements() > 1) && (starts->PositionFromPartition(1) <= deleteLength)) {
                starts->RemovePartition(1);
                values->Delete(0);
            }
            starts->InsertText(0, -deleteLength);
            if (Length() == 0) {
                ClearValue(0);
            }
        } else {
            const Sci::Position partition = starts->PartitionFromPosition(position);
            const bool atPartitionStart = position == starts->PositionFromPartition(partition);
            const Sci::Position partitionDelete = partition + (atPartitionStart ? 0 : 1);
            assert(partitionDelete > 0);
            for (;;) {
                const Sci::Position positionAtIndex = starts->PositionFromPartition(partitionDelete);
                assert(position <= positionAtIndex);
                if (positionAtIndex >= positionEnd) {
                    break;
                }
                assert(partitionDelete <= Elements());
                starts->RemovePartition(partitionDelete);
                values->Delete(partitionDelete);
            }
            starts->InsertText(partition - (atPartitionStart ? 1 : 0), -deleteLength);
        }
        Check();
    }
    Sci::Position IndexAfter(Sci::Position position) const noexcept {
        assert(position < Length());
        if (position < 0)
            return 0;
        const Sci::Position partition = starts->PartitionFromPosition(position);
        return partition + 1;
    }
    void Check() const {
#ifdef CHECK_CORRECTNESS
        starts->Check();
        if (starts->Partitions() != values->Length() - 1) {
            throw std::runtime_error("SparseVector: Partitions and values different lengths.");
        }
#endif
    }
};
 
}
 
#endif