1/* This file is part of the KDE project
2 Copyright (C) 2000 Torben Weis <weis@kde.org>
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 CLUSTER_H
21#define CLUSTER_H
22
23#include "Value.h"
24
25#define CALLIGRA_SHEETS_CLUSTER_LEVEL1 256
26#define CALLIGRA_SHEETS_CLUSTER_LEVEL2 256
27#define CALLIGRA_SHEETS_CLUSTER_MAX (256*256)
28
29class QPoint;
30
31namespace Calligra
32{
33namespace Sheets
34{
35class Cell;
36class ColumnFormat;
37class RowFormat;
38
39/**
40\ingroup Storage
41This class defines a pointer map to all cells, which makes access to them more performant
42and additionally limits memory consumption.
43
44In detail: The class defines 2 cluster, where the second cluster (LEVEL2) is a matrix for
45single cells, while the first cluster (LEVEL1) is a matrix to handle the matrices of LEVEL2.
46On initialization, one LEVEL1 matrix is generated only.
47Each time, a cell stores something, this class checks if for the given column and row a
48matrix of LEVEL2 is already initialized and in case not generates it on the fly.
49This helps to reduce the memory usage to only consum one pointer matrix for LEVEL1 and all
50matrices of LEVEL2 that are necessary.
51
52LEVEL1 is defined as 128x128 matrix.
53LEVEL2 is defined as 256x256 matrices.
54Each direction then can have LEVEL1 * LEVEL2 = 128*256 = 2^15 different cells, which
55is in total (2^15)^2 cells.
56
57It can be changed easily to different sizes, but it should be more senseful to have a small LEVEL1,
58as in most cases only one/two entries in LEVEL1 will be used.
59
60There are 2 additional special classes to store pointers for column and row formats.
61
62Future enhancements:
63To reduce memory consumption, it should be possible to enhance the functionality by
64another LEVEL0, which then keeps the LEVEL1 size smaller.
65
66Maybe the LEVEL1 should only be generated when there is a need for more than 1 LEVEL2.
67
68LEVEL1 maybe reallocated.
69
70Another interesting possibility would be to differentiate between x size and y size. Currently both
71are equal in both matrizes, but normally it will be the regular case, that you have more need for
72a lot of rows than columns. Maybe something like LEVEL1=128/256 and LEVEL2=256/128 (x/y), still keeping
732^15 values/cells in each direction (benefit: you won't loose memory in empty columns).
74*/
75class Cluster
76{
77 friend class ClusterTest;
78
79public:
80 Cluster();
81 ~Cluster();
82
83 Cell* lookup(int x, int y) const;
84
85 /**
86 * Removes all cells from the sheet and frees memory that
87 * was used for the clusters.
88 */
89 void clear();
90
91 /**
92 * Inserts a cell at the requested position. If there is already
93 * a cell, then @ref #remove is called on it.
94 */
95 void insert(Cell* cell, int x, int y);
96 /**
97 * Removes the cell at the given position, if there is any.
98 */
99 void remove(int x, int y);
100
101 void setAutoDelete(bool);
102 bool autoDelete() const;
103
104 Cell* firstCell() const;
105
106 bool insertShiftRight(const QPoint& marker);
107 /**
108 * Moves all cells in the column marker.x() beginning with
109 * the one at marker.y() one position downwards.
110 *
111 * @return false if a cell would drop out of the sheet because of that.
112 * In this case the shift is not performed.
113 */
114 bool insertShiftDown(const QPoint& marker);
115
116 /**
117 * Moves all cells in the column marker.x() beginning with
118 * the one at marker.y() + 1 one position upwards.
119 */
120 void removeShiftUp(const QPoint& marker);
121 void removeShiftLeft(const QPoint& marker);
122
123 /**
124 * Moves all columns beginning with @p col one position
125 * to the right. If that does not work because a cell would
126 * drop out of the sheet, then false is returned.
127 *
128 * @see #removeColumn
129 */
130 bool insertColumn(int col);
131 bool insertRow(int row);
132
133 /**
134 * Removes all elements from the column and
135 * move all columns right of @p col one position
136 * to the left.
137 *
138 * @see #clearColumn
139 */
140 void removeColumn(int col);
141 void removeRow(int row);
142
143 /**
144 * Removes all elements from the column.
145 *
146 */
147 void clearColumn(int col);
148 void clearRow(int row);
149
150 /** Retrieve a range of values stored in a Value.
151 The range is two-leveled with similar structure and reasoning as the
152 storage of cells themselves.
153 */
154 Value valueRange(int col1, int row1, int col2, int row2) const;
155
156 /**
157 * Retrieve the first used cell in a given column. Can be used in conjunction
158 * with getNextCellDown to loop through a column.
159 *
160 * @param col The column to get the first cell from
161 *
162 * @return Returns a pointer to the cell, or 0 if there are no used cells
163 * in this column
164 */
165 Cell* getFirstCellColumn(int col) const;
166
167 /**
168 * Retrieve the last used cell in a given column. Can be used in conjunction
169 * with getNextCellUp to loop through a column.
170 *
171 * @param col The column to get the cell from
172 *
173 * @return Returns a pointer to the cell, or 0 if there are no used cells
174 * in this column
175 */
176 Cell* getLastCellColumn(int col) const;
177
178 /**
179 * Retrieve the first used cell in a given row. Can be used in conjunction
180 * with getNextCellRight to loop through a row.
181 *
182 * @param row The row to get the first cell from
183 *
184 * @return Returns a pointer to the cell, or 0 if there are no used cells
185 * in this row
186 */
187 Cell* getFirstCellRow(int row) const;
188
189 /**
190 * Retrieve the last used cell in a given row. Can be used in conjunction
191 * with getNextCellLeft to loop through a row.
192 *
193 * @param row The row to get the last cell from
194 *
195 * @return Returns a pointer to the cell, or 0 if there are no used cells
196 * in this row
197 */
198 Cell* getLastCellRow(int row) const;
199
200 /**
201 * Retrieves the next used cell above the given col/row pair. The given
202 * col/row pair does not need to reference a used cell.
203 *
204 * @param col column to start looking through
205 * @param row the row above which to start looking.
206 *
207 * @return Returns the next used cell above this one, or 0 if there are none
208 */
209 Cell* getNextCellUp(int col, int row) const;
210
211 /**
212 * Retrieves the next used cell below the given col/row pair. The given
213 * col/row pair does not need to reference a used cell.
214 *
215 * @param col column to start looking through
216 * @param row the row below which to start looking.
217 *
218 * @return Returns the next used cell below this one, or 0 if there are none
219 */
220 Cell* getNextCellDown(int col, int row) const;
221
222 /**
223 * Retrieves the next used cell to the right of the given col/row pair.
224 * The given col/row pair does not need to reference a used cell.
225 *
226 * @param col the column after which should be searched
227 * @param row the row to search through
228 *
229 * @return Returns the next used cell to the right of this one, or 0 if
230 * there are none
231 */
232 Cell* getNextCellRight(int col, int row) const;
233
234 /**
235 * Retrieves the next used cell to the left of the given col/row pair.
236 * The given col/row pair does not need to reference a used cell.
237 *
238 * @param col the column before which should be searched
239 * @param row the row to search through
240 *
241 * @return Returns the next used cell to the left of this one, or 0 if
242 * there are none
243 */
244 Cell* getNextCellLeft(int col, int row) const;
245
246private:
247 /**
248 * @param work is set to true if the method found some clusters
249 * which belong to the shifted row.
250 */
251 bool insertShiftRight(const QPoint& marker, bool& work);
252 bool insertShiftDown(const QPoint& marker, bool& work);
253
254 void removeShiftUp(const QPoint& marker, bool& work);
255 void removeShiftLeft(const QPoint& marker, bool& work);
256
257 /** helper method used by valueRange */
258 Value makeArray(int col1, int row1, int col2, int row2) const;
259
260 Cell*** m_cluster;
261 Cell* m_first;
262 bool m_autoDelete;
263 int m_biggestX, m_biggestY;
264};
265
266/**
267 * \ingroup Storage
268 * A pointer map to all column formats.
269 * \see Cluster
270 */
271class ColumnCluster
272{
273public:
274 ColumnCluster();
275 ~ColumnCluster();
276
277 const ColumnFormat* lookup(int col) const;
278 ColumnFormat* lookup(int col);
279
280 void clear();
281
282 void insertElement(ColumnFormat*, int col);
283 void removeElement(int col);
284
285 bool insertColumn(int col);
286 bool removeColumn(int col);
287
288 void setAutoDelete(bool);
289 bool autoDelete() const;
290
291 ColumnFormat* first() const {
292 return m_first;
293 }
294 ColumnFormat* next(int col) const;
295
296 void operator=(const ColumnCluster& other);
297
298private:
299 ColumnCluster(const ColumnCluster& other);
300
301private:
302 ColumnFormat*** m_cluster;
303 ColumnFormat* m_first;
304 bool m_autoDelete;
305};
306
307/**
308 * \ingroup Storage
309 * A pointer map to all row formats.
310 * \see Cluster
311 */
312class RowCluster
313{
314public:
315 RowCluster();
316 ~RowCluster();
317
318 const RowFormat* lookup(int col) const;
319 RowFormat* lookup(int col);
320
321 void clear();
322
323 void insertElement(RowFormat*, int row);
324 void removeElement(int row);
325
326 bool insertRow(int row);
327 bool removeRow(int row);
328
329 void setAutoDelete(bool);
330 bool autoDelete() const;
331
332 RowFormat* first()const {
333 return m_first;
334 }
335
336 void operator=(const RowCluster& other);
337
338private:
339 RowCluster(const RowCluster& other);
340
341private:
342 RowFormat*** m_cluster;
343 RowFormat* m_first;
344 bool m_autoDelete;
345};
346
347} // namespace Sheets
348} // namespace Calligra
349
350#endif
351