scintilla/lexlib/SparseState.h

   1 // Scintilla source code edit control
   2 /** @file SparseState.h
   3  ** Hold lexer state that may change rarely.
   4  ** This is often per-line state such as whether a particular type of section has been entered.
   5  ** A state continues until it is changed.
   6  **/
   7 // Copyright 2011 by Neil Hodgson <neilh@scintilla.org>
   8 // The License.txt file describes the conditions under which this software may be distributed.
   9
  10 #ifndef SPARSESTATE_H
  11 #define SPARSESTATE_H
  12
  13 namespace Scintilla {
  14
  15 template <typename T>
  16 class SparseState {
  17         struct State {
  18                 Sci_Position position;
  19                 T value;
  20                 State(Sci_Position position_, T value_) : position(position_), value(value_) {
  21                 }
  22                 inline bool operator<(const State &other) const {
  23                         return position < other.position;
  24                 }
  25                 inline bool operator==(const State &other) const {
  26                         return (position == other.position) && (value == other.value);
  27                 }
  28         };
  29         Sci_Position positionFirst;
  30         typedef std::vector<State> stateVector;
  31         stateVector states;
  32
  33         typename stateVector::iterator Find(Sci_Position position) {
  34                 State searchValue(position, T());
  35                 return std::lower_bound(states.begin(), states.end(), searchValue);
  36         }
  37
  38 public:
  39         explicit SparseState(Sci_Position positionFirst_=-1) {
  40                 positionFirst = positionFirst_;
  41         }
  42         void Set(Sci_Position position, T value) {
  43                 Delete(position);
  44                 if (states.empty() || (value != states[states.size()-1].value)) {
  45                         states.push_back(State(position, value));
  46                 }
  47         }
  48         T ValueAt(Sci_Position position) {
  49                 if (states.empty())
  50                         return T();
  51                 if (position < states[0].position)
  52                         return T();
  53                 typename stateVector::iterator low = Find(position);
  54                 if (low == states.end()) {
  55                         return states[states.size()-1].value;
  56                 } else {
  57                         if (low->position > position) {
  58                                 --low;
  59                         }
  60                         return low->value;
  61                 }
  62         }
  63         bool Delete(Sci_Position position) {
  64                 typename stateVector::iterator low = Find(position);
  65                 if (low != states.end()) {
  66                         states.erase(low, states.end());
  67                         return true;
  68                 }
  69                 return false;
  70         }
  71         size_t size() const {
  72                 return states.size();
  73         }
  74
  75         // Returns true if Merge caused a significant change
  76         bool Merge(const SparseState<T> &other, Sci_Position ignoreAfter) {
  77                 // Changes caused beyond ignoreAfter are not significant
  78                 Delete(ignoreAfter+1);
  79
  80                 bool different = true;
  81                 bool changed = false;
  82                 typename stateVector::iterator low = Find(other.positionFirst);
  83                 if (static_cast<size_t>(states.end() - low) == other.states.size()) {
  84                         // Same number in other as after positionFirst in this
  85                         different = !std::equal(low, states.end(), other.states.begin());
  86                 }
  87                 if (different) {
  88                         if (low != states.end()) {
  89                                 states.erase(low, states.end());
  90                                 changed = true;
  91                         }
  92                         typename stateVector::const_iterator startOther = other.states.begin();
  93                         if (!states.empty() && !other.states.empty() && states.back().value == startOther->value)
  94                                 ++startOther;
  95                         if (startOther != other.states.end()) {
  96                                 states.insert(states.end(), startOther, other.states.end());
  97                                 changed = true;
  98                         }
  99                 }
 100                 return changed;
 101         }
 102 };
 103
 104 }
 105
 106 #endif