ext/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 #ifdef SCI_NAMESPACE
  14 namespace Scintilla {
  15 #endif
  16
  17 template <typename T>
  18 class SparseState {
  19         struct State {
  20                 int position;
  21                 T value;
  22                 State(int position_, T value_) : position(position_), value(value_) {
  23                 }
  24                 inline bool operator<(const State &other) const {
  25                         return position < other.position;
  26                 }
  27                 inline bool operator==(const State &other) const {
  28                         return (position == other.position) && (value == other.value);
  29                 }
  30         };
  31         int positionFirst;
  32         typedef std::vector<State> stateVector;
  33         stateVector states;
  34
  35         typename stateVector::iterator Find(int position) {
  36                 State searchValue(position, T());
  37                 return std::lower_bound(states.begin(), states.end(), searchValue);
  38         }
  39
  40 public:
  41         SparseState(int positionFirst_=-1) {
  42                 positionFirst = positionFirst_;
  43         }
  44         void Set(int position, T value) {
  45                 Delete(position);
  46                 if (states.empty() || (value != states[states.size()-1].value)) {
  47                         states.push_back(State(position, value));
  48                 }
  49         }
  50         T ValueAt(int position) {
  51                 if (states.empty())
  52                         return T();
  53                 if (position < states[0].position)
  54                         return T();
  55                 typename stateVector::iterator low = Find(position);
  56                 if (low == states.end()) {
  57                         return states[states.size()-1].value;
  58                 } else {
  59                         if (low->position > position) {
  60                                 --low;
  61                         }
  62                         return low->value;
  63                 }
  64         }
  65         bool Delete(int position) {
  66                 typename stateVector::iterator low = Find(position);
  67                 if (low != states.end()) {
  68                         states.erase(low, states.end());
  69                         return true;
  70                 }
  71                 return false;
  72         }
  73         size_t size() const {
  74                 return states.size();
  75         }
  76
  77         // Returns true if Merge caused a significant change
  78         bool Merge(const SparseState<T> &other, int ignoreAfter) {
  79                 // Changes caused beyond ignoreAfter are not significant
  80                 Delete(ignoreAfter+1);
  81
  82                 bool different = true;
  83                 bool changed = false;
  84                 typename stateVector::iterator low = Find(other.positionFirst);
  85                 if (static_cast<size_t>(states.end() - low) == other.states.size()) {
  86                         // Same number in other as after positionFirst in this
  87                         different = !std::equal(low, states.end(), other.states.begin());
  88                 }
  89                 if (different) {
  90                         if (low != states.end()) {
  91                                 states.erase(low, states.end());
  92                                 changed = true;
  93                         }
  94                         typename stateVector::const_iterator startOther = other.states.begin();
  95                         if (!states.empty() && !other.states.empty() && states.back().value == startOther->value)
  96                                 ++startOther;
  97                         if (startOther != other.states.end()) {
  98                                 states.insert(states.end(), startOther, other.states.end());
  99                                 changed = true;
 100                         }
 101                 }
 102                 return changed;
 103         }
 104 };
 105
 106 #ifdef SCI_NAMESPACE
 107 }
 108 #endif
 109
 110 #endif