## root / include / cksplit.h @ 47c4b975

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
``` |