|
Vaucanson 1.4
|
00001 // boost_graph.hxx: this file is part of the Vaucanson project. 00002 // 00003 // Vaucanson, a generic library for finite state machines. 00004 // 00005 // Copyright (C) 2007, 2008 The Vaucanson Group. 00006 // 00007 // This program is free software; you can redistribute it and/or 00008 // modify it under the terms of the GNU General Public License 00009 // as published by the Free Software Foundation; either version 2 00010 // of the License, or (at your option) any later version. 00011 // 00012 // The complete GNU General Public Licence Notice can be found as the 00013 // `COPYING' file in the root directory. 00014 // 00015 // The Vaucanson Group consists of people listed in the `AUTHORS' file. 00016 // 00017 00018 #ifndef VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_LETTERS_SPEC_HXX_ 00019 # define VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_LETTERS_SPEC_HXX_ 00020 00021 # include <vaucanson/automata/implementation/bmig_graph_letters_spec.hh> 00022 00023 namespace vcsn 00024 { 00025 namespace bmig 00026 { 00027 00028 /*--------------------. 00029 | Convenient macros. | 00030 `--------------------*/ 00031 00032 # define BMIGRAPH_TPARAM \ 00033 template <class WordValue, \ 00034 class SeriesValue, class Letter, class Tag, class GeometryCoords> 00035 00036 # define BMIGRAPH \ 00037 Graph<labels_are_letters, WordValue, bool, SeriesValue, Letter, Tag, GeometryCoords> 00038 00039 /*-------------------------. 00040 | Graph's implementation. | 00041 `-------------------------*/ 00042 00043 /*---------------. 00044 | Constructors. | 00045 `---------------*/ 00046 00047 BMIGRAPH_TPARAM 00048 inline 00049 BMIGRAPH::Graph () 00050 : initial_bitset_(0), 00051 final_bitset_(0), 00052 number_of_epsilon_(0), 00053 number_of_state_(0) 00054 { 00055 } 00056 00066 BMIGRAPH_TPARAM 00067 BMIGRAPH::Graph (unsigned initial_number_of_states, 00068 unsigned) 00069 : initial_bitset_(initial_number_of_states), 00070 final_bitset_(initial_number_of_states), 00071 number_of_epsilon_(0), 00072 number_of_state_(initial_number_of_states), 00073 states_(initial_number_of_states) 00074 { 00075 for (unsigned i = 0; i < initial_number_of_states; ++i) 00076 { 00077 boost::shared_ptr<unsigned> p(new unsigned(i)); 00078 states_[i] = p; 00079 } 00080 } 00081 00082 BMIGRAPH_TPARAM 00083 BMIGRAPH::Graph (const self_t& g) 00084 { 00085 tag_ = g.tag_; 00086 initial_bitset_ = g.initial_bitset_; 00087 final_bitset_ = g.final_bitset_; 00088 number_of_epsilon_ = g.number_of_epsilon_; 00089 number_of_state_ = g.number_of_state_; 00090 00091 initial_.clear(); 00092 final_.clear(); 00093 graph_.clear(); 00094 typename geometry_t::transitions_geometry_map_t& map_transitions = geometry_.transitions(); 00095 map_transitions.clear(); 00096 00097 states_.resize(g.number_of_state_); 00098 for (unsigned i = 0; i < g.number_of_state_; ++i) 00099 { 00100 boost::shared_ptr<unsigned> p(new unsigned(i)); 00101 states_[i] = p; 00102 } 00103 for (typename graph_data_t::const_iterator i = g.graph_.begin(); 00104 i != g.graph_.end(); 00105 ++i) 00106 graph_.insert(edge_data_t(states_[*i->from_], 00107 states_[*i->to_], 00108 i->label_)); 00109 for (initial_t::iterator it = g.initial_.begin(); it != g.initial_.end(); ++it) 00110 initial_.insert(states_[**it]); 00111 for (final_t::iterator it = g.final_.begin(); it != g.final_.end(); ++it) 00112 final_.insert(states_[**it]); 00113 00114 # define VCSN_COPY_GEOMETRY(Type) \ 00115 { \ 00116 typename geometry_t::Type##_geometry_map_t& map_##Type = geometry_.Type(); \ 00117 map_##Type.clear(); \ 00118 for (typename geometry_t::Type##_geometry_map_t::const_iterator i = g.geometry_.Type().begin(); \ 00119 i != g.geometry_.Type().end(); \ 00120 ++i) \ 00121 map_##Type[i->first] = i->second; \ 00122 } 00123 VCSN_COPY_GEOMETRY(states) 00124 VCSN_COPY_GEOMETRY(initials) 00125 VCSN_COPY_GEOMETRY(finals) 00126 # undef VCSN_COPY_GEOMETRY 00127 { 00128 for (typename geometry_t::transitions_geometry_map_t::const_iterator i = g.geometry_.transitions().begin(); 00129 i != g.geometry_.transitions().end(); 00130 ++i) 00131 { 00132 typename graph_data_t::const_iterator tmp = find_edge(states_[*i->first.value()->from_], 00133 states_[*i->first.value()->to_], 00134 i->first.value()->label_); 00135 if (tmp != graph_.end()) 00136 map_transitions[htransition_t(tmp)] = i->second; 00137 } 00138 } 00139 } 00140 00141 /*--------------. 00142 | Destructors. | 00143 `--------------*/ 00144 00145 BMIGRAPH_TPARAM 00146 inline 00147 BMIGRAPH::~Graph () 00148 { 00149 } 00150 00151 BMIGRAPH_TPARAM 00152 typename BMIGRAPH::self_t& 00153 BMIGRAPH::operator= (const self_t& g) 00154 { 00155 if (this == &g) 00156 return *this; 00157 tag_ = g.tag_; 00158 initial_bitset_ = g.initial_bitset_; 00159 final_bitset_ = g.final_bitset_; 00160 number_of_epsilon_ = g.number_of_epsilon_; 00161 number_of_state_ = g.number_of_state_; 00162 00163 initial_.clear(); 00164 final_.clear(); 00165 graph_.clear(); 00166 typename geometry_t::transitions_geometry_map_t& map_transitions = geometry_.transitions(); 00167 map_transitions.clear(); 00168 00169 states_.resize(g.number_of_state_); 00170 for (unsigned i = 0; i < g.number_of_state_; ++i) 00171 { 00172 boost::shared_ptr<unsigned> p(new unsigned(i)); 00173 states_[i] = p; 00174 } 00175 for (typename graph_data_t::const_iterator i = g.graph_.begin(); 00176 i != g.graph_.end(); 00177 ++i) 00178 graph_.insert(edge_data_t(states_[*i->from_], 00179 states_[*i->to_], 00180 i->label_)); 00181 for (initial_t::iterator it = g.initial_.begin(); it != g.initial_.end(); ++it) 00182 initial_.insert(states_[**it]); 00183 for (final_t::iterator it = g.final_.begin(); it != g.final_.end(); ++it) 00184 final_.insert(states_[**it]); 00185 00186 # define VCSN_COPY_GEOMETRY(Type) \ 00187 { \ 00188 typename geometry_t::Type##_geometry_map_t& map_##Type = geometry_.Type(); \ 00189 map_##Type.clear(); \ 00190 for (typename geometry_t::Type##_geometry_map_t::const_iterator i = g.geometry_.Type().begin(); \ 00191 i != g.geometry_.Type().end(); \ 00192 ++i) \ 00193 map_##Type[i->first] = i->second; \ 00194 } 00195 VCSN_COPY_GEOMETRY(states) 00196 VCSN_COPY_GEOMETRY(initials) 00197 VCSN_COPY_GEOMETRY(finals) 00198 # undef VCSN_COPY_GEOMETRY 00199 for (typename geometry_t::transitions_geometry_map_t::const_iterator i = g.geometry_.transitions().begin(); 00200 i != g.geometry_.transitions().end(); 00201 ++i) 00202 { 00203 typename graph_data_t::const_iterator tmp = find_edge(states_[*i->first.value()->from_], 00204 states_[*i->first.value()->to_], 00205 i->first.value()->label_); 00206 if (tmp != graph_.end()) 00207 map_transitions[htransition_t(tmp)] = i->second; 00208 } 00209 return *this; 00210 } 00211 00212 /*------------------. 00213 | Basic accessors. | 00214 `------------------*/ 00215 00216 BMIGRAPH_TPARAM 00217 typename BMIGRAPH::states_t 00218 BMIGRAPH::states() const 00219 { 00220 return misc::Support<states_data_t>(states_); 00221 } 00222 00223 BMIGRAPH_TPARAM 00224 typename BMIGRAPH::edges_t 00225 BMIGRAPH::edges() const 00226 { 00227 return edges_t(graph_); 00228 } 00229 00230 BMIGRAPH_TPARAM 00231 typename BMIGRAPH::initial_support_t 00232 BMIGRAPH::initial () const 00233 { 00234 return initial_support_t(initial_); 00235 } 00236 00237 BMIGRAPH_TPARAM 00238 typename BMIGRAPH::final_support_t 00239 BMIGRAPH::final () const 00240 { 00241 return final_support_t(final_); 00242 } 00243 00244 00245 /*----------------------. 00246 | State manipulations. | 00247 `----------------------*/ 00248 00249 BMIGRAPH_TPARAM 00250 bool 00251 BMIGRAPH::has_state (const hstate_t& s) const 00252 { 00253 return s < states_.size(); 00254 } 00255 00256 BMIGRAPH_TPARAM 00257 typename BMIGRAPH::hstate_t 00258 BMIGRAPH::add_state () 00259 { 00260 initial_bitset_.append(false); 00261 final_bitset_.append(false); 00262 boost::shared_ptr<unsigned> p(new unsigned(number_of_state_++)); 00263 state_t h(p); 00264 states_.push_back(h); 00265 return hstate_t(h); 00266 } 00267 00268 BMIGRAPH_TPARAM 00269 typename BMIGRAPH::hstate_t 00270 BMIGRAPH::get_state (unsigned s) const 00271 { 00272 precondition(s < states_.size()); 00273 return hstate_t(states_[s]); 00274 } 00275 00276 BMIGRAPH_TPARAM 00277 void 00278 BMIGRAPH::del_state (const hstate_t& s) 00279 { 00280 precondition (has_state(s)); 00281 00282 // One removes the state h 00283 graph_.get<src>().erase(s.value()); 00284 graph_.get<dst>().erase(s.value()); 00285 00286 if (number_of_state_ > 1 && s != (number_of_state_ - 1)) 00287 { 00288 state_t lastone = states_.back(); 00289 states_[s] = lastone; 00290 # define VCSN_UPDATE(Set) \ 00291 if (Set##bitset_[*lastone]) \ 00292 { \ 00293 if (Set##bitset_[s]) \ 00294 Set.erase(s.value()); \ 00295 else \ 00296 Set##bitset_[s] = true; \ 00297 } \ 00298 else \ 00299 { \ 00300 if (Set##bitset_[s]) \ 00301 { \ 00302 Set##bitset_[s] = false; \ 00303 Set.erase(s.value()); \ 00304 } \ 00305 } 00306 00307 //Updating initial/final states information 00308 VCSN_UPDATE(initial_) 00309 VCSN_UPDATE(final_) 00310 # undef VCSN_UPDATE 00311 *lastone = *s.value(); 00312 } 00313 else 00314 { 00315 initial_.erase(s.value()); 00316 final_.erase(s.value()); 00317 } 00318 00319 --number_of_state_; 00320 states_.pop_back(); 00321 postcondition(states_.size() == number_of_state_); 00322 initial_bitset_.resize(number_of_state_); 00323 final_bitset_.resize(number_of_state_); 00324 00325 //Useless postcondition since the states are renumbered 00326 //postcondition(!has_state(h)); 00327 } 00328 00329 BMIGRAPH_TPARAM 00330 void 00331 BMIGRAPH::set_initial (const hstate_t& s, 00332 const series_set_elt_value_t& v, 00333 const series_set_elt_value_t& z) 00334 { 00335 precondition(has_state(s)); 00336 if (z == v) 00337 { 00338 initial_.erase (s.value()); 00339 initial_bitset_[s] = false; 00340 } 00341 else 00342 { 00343 initial_.insert (s.value()); 00344 initial_bitset_[s] = true; 00345 } 00346 } 00347 00348 BMIGRAPH_TPARAM 00349 const typename BMIGRAPH::series_set_elt_value_t& 00350 BMIGRAPH::get_initial(const hstate_t& s, const series_set_elt_value_t &) const 00351 { 00352 precondition(has_state(s)); 00353 return initial_bitset_[s]; 00354 } 00355 00356 BMIGRAPH_TPARAM 00357 bool 00358 BMIGRAPH::is_initial(const hstate_t& s, const series_set_elt_value_t&) const 00359 { 00360 precondition(has_state(s)); 00361 return initial_bitset_[s]; 00362 } 00363 00364 BMIGRAPH_TPARAM 00365 void 00366 BMIGRAPH::clear_initial() 00367 { 00368 initial_.clear(); 00369 initial_bitset_.reset(); 00370 } 00371 00372 BMIGRAPH_TPARAM 00373 void 00374 BMIGRAPH::set_final(const hstate_t& s, 00375 const series_set_elt_value_t& v, 00376 const series_set_elt_value_t& z) 00377 { 00378 precondition(has_state(s)); 00379 if (z == v) 00380 { 00381 final_.erase (s.value()); 00382 final_bitset_[s] = false; 00383 } 00384 else 00385 { 00386 final_.insert (s.value()); 00387 final_bitset_[s] = true; 00388 } 00389 } 00390 00391 BMIGRAPH_TPARAM 00392 const typename BMIGRAPH::series_set_elt_value_t& 00393 BMIGRAPH::get_final(const hstate_t& s, const series_set_elt_value_t &) const 00394 { 00395 precondition(has_state(s)); 00396 return final_bitset_[s]; 00397 } 00398 00399 BMIGRAPH_TPARAM 00400 bool 00401 BMIGRAPH::is_final(const hstate_t& s, const series_set_elt_value_t&) const 00402 { 00403 precondition(has_state(s)); 00404 return final_bitset_[s]; 00405 } 00406 00407 BMIGRAPH_TPARAM 00408 void 00409 BMIGRAPH::clear_final() 00410 { 00411 final_.clear(); 00412 final_bitset_.reset(); 00413 } 00414 00415 /*---------------------. 00416 | Edge manipulations. | 00417 `---------------------*/ 00418 00419 BMIGRAPH_TPARAM 00420 bool 00421 BMIGRAPH::has_edge (const hedge_t& h) const 00422 { 00423 succ_range r = graph_.equal_range(boost::make_tuple(*h.value()->from_, 00424 h.value()->label_)); 00425 succ_iterator it; 00426 state_t to = h.value()->to_; 00427 for (it = r.first; it != r.second && it->to_ != to; ++it) 00428 /*Nothing*/; 00429 00430 return it != r.second; 00431 } 00432 00433 BMIGRAPH_TPARAM 00434 typename BMIGRAPH::hedge_t 00435 BMIGRAPH::add_edge (const hstate_t& from, const hstate_t& to, const label_t& l) 00436 { 00437 return hedge_t (graph_.insert (edge_data_t (from.value(), to.value(), l)).first); 00438 } 00439 00440 BMIGRAPH_TPARAM 00441 void 00442 BMIGRAPH::del_edge (const hedge_t& h) 00443 { 00444 precondition (has_edge(h)); 00445 graph_.erase(h.value()); 00446 00447 // h points to an invalid edgeValue since it is already destroyed. 00448 // We can't check this postcondition anymore! 00449 //postcondition(!has_edge(h)); 00450 } 00451 00452 BMIGRAPH_TPARAM 00453 typename BMIGRAPH::hstate_t 00454 BMIGRAPH::src_of (const hedge_t& h) const 00455 { 00456 return hstate_t(h.value()->from_); 00457 } 00458 00459 BMIGRAPH_TPARAM 00460 typename BMIGRAPH::hstate_t 00461 BMIGRAPH::dst_of (const hedge_t& h) const 00462 { 00463 return hstate_t(h.value()->to_); 00464 } 00465 00466 BMIGRAPH_TPARAM 00467 const typename BMIGRAPH::label_t& 00468 BMIGRAPH::label_of (const hedge_t& h) const 00469 { 00470 return h.value()->label_; 00471 } 00472 00473 BMIGRAPH_TPARAM 00474 void 00475 BMIGRAPH::update(const hedge_t& h, const label_t& l) 00476 { 00477 graph_.modify(h.value(), update_hlabel<label_t>(l)); 00478 } 00479 00480 BMIGRAPH_TPARAM 00481 template <class S> 00482 bool 00483 BMIGRAPH::exists (const AutomataBase<S>& s) const 00484 { 00485 typename WordValue::iterator it; 00486 typename label_t::const_iterator r; 00487 label_t l; 00488 WordValue w; 00489 00490 for (typename graph_data_t::iterator i = graph_.begin(); i != graph_.end(); ++i) 00491 { 00492 // Make sure that source and destination of edge are part of the 00493 // automaton. 00494 if (!has_state(dst_of(hedge_t(i))) || 00495 !has_state(src_of(hedge_t(i)))) 00496 return false; 00497 00498 // Make sure that every letter of the edge is in the alphabet. 00499 l = label_of(hedge_t(i)); 00500 for (r = l.begin(); r != l.end(); ++r) 00501 { 00502 w = r->first; 00503 for (it = w.begin(); it != w.end(); ++it) 00504 if (!s.series().monoid().alphabet().contains(*it)) 00505 return false; 00506 } 00507 } 00508 return true; 00509 } 00510 00511 BMIGRAPH_TPARAM 00512 inline 00513 typename BMIGRAPH::tag_t& 00514 BMIGRAPH::tag () 00515 { 00516 return tag_; 00517 } 00518 00519 BMIGRAPH_TPARAM 00520 inline 00521 const typename BMIGRAPH::tag_t& 00522 BMIGRAPH::tag () const 00523 { 00524 return tag_; 00525 } 00526 00527 BMIGRAPH_TPARAM 00528 inline 00529 typename BMIGRAPH::geometry_t& 00530 BMIGRAPH::geometry () 00531 { 00532 return geometry_; 00533 } 00534 00535 BMIGRAPH_TPARAM 00536 inline 00537 const typename BMIGRAPH::geometry_t& 00538 BMIGRAPH::geometry () const 00539 { 00540 return geometry_; 00541 } 00542 00543 template <class WordValue, class SeriesValue, 00544 class Letter, class Tag, class GeometryCoords, class I> 00545 Tag& 00546 op_tag(const AutomataBase<I>&, BMIGRAPH &g) 00547 { 00548 return g.tag(); 00549 } 00550 00551 template <class WordValue, class SeriesValue, 00552 class Letter, class Tag, class GeometryCoords, class I> 00553 const Tag& 00554 op_tag(const AutomataBase<I>&, BMIGRAPH &g) 00555 { 00556 return g.tag(); 00557 } 00558 00559 template <class WordValue, class SeriesValue, 00560 class Letter, class Tag, class GeometryCoords, class I> 00561 typename BMIGRAPH::geometry_t& 00562 op_geometry(const AutomataBase<I>&, BMIGRAPH &g) 00563 { 00564 return g.geometry(); 00565 } 00566 00567 template <class WordValue, class SeriesValue, 00568 class Letter, class Tag, class GeometryCoords, class I> 00569 const typename BMIGRAPH::geometry_t& 00570 op_geometry(const AutomataBase<I>&, const BMIGRAPH &g) 00571 { 00572 return g.geometry(); 00573 } 00574 00575 BMIGRAPH_TPARAM 00576 typename BMIGRAPH::graph_data_t::const_iterator 00577 BMIGRAPH::find_edge(const state_t& from, const state_t& to, 00578 const label_t& label) const 00579 { 00580 succ_range r = graph_.equal_range(::boost::make_tuple(from, label)); 00581 for (succ_iterator i = r.first; i != r.second; ++i) 00582 if (i->to_ == to) 00583 return i; 00584 return graph_.end(); 00585 } 00586 00587 /*------------------. 00588 | Delta functions. | 00589 `------------------*/ 00590 # define DEFINE_DELTA_FUNCTION(FunName, DeltaKind, Target, GetElt) \ 00591 BMIGRAPH_TPARAM \ 00592 template <typename OutputIterator, typename Query> \ 00593 void \ 00594 BMIGRAPH::FunName(OutputIterator res, \ 00595 const typename BMIGRAPH::hstate_t& s, \ 00596 const Query& query, \ 00597 ::vcsn::delta_kind::DeltaKind) const \ 00598 { \ 00599 assertion(has_state(s)); \ 00600 Target##_range r = graph_.get<Target>().equal_range(s.value()); \ 00601 for (Target##_iterator e = r.first; e != r.second; ++e) \ 00602 if (query(hedge_t(graph_.project<0>(e)))) \ 00603 *res++ = GetElt; \ 00604 } 00605 00606 DEFINE_DELTA_FUNCTION (delta, transitions, src, hedge_t(graph_.project<0>(e))); 00607 DEFINE_DELTA_FUNCTION (delta, states, src, hstate_t(e->to_)); 00608 DEFINE_DELTA_FUNCTION (rdelta, transitions, dst, hedge_t(graph_.project<0>(e))); 00609 DEFINE_DELTA_FUNCTION (rdelta, states, dst, hstate_t(e->from_)); 00610 00611 # undef DEFINE_DELTA_FUNCTION 00612 00613 00614 // End of syntactic sugar 00615 # undef BMIGRAPH_TPARAM 00616 # undef BMIGRAPH 00617 } // End of namespace boost 00618 } // End of namespace vcsn 00619 00620 #endif // !VCSN_AUTOMATA_IMPLEMENTATION_BMIG_GRAPH_IMPL_HXX_ //
1.7.4