← Back to branch summary

~ubuntu-branches/ubuntu/utopic/dicelab/utopic

« back to all changes in this revision

Viewing changes to optimize.tc

  • Committer: Bazaar Package Importer
  • Author(s): Robert Lemmen
  • Date: 2009-11-25 12:30:05 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20091125123005-ylg50em2n998a232
Tags: 0.7-1
New upstream release

Show diffs side-by-side

added added

removed removed

Lines of Context:
optimize.tc
 
1
%operation %virtual expression* optimize(expression *this)
 
2
 
 
3
%{
 
4
 
 
5
#include <values.h>
 
6
 
 
7
#ifndef MINFLOAT
 
8
#define MINFLOAT        0.0000001
 
9
#endif
 
10
 
 
11
// this is taken from http://en.wikipedia.org/wiki/Dice
 
12
// calculates the probability for value "pos" in the sum of "num" 
 
13
// dice with "sides" faces
 
14
double Fsumdice(double *cache, int mnum, int num, int sides, int pos) {
 
15
        if (pos > ((num*sides-num)/2)+num) {
 
16
                pos = num*sides - pos + num;
 
17
        }
 
18
 
 
19
        if (num == 1) {
 
20
                if ((pos < 1) || (pos > sides)) {
 
21
                        return 0.0;
 
22
                }
 
23
                return 1.0/sides;
 
24
        }
 
25
        else {
 
26
                if (pos < num) {
 
27
                        return 0.0;
 
28
                }
 
29
                int i;
 
30
                if (cache[mnum*(pos-num)+num] < -0.5) {
 
31
                        double ret = 0;
 
32
                        for (i = 1; i < min(pos, sides+1); i++) {
 
33
                                ret += Fsumdice(cache, mnum, 1, sides, i) 
 
34
                                        * Fsumdice(cache, mnum, num-1, sides, pos-i); 
 
35
                        }
 
36
                        cache[mnum*(pos-num)+num] = ret;
 
37
                        return ret;
 
38
                }
 
39
                return cache[mnum*(pos-num)+num];
 
40
        }
 
41
}
 
42
 
 
43
// calculates the probability that the sum of "num" rolls of 
 
44
// distribution "dist" have the value "pos"
 
45
double Fsumany(double *cache, int mnum, int minval, int maxval, int num,
 
46
        struct val_list *dist, int pos) {
 
47
    struct val_list *cdist = dist;
 
48
    if (num == 1) {
 
49
        while (cdist) {
 
50
            if (cdist->values[0] == pos) {
 
51
                return cdist->prob;
 
52
            }
 
53
            cdist = cdist->next;
 
54
        }
 
55
        return 0.0;
 
56
    }
 
57
    else {
 
58
        int cpos = pos*mnum+num;
 
59
        if ((pos < minval * num) || (pos > maxval * pos)) {
 
60
            return 0.0;
 
61
        }
 
62
        if (cache[cpos] < -0.5) {
 
63
                    double ret = 0.0;
 
64
            while (cdist) {
 
65
                ret += cdist->prob * Fsumany(cache, mnum, minval, maxval,
 
66
                    num - 1, dist, pos - cdist->values[0]);
 
67
                cdist = cdist->next;
 
68
            }
 
69
            cache[cpos] = ret;
 
70
            return ret;
 
71
        }
 
72
        return cache[cpos];
 
73
    }
 
74
}
 
75
 
 
76
%}
 
77
 
 
78
// optimized version of sum N#dM
 
79
%node sumrepdice expression =
 
80
{
 
81
        struct val_list *num_dice;
 
82
        int num_sides;
 
83
} 
 
84
 
 
85
roll(sumrepdice) {
 
86
        // unsupported, only used in eval
 
87
}
 
88
 
 
89
printtree(sumrepdice) {
 
90
        // unsupported, only used in eval
 
91
}
 
92
 
 
93
set_symtab(sumrepdice) {
 
94
        // not needed, don't use symtab
 
95
}
 
96
 
 
97
eval(sumrepdice) {
 
98
        int n;
 
99
        struct val_list *ret = NULL;
 
100
        struct val_list *cnum = this->num_dice;
 
101
        while (cnum) {
 
102
                if (cnum->count != 1) {
 
103
                        yyerror("Argument 1 to sumrep operator is not scalar");
 
104
                        list_free(this->num_dice);
 
105
                        list_free(ret);
 
106
                        return error_val();
 
107
                }
 
108
                int num_dice_val = cnum->values[0];
 
109
        if (num_dice_val > 0) {
 
110
            int expected = num_dice_val*
 
111
                ((num_dice_val*this->num_sides-num_dice_val)/2)
 
112
                +num_dice_val+1;
 
113
            double *cache = malloc(sizeof(double) * expected);
 
114
            for (n = 0; n < expected; n++) {
 
115
                cache[n] = -1.0;
 
116
            }
 
117
            for (n = num_dice_val * this->num_sides; 
 
118
                    n >= num_dice_val; n--) {
 
119
                struct val_list *cret = 
 
120
                    (struct val_list*)malloc(sizeof(struct val_list));
 
121
                cret->next = NULL;
 
122
                cret->count = 1;
 
123
                cret->prob = Fsumdice(cache, num_dice_val, num_dice_val, 
 
124
                    this->num_sides, n) * cnum->prob;
 
125
                cret->values = (int*)malloc(sizeof(int));
 
126
                cret->values[0] = n;
 
127
                list_add(&ret, cret, this->ordering);
 
128
            } 
 
129
            free(cache);
 
130
        }
 
131
                cnum = cnum->next;
 
132
        }
 
133
        if (ret == NULL) {
 
134
                return list_new(1, 1.0);
 
135
        }
 
136
        return ret;
 
137
}
 
138
 
 
139
%node sumrepany expression =
 
140
{
 
141
        struct val_list *number;
 
142
        struct val_list *data;
 
143
} 
 
144
 
 
145
roll(sumrepany) {
 
146
        // unsupported, only used in eval
 
147
}
 
148
 
 
149
printtree(sumrepany) {
 
150
        // unsupported, only used in eval
 
151
}
 
152
 
 
153
set_symtab(sumrepany) {
 
154
        // not needed, don't use symtab
 
155
}
 
156
 
 
157
eval(sumrepany) {
 
158
        int n;
 
159
        struct val_list *ret = NULL;
 
160
        struct val_list *cnum = this->number;
 
161
    int minval = -1;
 
162
    int maxval = 0;
 
163
    struct val_list *cval = this->data;
 
164
    while (cval) {
 
165
        if ((minval == -1) || (cval->values[0] < minval)) {
 
166
            minval = cval->values[0];
 
167
        }
 
168
        if (cval->values[0] > maxval) {
 
169
            maxval = cval->values[0];
 
170
        }
 
171
        cval = cval->next;
 
172
    }
 
173
        while (cnum) {
 
174
                if (cnum->count != 1) {
 
175
                        yyerror("Argument 1 to sumrep operator is not scalar");
 
176
                        list_free(this->number);
 
177
                        list_free(this->data);
 
178
                        list_free(ret);
 
179
                        return error_val();
 
180
                }
 
181
        if (cnum->values[0] == 0) {
 
182
            struct val_list *cret = 
 
183
                (struct val_list*)malloc(sizeof(struct val_list));
 
184
            cret->next = NULL;
 
185
            cret->count = 1;
 
186
            cret->prob = cnum->prob;
 
187
            cret->values = (int*)malloc(sizeof(int));
 
188
            cret->values[0] = 0;
 
189
            list_add(&ret, cret, this->ordering);
 
190
        }
 
191
        else {
 
192
            int expected = (cnum->values[0] * maxval + 1) * cnum->values[0] + 1;
 
193
            double *cache = malloc(sizeof(double) * expected);
 
194
            for (n = 0; n < expected; n++) {
 
195
                 cache[n] = -1.0;
 
196
            }
 
197
            for (n = cnum->values[0] * minval; n <= cnum->values[0] * maxval; n++) {
 
198
                struct val_list *cret = 
 
199
                    (struct val_list*)malloc(sizeof(struct val_list));
 
200
                cret->next = NULL;
 
201
                cret->count = 1;
 
202
                cret->prob = Fsumany(cache, cnum->values[0], minval, maxval,
 
203
                    cnum->values[0], this->data, n) * cnum->prob;
 
204
                cret->values = (int*)malloc(sizeof(int));
 
205
                cret->values[0] = n;
 
206
                if (cret->prob > MINFLOAT) { 
 
207
                    list_add(&ret, cret, this->ordering);
 
208
                }
 
209
                else {
 
210
                    list_free(cret);    
 
211
                }
 
212
            }
 
213
            free(cache);
 
214
        }
 
215
                cnum = cnum->next;
 
216
    }
 
217
        if (ret == NULL) {
 
218
                return list_new(1, 1.0);
 
219
        }
 
220
        return ret;
 
221
}
 
222
 
 
223
// optimization fuctions, replaces the tree with a different version
 
224
optimize(expression)
 
225
{
 
226
        return this;
 
227
}
 
228
 
 
229
optimize(binary)
 
230
{
 
231
        this->expr1 = optimize(this->expr1);
 
232
        this->expr2 = optimize(this->expr2);
 
233
        return (expression*)this;
 
234
}
 
235
 
 
236
optimize(unary)
 
237
{
 
238
        this->expr = optimize(this->expr);
 
239
        return (expression*)this;
 
240
}
 
241
 
 
242
optimize(ifthenelse)
 
243
{
 
244
        this->if_expr = optimize(this->if_expr);
 
245
        this->then_expr = optimize(this->then_expr);
 
246
        this->else_expr = optimize(this->else_expr);
 
247
        return (expression*)this;
 
248
}
 
249
 
 
250
optimize(sum)
 
251
{
 
252
        if (yykind(this->expr) == rep_kind) {
 
253
                rep *crep = (rep*)this->expr;
 
254
                if (yykind(crep->expr2) == dice_kind) {
 
255
                        dice *cdice = (dice*)crep->expr2;
 
256
                        if (yykind(cdice->expr) == number_kind) {
 
257
// case: sum N#dM
 
258
                                expression *replace = sumrepdice_create(
 
259
                                        eval(crep->expr1), 
 
260
                                        ((number*)cdice->expr)->num);
 
261
                                return replace;
 
262
                        }
 
263
                }
 
264
                else {
 
265
// case: sum N#XXX
 
266
                        expression *replace = sumrepany_create(
 
267
                                eval(crep->expr1),
 
268
                                eval(sum_create(crep->expr2))); 
 
269
                        return replace;                 
 
270
                }
 
271
        }
 
272
        return (expression*)this;
 
273
}