root / include / cksplit.h @ b781545c
History  View  Annotate  Download (10.2 KB)
1 
//==========================================================================


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 ksplit algorithm in 1 dimension

9 
//

10 
// Author: Babak Fakhamzadeh, TU Delft, MarJun 1996;

11 
// Rewritten by Andras Varga

12 
//

13 
//==========================================================================

14  
15 
/**

16 
Copyright (C) 19922008 Andras Varga

17 
Copyright (C) 20062008 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 ksplit, an adaptive histogramlike 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 ksplit

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 multiline 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 ksplit

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 precollected values into the ksplit 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 ksplit algorithm. */

304 
//@{

305  
306 
/**

307 
* Configures the ksplit algorithm by supplying a custom split

308 
* criterion function.

309 
*/

310 
void setCritFunc(CritFunc _critfunc, double *_critdata); 
311  
312 
/**

313 
* Configures the ksplit 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 ksplit 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 ksplit data structure. */

330 
//@{

331  
332 
/**

333 
* Returns the depth of the ksplit tree.

334 
*/

335 
int getTreeDepth() const; 
336  
337 
/**

338 
* Returns the depth of the ksplit 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 ksplit data structure to ev.

350 
*/

351 
void printGrids() const; 
352  
353 
/**

354 
* Returns the kth grid in the ksplit data structure.

355 
*/

356 
Grid& getGrid(int k) const {return gridv[k];} 
357  
358 
/**

359 
* Returns the root grid of the ksplit 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

379 