From 0aa9573079f6dbde549602e9d73980123c981b72 Mon Sep 17 00:00:00 2001 From: Mikko Rasa Date: Fri, 29 Oct 2010 21:30:03 +0000 Subject: [PATCH] Add TrackLoopIter Use it instead of manually maintaining visited sets --- source/libmarklin/trackiter.cpp | 51 ++++++++++++++++ source/libmarklin/trackiter.h | 32 ++++++++++ source/libmarklin/train.cpp | 102 ++++++++++++++++---------------- source/libmarklin/train.h | 2 +- 4 files changed, 136 insertions(+), 51 deletions(-) diff --git a/source/libmarklin/trackiter.cpp b/source/libmarklin/trackiter.cpp index 6ee7231..5f63399 100644 --- a/source/libmarklin/trackiter.cpp +++ b/source/libmarklin/trackiter.cpp @@ -5,6 +5,7 @@ Copyright © 2010 Mikkosoft Productions, Mikko Rasa Distributed under the GPL */ +#include #include #include "track.h" #include "trackiter.h" @@ -109,4 +110,54 @@ bool TrackIter::operator==(const TrackIter &other) const return _track==other._track && _entry==other._entry; } + +TrackLoopIter::TrackLoopIter(): + _looped(false) +{ } + +TrackLoopIter::TrackLoopIter(Track *t, unsigned e): + TrackIter(t, e), + _visited(new TrackList()), + _last(_visited->insert(_visited->end(), track())), + _looped(false) +{ } + +TrackLoopIter::TrackLoopIter(const TrackIter &i): + TrackIter(i), + _visited(new TrackList()), + _last(_visited->insert(_visited->end(), track())), + _looped(false) +{ } + +TrackLoopIter::TrackLoopIter(const TrackIter &i, RefPtr v, const TrackList::iterator &l): + TrackIter(i), + _looped(false) +{ + if(track()) + { + _visited = v; + _last = l; + _looped = (_visited && find(_visited->begin(), _last, track())!=_last); + + ++_last; + if(_last!=_visited->end()) + { + _visited = new TrackList(_visited->begin(), _last); + _last = _visited->end(); + } + _visited->push_back(track()); + --_last; + } +} + +TrackLoopIter TrackLoopIter::next() const +{ + return TrackLoopIter(TrackIter::next(), _visited, _last); +} + +TrackLoopIter TrackLoopIter::next(unsigned path) const +{ + return TrackLoopIter(TrackIter::next(path), _visited, _last); +} + } // namespace Marklin diff --git a/source/libmarklin/trackiter.h b/source/libmarklin/trackiter.h index c91a768..e756061 100644 --- a/source/libmarklin/trackiter.h +++ b/source/libmarklin/trackiter.h @@ -43,9 +43,41 @@ public: Track &operator*() const; Track *operator->() const { return _track; } bool operator==(const TrackIter &) const; + bool operator!=(const TrackIter &other) const { return !(*this==other); } operator bool() const { return _track!=0; } }; + +/** +A track iterator that detects looping. + +A list of visited tracks is maintained internally to the iterator. This list +is shared between iterators as long as next() is only called once per iterator. +Subsequent calls to next() cause the head of the list to be copied. +*/ +class TrackLoopIter: public TrackIter +{ +private: + typedef std::list TrackList; + + Msp::RefPtr _visited; + TrackList::iterator _last; + bool _looped; + +public: + TrackLoopIter(); + TrackLoopIter(Track *, unsigned); + TrackLoopIter(const TrackIter &); +private: + TrackLoopIter(const TrackIter &, Msp::RefPtr, const TrackList::iterator &); + +public: + bool looped() const { return _looped; } + + TrackLoopIter next() const; + TrackLoopIter next(unsigned) const; +}; + } // namespace Marklin #endif diff --git a/source/libmarklin/train.cpp b/source/libmarklin/train.cpp index b87447f..6962085 100644 --- a/source/libmarklin/train.cpp +++ b/source/libmarklin/train.cpp @@ -266,51 +266,49 @@ bool Train::divert(Track &from) if(routes.empty()) return false; - int path = -1; - unsigned from_ep = 0; + unsigned path = 0; + unsigned entry = 0; list::iterator route = routes.begin(); - BlockIter block = cur_blocks.back(); - set visited; // Follow our routes to find out where we're entering the turnout - while(1) + for(TrackLoopIter track = cur_blocks.back().track_iter();;) { - block = block.next(route->route); - - const Block::Endpoint &entry_ep = block->get_endpoints()[block.entry()]; - - if(visited.count(entry_ep.track)) - return false; - visited.insert(entry_ep.track); - - if(!advance_route(route, *entry_ep.track)) + if(!advance_route(route, *track)) return false; - if(entry_ep.track==&from) + if(&*track==&from) { - if(block->get_train()==this && !free_block(*block)) + Block &block = track->get_block(); + if(block.get_train()==this && !free_block(block)) return false; - from_ep = entry_ep.track_ep; - path = route->route->get_turnout(from.get_turnout_id()); - break; - } - } + int route_path = route->route->get_turnout(from.get_turnout_id()); - // Check that more than one path is available - unsigned ep_paths = from.get_type().get_endpoints()[from_ep].paths; - if(!(ep_paths&(ep_paths-1))) - return false; + // Check that more than one path is available + unsigned ep_paths = track->get_type().get_endpoints()[track.entry()].paths; + if(!(ep_paths&(ep_paths-1))) + return false; - // Choose some other path - for(int i=0; ep_paths>>i; ++i) - if((ep_paths&(1<>i; ++i) + if((ep_paths&(1<get_turnout_id(); + track = track.next(tid ? route->route->get_turnout(tid) : 0); + + if(!track || track.looped()) + return false; + } + + TrackIter track = TrackIter(&from, entry).next(path); if(!track) return false; @@ -325,7 +323,7 @@ bool Train::divert(Track &from) diversion->add_track(from); diversion->set_turnout(from.get_turnout_id(), path); - if(!is_valid_diversion(*diversion, from, from_ep)) + if(!is_valid_diversion(*diversion, TrackIter(&from, entry))) return false; // Follow the diversion route until we get back to the original route @@ -1270,48 +1268,52 @@ Route *Train::create_lead_route(Route *lead, const Route *target) return lead; } -bool Train::is_valid_diversion(const Route &diversion, Track &from, unsigned from_ep) +bool Train::is_valid_diversion(const Route &diversion, const TrackIter &from) { float diversion_len = 0; - TrackIter track(&from, from_ep); - while(diversion.has_track(*track)) + TrackLoopIter track1 = from; + while(diversion.has_track(*track1)) { - unsigned tid = track->get_turnout_id(); + unsigned tid = track1->get_turnout_id(); unsigned path = (tid ? diversion.get_turnout(tid) : 0); - diversion_len += track->get_type().get_path_length(path); + diversion_len += track1->get_type().get_path_length(path); - track = track.next(path); + track1 = track1.next(path); - if(&*track==&from) + if(track1.looped()) return false; } list::iterator route = routes.begin(); - if(!advance_route(route, from)) + if(!advance_route(route, *from)) return false; - set visited; float route_len = 0; - track = TrackIter(&from, from_ep); + TrackLoopIter track2 = from; while(1) { - unsigned tid = track->get_turnout_id(); + unsigned tid = track2->get_turnout_id(); unsigned path = (tid ? route->route->get_turnout(tid) : 0); - route_len += track->get_type().get_path_length(path); + route_len += track2->get_type().get_path_length(path); + + bool ok = (track2!=from && diversion.has_track(*track2)); - if(&*track!=&from && diversion.has_track(*track)) + track2 = track2.next(path); + + if(ok) break; - if(visited.count(&*track)) + if(track2.looped()) return false; - visited.insert(&*track); - track = track.next(path); - - if(!advance_route(route, *track)) + if(!advance_route(route, *track2)) return false; } + // Must end up at the same place through both routes + if(track2!=track1) + return false; + return diversion_len::iterator &, Track &); Route *create_lead_route(Route *, const Route *); - bool is_valid_diversion(const Route &, Track &, unsigned); + bool is_valid_diversion(const Route &, const TrackIter &); }; } // namespace Marklin -- 2.45.2