« back to all changes in this revision
Viewing changes to PetriEngine/PQL/Expressions.cpp
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Jonas Finnemann Jensen
- Date: 2011-09-15 13:30:00 UTC
- Revision ID: jopsen@gmail.com-20110915133000-wnywm1odf82emiuw
Import of sources from github
- files added:
- PetriEngine
- PetriEngine/DTAPN
- PetriEngine/PQL
- PetriEngine/Reachability
- PetriEngine/Structures
- PetriParse
- PetriParse/xmlsp
- Tests
added
removed
PetriEngine/PQL/Expressions.cpp
1
/* PeTe - Petri Engine exTremE
2
* Copyright (C) 2011 Jonas Finnemann Jensen <jopsen@gmail.com>,
3
* Thomas Søndersø Nielsen <primogens@gmail.com>,
4
* Lars Kærlund Østergaard <larsko@gmail.com>,
5
*
6
* This program is free software: you can redistribute it and/or modify
7
* it under the terms of the GNU General Public License as published by
8
* the Free Software Foundation, either version 3 of the License, or
9
* (at your option) any later version.
10
*
11
* This program is distributed in the hope that it will be useful,
12
* but WITHOUT ANY WARRANTY; without even the implied warranty of
13
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14
* GNU General Public License for more details.
15
*
16
* You should have received a copy of the GNU General Public License
17
* along with this program. If not, see <http://www.gnu.org/licenses/>.
18
*/
19
#include "Contexts.h"
20
#include "Expressions.h"
21
22
#include <sstream>
23
#include <assert.h>
24
#include <string.h>
25
#include <stdio.h>
26
#include <iostream>
27
#include <set>
28
29
namespace PetriEngine {
30
namespace PQL{
31
32
/******************** Destructors ********************/
33
34
BinaryExpr::~BinaryExpr(){
35
if(_expr1)
36
delete _expr1;
37
_expr1 = NULL;
38
if(_expr2)
39
delete _expr2;
40
_expr2 = NULL;
41
}
42
43
MinusExpr::~MinusExpr(){
44
if(_expr)
45
delete _expr;
46
_expr = NULL;
47
}
48
49
LogicalCondition::~LogicalCondition(){
50
if(_cond1)
51
delete _cond1;
52
_cond1 = NULL;
53
if(_cond2)
54
delete _cond2;
55
_cond2 = NULL;
56
}
57
58
CompareCondition::~CompareCondition(){
59
if(_expr1)
60
delete _expr1;
61
_expr1 = NULL;
62
if(_expr2)
63
delete _expr2;
64
_expr2 = NULL;
65
}
66
67
NotCondition::~NotCondition(){
68
if(_cond)
69
delete _cond;
70
_cond = NULL;
71
}
72
73
/******************** To String ********************/
74
75
std::string LiteralExpr::toString() const{
76
std::stringstream stream;
77
stream <<_value;
78
return stream.str();
79
}
80
81
std::string IdentifierExpr::toString() const{
82
return _name;
83
}
84
85
std::string BinaryExpr::toString() const{
86
return "(" + _expr1->toString() + " " + op() + " " + _expr2->toString() + ")";
87
}
88
89
std::string MinusExpr::toString() const{
90
return "-" + _expr->toString();
91
}
92
93
std::string LogicalCondition::toString() const{
94
return "(" + _cond1->toString() + " " + op() + " " + _cond2->toString() + ")";
95
}
96
97
std::string CompareCondition::toString() const{
98
return "(" + _expr1->toString() + " " + op() + " " + _expr2->toString() + ")";
99
}
100
101
std::string NotCondition::toString() const {
102
return "(not " + _cond->toString() + ")";
103
}
104
105
/******************** To TAPAAL Query ********************/
106
107
std::string LogicalCondition::toTAPAALQuery(TAPAALConditionExportContext& context) const{
108
return " ( " + _cond1->toTAPAALQuery(context) + " " + op() + " " + _cond2->toTAPAALQuery(context) + " ) ";
109
}
110
111
std::string CompareCondition::toTAPAALQuery(TAPAALConditionExportContext& context) const{
112
//If <id> <op> <literal>
113
if(_expr1->type() == Expr::IdentifierExpr && _expr2->type() == Expr::LiteralExpr){
114
return " ( " + context.netName + "." + _expr1->toString() + " " + opTAPAAL() + " " + _expr2->toString() + " ) ";
115
//If <literal> <op> <id>
116
}else if(_expr2->type() == Expr::IdentifierExpr && _expr1->type() == Expr::LiteralExpr){
117
return " ( " + _expr1->toString() + " " + sopTAPAAL() + " " + context.netName + "." + _expr2->toString() + " ) ";
118
}else{
119
context.failed = true;
120
return " false ";
121
}
122
}
123
124
std::string NotEqualCondition::toTAPAALQuery(TAPAALConditionExportContext& context) const{
125
return " !( " + CompareCondition::toTAPAALQuery(context) + " ) ";
126
}
127
128
std::string NotCondition::toTAPAALQuery(TAPAALConditionExportContext& context) const{
129
return " !( " + _cond->toTAPAALQuery(context) + " ) ";
130
}
131
132
/******************** opTAPAAL ********************/
133
134
std::string EqualCondition::opTAPAAL() const { return "="; }
135
std::string NotEqualCondition::opTAPAAL() const { return "="; } //Handled with hack in NotEqualCondition::toTAPAALQuery
136
std::string LessThanCondition::opTAPAAL() const { return "<"; }
137
std::string LessThanOrEqualCondition::opTAPAAL() const { return "<="; }
138
std::string GreaterThanCondition::opTAPAAL() const { return ">"; }
139
std::string GreaterThanOrEqualCondition::opTAPAAL() const { return ">="; }
140
141
std::string EqualCondition::sopTAPAAL() const { return "="; }
142
std::string NotEqualCondition::sopTAPAAL() const { return "="; } //Handled with hack in NotEqualCondition::toTAPAALQuery
143
std::string LessThanCondition::sopTAPAAL() const { return ">="; }
144
std::string LessThanOrEqualCondition::sopTAPAAL() const { return ">"; }
145
std::string GreaterThanCondition::sopTAPAAL() const { return "<="; }
146
std::string GreaterThanOrEqualCondition::sopTAPAAL() const { return "<"; }
147
148
/******************** Context Analysis ********************/
149
150
void BinaryExpr::analyze(AnalysisContext& context){
151
_expr1->analyze(context);
152
_expr2->analyze(context);
153
}
154
155
void MinusExpr::analyze(AnalysisContext& context){
156
_expr->analyze(context);
157
}
158
159
void LiteralExpr::analyze(AnalysisContext&){
160
return;
161
}
162
163
void IdentifierExpr::analyze(AnalysisContext& context){
164
AnalysisContext::ResolutionResult result = context.resolve(_name);
165
if(result.success){
166
_offsetInMarking = result.offset;
167
isPlace = result.isPlace;
168
}
169
else{
170
ExprError error("Unable to resolve identifier \"" + _name + "\"",
171
_srcOffset,
172
_name.length());
173
context.reportError(error);
174
}
175
}
176
177
void LogicalCondition::analyze(AnalysisContext& context){
178
_cond1->analyze(context);
179
_cond2->analyze(context);
180
}
181
182
void CompareCondition::analyze(AnalysisContext& context){
183
_expr1->analyze(context);
184
_expr2->analyze(context);
185
}
186
187
void NotCondition::analyze(AnalysisContext &context){
188
_cond->analyze(context);
189
}
190
191
/******************** Evaluation ********************/
192
193
int BinaryExpr::evaluate(const EvaluationContext& context) const{
194
int v1 = _expr1->evaluate(context);
195
int v2 = _expr2->evaluate(context);
196
return apply(v1, v2);
197
}
198
199
int MinusExpr::evaluate(const EvaluationContext& context) const{
200
return -(_expr->evaluate(context));
201
}
202
203
int LiteralExpr::evaluate(const EvaluationContext&) const{
204
return _value;
205
}
206
207
int IdentifierExpr::evaluate(const EvaluationContext& context) const{
208
assert(_offsetInMarking != -1);
209
if(isPlace)
210
return context.marking()[_offsetInMarking];
211
return context.assignment()[_offsetInMarking];
212
}
213
214
bool LogicalCondition::evaluate(const EvaluationContext& context) const{
215
bool b1 = _cond1->evaluate(context);
216
bool b2 = _cond2->evaluate(context);
217
return apply(b1,b2);
218
}
219
220
bool CompareCondition::evaluate(const EvaluationContext& context) const{
221
int v1 = _expr1->evaluate(context);
222
int v2 = _expr2->evaluate(context);
223
return apply(v1,v2);
224
}
225
226
227
bool NotCondition::evaluate(const EvaluationContext& context) const{
228
return !(_cond->evaluate(context));
229
}
230
231
void AssignmentExpression::evaluate(const MarkVal* m,
232
const VarVal *a,
233
VarVal* result_a,
234
VarVal* ranges,
235
size_t nvars) const{
236
//If the same memory is used for a and result_a, do a little hack...
237
if(a == result_a){
238
VarVal acpy[nvars];
239
memcpy(acpy, a, sizeof(VarVal) * nvars);
240
memcpy(result_a, acpy, sizeof(VarVal) * nvars);
241
EvaluationContext context(m, acpy);
242
for(const_iter it = assignments.begin(); it != assignments.end(); it++)
243
result_a[it->offset] = it->expr->evaluate(context) % (ranges[it->offset]+1);
244
}else{
245
memcpy(result_a, a, sizeof(VarVal) * nvars);
246
EvaluationContext context(m, a);
247
for(const_iter it = assignments.begin(); it != assignments.end(); it++)
248
result_a[it->offset] = it->expr->evaluate(context) % (ranges[it->offset]+1);
249
}
250
}
251
252
/******************** Apply (BinaryExpr subclasses) ********************/
253
254
int PlusExpr::apply(int v1, int v2) const { return v1 + v2; }
255
int SubtractExpr::apply(int v1, int v2) const { return v1 - v2; }
256
int MultiplyExpr::apply(int v1, int v2) const { return v1 * v2; }
257
258
/******************** Apply (LogicalCondition subclasses) ********************/
259
260
bool AndCondition::apply(bool b1, bool b2) const { return b1 && b2; }
261
bool OrCondition::apply(bool b1, bool b2) const { return b1 || b2; }
262
263
/******************** Apply (CompareCondition subclasses) ********************/
264
265
bool EqualCondition::apply(int v1, int v2) const { return v1 == v2; }
266
bool NotEqualCondition::apply(int v1, int v2) const { return v1 != v2; }
267
bool LessThanCondition::apply(int v1, int v2) const { return v1 < v2; }
268
bool LessThanOrEqualCondition::apply(int v1, int v2) const { return v1 <= v2; }
269
bool GreaterThanCondition::apply(int v1, int v2) const { return v1 > v2; }
270
bool GreaterThanOrEqualCondition::apply(int v1, int v2) const { return v1 >= v2; }
271
272
/******************** Op (BinaryExpr subclasses) ********************/
273
274
std::string PlusExpr::op() const { return "+"; }
275
std::string SubtractExpr::op() const { return "-"; }
276
std::string MultiplyExpr::op() const { return "*"; }
277
278
/******************** Op (LogicalCondition subclasses) ********************/
279
280
std::string AndCondition::op() const { return "and"; }
281
std::string OrCondition::op() const { return "or"; }
282
283
/******************** Op (CompareCondition subclasses) ********************/
284
285
std::string EqualCondition::op() const { return "=="; }
286
std::string NotEqualCondition::op() const { return "!="; }
287
std::string LessThanCondition::op() const { return "<"; }
288
std::string LessThanOrEqualCondition::op() const { return "<="; }
289
std::string GreaterThanCondition::op() const { return ">"; }
290
std::string GreaterThanOrEqualCondition::op() const { return ">="; }
291
292
/******************** p-free Expression ********************/
293
294
bool BinaryExpr::pfree() const { return _expr1->pfree() && _expr2->pfree(); }
295
bool MinusExpr::pfree() const { return _expr->pfree(); }
296
bool LiteralExpr::pfree() const { return true; }
297
bool IdentifierExpr::pfree() const { return !this->isPlace; }
298
299
/******************** Expr::type() implementation ********************/
300
301
Expr::Types PlusExpr::type() const { return Expr::PlusExpr; }
302
Expr::Types SubtractExpr::type() const { return Expr::SubtractExpr; }
303
Expr::Types MultiplyExpr::type() const { return Expr::MinusExpr; }
304
Expr::Types MinusExpr::type() const { return Expr::MinusExpr; }
305
Expr::Types LiteralExpr::type() const { return Expr::LiteralExpr; }
306
Expr::Types IdentifierExpr::type() const { return Expr::IdentifierExpr; }
307
308
/******************** Scale Expression ********************/
309
310
void BinaryExpr::scale(int factor) {_expr1->scale(factor); _expr2->scale(factor);}
311
void MinusExpr::scale(int factor) {_expr->scale(factor);}
312
void LiteralExpr::scale(int factor) {_value = _value * factor;}
313
void IdentifierExpr::scale(int) {}
314
315
/******************** Scale Conditions ********************/
316
317
void LogicalCondition::scale(int factor) {_cond1->scale(factor);_cond2->scale(factor);}
318
void CompareCondition::scale(int factor) {_expr1->scale(factor);_expr2->scale(factor);}
319
void NotCondition::scale(int factor) {_cond->scale(factor);}
320
321
/******************** Constraint Analysis ********************/
322
323
void LogicalCondition::findConstraints(ConstraintAnalysisContext& context) const{
324
if(!context.canAnalyze)
325
return;
326
_cond1->findConstraints(context);
327
ConstraintAnalysisContext::ConstraintSet left = context.retval;
328
_cond2->findConstraints(context);
329
mergeConstraints(context.retval, left, context.negated);
330
}
331
332
void AndCondition::mergeConstraints(ConstraintAnalysisContext::ConstraintSet& result,
333
ConstraintAnalysisContext::ConstraintSet& other,
334
bool negated) const{
335
if(!negated)
336
result = Structures::StateConstraints::mergeAnd(result, other);
337
else
338
result = Structures::StateConstraints::mergeOr(result, other);
339
}
340
void OrCondition::mergeConstraints(ConstraintAnalysisContext::ConstraintSet& result,
341
ConstraintAnalysisContext::ConstraintSet& other,
342
bool negated) const{
343
if(!negated)
344
result = Structures::StateConstraints::mergeOr(result, other);
345
else
346
result = Structures::StateConstraints::mergeAnd(result, other);
347
}
348
349
void CompareCondition::findConstraints(ConstraintAnalysisContext& context) const{
350
if(!context.canAnalyze)
351
return;
352
context.retval.clear();
353
if(_expr1->type() == Expr::LiteralExpr && _expr2->type() == Expr::IdentifierExpr){
354
IdentifierExpr* id = (IdentifierExpr*)_expr2;
355
LiteralExpr* literal = (LiteralExpr*)_expr1;
356
addConstraints(context, literal->value(), id);
357
}else if(_expr1->type() == Expr::IdentifierExpr && _expr2->type() == Expr::LiteralExpr){
358
IdentifierExpr* id = (IdentifierExpr*)_expr1;
359
LiteralExpr* literal = (LiteralExpr*)_expr2;
360
addConstraints(context, id, literal->value());
361
}else
362
context.canAnalyze = false;
363
}
364
365
void NotCondition::findConstraints(ConstraintAnalysisContext& context) const{
366
if(context.canAnalyze){
367
context.negated = !context.negated;
368
this->_cond->findConstraints(context);
369
context.negated = !context.negated;
370
}
371
}
372
373
/******************** CompareCondition::addConstraints ********************/
374
375
376
void EqualCondition::addConstraints(ConstraintAnalysisContext& context, IdentifierExpr* id, int value) const{
377
if(!context.negated){
378
Structures::StateConstraints* s = new Structures::StateConstraints(context.net());
379
if(id->pfree()){
380
s->setVarMin(id->offset(), value);
381
s->setVarMax(id->offset(), value);
382
}else{
383
s->setPlaceMin(id->offset(), value);
384
s->setPlaceMax(id->offset(), value);
385
}
386
assert(s);
387
context.retval.push_back(s);
388
}else{
389
Structures::StateConstraints* s1 = new Structures::StateConstraints(context.net());
390
Structures::StateConstraints* s2 = NULL;
391
if(value != 0)
392
s2 = new Structures::StateConstraints(context.net());
393
if(id->pfree()){
394
s1->setVarMin(id->offset(), value+1);
395
if(value != 0)
396
s2->setVarMax(id->offset(), value-1);
397
}else{
398
s1->setPlaceMin(id->offset(), value+1);
399
if(value != 0)
400
s2->setPlaceMax(id->offset(), value-1);
401
}
402
assert((s2 || value == 0) && s1);
403
context.retval.push_back(s1);
404
if(value != 0)
405
context.retval.push_back(s2);
406
}
407
}
408
409
void EqualCondition::addConstraints(ConstraintAnalysisContext& context, int value, IdentifierExpr* id) const{
410
addConstraints(context, id, value);
411
}
412
413
void NotEqualCondition::addConstraints(ConstraintAnalysisContext& context, IdentifierExpr* id, int value) const{
414
if(context.negated){
415
Structures::StateConstraints* s = new Structures::StateConstraints(context.net());
416
if(id->pfree()){
417
s->setVarMin(id->offset(), value);
418
s->setVarMax(id->offset(), value);
419
}else{
420
s->setPlaceMin(id->offset(), value);
421
s->setPlaceMax(id->offset(), value);
422
}
423
assert(s);
424
context.retval.push_back(s);
425
}else{
426
Structures::StateConstraints* s1 = new Structures::StateConstraints(context.net());
427
Structures::StateConstraints* s2 = NULL;
428
if(value != 0)
429
s2 = new Structures::StateConstraints(context.net());
430
if(id->pfree()){
431
s1->setVarMin(id->offset(), value+1);
432
if(value != 0)
433
s2->setVarMax(id->offset(), value-1);
434
}else{
435
s1->setPlaceMin(id->offset(), value+1);
436
if(value != 0)
437
s2->setPlaceMax(id->offset(), value-1);
438
}
439
assert((s2 || value == 0) && s1);
440
context.retval.push_back(s1);
441
if(value != 0)
442
context.retval.push_back(s2);
443
}
444
}
445
446
void NotEqualCondition::addConstraints(ConstraintAnalysisContext& context, int value, IdentifierExpr* id) const{
447
addConstraints(context, id, value);
448
}
449
450
void LessThanCondition::addConstraints(ConstraintAnalysisContext& context, IdentifierExpr* id, int value) const{
451
Structures::StateConstraints* nc = new Structures::StateConstraints(context.net());
452
if(!context.negated){
453
if(!id->pfree())
454
nc->setPlaceMax(id->offset(), value-1);
455
else
456
nc->setVarMax(id->offset(), value-1);
457
}else{
458
if(!id->pfree())
459
nc->setPlaceMin(id->offset(), value);
460
else
461
nc->setVarMin(id->offset(), value);
462
}
463
context.retval.push_back(nc);
464
}
465
466
void LessThanCondition::addConstraints(ConstraintAnalysisContext& context, int value, IdentifierExpr* id) const{
467
Structures::StateConstraints* nc = new Structures::StateConstraints(context.net());
468
if(!context.negated){
469
if(!id->pfree())
470
nc->setPlaceMin(id->offset(), value+1);
471
else
472
nc->setVarMin(id->offset(), value+1);
473
}else{
474
if(!id->pfree())
475
nc->setPlaceMax(id->offset(), value);
476
else
477
nc->setVarMax(id->offset(), value);
478
}
479
context.retval.push_back(nc);
480
}
481
482
483
void LessThanOrEqualCondition::addConstraints(ConstraintAnalysisContext& context, IdentifierExpr* id, int value) const{
484
Structures::StateConstraints* nc = new Structures::StateConstraints(context.net());
485
if(!context.negated){
486
if(!id->pfree())
487
nc->setPlaceMax(id->offset(), value);
488
else
489
nc->setVarMax(id->offset(), value);
490
}else{
491
if(!id->pfree())
492
nc->setPlaceMin(id->offset(), value+1);
493
else
494
nc->setVarMin(id->offset(), value+1);
495
}
496
context.retval.push_back(nc);
497
}
498
499
void LessThanOrEqualCondition::addConstraints(ConstraintAnalysisContext& context, int value, IdentifierExpr* id) const{
500
Structures::StateConstraints* nc = new Structures::StateConstraints(context.net());
501
if(!context.negated){
502
if(!id->pfree())
503
nc->setPlaceMin(id->offset(), value);
504
else
505
nc->setVarMin(id->offset(), value);
506
}else{
507
if(!id->pfree())
508
nc->setPlaceMax(id->offset(), value-1);
509
else
510
nc->setVarMax(id->offset(), value-1);
511
}
512
context.retval.push_back(nc);
513
}
514
515
void GreaterThanCondition::addConstraints(ConstraintAnalysisContext& context, IdentifierExpr* id, int value) const{
516
Structures::StateConstraints* nc = new Structures::StateConstraints(context.net());
517
if(!context.negated){
518
if(!id->pfree()) // p1 > 5
519
nc->setPlaceMin(id->offset(), value+1);
520
else
521
nc->setVarMin(id->offset(), value+1);
522
}else{
523
if(!id->pfree())
524
nc->setPlaceMax(id->offset(), value);
525
else
526
nc->setVarMax(id->offset(), value);
527
}
528
context.retval.push_back(nc);
529
}
530
531
void GreaterThanCondition::addConstraints(ConstraintAnalysisContext& context, int value, IdentifierExpr* id) const{
532
Structures::StateConstraints* nc = new Structures::StateConstraints(context.net());
533
if(!context.negated){
534
if(!id->pfree()) // 5 > p1
535
nc->setPlaceMax(id->offset(), value-1);
536
else
537
nc->setVarMax(id->offset(), value-1);
538
}else{
539
if(!id->pfree()) // !(5 > p1)
540
nc->setPlaceMin(id->offset(), value);
541
else
542
nc->setVarMin(id->offset(), value);
543
}
544
context.retval.push_back(nc);
545
}
546
547
void GreaterThanOrEqualCondition::addConstraints(ConstraintAnalysisContext& context, IdentifierExpr* id, int value) const{
548
Structures::StateConstraints* nc = new Structures::StateConstraints(context.net());
549
if(!context.negated){
550
if(!id->pfree()) // p1 >= 5
551
nc->setPlaceMin(id->offset(), value);
552
else
553
nc->setVarMin(id->offset(), value);
554
}else{
555
if(!id->pfree()) // !(p1 >= 5)
556
nc->setPlaceMax(id->offset(), value-1);
557
else
558
nc->setVarMax(id->offset(), value-1);
559
}
560
context.retval.push_back(nc);
561
}
562
563
void GreaterThanOrEqualCondition::addConstraints(ConstraintAnalysisContext& context, int value, IdentifierExpr* id) const{
564
Structures::StateConstraints* nc = new Structures::StateConstraints(context.net());
565
if(!context.negated){
566
if(!id->pfree()) // 5 >= p1
567
nc->setPlaceMax(id->offset(), value);
568
else
569
nc->setVarMax(id->offset(), value);
570
}else{
571
if(!id->pfree()) // !(5 >= p1)
572
nc->setPlaceMin(id->offset(), value+1);
573
else
574
nc->setVarMin(id->offset(), value+1);
575
}
576
context.retval.push_back(nc);
577
}
578
579
/******************** Distance Condition ********************/
580
581
#define MAX(v1, v2) (v1 > v2 ? v1 : v2)
582
#define MIN(v1, v2) (v1 < v2 ? v1 : v2)
583
584
double NotCondition::distance(DistanceContext& context) const{
585
context.negate();
586
double retval = _cond->distance(context);
587
context.negate();
588
return retval;
589
}
590
591
double LogicalCondition::distance(DistanceContext& context) const{
592
double d1 = _cond1->distance(context);
593
double d2 = _cond2->distance(context);
594
return delta(d1, d2, context);
595
}
596
597
double AndCondition::delta(double d1,
598
double d2,
599
const DistanceContext& context) const{
600
if(context.strategy() & DistanceContext::AndExtreme)
601
if(context.negated())
602
return MIN(d1, d2);
603
else
604
return MAX(d1, d2);
605
else if(context.strategy() & DistanceContext::AndSum)
606
return d1 + d2;
607
else
608
return (d1 + d2) / 2;
609
}
610
611
double OrCondition::delta(double d1,
612
double d2,
613
const DistanceContext& context) const{
614
if(context.strategy() & DistanceContext::OrExtreme)
615
if(context.negated())
616
return MAX(d1, d2);
617
else
618
return MIN(d1, d2);
619
else
620
return (d1 + d2) / 2;
621
}
622
623
struct S{
624
int d;
625
unsigned int p;
626
};
627
628
int dfsArcLen(const PetriNet& net,
629
const MarkVal *m,
630
unsigned int place){
631
std::list<S> places;
632
std::set<unsigned int> visited;
633
S s;
634
s.d = 0;
635
s.p = place;
636
places.push_back(s);
637
visited.insert(place);
638
while(!places.empty()){
639
s = places.front();
640
places.pop_front();
641
for(unsigned int t = 0; t < net.numberOfTransitions(); t++){
642
if(net.outArc(t, place)){
643
for(unsigned int p = 0; p < net.numberOfPlaces(); p++){
644
if(net.inArc(p, t)){
645
if(!visited.count(p)){
646
if(m[p])
647
return s.d + 1;
648
visited.insert(p);
649
S sp;
650
sp.d = s.d + 1;
651
sp.p = p;
652
places.push_back(sp);
653
}
654
}
655
}
656
}
657
}
658
}
659
return s.d + 1;
660
}
661
662
double CompareCondition::distance(DistanceContext& context) const{
663
int v1 = _expr1->evaluate(context);
664
int v2 = _expr2->evaluate(context);
665
if(context.strategy() & DistanceContext::ArcCount){
666
int d = delta(v1, v2, context.negated());
667
if(!d) return 0;
668
if(_expr1->pfree() && !_expr2->pfree() && _expr2->type() == Expr::IdentifierExpr){
669
IdentifierExpr* id = (IdentifierExpr*)_expr2;
670
return dfsArcLen(context.net(), context.marking(), id->offset()) * d;
671
}else if(_expr2->pfree() && !_expr1->pfree() && _expr1->type() == Expr::IdentifierExpr){
672
IdentifierExpr* id = (IdentifierExpr*)_expr1;
673
return dfsArcLen(context.net(), context.marking(), id->offset()) * d;
674
}
675
} else if(context.strategy() & DistanceContext::TokenCost){
676
677
//TODO: Account for when we have too many tokens instead of too few
678
if(_expr1->pfree() && !_expr2->pfree() && _expr2->type() == Expr::IdentifierExpr){
679
int d = delta(v2, v1, context.negated());
680
if(d == 0) return 0;
681
if(d < 0) return abs(d);
682
IdentifierExpr* id = (IdentifierExpr*)_expr2;
683
return context.distanceMatrix()->tokenCost(id->offset(), d, context.marking());
684
}else if(_expr2->pfree() && !_expr1->pfree() && _expr1->type() == Expr::IdentifierExpr){
685
int d = delta(v1, v2, context.negated());
686
if(d == 0) return 0;
687
if(d < 0) return abs(d);
688
IdentifierExpr* id = (IdentifierExpr*)_expr1;
689
return context.distanceMatrix()->tokenCost(id->offset(), d, context.marking());
690
}
691
}
692
return abs(delta(v1, v2, context.negated()));
693
}
694
695
double EqualCondition::delta(int v1, int v2, bool negated) const{
696
if(!negated)
697
return v1 - v2;
698
else
699
return v1 == v2 ? 1 : 0;
700
}
701
702
double NotEqualCondition::delta(int v1, int v2, bool negated) const{
703
if(negated)
704
return v1 - v2;
705
else
706
return v1 == v2 ? 1 : 0;
707
}
708
709
double LessThanCondition::delta(int v1, int v2, bool negated) const{
710
if(!negated)
711
return v1 < v2 ? 0 : v1 - v2 + 1;
712
else
713
return v1 >= v2 ? 0 : v2 - v1;
714
}
715
716
double LessThanOrEqualCondition::delta(int v1, int v2, bool negated) const{
717
if(!negated)
718
return v1 <= v2 ? 0 : v1 - v2;
719
else
720
return v1 > v2 ? 0 : v2 - v1 + 1;
721
}
722
723
double GreaterThanCondition::delta(int v1, int v2, bool negated) const{
724
if(!negated)
725
return v1 > v2 ? 0 : v2 - v1 + 1;
726
else
727
return v1 <= v2 ? 0 : v1 - v2;
728
}
729
730
double GreaterThanOrEqualCondition::delta(int v1, int v2, bool negated) const{
731
if(!negated)
732
return v1 >= v2 ? 0 : v2 - v1;
733
else
734
return v1 < v2 ? 0 : v1 - v2 + 1;
735
}
736
737
738
/******************** Just-In-Time Compilation ********************/
739
740
} // PQL
741
} // PetriEngine
742
Loggerhead is a web-based interface for Breezy
Version: 2.0.1