Project

General

Profile

Statistics
| Branch: | Revision:

root / include / pdf.h @ 8b911557

History | View | Annotate | Download (6.47 KB)

1
//==========================================================================
2
//   PDF.H  -  header for
3
//                     OMNeT++/OMNEST
4
//            Discrete System Simulation in C++
5
//
6
//
7
//  Declaration of the following classes:
8
//    Pdf          : probability distribution functionality
9
//
10
//==========================================================================
11

    
12
/*--------------------------------------------------------------*
13
 Copyright (C) 2013 Mirko Stoffers
14

15
 This file is distributed WITHOUT ANY WARRANTY. See the file
16
 `license' for details on this and other legal matters.
17
 *--------------------------------------------------------------*/
18

    
19
#pragma once
20

    
21
class Pdf
22
{
23
        private:
24
                typedef struct Bin
25
                {
26
                        public:
27
                                simtime_t rightBorder;
28
                                size_t bin;
29

    
30
                                bool operator<(const Bin& b)
31
                                {
32
                                        return this->rightBorder<b.rightBorder;
33
                                }
34

    
35
                                bool operator<=(const Bin& b)
36
                                {
37
                                        return this->rightBorder<=b.rightBorder;
38
                                }
39

    
40
                                bool operator>(const Bin& b)
41
                                {
42
                                        return this->rightBorder>b.rightBorder;
43
                                }
44

    
45
                                bool operator>=(const Bin& b)
46
                                {
47
                                        return this->rightBorder>=b.rightBorder;
48
                                }
49
                } bin_t;
50

    
51
                static const size_t size=9; // MUST BE (2^n)+1 for some integer n (like 3,5,9,17,...)
52
                size_t bins[size];
53
                simtime_t leftBorders[size+1];
54
                simtime_t* rightBorders;
55
                size_t count;
56
                size_t baseLine;
57
                bool isDet;
58
                simtime_t detVal;
59

    
60
                Pdf& convolveInPlaceDetDet(const Pdf& b)
61
                {
62
                        this->detVal+=b.detVal;
63
                        this->count*=b.count;
64
                        this->baseLine*=b.baseLine;
65
                        return *this;
66
                }
67

    
68
                Pdf& convolveInPlaceDetBin(const Pdf& b)
69
                {
70
                        memcpy(this->bins,b.bins,sizeof(bins));
71
                        memcpy(this->leftBorders,b.leftBorders,sizeof(leftBorders));
72
                        rightBorders=&(leftBorders[1]);
73
                        this->baseLine*=b.baseLine;
74
                        this->isDet=false;
75
                        bins[0]*=this->count;
76
                        for(size_t i=1;i<size;i++)
77
                        {
78
                                leftBorders[i]+=this->detVal;
79
                                bins[i]*=this->count;
80
                        }
81
                        return *this;
82
                }
83

    
84
                Pdf& convolveInPlaceBinDet(const Pdf& b)
85
                {
86
                        this->baseLine*=b.baseLine;
87
                        bins[0]*=b.count;
88
                        for(size_t i=1;i<size;i++)
89
                        {
90
                                leftBorders[i]+=b.detVal;
91
                                bins[i]*=b.count;
92
                        }
93
                        return *this;
94
                }
95

    
96
                Pdf& convolveInPlaceBinBin(const Pdf& b)
97
                {
98
                        const size_t s1=size-1;
99
                        size_t from=1;
100
                        size_t to=0;
101
                        bin_t matrix[size][s1*s1][2];
102
                        bin_t b1,b2;
103

    
104
                        for(size_t i=0;i<s1;i++)
105
                        {
106
                                for(size_t j=0;j<s1;j++)
107
                                {
108
                                        matrix[i][j][to].rightBorder=this->rightBorders[i]+b.rightBorders[j];
109
                                        matrix[i][j][to].bin=this->bins[i]*b.bins[j];
110
                                }
111
                        }
112

    
113
                        size_t m;
114
                        for(m=1;m<s1;m*=2)
115
                        {
116
                                from=1-from;
117
                                to=1-to;
118
                                for(size_t i=0;i<s1/m;i+=2)
119
                                {
120
                                        size_t k=0;
121
                                        size_t l=0;
122
                                        for(size_t j=0;j<m*2*s1;j++)
123
                                        {
124
                                                if(k<m*s1) b1=matrix[i][k][from];
125
                                                else
126
                                                {
127
                                                        b1.bin=(size_t)-1;
128
                                                        b1.rightBorder=MAXTIME;
129
                                                }
130
                                                if(l<m*s1) b2=matrix[i+1][l][from];
131
                                                else
132
                                                {
133
                                                        b2.bin=(size_t)-1;
134
                                                        b2.rightBorder=MAXTIME;
135
                                                }
136
                                                if(b1<=b2)
137
                                                {
138
                                                        matrix[i/2][j][to]=b1;
139
                                                        k++;
140
                                                }
141
                                                else
142
                                                {
143
                                                        matrix[i/2][j][to]=b2;
144
                                                        l++;
145
                                                }
146
                                        }
147
                                }
148
                        }
149
                        assert(m==s1);
150

    
151
                        // now we have the sorted borders in borderMatrix[0][x][to]
152

    
153
                        for(size_t i=0;i<s1;i++)
154
                        {
155
                                this->bins[i]=0;
156
                                for(size_t j=0;j<s1;j++)
157
                                {
158
                                        this->bins[i]+=matrix[0][j+i*s1][to].bin;
159
                                }
160
                                this->rightBorders[i]=matrix[0][s1-1+i*s1][to].rightBorder;
161
                        }
162
                        this->bins[s1]*=b.bins[s1];
163
                        this->baseLine*=b.baseLine;
164
                        return *this;
165
                }
166

    
167
                void insert(simtime_t delay, size_t count=1)
168
                {
169
                        for(size_t i=0;i<size;i++)
170
                        {
171
                                if(leftBorders[i]<=delay&&rightBorders[i]>=delay)
172
                                {
173
                                        bins[i]+=count;
174
                                        return;
175
                                }
176
                        }
177
                        assert(false);
178
                }
179

    
180
                void convertDetToNonDet(simtime_t delay)
181
                {
182
                        rightBorders=&(leftBorders[1]);
183
                        /*
184
                         * Borders:
185
                         * a=min/2
186
                         * b=max*2
187
                         * d=b-a
188
                         * 0: -inf                a
189
                         * 1: a+d*1/8        a+d*2/8
190
                         * 2: a+d*2/8        a+d*3/8
191
                         * 3: a+d*3/8        a+d*4/8
192
                         * 4: a+d*4/8        a+d*5/8
193
                         * 5: a+d*5/8        a+d*6/8
194
                         * 6: a+d*6/8        a+d*7/8
195
                         * 7: a+d*7/8        a+d*8/8
196
                         * 8: b                        inf
197
                         */
198
                        simtime_t min=delay<detVal?delay:detVal;
199
                        simtime_t max=delay<detVal?detVal:delay;
200
                        simtime_t a=min/2;
201
                        simtime_t b=max/2;
202
                        simtime_t step=(b-a)/(size-1);
203
                        leftBorders[0]=MINTIME;
204
                        bins[0]=0;
205
                        simtime_t next=a;
206
                        for(size_t i=1;i<size;i++)
207
                        {
208
                                bins[i]=0;
209
                                leftBorders[i]=next;
210
                                next+=step;
211
                        }
212
                        rightBorders[size-1]=MAXTIME;
213
                        isDet=false;
214
                        insert(detVal,count);
215
                        insert(delay);
216
                        assert(isValidPdf());
217
                }
218

    
219
        public:
220
                Pdf(simtime_t delay,size_t baseLine)
221
                {
222
                        isDet=true;
223
                        detVal=delay;
224
                        count=1;
225
                        this->baseLine=baseLine;
226
                        assert(isValidPdf());
227
                }
228

    
229
                Pdf(const Pdf& other)
230
                {
231
                        memcpy(this,&other,sizeof(*this));
232
                        rightBorders=&(leftBorders[1]);
233
                }
234

    
235
                Pdf& operator+=(const Pdf& b)
236
                {
237
                        if( this->isDet &&  b.isDet)
238
                                convolveInPlaceDetDet(b);
239
                        else if( this->isDet && !b.isDet)
240
                                convolveInPlaceDetBin(b);
241
                        else if(!this->isDet &&  b.isDet)
242
                                convolveInPlaceBinDet(b);
243
                        else if(!this->isDet && !b.isDet)
244
                                convolveInPlaceBinBin(b);
245
                        else
246
                                assert(false);
247
                        //print();
248
                        assert(isValidPdf());
249
                        return *this;
250
                }
251

    
252
                double getProbability(simtime_t val) const
253
                {
254
                        if(isDet && detVal< val) return 1;
255
                        if(isDet && detVal>=val) return 0;
256

    
257
                        size_t sum=0;
258
                        for(size_t i=0;i<size;i++)
259
                        {
260
                                if(leftBorders[i]<val) sum+=bins[i];
261
                                else return (double)sum/baseLine;
262
                        }
263
                        return (double)sum/baseLine;
264
                }
265

    
266
                void sample(simtime_t delay)
267
                {
268
                        if(isDet)
269
                        {
270
                                if(detVal==delay) count++;
271
                                else convertDetToNonDet(delay);
272
                        }
273
                        else
274
                        {
275
                                insert(delay);
276
                        }
277
                        assert(isValidPdf());
278
                }
279

    
280
                void print() const
281
                {
282
                        std::cout << "printing " << this << std::endl;
283
                        std::cout << "base line: " << baseLine << std::endl;
284
                        if(isDet)
285
                        {
286
                                std::cout << "Deterministic, value: " << detVal << std::endl;
287
                        }
288
                        else
289
                        {
290
                                std::cout << "=======" << std::endl;
291
                                std::cout << leftBorders << "," << &(leftBorders[1]) << "," << rightBorders << std::endl;
292
                                assert(rightBorders==&(leftBorders[1]));
293
                                for(size_t i=0;i<size;i++)
294
                                        std::cout << "[" << leftBorders[i] << ";" << rightBorders[i] << "]: " << bins[i] << std::endl;
295
                                std::cout << "=======" << std::endl;
296
                        }
297
                }
298

    
299
                bool isValidPdf() const
300
                {
301
                        if(isDet)
302
                        {
303
                                return count!=0 && count <= baseLine;
304
                        }
305
                        else
306
                        {
307
                                size_t sum=0;
308
                                for(size_t i=0;i<size;i++)
309
                                {
310
                                        if(leftBorders[i]>rightBorders[i]) return false;
311
                                        sum+=bins[i];
312
                                }
313
                                if(sum>baseLine) return false;
314
                                else return true;
315
                        }
316
                }
317

    
318
                void setBaseLine(size_t newBaseLine)
319
                {
320
                        baseLine=newBaseLine;
321
                }
322
};
323