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
32namespace Calligra
33{
34namespace 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 */
65template<typename T>
66class PointStorage
67{
68 friend class PointStorageBenchmark;
69 friend class PointStorageTest;
70
71public:
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
860private:
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
867private:
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