tgbaexplicit.cc 5.8 KB
Newer Older
1
#include "ltlast/atomic_prop.hh"
2
#include "ltlast/constant.hh"
3
#include "ltlvisit/destroy.hh"
4
5
6
7
8
9
10
11
12
13
#include "tgbaexplicit.hh"
#include <cassert>

namespace spot
{

  ////////////////////////////////////////
  // tgba_explicit_succ_iterator

  tgba_explicit_succ_iterator::tgba_explicit_succ_iterator
14
15
  (const tgba_explicit::state* s, bdd all_acc)
    : s_(s), all_accepting_conditions_(all_acc)
16
17
18
  {
  }

19
  void
20
21
22
23
24
  tgba_explicit_succ_iterator::first()
  {
    i_ = s_->begin();
  }

25
  void
26
27
28
29
30
  tgba_explicit_succ_iterator::next()
  {
    ++i_;
  }

31
  bool
32
  tgba_explicit_succ_iterator::done() const
33
34
35
36
  {
    return i_ == s_->end();
  }

37
  state_explicit*
38
39
40
41
42
  tgba_explicit_succ_iterator::current_state()
  {
    return new state_explicit((*i_)->dest);
  }

43
  bdd
44
45
46
47
48
  tgba_explicit_succ_iterator::current_condition()
  {
    return (*i_)->condition;
  }

49
  bdd
50
  tgba_explicit_succ_iterator::current_accepting_conditions()
51
  {
52
    return (*i_)->accepting_conditions & all_accepting_conditions_;
53
54
55
56
57
58
  }


  ////////////////////////////////////////
  // state_explicit

59
  const tgba_explicit::state*
60
61
62
63
64
65
66
67
68
69
70
71
72
  state_explicit::get_state() const
  {
    return state_;
  }

  int
  state_explicit::compare(const spot::state* other) const
  {
    const state_explicit* o = dynamic_cast<const state_explicit*>(other);
    assert(o);
    return o->get_state() - get_state();
  }

73
74
75
76
77
78
  state_explicit*
  state_explicit::clone() const
  {
    return new state_explicit(*this);
  }

79
80
81
82
83
  ////////////////////////////////////////
  // tgba_explicit


  tgba_explicit::tgba_explicit()
84
85
86
    : init_(0), all_accepting_conditions_(bddfalse),
      neg_accepting_conditions_(bddtrue),
      all_accepting_conditions_computed_(false)
87
88
89
90
91
92
93
94
95
96
97
98
99
100
  {
  }

  tgba_explicit::~tgba_explicit()
  {
    ns_map::iterator i;
    for (i = name_state_map_.begin(); i != name_state_map_.end(); ++i)
      {
	tgba_explicit::state::iterator i2;
	for (i2 = i->second->begin(); i2 != i->second->end(); ++i2)
	  delete *i2;
	delete i->second;
      }
  }
101

102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
  tgba_explicit::state*
  tgba_explicit::add_state(const std::string& name)
  {
    ns_map::iterator i = name_state_map_.find(name);
    if (i == name_state_map_.end())
      {
	tgba_explicit::state* s = new tgba_explicit::state;
	name_state_map_[name] = s;
	state_name_map_[s] = name;

	// The first state we add is the inititial state.
	if (! init_)
	  init_ = s;

	return s;
      }
    return i->second;
  }

  tgba_explicit::transition*
122
  tgba_explicit::create_transition(const std::string& source,
123
124
125
126
127
128
129
				   const std::string& dest)
  {
    tgba_explicit::state* s = add_state(source);
    tgba_explicit::state* d = add_state(dest);
    transition* t = new transition;
    t->dest = d;
    t->condition = bddtrue;
130
    t->accepting_conditions = bddfalse;
131
132
133
134
    s->push_back(t);
    return t;
  }

135
136
  bdd
  tgba_explicit::get_condition(ltl::formula* f)
137
138
139
140
141
142
143
144
145
146
147
148
  {
    assert(dynamic_cast<ltl::atomic_prop*>(f));
    tgba_bdd_dict::fv_map::iterator i = dict_.var_map.find(f);
    int v;
    if (i == dict_.var_map.end())
      {
	v = create_node();
	dict_.var_map[f] = v;
	dict_.var_formula_map[v] = f;
      }
    else
      {
149
	ltl::destroy(f);
150
151
	v = i->second;
      }
152
    return ithvar(v);
153
154
  }

155
156
  void
  tgba_explicit::add_condition(transition* t, ltl::formula* f)
157
  {
158
    t->condition &= get_condition(f);
159
160
  }

161
162
  void
  tgba_explicit::add_neg_condition(transition* t, ltl::formula* f)
163
  {
164
    t->condition &= ! get_condition(f);
165
166
  }

167
168
  void
  tgba_explicit::declare_accepting_condition(ltl::formula* f)
169
  {
170
171
    tgba_bdd_dict::fv_map::iterator i = dict_.acc_map.find(f);
    if (i == dict_.acc_map.end())
172
      {
173
	int v;
174
	v = create_node();
175
176
177
	dict_.acc_map[f] = v;
	dict_.acc_formula_map[v] = f;
	neg_accepting_conditions_ &= !ithvar(v);
178
      }
179
180
  }

181
182
183
184
185
186
187
188
189
  bool
  tgba_explicit::has_accepting_condition(ltl::formula* f) const
  {
    tgba_bdd_dict::fv_map::const_iterator i = dict_.acc_map.find(f);
    return i != dict_.acc_map.end();
  }

  bdd
  tgba_explicit::get_accepting_condition(ltl::formula* f)
190
  {
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
    ltl::constant* c = dynamic_cast<ltl::constant*>(f);
    if (c)
      {
	switch (c->val())
	  {
	  case ltl::constant::True:
	    return bddtrue;
	  case ltl::constant::False:
	    return bddfalse;
	  }
	/* Unreachable code.  */
	assert(0);
      }

    tgba_bdd_dict::fv_map::iterator i = dict_.acc_map.find(f);
    assert (i != dict_.acc_map.end());
    ltl::destroy(f);
    bdd v = ithvar(i->second);
    v &= bdd_exist(neg_accepting_conditions_, v);
    return v;
211
212
  }

213
214
  void
  tgba_explicit::add_accepting_condition(transition* t, ltl::formula* f)
215
  {
216
217
    bdd c = get_accepting_condition(f);
    t->accepting_conditions |= c;
218
219
  }

220
  state*
221
222
223
224
225
  tgba_explicit::get_init_state() const
  {
    return new state_explicit(init_);
  }

226
  tgba_succ_iterator*
227
228
229
230
  tgba_explicit::succ_iter(const spot::state* state) const
  {
    const state_explicit* s = dynamic_cast<const state_explicit*>(state);
    assert(s);
231
232
    return new tgba_explicit_succ_iterator(s->get_state(),
					   all_accepting_conditions());
233
  }
234
235

  const tgba_bdd_dict&
236
237
238
239
240
  tgba_explicit::get_dict() const
  {
    return dict_;
  }

241
  std::string
242
243
244
245
246
247
248
249
250
  tgba_explicit::format_state(const spot::state* s) const
  {
    const state_explicit* se = dynamic_cast<const state_explicit*>(s);
    assert(se);
    sn_map::const_iterator i = state_name_map_.find(se->get_state());
    assert(i != state_name_map_.end());
    return i->second;
  }

251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
  bdd
  tgba_explicit::all_accepting_conditions() const
  {
    if (!all_accepting_conditions_computed_)
      {
	bdd all = bddfalse;
	tgba_bdd_dict::fv_map::const_iterator i;
	for (i = dict_.acc_map.begin(); i != dict_.acc_map.end(); ++i)
	  {
	    bdd v = ithvar(i->second);
	    all |= v & bdd_exist(neg_accepting_conditions_, v);
	  }
	all_accepting_conditions_ = all;
	all_accepting_conditions_computed_ = true;
      }
    return all_accepting_conditions_;
  }

  bdd
  tgba_explicit::neg_accepting_conditions() const
  {
    return neg_accepting_conditions_;
  }

275
}