summaryrefslogtreecommitdiffstats
path: root/kspread/kspread_cluster.h
blob: 702fc746c19a73d21a29bb868be44787038bcc5f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
/* This file is part of the KDE project
   Copyright (C) 2000 Torben Weis <weis@kde.org>

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.

   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Library General Public License for more details.

   You should have received a copy of the GNU Library General Public License
   along with this library; see the file COPYING.LIB.  If not, write to
   the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
*/

#ifndef kspread_cluster_h
#define kspread_cluster_h

#include "kspread_value.h"

#define KSPREAD_CLUSTER_LEVEL1 128
#define KSPREAD_CLUSTER_LEVEL2 256
#define KSPREAD_CLUSTER_MAX (128*256)

class TQPoint;

namespace KSpread
{
class Cell;
class ColumnFormat;
class RowFormat;

/** Philipp
This class defines a pointer map to all cells, which makes access to them more performant
and additionally limits memory consumption.

In detail: The class defines 2 cluster, where the second cluster (LEVEL2) is a matrix for
single cells, while the first cluster (LEVEL1) is a matrix to handle the matrices of LEVEL2.
On initialization, one LEVEL1 matrix is generated only.
Each time, a cell stores something, this class checks if for the given column and row a
matrix of LEVEL2 is already initialized and in case not generates it on the fly.
This helps to reduce the memory usage to only consum one pointer matrix for LEVEL1 and all
matrices of LEVEL2 that are necessary.

LEVEL1 is defined as 128x128 matrix.
LEVEL2 is defined as 256x256 matrices.
Each direction then can have LEVEL1 * LEVEL2 = 128*256 = 2^15 different cells, which
is in total (2^15)^2 cells.

It can be changed easily to different sizes, but it should be more senseful to have a small LEVEL1,
as in most cases only one/two entries in LEVEL1 will be used.

There are 2 additional special classes to store pointers for column and row formats.

Future enhancements:
To reduce memory consumption, it should be possible to enhance the functionality by
another LEVEL0, which then keeps the LEVEL1 size smaller.

Maybe the LEVEL1 should only be generated when there is a need for more than 1 LEVEL2.

LEVEL1 maybe reallocated.

Another interesting possibility would be to differentiate between x size and y size. Currently both
are equal in both matrizes, but normally it will be the regular case, that you have more need for
a lot of rows than columns. Maybe something like LEVEL1=128/256 and LEVEL2=256/128 (x/y), still keeping
2^15 values/cells in each direction (benefit: you won't loose memory in empty columns).
*/
class Cluster
{
public:
    Cluster();
    ~Cluster();

    Cell* lookup( int x, int y ) const;

    /**
     * Removes all cells from the sheet and frees memory that
     * was used for the clusters.
     */
    void clear();

    /**
     * Inserts a cell at the requested position. If there is already
     * a cell, then @ref #remove is called on it.
     */
    void insert( Cell* cell, int x, int y );
    /**
     * Removes the cell at the given position, if there is any.
     */
    void remove( int x, int y );

    void setAutoDelete( bool );
    bool autoDelete() const;

    Cell* firstCell() const;

    bool shiftRow( const TQPoint& marker );
    /**
     * Moves all cells in the column marker.x() beginning with
     * the one at marker.y() one position downwards.
     *
     * @return false if a cell would drop out of the sheet because of that.
     *         In this case the shift is not performed.
     */
    bool shiftColumn( const TQPoint& marker );

    /**
     * Moves all cells in the column marker.x() beginning with
     * the one at marker.y() + 1 one position upwards.
     */
    void unshiftColumn( const TQPoint& marker );
    void unshiftRow( const TQPoint& marker );

    /**
     * Moves all columns beginning with @p col one position
     * to the right. If that does not work because a cell would
     * drop out of the sheet, then false is returned.
     *
     * @see #removeColumn
     */
    bool insertColumn( int col );
    bool insertRow( int row );

    /**
     * Removes all elements from the column and
     * move all columns right of @p col one position
     * to the left.
     *
     * @see #clearColumn
     */
    void removeColumn( int col );
    void removeRow( int row );

    /**
     * Removes all elements from the column.
     *
     */
    void clearColumn( int col );
    void clearRow( int row );

  /** Retrieve a range of values stored in a Value.
  The range is two-leveled with similar structure and reasoning as the
  storage of cells themselves.
  */
  Value valueRange (int col1, int row1, int col2, int row2) const;

  /**
   * Retrieve the first used cell in a given column.  Can be used in conjunction
   * with getNextCellDown to loop through a column.
   *
   * @param col The column to get the first cell from
   *
   * @return Returns a pointer to the cell, or NULL if there are no used cells
   *         in this column
   */
  Cell* getFirstCellColumn(int col) const;

  /**
   * Retrieve the last used cell in a given column.  Can be used in conjunction
   * with getNextCellUp to loop through a column.
   *
   * @param col The column to get the cell from
   *
   * @return Returns a pointer to the cell, or NULL if there are no used cells
   *         in this column
   */
  Cell* getLastCellColumn(int col) const;

  /**
   * Retrieve the first used cell in a given row.  Can be used in conjunction
   * with getNextCellRight to loop through a row.
   *
   * @param row The row to get the first cell from
   *
   * @return Returns a pointer to the cell, or NULL if there are no used cells
   *         in this row
   */
  Cell* getFirstCellRow(int row) const;

  /**
   * Retrieve the last used cell in a given row.  Can be used in conjunction
   * with getNextCellLeft to loop through a row.
   *
   * @param row The row to get the last cell from
   *
   * @return Returns a pointer to the cell, or NULL if there are no used cells
   *         in this row
   */
  Cell* getLastCellRow(int row) const;

  /**
   * Retrieves the next used cell above the given col/row pair.  The given
   * col/row pair does not need to reference a used cell.
   *
   * @param col column to start looking through
   * @param row the row above which to start looking.
   *
   * @return Returns the next used cell above this one, or NULL if there are none
   */
  Cell* getNextCellUp(int col, int row) const;

  /**
   * Retrieves the next used cell below the given col/row pair.  The given
   * col/row pair does not need to reference a used cell.
   *
   * @param col column to start looking through
   * @param row the row below which to start looking.
   *
   * @return Returns the next used cell below this one, or NULL if there are none
   */
  Cell* getNextCellDown(int col, int row) const;

  /**
   * Retrieves the next used cell to the right of the given col/row pair.
   * The given col/row pair does not need to reference a used cell.
   *
   * @param col the column after which should be searched
   * @param row the row to search through
   *
   * @return Returns the next used cell to the right of this one, or NULL if
   * there are none
   */
  Cell* getNextCellRight(int col, int row) const;

  /**
   * Retrieves the next used cell to the left of the given col/row pair.
   * The given col/row pair does not need to reference a used cell.
   *
   * @param col the column before which should be searched
   * @param row the row to search through
   *
   * @return Returns the next used cell to the left of this one, or NULL if
   * there are none
   */
  Cell* getNextCellLeft(int col, int row) const;

private:
    /**
     * @param work is set to true if the method found some clusters
     *        which belong to the shifted row.
     */
    bool shiftRow( const TQPoint& marker, bool& work );
    bool shiftColumn( const TQPoint& marker, bool& work );

    void unshiftColumn( const TQPoint& marker, bool& work );
    void unshiftRow( const TQPoint& marker, bool& work );

    /** helper method used by valueRange */
    Value makeArray (int col1, int row1, int col2, int row2) const;

    Cell*** m_cluster;
    Cell* m_first;
    bool m_autoDelete;
    int m_biggestX, m_biggestY;
};

class ColumnCluster
{
public:
    ColumnCluster();
    ~ColumnCluster();

    const ColumnFormat* lookup( int col ) const;
    ColumnFormat* lookup( int col );

    void clear();

    void insertElement( ColumnFormat*, int col );
    void removeElement( int col );

    bool insertColumn( int col );
    bool removeColumn( int col );

    void setAutoDelete( bool );
    bool autoDelete() const;

    ColumnFormat* first() const { return m_first; }
    ColumnFormat* next( int col ) const;

private:
    ColumnFormat*** m_cluster;
    ColumnFormat* m_first;
    bool m_autoDelete;
};

class RowCluster
{
public:
    RowCluster();
    ~RowCluster();

    const RowFormat* lookup( int col ) const;
    RowFormat* lookup( int col );

    void clear();

    void insertElement( RowFormat*, int row );
    void removeElement( int row );

    bool insertRow( int row );
    bool removeRow( int row );

    void setAutoDelete( bool );
    bool autoDelete() const;

    RowFormat* first()const { return m_first; }

private:
    RowFormat*** m_cluster;
    RowFormat* m_first;
    bool m_autoDelete;
};

} // namespace KSpread;

#endif