1 | /* This file is part of the KDE project |
2 | Copyright 2007 Stefan Nikolaus <stefan.nikolaus@kdemail.net> |
3 | |
4 | This library is free software; you can redistribute it and/or |
5 | modify it under the terms of the GNU Library General Public |
6 | License as published by the Free Software Foundation; either |
7 | version 2 of the License, or (at your option) any later version. |
8 | |
9 | This library is distributed in the hope that it will be useful, |
10 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
11 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
12 | Library General Public License for more details. |
13 | |
14 | You should have received a copy of the GNU Library General Public License |
15 | along with this library; see the file COPYING.LIB. If not, write to |
16 | the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
17 | Boston, MA 02110-1301, USA. |
18 | */ |
19 | |
20 | #ifndef CALLIGRA_SHEETS_POINT_STORAGE |
21 | #define CALLIGRA_SHEETS_POINT_STORAGE |
22 | |
23 | #include <QRect> |
24 | #include <QString> |
25 | #include <QVector> |
26 | |
27 | #include "Region.h" |
28 | #include "calligra_sheets_limits.h" |
29 | |
30 | // #define KSPREAD_POINT_STORAGE_HASH |
31 | |
32 | namespace Calligra |
33 | { |
34 | namespace Sheets |
35 | { |
36 | |
37 | /** |
38 | * \ingroup Storage |
39 | * A custom pointwise storage. |
40 | * Based on a compressed sparse matrix data structure. |
41 | * Usable for any kind of data attached to 2D coordinates. |
42 | * |
43 | * Only non-default data with its coordinate is stored. Hence, the storage |
44 | * has a small memory footprint nearly regardless of the data's location. |
45 | * Each empty row before a location occupy an integer, which is not the case |
46 | * for columns. Iterating over the data becomes fast compared to dense |
47 | * matrix/array, where each location has to be traversed irrespective of |
48 | * default or non-default data. |
49 | * |
50 | * The actual data is stored in the list m_data. It is grouped by rows in |
51 | * ascending order. The rows' beginnings and ends are stored in the list |
52 | * m_rows. Its index corresponds to the row index. The values denote the |
53 | * starting index of a row in m_data. The row's end is determined by |
54 | * the starting position of the next row. The entries in each row are ordered |
55 | * by column. The corresponding column indices are stored in m_cols. Hence, |
56 | * m_cols has the same amount of entries as m_data. |
57 | * |
58 | * \author Stefan Nikolaus <stefan.nikolaus@kdemail.net> |
59 | * |
60 | * \note If you fill the storage, do it row-wise. That's more performant. |
61 | * \note For data assigned to rectangular regions use RectStorage. |
62 | * \note It's QVector based. To boost performance a lot, declare the stored |
63 | * data type as movable. |
64 | */ |
65 | template<typename T> |
66 | class PointStorage |
67 | { |
68 | friend class PointStorageBenchmark; |
69 | friend class PointStorageTest; |
70 | |
71 | public: |
72 | /** |
73 | * Constructor. |
74 | * Creates an empty storage. Actually, does nothing. |
75 | */ |
76 | PointStorage() {} |
77 | |
78 | /** |
79 | * Destructor. |
80 | */ |
81 | ~PointStorage() {} |
82 | |
83 | /** |
84 | * Clears the storage. |
85 | */ |
86 | void clear() { |
87 | m_cols.clear(); |
88 | m_rows.clear(); |
89 | m_data.clear(); |
90 | } |
91 | |
92 | /** |
93 | * Returns the number of items in the storage. |
94 | * Usable to iterate over all non-default data. |
95 | * \return number of items |
96 | * \see col() |
97 | * \see row() |
98 | * \see data() |
99 | */ |
100 | int count() const { |
101 | return m_data.count(); |
102 | } |
103 | |
104 | /** |
105 | * Inserts \p data at \p col , \p row . |
106 | * \return the overridden data (default data, if no overwrite) |
107 | */ |
108 | T insert(int col, int row, const T& data) { |
109 | Q_ASSERT(1 <= col && col <= KS_colMax); |
110 | Q_ASSERT(1 <= row && row <= KS_rowMax); |
111 | // row's missing? |
112 | if (row > m_rows.count()) { |
113 | // insert missing rows |
114 | m_rows.insert(m_rows.count(), row - m_rows.count(), m_data.count()); |
115 | // append the actual data |
116 | #ifdef KSPREAD_POINT_STORAGE_HASH |
117 | m_data.append(*m_usedData.insert(data)); |
118 | #else |
119 | m_data.append(data); |
120 | #endif |
121 | // append the column index |
122 | m_cols.append(col); |
123 | } |
124 | // the row exists |
125 | else { |
126 | const QVector<int>::const_iterator cstart(m_cols.begin() + m_rows.value(row - 1)); |
127 | const QVector<int>::const_iterator cend((row < m_rows.count()) ? (m_cols.begin() + m_rows.value(row)) : m_cols.end()); |
128 | const QVector<int>::const_iterator cit = qLowerBound(cstart, cend, col); |
129 | // column's missing? |
130 | if (cit == cend || *cit != col) { |
131 | // determine the index where the data and column has to be inserted |
132 | const int index = m_rows.value(row - 1) + (cit - cstart); |
133 | // insert the actual data |
134 | #ifdef KSPREAD_POINT_STORAGE_HASH |
135 | m_data.insert(index, *m_usedData.insert(data)); |
136 | #else |
137 | m_data.insert(index, data); |
138 | #endif |
139 | // insert the column index |
140 | m_cols.insert(index, col); |
141 | // adjust the offsets of the following rows |
142 | for (int r = row; r < m_rows.count(); ++r) |
143 | ++m_rows[r]; |
144 | } |
145 | // column exists |
146 | else { |
147 | const int index = m_rows.value(row - 1) + (cit - cstart); |
148 | const T oldData = m_data[ index ]; |
149 | #ifdef KSPREAD_POINT_STORAGE_HASH |
150 | m_data[ index ] = *m_usedData.insert(data); |
151 | #else |
152 | m_data[ index ] = data; |
153 | #endif |
154 | return oldData; |
155 | } |
156 | } |
157 | squeezeRows(); |
158 | return T(); |
159 | } |
160 | |
161 | /** |
162 | * Looks up the data at \p col , \p row . If no data was found returns a |
163 | * default object. |
164 | * \return the data at the given coordinate |
165 | */ |
166 | T lookup(int col, int row, const T& defaultVal = T()) const { |
167 | Q_ASSERT(1 <= col && col <= KS_colMax); |
168 | Q_ASSERT(1 <= row && row <= KS_rowMax); |
169 | // is the row not present? |
170 | if (row > m_rows.count()) |
171 | return defaultVal; |
172 | const QVector<int>::const_iterator cstart(m_cols.begin() + m_rows.value(row - 1)); |
173 | const QVector<int>::const_iterator cend((row < m_rows.count()) ? (m_cols.begin() + m_rows.value(row)) : m_cols.end()); |
174 | const QVector<int>::const_iterator cit = qBinaryFind(cstart, cend, col); |
175 | // is the col not present? |
176 | if (cit == cend) |
177 | return defaultVal; |
178 | return m_data.value(m_rows.value(row - 1) + (cit - cstart)); |
179 | } |
180 | |
181 | /** |
182 | * Removes data at \p col , \p row . |
183 | * \return the removed data (default data, if none) |
184 | */ |
185 | T take(int col, int row, const T& defaultVal = T()) { |
186 | Q_ASSERT(1 <= col && col <= KS_colMax); |
187 | Q_ASSERT(1 <= row && row <= KS_rowMax); |
188 | // row's missing? |
189 | if (row > m_rows.count()) |
190 | return defaultVal; |
191 | const int rowStart = (row - 1 < m_rows.count()) ? m_rows.value(row - 1) : m_data.count(); |
192 | const int rowLength = (row < m_rows.count()) ? m_rows.value(row) - rowStart : -1; |
193 | const QVector<int> cols = m_cols.mid(rowStart, rowLength); |
194 | QVector<int>::const_iterator cit = qBinaryFind(cols, col); |
195 | // column's missing? |
196 | if (cit == cols.constEnd()) |
197 | return defaultVal; |
198 | const int index = rowStart + (cit - cols.constBegin()); |
199 | // save the old data |
200 | const T oldData = m_data[ index ]; |
201 | // remove the actual data |
202 | m_data.remove(index); |
203 | // remove the column index |
204 | m_cols.remove(index); |
205 | // adjust the offsets of the following rows |
206 | for (int r = row; r < m_rows.count(); ++r) |
207 | --m_rows[r]; |
208 | squeezeRows(); |
209 | return oldData; |
210 | } |
211 | |
212 | /** |
213 | * Insert \p number columns at \p position . |
214 | * \return the data, that became out of range (shifted over the end) |
215 | */ |
216 | QVector< QPair<QPoint, T> > insertColumns(int position, int number) { |
217 | Q_ASSERT(1 <= position && position <= KS_colMax); |
218 | QVector< QPair<QPoint, T> > oldData; |
219 | for (int row = m_rows.count(); row >= 1; --row) { |
220 | const int rowStart = m_rows.value(row - 1); |
221 | const int rowLength = (row < m_rows.count()) ? m_rows.value(row) - rowStart : -1; |
222 | const QVector<int> cols = m_cols.mid(rowStart, rowLength); |
223 | for (int col = cols.count(); col >= 0; --col) { |
224 | if (cols.value(col) + number > KS_colMax) { |
225 | oldData.append(qMakePair(QPoint(cols.value(col), row), m_data.value(rowStart + col))); |
226 | m_cols.remove(rowStart + col); |
227 | m_data.remove(rowStart + col); |
228 | // adjust the offsets of the following rows |
229 | for (int r = row; r < m_rows.count(); ++r) |
230 | --m_rows[r]; |
231 | } else if (cols.value(col) >= position) |
232 | m_cols[rowStart + col] += number; |
233 | } |
234 | } |
235 | squeezeRows(); |
236 | return oldData; |
237 | } |
238 | |
239 | /** |
240 | * Removes \p number columns at \p position . |
241 | * \return the removed data |
242 | */ |
243 | QVector< QPair<QPoint, T> > removeColumns(int position, int number) { |
244 | Q_ASSERT(1 <= position && position <= KS_colMax); |
245 | QVector< QPair<QPoint, T> > oldData; |
246 | for (int row = m_rows.count(); row >= 1; --row) { |
247 | const int rowStart = m_rows.value(row - 1); |
248 | const int rowLength = (row < m_rows.count()) ? m_rows.value(row) - rowStart : -1; |
249 | const QVector<int> cols = m_cols.mid(rowStart, rowLength); |
250 | for (int col = cols.count() - 1; col >= 0; --col) { |
251 | if (cols.value(col) >= position) { |
252 | if (cols.value(col) < position + number) { |
253 | oldData.append(qMakePair(QPoint(cols.value(col), row), m_data.value(rowStart + col))); |
254 | m_cols.remove(rowStart + col); |
255 | m_data.remove(rowStart + col); |
256 | for (int r = row; r < m_rows.count(); ++r) |
257 | --m_rows[r]; |
258 | } else |
259 | m_cols[rowStart + col] -= number; |
260 | } |
261 | } |
262 | } |
263 | squeezeRows(); |
264 | return oldData; |
265 | } |
266 | |
267 | /** |
268 | * Insert \p number rows at \p position . |
269 | * \return the data, that became out of range (shifted over the end) |
270 | */ |
271 | QVector< QPair<QPoint, T> > insertRows(int position, int number) { |
272 | Q_ASSERT(1 <= position && position <= KS_rowMax); |
273 | // row's missing? |
274 | if (position > m_rows.count()) |
275 | return QVector< QPair<QPoint, T> >(); |
276 | QVector< QPair<QPoint, T> > oldData; |
277 | int dataCount = 0; |
278 | int rowCount = 0; |
279 | // save the old data |
280 | for (int row = KS_rowMax - number + 1; row <= m_rows.count() && row <= KS_rowMax; ++row) { |
281 | const QVector<int>::const_iterator cstart(m_cols.begin() + m_rows.value(row - 1)); |
282 | const QVector<int>::const_iterator cend((row < m_rows.count()) ? (m_cols.begin() + m_rows.value(row)) : m_cols.end()); |
283 | for (QVector<int>::const_iterator cit = cstart; cit != cend; ++cit) |
284 | oldData.append(qMakePair(QPoint(*cit, row), m_data.value(cit - m_cols.constBegin()))); |
285 | dataCount += (cend - cstart); |
286 | ++rowCount; |
287 | } |
288 | // remove the out of range data |
289 | while (dataCount-- > 0) { |
290 | m_data.remove(m_data.count() - 1); |
291 | m_cols.remove(m_cols.count() - 1); |
292 | } |
293 | while (rowCount-- > 0) |
294 | m_rows.remove(m_rows.count() - 1); |
295 | // insert the new rows |
296 | const int index = m_rows.value(position - 1); |
297 | for (int r = 0; r < number; ++r) |
298 | m_rows.insert(position, index); |
299 | squeezeRows(); |
300 | return oldData; |
301 | } |
302 | |
303 | /** |
304 | * Removes \p number rows at \p position . |
305 | * \return the removed data |
306 | */ |
307 | QVector< QPair<QPoint, T> > removeRows(int position, int number) { |
308 | Q_ASSERT(1 <= position && position <= KS_rowMax); |
309 | // row's missing? |
310 | if (position > m_rows.count()) |
311 | return QVector< QPair<QPoint, T> >(); |
312 | QVector< QPair<QPoint, T> > oldData; |
313 | int dataCount = 0; |
314 | int rowCount = 0; |
315 | // save the old data |
316 | for (int row = position; row <= m_rows.count() && row <= position + number - 1; ++row) { |
317 | const int rowStart = m_rows.value(row - 1); |
318 | const int rowLength = (row < m_rows.count()) ? m_rows.value(row) - rowStart : -1; |
319 | const QVector<int> cols = m_cols.mid(rowStart, rowLength); |
320 | const QVector<T> data = m_data.mid(rowStart, rowLength); |
321 | for (int col = 0; col < cols.count(); ++col) |
322 | oldData.append(qMakePair(QPoint(cols.value(col), row), data.value(col))); |
323 | dataCount += data.count(); |
324 | ++rowCount; |
325 | } |
326 | // adjust the offsets of the following rows |
327 | for (int r = position + number - 1; r < m_rows.count(); ++r) |
328 | m_rows[r] -= dataCount; |
329 | // remove the out of range data |
330 | while (dataCount-- > 0) { |
331 | m_data.remove(m_rows.value(position - 1)); |
332 | m_cols.remove(m_rows.value(position - 1)); |
333 | } |
334 | while (rowCount-- > 0) |
335 | m_rows.remove(position - 1); |
336 | squeezeRows(); |
337 | return oldData; |
338 | } |
339 | |
340 | /** |
341 | * Shifts the data right of \p rect to the left by the width of \p rect . |
342 | * The data formerly contained in \p rect becomes overridden. |
343 | * \return the removed data |
344 | */ |
345 | QVector< QPair<QPoint, T> > removeShiftLeft(const QRect& rect) { |
346 | Q_ASSERT(1 <= rect.left() && rect.left() <= KS_colMax); |
347 | QVector< QPair<QPoint, T> > oldData; |
348 | for (int row = qMin(rect.bottom(), m_rows.count()); row >= rect.top(); --row) { |
349 | const int rowStart = m_rows.value(row - 1); |
350 | const int rowLength = (row < m_rows.count()) ? m_rows.value(row) - rowStart : -1; |
351 | const QVector<int> cols = m_cols.mid(rowStart, rowLength); |
352 | for (int col = cols.count() - 1; col >= 0; --col) { |
353 | if (cols.value(col) >= rect.left()) { |
354 | if (cols.value(col) <= rect.right()) { |
355 | oldData.append(qMakePair(QPoint(cols.value(col), row), m_data.value(rowStart + col))); |
356 | m_cols.remove(rowStart + col); |
357 | m_data.remove(rowStart + col); |
358 | for (int r = row; r < m_rows.count(); ++r) |
359 | --m_rows[r]; |
360 | } else |
361 | m_cols[rowStart + col] -= rect.width(); |
362 | } |
363 | } |
364 | } |
365 | squeezeRows(); |
366 | return oldData; |
367 | } |
368 | |
369 | /** |
370 | * Shifts the data in and right of \p rect to the right by the width of \p rect . |
371 | * \return the data, that became out of range (shifted over the end) |
372 | */ |
373 | QVector< QPair<QPoint, T> > insertShiftRight(const QRect& rect) { |
374 | Q_ASSERT(1 <= rect.left() && rect.left() <= KS_colMax); |
375 | QVector< QPair<QPoint, T> > oldData; |
376 | for (int row = rect.top(); row <= rect.bottom() && row <= m_rows.count(); ++row) { |
377 | const int rowStart = m_rows.value(row - 1); |
378 | const int rowLength = (row < m_rows.count()) ? m_rows.value(row) - rowStart : -1; |
379 | const QVector<int> cols = m_cols.mid(rowStart, rowLength); |
380 | for (int col = cols.count(); col >= 0; --col) { |
381 | if (cols.value(col) + rect.width() > KS_colMax) { |
382 | oldData.append(qMakePair(QPoint(cols.value(col), row), m_data.value(rowStart + col))); |
383 | m_cols.remove(rowStart + col); |
384 | m_data.remove(rowStart + col); |
385 | // adjust the offsets of the following rows |
386 | for (int r = row; r < m_rows.count(); ++r) |
387 | --m_rows[r]; |
388 | } else if (cols.value(col) >= rect.left()) |
389 | m_cols[rowStart + col] += rect.width(); |
390 | } |
391 | } |
392 | squeezeRows(); |
393 | return oldData; |
394 | } |
395 | |
396 | /** |
397 | * Shifts the data below \p rect to the top by the height of \p rect . |
398 | * The data formerly contained in \p rect becomes overridden. |
399 | * \return the removed data |
400 | */ |
401 | QVector< QPair<QPoint, T> > removeShiftUp(const QRect& rect) { |
402 | Q_ASSERT(1 <= rect.top() && rect.top() <= KS_rowMax); |
403 | // row's missing? |
404 | if (rect.top() > m_rows.count()) |
405 | return QVector< QPair<QPoint, T> >(); |
406 | QVector< QPair<QPoint, T> > oldData; |
407 | for (int row = rect.top(); row <= m_rows.count() && row <= KS_rowMax - rect.height(); ++row) { |
408 | const int rowStart = m_rows.value(row - 1); |
409 | const int rowLength = (row < m_rows.count()) ? m_rows.value(row) - rowStart : -1; |
410 | const QVector<int> cols = m_cols.mid(rowStart, rowLength); |
411 | const QVector<T> data = m_data.mid(rowStart, rowLength); |
412 | // first, iterate over the destination row |
413 | for (int col = cols.count() - 1; col >= 0; --col) { |
414 | const int column = cols.value(col); // real column value (1...KS_colMax) |
415 | if (column >= rect.left() && column <= rect.right()) { |
416 | // save the old data |
417 | if (row <= rect.bottom()) |
418 | oldData.append(qMakePair(QPoint(column, row), data.value(col))); |
419 | // search |
420 | const int srcRow = row + rect.height(); |
421 | const QVector<int>::const_iterator cstart2((srcRow - 1 < m_rows.count()) ? m_cols.begin() + m_rows.value(srcRow - 1) : m_cols.end()); |
422 | const QVector<int>::const_iterator cend2((srcRow < m_rows.count()) ? (m_cols.begin() + m_rows.value(srcRow)) : m_cols.end()); |
423 | const QVector<int>::const_iterator cit2 = qBinaryFind(cstart2, cend2, column); |
424 | // column's missing? |
425 | if (cit2 == cend2) { |
426 | m_cols.remove(rowStart + col); |
427 | m_data.remove(rowStart + col); |
428 | // adjust the offsets of the following rows |
429 | for (int r = row; r < m_rows.count(); ++r) |
430 | --m_rows[r]; |
431 | } |
432 | // column exists |
433 | else { |
434 | // copy |
435 | m_data[rowStart + col] = m_data.value(cit2 - m_cols.constBegin()); |
436 | // remove |
437 | m_cols.remove(cit2 - m_cols.constBegin()); |
438 | m_data.remove(cit2 - m_cols.constBegin()); |
439 | // adjust the offsets of the following rows |
440 | for (int r = row + rect.height(); r < m_rows.count(); ++r) |
441 | --m_rows[r]; |
442 | } |
443 | } |
444 | } |
445 | // last, iterate over the source row |
446 | const int srcRow = row + rect.height(); |
447 | const int rowStart2 = (srcRow - 1 < m_rows.count()) ? m_rows.value(srcRow - 1) : m_data.count(); |
448 | const int rowLength2 = (srcRow < m_rows.count()) ? m_rows.value(srcRow) - rowStart2 : -1; |
449 | const QVector<int> cols2 = m_cols.mid(rowStart2, rowLength2); |
450 | const QVector<T> data2 = m_data.mid(rowStart2, rowLength2); |
451 | int offset = 0; |
452 | for (int col = cols2.count() - 1; col >= 0; --col) { |
453 | const int column = cols2.value(col); // real column value (1...KS_colMax) |
454 | if (column >= rect.left() && column <= rect.right()) { |
455 | // find the insertion position |
456 | const QVector<int>::const_iterator cstart((row - 1 < m_rows.count()) ? m_cols.begin() + m_rows.value(row - 1) : m_cols.end()); |
457 | const QVector<int>::const_iterator cend(((row < m_rows.count())) ? (m_cols.begin() + m_rows.value(row)) : m_cols.end()); |
458 | const QVector<int>::const_iterator cit = qUpperBound(cstart, cend, cols2.value(col)); |
459 | // Destination column: |
460 | const QVector<int>::const_iterator dstcit = qBinaryFind(cols.begin(), cols.end(), column); |
461 | if (dstcit != cols.end()) { // destination column exists |
462 | // replace the existing destination value |
463 | const int dstCol = (dstcit - cols.constBegin()); |
464 | m_data[rowStart + dstCol] = m_data.value(rowStart2 + col); |
465 | // remove it from its old position |
466 | m_data.remove(rowStart2 + col + 1); |
467 | m_cols.remove(rowStart2 + col + 1); |
468 | // The amount of values in the range from the |
469 | // destination row to the source row have not changed. |
470 | // adjust the offsets of the following rows |
471 | for (int r = srcRow; r < m_rows.count(); ++r) { |
472 | ++m_rows[r]; |
473 | } |
474 | } else { // destination column does not exist yet |
475 | // copy it to its new position |
476 | const int dstCol = cit - m_cols.constBegin(); |
477 | m_data.insert(dstCol, data2.value(col)); |
478 | m_cols.insert(dstCol, cols2.value(col)); |
479 | // remove it from its old position |
480 | m_data.remove(rowStart2 + col + 1 + offset); |
481 | m_cols.remove(rowStart2 + col + 1 + offset); |
482 | ++offset; |
483 | // adjust the offsets of the following rows |
484 | for (int r = row; r < srcRow; ++r) { |
485 | ++m_rows[r]; |
486 | } |
487 | } |
488 | } |
489 | } |
490 | } |
491 | squeezeRows(); |
492 | return oldData; |
493 | } |
494 | |
495 | /** |
496 | * Shifts the data in and below \p rect to the bottom by the height of \p rect . |
497 | * \return the data, that became out of range (shifted over the end) |
498 | */ |
499 | QVector< QPair<QPoint, T> > insertShiftDown(const QRect& rect) { |
500 | Q_ASSERT(1 <= rect.top() && rect.top() <= KS_rowMax); |
501 | // row's missing? |
502 | if (rect.top() > m_rows.count()) |
503 | return QVector< QPair<QPoint, T> >(); |
504 | QVector< QPair<QPoint, T> > oldData; |
505 | for (int row = m_rows.count(); row >= rect.top(); --row) { |
506 | const int rowStart = m_rows.value(row - 1); |
507 | const int rowLength = (row < m_rows.count()) ? m_rows.value(row) - rowStart : -1; |
508 | const QVector<int> cols = m_cols.mid(rowStart, rowLength); |
509 | const QVector<T> data = m_data.mid(rowStart, rowLength); |
510 | for (int col = cols.count() - 1; col >= 0; --col) { |
511 | if (cols.value(col) >= rect.left() && cols.value(col) <= rect.right()) { |
512 | if (row + rect.height() > KS_rowMax) { |
513 | // save old data |
514 | oldData.append(qMakePair(QPoint(cols.value(col), row), data.value(col))); |
515 | } else { |
516 | // insert missing rows |
517 | if (row + rect.height() > m_rows.count()) |
518 | m_rows.insert(m_rows.count(), row + rect.height() - m_rows.count(), m_data.count()); |
519 | |
520 | // copy the data down |
521 | const int row2 = row + rect.height(); |
522 | const QVector<int>::const_iterator cstart2(m_cols.begin() + m_rows.value(row2 - 1)); |
523 | const QVector<int>::const_iterator cend2((row2 < m_rows.count()) ? (m_cols.begin() + m_rows.value(row2)) : m_cols.end()); |
524 | const QVector<int>::const_iterator cit2 = qLowerBound(cstart2, cend2, cols.value(col)); |
525 | // column's missing? |
526 | if (cit2 == cend2 || *cit2 != cols.value(col)) { |
527 | // determine the index where the data and column has to be inserted |
528 | const int index = m_rows.value(row2 - 1) + (cit2 - cstart2); |
529 | // insert the actual data |
530 | m_data.insert(index, data.value(col)); |
531 | // insert the column index |
532 | m_cols.insert(index, cols.value(col)); |
533 | // adjust the offsets of the following rows |
534 | for (int r = row2; r < m_rows.count(); ++r) |
535 | ++m_rows[r]; |
536 | } |
537 | // column exists |
538 | else { |
539 | const int index = m_rows.value(row2 - 1) + (cit2 - cstart2); |
540 | m_data[ index ] = data.value(col); |
541 | } |
542 | } |
543 | |
544 | // remove the data |
545 | m_cols.remove(rowStart + col); |
546 | m_data.remove(rowStart + col); |
547 | // adjust the offsets of the following rows |
548 | for (int r = row; r < m_rows.count(); ++r) |
549 | --m_rows[r]; |
550 | } |
551 | } |
552 | } |
553 | squeezeRows(); |
554 | return oldData; |
555 | } |
556 | |
557 | /** |
558 | * Retrieve the first used data in \p col . |
559 | * Can be used in conjunction with nextInColumn() to loop through a column. |
560 | * \return the first used data in \p col or the default data, if the column is empty. |
561 | */ |
562 | T firstInColumn(int col, int* newRow = 0) const { |
563 | Q_ASSERT(1 <= col && col <= KS_colMax); |
564 | const int index = m_cols.indexOf(col); |
565 | if (newRow) { |
566 | if (index == -1) // not found |
567 | *newRow = 0; |
568 | else |
569 | *newRow = qUpperBound(m_rows, index) - m_rows.begin(); |
570 | } |
571 | return m_data.value(index); |
572 | } |
573 | |
574 | /** |
575 | * Retrieve the first used data in \p row . |
576 | * Can be used in conjunction with nextInRow() to loop through a row. |
577 | * \return the first used data in \p row or the default data, if the row is empty. |
578 | */ |
579 | T firstInRow(int row, int* newCol = 0) const { |
580 | Q_ASSERT(1 <= row && row <= KS_rowMax); |
581 | // row's empty? |
582 | if (row > m_rows.count() || ((row < m_rows.count()) && m_rows.value(row - 1) == m_rows.value(row))) { |
583 | if (newCol) |
584 | *newCol = 0; |
585 | return T(); |
586 | } |
587 | if (newCol) |
588 | *newCol = m_cols.value(m_rows.value(row - 1)); |
589 | return m_data.value(m_rows.value(row - 1)); |
590 | } |
591 | |
592 | /** |
593 | * Retrieve the last used data in \p col . |
594 | * Can be used in conjunction with prevInColumn() to loop through a column. |
595 | * \return the last used data in \p col or the default data, if the column is empty. |
596 | */ |
597 | T lastInColumn(int col, int* newRow = 0) const { |
598 | Q_ASSERT(1 <= col && col <= KS_colMax); |
599 | const int index = m_cols.lastIndexOf(col); |
600 | if (newRow) { |
601 | if (index == -1) // not found |
602 | *newRow = 0; |
603 | else |
604 | *newRow = qUpperBound(m_rows, index) - m_rows.begin(); |
605 | } |
606 | return m_data.value(index); |
607 | } |
608 | |
609 | /** |
610 | * Retrieve the last used data in \p row . |
611 | * Can be used in conjunction with prevInRow() to loop through a row. |
612 | * \return the last used data in \p row or the default data, if the row is empty. |
613 | */ |
614 | T lastInRow(int row, int* newCol = 0) const { |
615 | Q_ASSERT(1 <= row && row <= KS_rowMax); |
616 | // row's empty? |
617 | if (m_rows.value(row - 1) == m_rows.value(row) || m_rows.value(row - 1) == m_data.count()) { |
618 | if (newCol) |
619 | *newCol = 0; |
620 | return T(); |
621 | } |
622 | // last row ends on data vector end |
623 | if (row == m_rows.count()) { |
624 | if (newCol) |
625 | *newCol = m_cols.value(m_data.count() - 1); |
626 | return m_data.value(m_data.count() - 1); |
627 | } |
628 | if (newCol) |
629 | *newCol = m_cols.value(m_rows.value(row) - 1); |
630 | return m_data.value(m_rows.value(row) - 1); |
631 | } |
632 | |
633 | /** |
634 | * Retrieve the next used data in \p col after \p row . |
635 | * Can be used in conjunction with firstInColumn() to loop through a column. |
636 | * \return the next used data in \p col or the default data, there is no further data. |
637 | */ |
638 | T nextInColumn(int col, int row, int* newRow = 0) const { |
639 | Q_ASSERT(1 <= col && col <= KS_colMax); |
640 | Q_ASSERT(1 <= row && row <= KS_rowMax); |
641 | // no next row? |
642 | if (row + 1 > m_rows.count()) { |
643 | if (newRow) |
644 | *newRow = 0; |
645 | return T(); |
646 | } |
647 | // search beginning in rows after the specified row |
648 | const int index = m_cols.indexOf(col, m_rows.value(row)); |
649 | if (newRow) { |
650 | if (index == -1) // not found |
651 | *newRow = 0; |
652 | else |
653 | *newRow = qUpperBound(m_rows, index) - m_rows.begin(); |
654 | } |
655 | return m_data.value(index); |
656 | } |
657 | |
658 | /** |
659 | * Retrieve the next used data in \p row after \p col . |
660 | * Can be used in conjunction with firstInRow() to loop through a row. |
661 | * \return the next used data in \p row or the default data, if there is no further data. |
662 | */ |
663 | T nextInRow(int col, int row, int* newCol = 0) const { |
664 | Q_ASSERT(1 <= col && col <= KS_colMax); |
665 | Q_ASSERT(1 <= row && row <= KS_rowMax); |
666 | // is the row not present? |
667 | if (row > m_rows.count()) { |
668 | if (newCol) |
669 | *newCol = 0; |
670 | return T(); |
671 | } |
672 | const QVector<int>::const_iterator cstart(m_cols.begin() + m_rows.value(row - 1)); |
673 | const QVector<int>::const_iterator cend((row < m_rows.count()) ? (m_cols.begin() + m_rows.value(row)) : m_cols.end()); |
674 | const QVector<int>::const_iterator cit = qUpperBound(cstart, cend, col); |
675 | if (cit == cend || *cit <= col) { |
676 | if (newCol) |
677 | *newCol = 0; |
678 | return T(); |
679 | } |
680 | if (newCol) |
681 | *newCol = m_cols.value(m_rows.value(row - 1) + (cit - cstart)); |
682 | return m_data.value(m_rows.value(row - 1) + (cit - cstart)); |
683 | } |
684 | |
685 | /** |
686 | * Retrieve the previous used data in \p col after \p row . |
687 | * Can be used in conjunction with lastInColumn() to loop through a column. |
688 | * \return the previous used data in \p col or the default data, there is no further data. |
689 | */ |
690 | T prevInColumn(int col, int row, int* newRow = 0) const { |
691 | Q_ASSERT(1 <= col && col <= KS_colMax); |
692 | Q_ASSERT(1 <= row && row <= KS_rowMax); |
693 | // first row? |
694 | if (row <= m_rows.count() && m_rows.value(row - 1) == 0) { |
695 | if (newRow) |
696 | *newRow = 0; |
697 | return T(); |
698 | } |
699 | const int index = m_cols.lastIndexOf(col, m_rows.value(row - 1) - 1); |
700 | if (newRow) { |
701 | if (index == -1) // not found |
702 | *newRow = 0; |
703 | else |
704 | *newRow = qUpperBound(m_rows, index) - m_rows.begin(); |
705 | } |
706 | return m_data.value(index); |
707 | } |
708 | |
709 | /** |
710 | * Retrieve the previous used data in \p row after \p col . |
711 | * Can be used in conjunction with lastInRow() to loop through a row. |
712 | * \return the previous used data in \p row or the default data, if there is no further data. |
713 | */ |
714 | T prevInRow(int col, int row, int* newCol = 0) const { |
715 | Q_ASSERT(1 <= col && col <= KS_colMax); |
716 | Q_ASSERT(1 <= row && row <= KS_rowMax); |
717 | const QVector<int>::const_iterator cstart((row - 1 < m_rows.count()) ? m_cols.begin() + m_rows.value(row - 1) : m_cols.end()); |
718 | const QVector<int>::const_iterator cend((row < m_rows.count()) ? (m_cols.begin() + m_rows.value(row)) : m_cols.end()); |
719 | const QVector<int>::const_iterator cit = qLowerBound(cstart, cend, col); |
720 | if (cit == cstart) { |
721 | if (newCol) |
722 | *newCol = 0; |
723 | return T(); |
724 | } |
725 | if (newCol) |
726 | *newCol = m_cols.value(cit - 1 - m_cols.begin()); |
727 | return m_data.value(cit - 1 - m_cols.begin()); |
728 | } |
729 | |
730 | /** |
731 | * For debugging/testing purposes. |
732 | * \note only works with primitive/printable data |
733 | */ |
734 | QString dump() const { |
735 | QString str; |
736 | // determine the dimension of the matrix (the missing column number) |
737 | int maxCols = 0; |
738 | for (int row = 0; row < m_rows.count(); ++row) { |
739 | const int rowStart = m_rows.value(row); |
740 | const int rowLength = (row + 1 < m_rows.count()) ? m_rows.value(row + 1) - rowStart : -1; |
741 | const QVector<int> cols = m_cols.mid(rowStart, rowLength); |
742 | maxCols = qMax(maxCols, cols.value(cols.count() - 1)); |
743 | } |
744 | for (int row = 0; row < m_rows.count(); ++row) { |
745 | str += '('; |
746 | const int rowStart = m_rows.value(row); |
747 | const int rowLength = (row + 1 < m_rows.count()) ? m_rows.value(row + 1) - rowStart : -1; |
748 | const QVector<int> cols = m_cols.mid(rowStart, rowLength); |
749 | const QVector<T> data = m_data.mid(rowStart, rowLength); |
750 | int lastCol = 0; |
751 | for (int col = 0; col < cols.count(); ++col) { |
752 | int counter = cols.value(col) - lastCol; |
753 | while (counter-- > 1) |
754 | str += " ," ; |
755 | str += QString("%1," ).arg(data.value(col), 2); |
756 | // str += QString( "%1," ).arg( (data.value( col ) == T()) ? "" : "_", 2 ); |
757 | lastCol = cols.value(col); |
758 | } |
759 | // fill the column up to the max |
760 | int counter = maxCols - lastCol; |
761 | while (counter-- > 0) |
762 | str += " ," ; |
763 | // replace the last comma |
764 | str[str.length()-1] = ')'; |
765 | str += '\n'; |
766 | } |
767 | return str.isEmpty() ? QString("()" ) : str.mid(0, str.length() - 1); |
768 | } |
769 | |
770 | /** |
771 | * Returns the column of the non-default data at \p index . |
772 | * \return the data's column at \p index . |
773 | * \see count() |
774 | * \see row() |
775 | * \see data() |
776 | */ |
777 | int col(int index) const { |
778 | return m_cols.value(index); |
779 | } |
780 | |
781 | /** |
782 | * Returns the row of the non-default data at \p index . |
783 | * \return the data's row at \p index . |
784 | * \see count() |
785 | * \see col() |
786 | * \see data() |
787 | */ |
788 | int row(int index) const { |
789 | return qUpperBound(m_rows, index) - m_rows.begin(); |
790 | } |
791 | |
792 | /** |
793 | * Returns the non-default data at \p index . |
794 | * \return the data at \p index . |
795 | * \see count() |
796 | * \see col() |
797 | * \see row() |
798 | */ |
799 | T data(int index) const { |
800 | return m_data.value(index); |
801 | } |
802 | |
803 | /** |
804 | * The maximum occupied column, i.e. the horizontal storage dimension. |
805 | * \return the maximum column |
806 | */ |
807 | int columns() const { |
808 | int columns = 0; |
809 | for (int c = 0; c < m_cols.count(); ++c) |
810 | columns = qMax(m_cols.value(c), columns); |
811 | return columns; |
812 | } |
813 | |
814 | /** |
815 | * The maximum occupied row, i.e. the vertical storage dimension. |
816 | * \return the maximum row |
817 | */ |
818 | int rows() const { |
819 | return m_rows.count(); |
820 | } |
821 | |
822 | /** |
823 | * Creates a substorage consisting of the values in \p region. |
824 | * If \p keepOffset is \c true, the values' positions are not altered. |
825 | * Otherwise, the upper left of \p region's bounding rect is used as new origin, |
826 | * and all positions are adjusted. |
827 | * \return a subset of the storage stripped down to the values in \p region |
828 | */ |
829 | PointStorage<T> subStorage(const Region& region, bool keepOffset = true) const { |
830 | // Determine the offset. |
831 | const QPoint offset = keepOffset ? QPoint(0, 0) : region.boundingRect().topLeft() - QPoint(1, 1); |
832 | // this generates an array of values |
833 | PointStorage<T> subStorage; |
834 | Region::ConstIterator end(region.constEnd()); |
835 | for (Region::ConstIterator it(region.constBegin()); it != end; ++it) { |
836 | const QRect rect = (*it)->rect(); |
837 | for (int row = rect.top(); row <= rect.bottom() && row <= m_rows.count(); ++row) { |
838 | const QVector<int>::const_iterator cstart(m_cols.begin() + m_rows.value(row - 1)); |
839 | const QVector<int>::const_iterator cend((row < m_rows.count()) ? (m_cols.begin() + m_rows.value(row)) : m_cols.end()); |
840 | for (QVector<int>::const_iterator cit = cstart; cit != cend; ++cit) { |
841 | if (*cit >= rect.left() && *cit <= rect.right()) { |
842 | if (keepOffset) |
843 | subStorage.insert(*cit, row, m_data.value(cit - m_cols.begin())); |
844 | else |
845 | subStorage.insert(*cit - offset.x(), row - offset.y(), m_data.value(cit - m_cols.begin())); |
846 | } |
847 | } |
848 | } |
849 | } |
850 | return subStorage; |
851 | } |
852 | |
853 | /** |
854 | * Equality operator. |
855 | */ |
856 | bool operator==(const PointStorage<T>& o) const { |
857 | return (m_rows == o.m_rows && m_cols == o.m_cols && m_data == o.m_data); |
858 | } |
859 | |
860 | private: |
861 | void squeezeRows() { |
862 | int row = m_rows.count() - 1; |
863 | while (m_rows.value(row) == m_data.count() && row >= 0) |
864 | m_rows.remove(row--); |
865 | } |
866 | |
867 | private: |
868 | QVector<int> m_cols; // stores the column indices (beginning with one) |
869 | QVector<int> m_rows; // stores the row offsets in m_data |
870 | QVector<T> m_data; // stores the actual non-default data |
871 | |
872 | #ifdef KSPREAD_POINT_STORAGE_HASH |
873 | QSet<T> m_usedData; |
874 | #endif |
875 | }; |
876 | |
877 | } // namespace Sheets |
878 | } // namespace Calligra |
879 | |
880 | #endif // CALLIGRA_SHEETS_POINT_STORAGE |
881 | |