1 /* 2 For general Scribus (>=1.3.2) copyright and licensing information please refer 3 to the COPYING file provided with the program. Following this notice may exist 4 a copyright and/or license notice that predates the release of Scribus 1.3.2 5 for which a new license (GPL+exception) is in place. 6 */ 7 8 #ifndef INDEX_H 9 #define INDEX_H 10 11 #undef NDEBUG 12 13 #include "scribusapi.h" 14 #include <cassert> 15 #include <vector> 16 #include <QList> 17 18 typedef unsigned int uint; 19 20 /** 21 * Holds track of an ordered set of integers, e.g. positions of inline frames within a text. 22 * When the underlying text is edited, the adjust() method must be used to update the index. 23 */ 24 25 class SCRIBUS_API RunIndex { 26 private: 27 std::vector<uint> runEnds; 28 /** 29 * returns the first idx where runStart(idx) >= pos and pos < runEnd(idx) 30 * returns count() if pos > runStart(count()-1) 31 */ 32 uint search(int pos) const; 33 34 public: 35 36 struct Run { 37 uint start; 38 uint end; RunRun39 Run(uint s, uint e) : start(s), end(e) {} 40 }; 41 42 runCount()43 uint runCount() const 44 { 45 return runEnds.size(); 46 } 47 48 runStart(uint idx)49 int runStart(uint idx) const 50 { 51 assert( idx <= unsigned(runEnds.size()) ); 52 53 return idx == 0? 0 : runEnds[idx-1]; 54 } 55 56 runEnd(uint idx)57 int runEnd(uint idx) const 58 { 59 return runEnds[idx]; 60 } 61 62 63 /** return the length of the run ending with position idx, usually runEnd(idx) - runEnd(idx-1) */ runLength(uint idx)64 int runLength(uint idx) const 65 { 66 return runEnd(idx) - runStart(idx); 67 } 68 69 length()70 int length() const 71 { 72 return runEnds.size() == 0? 0 : runEnds[runEnds.size()-1]; 73 } 74 75 76 /** Find the run index for a given position */ operator()77 uint operator() (int pos) const 78 { 79 return search(pos); 80 } 81 82 83 Run operator[] (int pos) 84 { 85 uint idx = search(pos); 86 return Run(runStart(idx), runEnd(idx)); 87 } 88 89 90 /** insert a new position and return its index. Splits the run currently covering pos */ 91 uint insert(int pos); 92 93 94 /** remove a run, merging it with the preceding one */ 95 void remove (uint idx); 96 97 98 /** update all positions >= pos with delta */ 99 void adjust(int pos, int delta); 100 clear()101 void clear() 102 { 103 runEnds.clear(); 104 } 105 }; 106 107 108 109 110 111 112 template<typename T> 113 class IndexedList 114 { 115 QList<T> elems; 116 RunIndex offsets; 117 118 public: 119 operator()120 T& operator() (int pos) 121 { 122 return elems[offsets(pos)]; 123 } 124 125 containsPosition(int pos)126 bool containsPosition(int pos) const 127 { 128 return pos >= 0 && offsets(pos) < offsets.runCount(); 129 } 130 131 operator()132 const T& operator() (int pos) const 133 { 134 return elems[offsets(pos)]; 135 } 136 137 adjust(int pos,int delta)138 void adjust(int pos, int delta) 139 { 140 offsets.adjust(pos, delta); 141 } 142 143 144 T& operator[] (uint idx) 145 { 146 return elems[idx]; 147 } 148 149 const T& operator[] (uint idx) const 150 { 151 return elems[idx]; 152 } 153 154 at(uint idx)155 T& at(uint idx) 156 { 157 return elems.at(idx); 158 } 159 at(uint idx)160 const T& at(uint idx) const 161 { 162 return elems.at(idx); 163 } 164 count()165 int count() const { return elems.size(); } 166 isExactPosition(int pos)167 bool isExactPosition(int pos) const 168 { 169 return pos == 0 || pos == exactPositionAfter(pos-1); 170 } 171 exactPositionBefore(int pos)172 int exactPositionBefore(int pos) const 173 { 174 return offsets.runStart(offsets(pos)); 175 } 176 exactPositionAfter(int pos)177 int exactPositionAfter(int pos) const 178 { 179 return offsets.runEnd(offsets(pos)); 180 } 181 removeAt(uint idx)182 void removeAt(uint idx) 183 { 184 elems.removeAt(idx); 185 offsets.remove(idx); 186 } 187 remove(int pos)188 void remove(int pos) 189 { 190 uint idx = offsets(pos); 191 removeAt(idx); 192 } 193 insert(int pos,const T & elem)194 void insert(int pos, const T& elem) 195 { 196 uint idx = offsets.insert(pos); 197 elems.insert(idx, elem); 198 } 199 replace(int pos,uint len,const T & elem)200 void replace(int pos, uint len, const T& elem) 201 { 202 if (!isExactPosition(pos + len)) 203 { 204 insert(pos + len, (*this)(pos + len)); 205 } 206 insert(pos, elem); 207 uint idx1 = offsets(pos) + 1; 208 uint idx2 = offsets(pos + len); 209 for (uint i = idx1; i < idx2; ++i) 210 { 211 removeAt(idx1); 212 } 213 } 214 clear()215 void clear() 216 { 217 offsets.clear(); 218 elems.clear(); 219 } 220 }; 221 222 #endif 223