Project

General

Profile

Statistics
| Branch: | Revision:

root / include / cksplit.h @ 0e7ff5c8

History | View | Annotate | Download (10.2 KB)

1 01873262 Georg Kunz
//==========================================================================
2
//  CKSPLIT.H - part of
3
//                     OMNeT++/OMNEST
4
//            Discrete System Simulation in C++
5
//
6
//
7
//  Declaration of the following classes:
8
//    cKSplit : implements the k-split algorithm in 1 dimension
9
//
10
//  Author: Babak Fakhamzadeh, TU Delft, Mar-Jun 1996;
11
//  Rewritten by Andras Varga
12
//
13
//==========================================================================
14
15
/*--------------------------------------------------------------*
16
  Copyright (C) 1992-2008 Andras Varga
17
  Copyright (C) 2006-2008 OpenSim Ltd.
18

19
  This file is distributed WITHOUT ANY WARRANTY. See the file
20
  `license' for details on this and other legal matters.
21
*--------------------------------------------------------------*/
22
23
#ifndef __CKSPLIT_H
24
#define __CKSPLIT_H
25
26
#include "cdensityestbase.h"
27
28
NAMESPACE_BEGIN
29
30
31
/**
32
 * Implements k-split, an adaptive histogram-like density estimation
33
 * algorithm.
34
 *
35
 * @ingroup Statistics
36
 * @see Iterator Grid
37
 */
38
class SIM_API cKSplit : public cDensityEstBase
39
{
40
  public:
41
    /**
42
     * K is the grid size of the algorithm. It must be 2, or a >=3 odd number.
43
     */
44
    enum { K = 2 };
45
46
    /**
47
     * Supporting struct for cKSplit. Represents one grid in the k-split
48
     * data structure.
49
     */
50
    struct Grid
51
    {
52
      int parent;      ///< index of parent grid
53
      int reldepth;    ///< depth = (reldepth - rootgrid's reldepth)
54
      long total;      ///< sum of cells & all subgrids (also includes 'mother')
55
      int mother;      ///< observations 'inherited' from mother cell
56
      int cells[K];    ///< cell values
57
    };
58
59
    /**
60
     * Prototype for cell split criterion functions used by cKSplit objects.
61
     * @ingroup EnumsTypes
62
     */
63
    typedef int (*CritFunc)(const cKSplit&, cKSplit::Grid&, int, double *);
64
65
    /**
66
     * Prototype for cell division criterion functions used by cKSplit objects.
67
     * @ingroup EnumsTypes
68
     */
69
    typedef double (*DivFunc)(const cKSplit&, cKSplit::Grid&, double, double *);
70
71
    /**
72
     * Walks along cells of the distribution stored in a cKSplit object.
73
     */
74
    class Iterator
75
    {
76
      private:
77
        cKSplit *ks;             // host object
78
        int cellnum;             // global index of current cell
79
        int grid, cell;          // root index in gridv[], cell index in grid.cell[]
80
        double gridmin;          // left edge of current grid
81
        double cellsize;         // cell width on current grid
82
83
        // internal
84
        void dive(int where);
85
86
      public:
87
        /**
88
         * Constructor.
89
         */
90
        Iterator(const cKSplit& ksplit, bool atbeginning=true);
91
92
        /**
93
         * Reinitializes the iterator.
94
         */
95
        void init(const cKSplit& ksplit, bool atbeginning=true);
96
97
        /**
98
         * Moves the iterator to the next cell.
99
         */
100
        void operator++(int);
101
102
        /**
103
         * Moves the iterator to the previous cell.
104
         */
105
        void operator--(int);
106
107
        /**
108
         * Returns true if the iterator has reached either end of the cell sequence.
109
         */
110
        bool end() const  {return grid==0;}
111
112
        /**
113
         * Returns the index of the current cell.
114
         */
115
        int getCellNumber() const  {return cellnum;}
116
117
        /**
118
         * Returns the upper lower of the current cell.
119
         */
120
        double getCellMin() const  {return gridmin+cell*cellsize;}
121
122
        /**
123
         * Returns the upper bound of the current cell.
124
         */
125
        double getCellMax() const  {return gridmin+(cell+1)*cellsize;}
126
127
        /**
128
         * Returns the size of the current cell.
129
         */
130
        double getCellSize() const  {return cellsize;}
131
132
        /**
133
         * Returns the actual amount of observations in current cell.
134
         * This is not necessarily an integer value because of previous cell splits.
135
         */
136
        double getCellValue() const;
137
    };
138
139
    friend class Iterator;
140
141
  protected:
142
    int num_cells;            // number of cells
143
144
    Grid *gridv;              // grid vector
145
    int gridv_size;           // size of gridv[]+1
146
    int rootgrid, lastgrid;   // indices into gridv[]
147
    bool rangeext_enabled;    // enable/disable range extension
148
149
    CritFunc critfunc;        // function that determines when to split a cell
150
    double *critdata;         // data array to pass to crit. function
151
152
    DivFunc divfunc;          // function to calc. lambda for cell division
153
    double *divdata;          // data array to pass to div. function
154
155
    mutable Iterator *iter;   // iterator used by getBasepoint(), getCellValue() etc.
156
    mutable long iter_num_vals; // num_vals when iterator was created
157
158
  protected:
159
    // internal:
160
    void resetGrids(int grid);
161
162
    // internal:
163
    void createRootGrid();
164
165
    // internal:
166
    void newRootGrids(double x);
167
168
    // internal:
169
    void insertIntoGrids(double x, int enable_splits);
170
171
    // internal:
172
    void splitCell(int grid, int cell);
173
174
    // internal:
175
    void distributeMotherObservations(int grid);
176
177
    // internal:
178
    void expandGridVector();
179
180
    // internal: helper for getBasepoint(), getCellValue()
181
    void iteratorToCell(int cell_nr) const;
182
183
    // abstract method in cDensityEstBase
184
    virtual void doMergeCellValues(const cDensityEstBase *other);
185
186
  public:
187
    /** @name Constructors, destructor, assignment. */
188
    //@{
189
190
    /**
191
     * Copy constructor.
192
     */
193
    cKSplit(const cKSplit& r);
194
195
    /**
196
     * Constructor.
197
     */
198
    explicit cKSplit(const char *name=NULL);
199
200
    /**
201
     * Destructor.
202
     */
203
    virtual ~cKSplit();
204
205
    /**
206
     * Assignment operator. The name member is not copied; see cNamedObject's operator=() for more details.
207
     */
208
    cKSplit& operator=(const cKSplit& res);
209
    //@}
210
211
    /** @name Redefined cObject member functions. */
212
    //@{
213
214
    /**
215
     * Creates and returns an exact copy of this object.
216
     * See cObject for more details.
217
     */
218
    virtual cKSplit *dup() const  {return new cKSplit (*this);}
219
220
    /**
221
     * Produces a multi-line description of the object's contents.
222
     * See cObject for more details.
223
     */
224
    virtual std::string detailedInfo() const;
225
226
    /**
227
     * Serializes the object into an MPI send buffer.
228
     * Used by the simulation kernel for parallel execution.
229
     * See cObject for more details.
230
     */
231
    virtual void parsimPack(cCommBuffer *buffer);
232
233
    /**
234
     * Deserializes the object from an MPI receive buffer.
235
     * Used by the simulation kernel for parallel execution.
236
     * See cObject for more details.
237
     */
238
    virtual void parsimUnpack(cCommBuffer *buffer);
239
    //@}
240
241
  protected:
242
    /**
243
     * Called internally by collect(), this method updates the k-split
244
     * data structure with the new value.
245
     */
246
    virtual void collectTransformed(double val);
247
248
  public:
249
    /** @name Redefined member functions from cStatistic and its subclasses. */
250
    //@{
251
252
    /**
253
     * Transforms the table of pre-collected values into the k-split data structure.
254
     */
255
    virtual void transform();
256
257
    /**
258
     * Returns the number of histogram cells used.
259
     */
260
    virtual int getNumCells() const;
261
262
    /**
263
     * Returns the kth cell boundary.
264
     */
265
    virtual double getBasepoint(int k) const;
266
267
    /**
268
     * Returns the number of observations that fell into the kth histogram cell.
269
     */
270
    virtual double getCellValue(int k) const;
271
272
    /**
273
     * Returns the value of the Probability Density Function at a given x.
274
     */
275
    virtual double getPDF(double x) const;
276
277
    /**
278
     * Returns the value of the Cumulated Density Function at a given x.
279
     */
280
    virtual double getCDF(double x) const;
281
282
    /**
283
     * Merging is not supported by this class. This method throws an error.
284
     */
285
    virtual void merge(const cStatistic *other);
286
287
    /**
288
     * Generates a random number based on the collected data. Uses the random number generator set by setGenK().
289
     */
290
    virtual double random() const;
291
292
    /**
293
     * Writes the contents of the object into a text file.
294
     */
295
    virtual void saveToFile(FILE *) const;
296
297
    /**
298
     * Reads the object data from a file, in the format written out by saveToFile().
299
     */
300
    virtual void loadFromFile(FILE *);
301
    //@}
302
303
    /** @name Configuring the k-split algorithm. */
304
    //@{
305
306
    /**
307
     * Configures the k-split algorithm by supplying a custom split
308
     * criterion function.
309
     */
310
    void setCritFunc(CritFunc _critfunc, double *_critdata);
311
312
    /**
313
     * Configures the k-split algorithm by supplying a custom cell division
314
     * function.
315
     */
316
    void setDivFunc(DivFunc _divfunc, double *_divdata);
317
318
    /**
319
     * Enables/disables range extension. If range extension is enabled,
320
     * a new observation that falls outside the k-split range (ie. outside
321
     * the root grid) will cause the range to be expanded (i.e. new
322
     * root getGrid(s) to be placed above the current root grid).
323
     * If range extension is disabled, such observations will simply be
324
     * counted as underflows or overflows.
325
     */
326
    void rangeExtension(bool enabled);
327
    //@}
328
329
    /** @name Querying the k-split data structure. */
330
    //@{
331
332
    /**
333
     * Returns the depth of the k-split tree.
334
     */
335
    int getTreeDepth() const;
336
337
    /**
338
     * Returns the depth of the k-split tree measured from the specified grid.
339
     */
340
    int getTreeDepth(Grid& grid) const;
341
342
    /**
343
     * Returns the actual amount of observations in cell 'cell' of 'grid'.
344
     * This is not necessarily an integer value because of previous cell splits.
345
     */
346
    double getRealCellValue(Grid& grid, int cell) const;
347
348
    /**
349
     * Dumps the contents of the k-split data structure to ev.
350
     */
351
    void printGrids() const;
352
353
    /**
354
     * Returns the kth grid in the k-split data structure.
355
     */
356
    Grid& getGrid(int k) const {return gridv[k];}
357
358
    /**
359
     * Returns the root grid of the k-split data structure.
360
     */
361
    Grid& getRootGrid() const {return gridv[rootgrid];}
362
    //@}
363
};
364
365
366
// cell split criteria
367
int critfunc_const(const cKSplit&, cKSplit::Grid&, int, double *);
368
int critfunc_depth(const cKSplit&, cKSplit::Grid&, int, double *);
369
370
// cell division criteria
371
double divfunc_const(const cKSplit&, cKSplit::Grid&, double, double *);
372
double divfunc_babak(const cKSplit&, cKSplit::Grid&, double, double *);
373
374
375
NAMESPACE_END
376
377
378
#endif