| 1 | package Map::Tube; | ||
| 2 | |||
| 3 | 19 | ▶ | use strict; |
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||
| 4 | 19 | ▶ | use warnings; |
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||
| 5 | 19 | ▶ | use version; |
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||
| 6 | |||
| 7 | our $VERSION = qv('v5.2.0'); | ||
| 8 | our $AUTHORITY = 'cpan:MANWAR'; | ||
| 9 | |||
| 10 | =head1 NAME | ||
| 11 | |||
| 12 | Map::Tube - Lightweight Routing Framework. | ||
| 13 | |||
| 14 | =head1 VERSION | ||
| 15 | |||
| 16 | Version v5.2.0 | ||
| 17 | |||
| 18 | =cut | ||
| 19 | |||
| 20 | 19 | ▶ | use Carp (); |
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||
| 21 | 19 | ▶ | use Unicode::Normalize; |
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||
| 22 | 19 | ▶ | use Encode qw(decode_utf8); |
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||
| 23 | |||
| 24 | 19 | ▶ | use v5.14; |
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||
| 25 | 0 | ▶ | use XML::Twig; |
|
Subroutine
BEGIN: called CC=1 SCAR=2.6
| |||
| 26 | use Data::Dumper; | ||
| 27 | use Map::Tube::Node; | ||
| 28 | use Map::Tube::Line; | ||
| 29 | use Map::Tube::Table; | ||
| 30 | use Map::Tube::Route; | ||
| 31 | use Map::Tube::Pluggable; | ||
| 32 | use Map::Tube::Exception::MissingMapData; | ||
| 33 | use Map::Tube::Exception::MissingStationName; | ||
| 34 | use Map::Tube::Exception::InvalidStationName; | ||
| 35 | use Map::Tube::Exception::MissingStationId; | ||
| 36 | use Map::Tube::Exception::InvalidStationId; | ||
| 37 | use Map::Tube::Exception::InvalidStationLineId; | ||
| 38 | use Map::Tube::Exception::MissingLineId; | ||
| 39 | use Map::Tube::Exception::InvalidLineId; | ||
| 40 | use Map::Tube::Exception::MissingLineName; | ||
| 41 | use Map::Tube::Exception::InvalidLineName; | ||
| 42 | use Map::Tube::Exception::InvalidLineColor; | ||
| 43 | use Map::Tube::Exception::FoundMultiLinedStation; | ||
| 44 | use Map::Tube::Exception::FoundMultiLinkedStation; | ||
| 45 | use Map::Tube::Exception::FoundSelfLinkedStation; | ||
| 46 | use Map::Tube::Exception::DuplicateStationId; | ||
| 47 | use Map::Tube::Exception::DuplicateStationName; | ||
| 48 | use Map::Tube::Exception::MissingPluginGraph; | ||
| 49 | use Map::Tube::Exception::MissingPluginFormatter; | ||
| 50 | use Map::Tube::Exception::MissingPluginFuzzyFind; | ||
| 51 | use Map::Tube::Exception::MalformedMapData; | ||
| 52 | use Map::Tube::Exception::InvalidLineStructure; | ||
| 53 | use Map::Tube::Exception::InvalidStationStructure; | ||
| 54 | use Map::Tube::Exception::RouteNotFound; | ||
| 55 | use Map::Tube::Utils qw(to_perl is_same trim common_lines get_method_map is_valid_color); | ||
| 56 | use Map::Tube::Types qw(Routes Tables Lines NodeMap LineMap Color); | ||
| 57 | |||
| 58 | use Moo::Role; | ||
| 59 | use Role::Tiny qw(); | ||
| 60 | use Types::Common::Numeric qw(PositiveOrZeroNum); | ||
| 61 | use namespace::autoclean; | ||
| 62 | |||
| 63 | =encoding utf8 | ||
| 64 | |||
| 65 | =head1 DESCRIPTION | ||
| 66 | |||
| 67 | The core module defined as a Role (Moo) to process the map data. It provides the | ||
| 68 | interface to find the shortest route in terms of stoppage between two nodes. Also | ||
| 69 | you can get all possible routes between two given nodes. | ||
| 70 | |||
| 71 | The routing algorithm is line-change-aware: when two candidate routes have the | ||
| 72 | same number of stops, the one requiring fewer line changes is preferred. Each | ||
| 73 | line change incurs a small fractional penalty (0.5) on top of the normal per-hop | ||
| 74 | cost of 1, so hop count always dominates but unnecessary changes are avoided. | ||
| 75 | |||
| 76 | If you are keen to know the internals of L<Map::Tube> then please follow the note | ||
| 77 | documented in L<Map::Tube::Cookbook>. | ||
| 78 | |||
| 79 | =head1 MAP LEADER BOARD | ||
| 80 | |||
| 81 | +----------------------+-----------+------------------------------------------+ | ||
| 82 | | Author | PAUSE ID | Map Count (City) | | ||
| 83 | +----------------------+-----------+------------------------------------------+ | ||
| 84 | | Michal Josef Spacek | SKIM | 22 (Bucharest, Budapest, Dnipropetrovsk, | | ||
| 85 | | | | Kazan, Kharkiv, Kiev, KualaLumpur, | | ||
| 86 | | | | Malaga, Minsk, Moscow, Nanjing, | | ||
| 87 | | | | NizhnyNovgorod, Novosibirsk, Prague, | | ||
| 88 | | | | SaintPetersburg, Samara, Singapore, | | ||
| 89 | | | | Sofia, Tbilisi, Vienna, Warsaw, | | ||
| 90 | | | | Yekaterinburg) | | ||
| 91 | | | | | | ||
| 92 | | Gisbert W Selke | GWS | 17 (Beijing, Brussels, Chicago, Glasgow, | | ||
| 93 | | | | Hamburg, Hannover, KoelnBonn, Lyon, | | ||
| 94 | | | | Muenchen, Napoli, Oslo, Paris, RheinRuhr,| | ||
| 95 | | | | San Francisco, Stockholm, Stuttgart, | | ||
| 96 | | | | Toulouse) | | ||
| 97 | | | | | | ||
| 98 | | Mohammad Sajid Anwar | MANWAR | 8 (Barcelona, Delhi, Kolkatta, Leipzig, | | ||
| 99 | | | | London, Madrid, NYC, Tokyo) | | ||
| 100 | | | | | | ||
| 101 | | FUNG Cheok Yin | CYFUNG | 1 (Hong Kong) | | ||
| 102 | | | | | | ||
| 103 | | Peter Harrison | EARLYBEAN | 1 (Sydney) | | ||
| 104 | | | | | | ||
| 105 | | Errietta Kostala | ERRIETTA | 1 (Athens) | | ||
| 106 | | | | | | ||
| 107 | | Giuseppe Di Terlizzi | GDT | 1 (Rome) | | ||
| 108 | | | | | | ||
| 109 | | Marco Fontani | MFONTANI | 1 (Milan) | | ||
| 110 | | | | | | ||
| 111 | | Renee Baecker | RENEEB | 1 (Frankfurt) | | ||
| 112 | | | | | | ||
| 113 | | Soren Lund | SLU | 1 (Copenhagen) | | ||
| 114 | | | | | | ||
| 115 | | Slaven Rezic | SREZIC | 1 (Berlin) | | ||
| 116 | | | | | | ||
| 117 | | Stefan Limbacher | STELIM | 1 (Nuremberg) | | ||
| 118 | | | | | | ||
| 119 | | Vitali Peil | VPEIL | 1 (Bielefeld) | | ||
| 120 | +----------------------+-----------+------------------------------------------+ | ||
| 121 | |||
| 122 | =cut | ||
| 123 | |||
| 124 | has [qw(name name_to_id plugins _active_link _other_links _link_lines _line_stations _line_station_index _common_lines)] => (is => 'rw'); | ||
| 125 | has experimental => (is => 'ro', default => sub { 0 }); | ||
| 126 | has nodes => (is => 'rw', isa => NodeMap); | ||
| 127 | has lines => (is => 'rw', isa => Lines ); | ||
| 128 | has tables => (is => 'rw', isa => Tables ); | ||
| 129 | has routes => (is => 'rw', isa => Routes ); | ||
| 130 | has _lines => (is => 'rw', isa => LineMap); | ||
| 131 | has bgcolor => (is => 'rw', isa => Color ); | ||
| 132 | has line_change_penalty => (is => 'rw', isa => PositiveOrZeroNum, default => 0.5 ); | ||
| 133 | |||
| 134 | our $AUTOLOAD; | ||
| 135 | our $PLUGINS = { | ||
| 136 | 'Map::Tube::Plugin::Graph' => 1, | ||
| 137 | 'Map::Tube::Plugin::FuzzyFind' => 1, | ||
| 138 | }; | ||
| 139 | |||
| 140 | sub AUTOLOAD { | ||
| 141 | |||
| 142 | my $name = $AUTOLOAD; | ||
| 143 | $name =~ s/.*://; | ||
| 144 | |||
| 145 | return if $name eq 'DESTROY'; | ||
| 146 | |||
| 147 | my @caller = caller(0); | ||
| 148 | @caller = caller(2) if $caller[3] eq '(eval)'; | ||
| 149 | |||
| 150 | my $method_map = get_method_map(); | ||
| 151 | if (exists $method_map->{$name}) { | ||
| 152 | my $module = $method_map->{$name}->{module}; | ||
| 153 | my $exception = $method_map->{$name}->{exception}; | ||
| 154 | $exception->throw({ | ||
| 155 | method => "${module}::${name}", | ||
| 156 | message => "ERROR: Missing plugin $module.", | ||
| 157 | filename => $caller[1], | ||
| 158 | line_number => $caller[2] }); | ||
| 159 | } | ||
| 160 | |||
| 161 | my $class = ref($_[0]) || $_[0]; | ||
| 162 | Carp::croak(qq{Can't locate object method "$name" via package "$class"}); | ||
| 163 | } | ||
| 164 | |||
| 165 | sub BUILD { | ||
| 166 | my ($self) = @_; | ||
| 167 | |||
| 168 | # Handle lazy attributes. | ||
| 169 | my @attributes = (keys %{Moo->_constructor_maker_for(ref($self))->all_attribute_specs}); | ||
| 170 | unless ((grep /^xml$/, @attributes) || (grep /^json$/, @attributes)) { | ||
| 171 | die "ERROR: Can't apply Map::Tube role, missing 'xml' or 'json'."; | ||
| 172 | } | ||
| 173 | |||
| 174 | $self->_init_map; | ||
| 175 | $self->_load_plugins; | ||
| 176 | } | ||
| 177 | |||
| 178 | =head1 SYNOPSIS | ||
| 179 | |||
| 180 | =head2 Common Usage | ||
| 181 | |||
| 182 | use strict; use warnings; | ||
| 183 | use Map::Tube::London; | ||
| 184 | |||
| 185 | my $map = Map::Tube::London->new; | ||
| 186 | print $map->get_shortest_route('Baker Street', 'Euston Square'), "\n"; | ||
| 187 | |||
| 188 | You should expect the result like below: | ||
| 189 | |||
| 190 | Baker Street (Circle, Hammersmith & City, Bakerloo, Metropolitan, Jubilee), Great Portland Street (Circle, Hammersmith & City, Metropolitan), Euston Square (Circle, Hammersmith & City, Metropolitan) | ||
| 191 | |||
| 192 | Alternatively, | ||
| 193 | |||
| 194 | use strict; use warnings; | ||
| 195 | use Map::Tube::London; | ||
| 196 | |||
| 197 | my $map = Map::Tube::London->new; | ||
| 198 | print $map->get_shortest_route('Baker Street', 'Euston Square')->preferred, "\n"; | ||
| 199 | |||
| 200 | You should now expect the result like below: | ||
| 201 | |||
| 202 | Baker Street (Circle, Hammersmith & City, Metropolitan), Great Portland Street (Circle, Hammersmith & City, Metropolitan), Euston Square (Circle, Hammersmith & City, Metropolitan) | ||
| 203 | |||
| 204 | =head1 METHODS | ||
| 205 | |||
| 206 | =head2 get_shortest_routes($from, $to) | ||
| 207 | |||
| 208 | This requires C<$from> and C<$to> station names parameters. It returns an object | ||
| 209 | of type L<Map::Tube::Route>. On error it throws an exception of type L<Map::Tube::Exception>. | ||
| 210 | |||
| 211 | =cut | ||
| 212 | |||
| 213 | sub get_shortest_route { | ||
| 214 | my ($self, $from, $to) = @_; | ||
| 215 | |||
| 216 | ($from, $to) = | ||
| 217 | $self->_validate_input('get_shortest_route', $from, $to); | ||
| 218 | |||
| 219 | my $_from = $self->get_node_by_id($from); | ||
| 220 | my $_to = $self->get_node_by_id($to); | ||
| 221 | |||
| 222 | $self->_capture_common_lines($_from, $_to); | ||
| 223 | |||
| 224 | my $reverse = 0; | ||
| 225 | |||
| 226 | # Found common lines between start and end nodes. | ||
| 227 | if (@{$self->{_common_lines}}) { | ||
| 228 | my $_common_line = $self->{_common_lines}->[0]; | ||
| 229 | my $from_index = $self->{_line_station_index} | ||
| 230 | ->{uc($_common_line)} | ||
| 231 | ->{$_from->id}; | ||
| 232 | my $to_index = $self->{_line_station_index} | ||
| 233 | ->{uc($_common_line)} | ||
| 234 | ->{$_to->id}; | ||
| 235 | |||
| 236 | # TODO: This cause issue with unidirection route with station index. | ||
| 237 | # $reverse = 1 if (defined $from_index | ||
| 238 | # && defined $to_index | ||
| 239 | # && ($from_index < $to_index)); | ||
| 240 | } | ||
| 241 | |||
| 242 | if ($reverse) { | ||
| 243 | ($from, $to) = ($to, $from); | ||
| 244 | ($_from, $_to) = ($_to, $_from); | ||
| 245 | } | ||
| 246 | |||
| 247 | $self->_get_shortest_route($from); | ||
| 248 | |||
| 249 | my $nodes = []; | ||
| 250 | while (defined($to) && !(is_same($from, $to))) { | ||
| 251 | push @$nodes, $self->get_node_by_id($to); | ||
| 252 | $to = $self->_get_path($to); | ||
| 253 | } | ||
| 254 | |||
| 255 | push @$nodes, $_from; | ||
| 256 | |||
| 257 | my $_nodes; | ||
| 258 | |||
| 259 | if ($reverse) { | ||
| 260 | $_nodes = [ @$nodes ]; | ||
| 261 | } | ||
| 262 | else { | ||
| 263 | $_nodes = [ reverse(@$nodes) ]; | ||
| 264 | } | ||
| 265 | |||
| 266 | my $start = $_nodes->[0]; | ||
| 267 | my $end = $_nodes->[-1]; | ||
| 268 | |||
| 269 | # If you end up with just 2 nodes i.e. start and end, then | ||
| 270 | # double check, if start is directly linked to end node. | ||
| 271 | if (scalar(@$_nodes) == 2) { | ||
| 272 | my $start_name = $start->name; | ||
| 273 | my $end_name = $end->name; | ||
| 274 | unless ($self->_is_directly_linked($start_name, $end_name)) { | ||
| 275 | my @caller = caller(0); | ||
| 276 | @caller = caller(2) if $caller[3] eq '(eval)'; | ||
| 277 | Map::Tube::Exception::RouteNotFound->throw({ | ||
| 278 | method => __PACKAGE__."::get_shortest_route", | ||
| 279 | message => "ERROR: Route not found from [$start_name] to [$end_name].", | ||
| 280 | filename => $caller[1], | ||
| 281 | line_number => $caller[2] }); | ||
| 282 | } | ||
| 283 | } | ||
| 284 | |||
| 285 | return Map::Tube::Route->new( | ||
| 286 | { from => $start, | ||
| 287 | to => $end, | ||
| 288 | nodes => $_nodes, | ||
| 289 | link_lines => $self->_link_lines, | ||
| 290 | } | ||
| 291 | ); | ||
| 292 | } | ||
| 293 | |||
| 294 | =head2 get_all_routes($from, $to) *** EXPERIMENTAL *** | ||
| 295 | |||
| 296 | This requires C<$from> and C<$to> station names as parameters. It returns a ref to a | ||
| 297 | list of objects of type L<Map::Tube::Route>. On error it throws an exception of type | ||
| 298 | L<Map::Tube::Exception>. | ||
| 299 | |||
| 300 | Be careful when using this against a large map. You may encounter a warning similar to | ||
| 301 | this one when running against London map: | ||
| 302 | |||
| 303 | Deep recursion on subroutine "Map::Tube::_get_all_routes" | ||
| 304 | |||
| 305 | However, for comparatively smaller maps, like below, it is happy to give all routes. | ||
| 306 | |||
| 307 | A(1) ---- B(2) | ||
| 308 | / \ | ||
| 309 | C(3) -------- F(6) --- G(7) ---- H(8) | ||
| 310 | \ / | ||
| 311 | D(4) ---- E(5) | ||
| 312 | |||
| 313 | =cut | ||
| 314 | |||
| 315 | sub get_all_routes { | ||
| 316 | my ($self, $from, $to) = @_; | ||
| 317 | |||
| 318 | ($from, $to) = | ||
| 319 | $self->_validate_input('get_all_routes', $from, $to); | ||
| 320 | |||
| 321 | return $self->_get_all_routes([ $from ], $to); | ||
| 322 | } | ||
| 323 | |||
| 324 | =head2 name() | ||
| 325 | |||
| 326 | Returns the map name. | ||
| 327 | |||
| 328 | =head2 get_node_by_id($node_id) | ||
| 329 | |||
| 330 | Returns an object of type L<Map::Tube::Node> for a given C<$node_id>. | ||
| 331 | |||
| 332 | =cut | ||
| 333 | |||
| 334 | sub get_node_by_id { | ||
| 335 | my ($self, $id) = @_; | ||
| 336 | |||
| 337 | my @caller = caller(0); | ||
| 338 | @caller = caller(2) if $caller[3] eq '(eval)'; | ||
| 339 | Map::Tube::Exception::MissingStationId->throw({ | ||
| 340 | method => __PACKAGE__."::get_node_by_id", | ||
| 341 | message => "ERROR: Missing Station ID.", | ||
| 342 | filename => $caller[1], | ||
| 343 | line_number => $caller[2] }) unless defined $id; | ||
| 344 | |||
| 345 | my $node = $self->{nodes}->{$id}; | ||
| 346 | Map::Tube::Exception::InvalidStationId->throw({ | ||
| 347 | method => __PACKAGE__."::get_node_by_id", | ||
| 348 | message => "ERROR: Invalid Station ID [$id].", | ||
| 349 | filename => $caller[1], | ||
| 350 | line_number => $caller[2] }) unless defined $node; | ||
| 351 | |||
| 352 | # Check if the node name appears more than once with different id. | ||
| 353 | my @nodes = $self->_get_node_id($node->name); | ||
| 354 | return $node if (scalar(@nodes) == 1); | ||
| 355 | |||
| 356 | my $lines = {}; | ||
| 357 | foreach my $l (@{$node->line}) { | ||
| 358 | $lines->{$l->name} = $l if defined $l->name; | ||
| 359 | } | ||
| 360 | foreach my $i (@nodes) { | ||
| 361 | foreach my $j (@{$self->{nodes}->{$i}->line}) { | ||
| 362 | $lines->{$j->name} = $j if defined $j->name; | ||
| 363 | } | ||
| 364 | } | ||
| 365 | $node->line([ values %$lines ]); | ||
| 366 | |||
| 367 | return $node; | ||
| 368 | } | ||
| 369 | |||
| 370 | =head2 get_node_by_name($node_name) | ||
| 371 | |||
| 372 | Returns an object of type L<Map::Tube::Node> for a given C<$node_name>. | ||
| 373 | |||
| 374 | =cut | ||
| 375 | |||
| 376 | sub get_node_by_name { | ||
| 377 | my ($self, $name) = @_; | ||
| 378 | |||
| 379 | my @caller = caller(0); | ||
| 380 | @caller = caller(2) if $caller[3] eq '(eval)'; | ||
| 381 | Map::Tube::Exception::MissingStationName->throw({ | ||
| 382 | method => __PACKAGE__."::get_node_by_name", | ||
| 383 | message => "ERROR: Missing Station Name.", | ||
| 384 | filename => $caller[1], | ||
| 385 | line_number => $caller[2] }) unless defined $name; | ||
| 386 | |||
| 387 | my $id = $self->_get_node_id($name); | ||
| 388 | Map::Tube::Exception::InvalidStationName->throw({ | ||
| 389 | method => __PACKAGE__."::get_node_by_name", | ||
| 390 | message => "ERROR: Invalid Station Name [$name].", | ||
| 391 | filename => $caller[1], | ||
| 392 | line_number => $caller[2] }) unless defined $id; | ||
| 393 | |||
| 394 | return $self->get_node_by_id($id); | ||
| 395 | } | ||
| 396 | |||
| 397 | =head2 get_line_by_id($line_id) | ||
| 398 | |||
| 399 | Returns an object of type L<Map::Tube::Line>. | ||
| 400 | |||
| 401 | =cut | ||
| 402 | |||
| 403 | sub get_line_by_id { | ||
| 404 | my ($self, $id) = @_; | ||
| 405 | |||
| 406 | my @caller = caller(0); | ||
| 407 | @caller = caller(2) if $caller[3] eq '(eval)'; | ||
| 408 | Map::Tube::Exception::MissingLineId->throw({ | ||
| 409 | method => __PACKAGE__."::get_line_by_id", | ||
| 410 | message => "ERROR: Missing Line ID.", | ||
| 411 | filename => $caller[1], | ||
| 412 | line_number => $caller[2] }) unless defined $id; | ||
| 413 | |||
| 414 | my $line = $self->_get_line_object_by_id($id); | ||
| 415 | Map::Tube::Exception::InvalidLineId->throw({ | ||
| 416 | method => __PACKAGE__."::get_line_by_id", | ||
| 417 | message => "ERROR: Invalid Line ID [$id].", | ||
| 418 | filename => $caller[1], | ||
| 419 | line_number => $caller[2] }) unless defined $line; | ||
| 420 | |||
| 421 | return $line; | ||
| 422 | } | ||
| 423 | |||
| 424 | =head2 get_line_by_name($line_name) | ||
| 425 | |||
| 426 | Returns an object of type L<Map::Tube::Line>. | ||
| 427 | |||
| 428 | =cut | ||
| 429 | |||
| 430 | sub get_line_by_name { | ||
| 431 | my ($self, $name) = @_; | ||
| 432 | |||
| 433 | my @caller = caller(0); | ||
| 434 | @caller = caller(2) if $caller[3] eq '(eval)'; | ||
| 435 | Map::Tube::Exception::MissingLineName->throw({ | ||
| 436 | method => __PACKAGE__."::get_line_by_name", | ||
| 437 | message => "ERROR: Missing Line Name.", | ||
| 438 | filename => $caller[1], | ||
| 439 | line_number => $caller[2] }) unless defined $name; | ||
| 440 | |||
| 441 | my $line = $self->_get_line_object_by_name($name); | ||
| 442 | $name = _decode_utf8_if_needed($name); | ||
| 443 | Map::Tube::Exception::InvalidLineName->throw({ | ||
| 444 | method => __PACKAGE__."::get_line_by_name", | ||
| 445 | message => "ERROR: Invalid Line Name [$name].", | ||
| 446 | filename => $caller[1], | ||
| 447 | line_number => $caller[2] }) unless defined $line; | ||
| 448 | |||
| 449 | return $line; | ||
| 450 | } | ||
| 451 | |||
| 452 | =head2 get_lines() | ||
| 453 | |||
| 454 | Returns a ref to a list of objects of type L<Map::Tube::Line>, containing | ||
| 455 | all lines in the map (but excluding "other links"). | ||
| 456 | |||
| 457 | =cut | ||
| 458 | |||
| 459 | sub get_lines { | ||
| 460 | my ($self) = @_; | ||
| 461 | |||
| 462 | my $lines = []; | ||
| 463 | my $other_links = $self->_other_links; | ||
| 464 | foreach (@{$self->{lines}}) { | ||
| 465 | next if exists $other_links->{uc($_->id)}; | ||
| 466 | push @$lines, $_ if defined $_->name; | ||
| 467 | } | ||
| 468 | |||
| 469 | return $lines; | ||
| 470 | } | ||
| 471 | |||
| 472 | =head2 get_stations($line_name) | ||
| 473 | |||
| 474 | Returns a ref to a list of objects of type L<Map::Tube::Node> for the line called C<$line_name>. | ||
| 475 | If C<$line_name> is missing, it will return all stations in the map. | ||
| 476 | |||
| 477 | =cut | ||
| 478 | |||
| 479 | sub get_stations { | ||
| 480 | my ($self, $line_name) = @_; | ||
| 481 | |||
| 482 | my $lines = []; | ||
| 483 | my $stations = []; | ||
| 484 | my $seen = {}; | ||
| 485 | |||
| 486 | if (defined $line_name) { | ||
| 487 | my @caller = caller(0); | ||
| 488 | @caller = caller(2) if $caller[3] eq '(eval)'; | ||
| 489 | |||
| 490 | my $line = $self->_get_line_object_by_name($line_name); | ||
| 491 | Map::Tube::Exception::InvalidLineName->throw({ | ||
| 492 | method => __PACKAGE__."::get_stations", | ||
| 493 | message => "ERROR: Invalid Line Name [$line_name].", | ||
| 494 | filename => $caller[1], | ||
| 495 | line_number => $caller[2] }) | ||
| 496 | unless defined $line; | ||
| 497 | |||
| 498 | $lines = [ $self->_get_line_object_by_name($line_name) ]; | ||
| 499 | } | ||
| 500 | else { | ||
| 501 | $lines = $self->get_lines; | ||
| 502 | } | ||
| 503 | |||
| 504 | foreach my $line (@$lines) { | ||
| 505 | foreach my $station (@{$line->{stations}}) { | ||
| 506 | unless (exists $seen->{$station->id}) { | ||
| 507 | push @$stations, $self->get_node_by_id($station->id); | ||
| 508 | $seen->{$station->id} = 1; | ||
| 509 | } | ||
| 510 | } | ||
| 511 | } | ||
| 512 | |||
| 513 | return $stations; | ||
| 514 | } | ||
| 515 | |||
| 516 | =head2 get_next_stations($station_name) | ||
| 517 | |||
| 518 | Returns a ref to the list of next stations from the given C<$station_name> as objects | ||
| 519 | of type L<Map::Tube::Node>. | ||
| 520 | |||
| 521 | =cut | ||
| 522 | |||
| 523 | sub get_next_stations { | ||
| 524 | my ($self, $station_name, $line_name) = @_; | ||
| 525 | |||
| 526 | my @caller = caller(0); | ||
| 527 | @caller = caller(2) if $caller[3] eq '(eval)'; | ||
| 528 | Map::Tube::Exception::MissingStationName->throw({ | ||
| 529 | method => __PACKAGE__."::get_next_stations", | ||
| 530 | message => "ERROR: Missing Station Name.", | ||
| 531 | filename => $caller[1], | ||
| 532 | line_number => $caller[2] }) unless defined $station_name; | ||
| 533 | |||
| 534 | my $node_id = $self->_get_node_id($station_name); | ||
| 535 | Map::Tube::Exception::InvalidStationName->throw({ | ||
| 536 | method => __PACKAGE__."::get_next_stations", | ||
| 537 | message => "ERROR: Invalid Station Name [$station_name].", | ||
| 538 | filename => $caller[1], | ||
| 539 | line_number => $caller[2] }) unless defined $node_id; | ||
| 540 | |||
| 541 | # Optional: restrict results to stations reachable from this one on a | ||
| 542 | # specific line. This takes any per-edge line restriction (set via the | ||
| 543 | # "A:x" style link syntax) into account, so a link that physically only | ||
| 544 | # runs on line x will correctly be excluded when asking about line y, | ||
| 545 | # even though both stations are nominally on both lines. | ||
| 546 | my $_line_id; | ||
| 547 | if (defined $line_name) { | ||
| 548 | my $_line = $self->_get_line_object_by_name($line_name); | ||
| 549 | Map::Tube::Exception::InvalidLineName->throw({ | ||
| 550 | method => __PACKAGE__."::get_next_stations", | ||
| 551 | message => "ERROR: Invalid Line Name [$line_name].", | ||
| 552 | filename => $caller[1], | ||
| 553 | line_number => $caller[2] }) unless defined $_line; | ||
| 554 | $_line_id = uc($_line->id); | ||
| 555 | } | ||
| 556 | |||
| 557 | my $nodes = []; | ||
| 558 | my $node = $self->get_node_by_id($node_id); | ||
| 559 | |||
| 560 | if (defined $_line_id) { | ||
| 561 | my %_node_lines = map { uc($_->{id}) => 1 } @{$node->{line}}; | ||
| 562 | # If the starting station isn't even served by this line, it has | ||
| 563 | # no neighbors on it, full stop. | ||
| 564 | return $nodes unless $_node_lines{$_line_id}; | ||
| 565 | } | ||
| 566 | |||
| 567 | foreach my $link (split /,/,$node->{link}) { | ||
| 568 | my $_next_node = $self->get_node_by_id($link); | ||
| 569 | |||
| 570 | if (defined $_line_id) { | ||
| 571 | my %_next_lines = map { uc($_->{id}) => 1 } @{$_next_node->{line}}; | ||
| 572 | |||
| 573 | my $_node_restrictions = $self->{_link_lines}->{uc($node_id)}; | ||
| 574 | my $_restriction = defined($_node_restrictions) ? $_node_restrictions->{uc($link)} : undef; | ||
| 575 | if (defined $_restriction) { | ||
| 576 | my %_allowed = map { uc($_) => 1 } @$_restriction; | ||
| 577 | next unless $_allowed{$_line_id}; | ||
| 578 | } | ||
| 579 | next unless $_next_lines{$_line_id}; | ||
| 580 | } | ||
| 581 | |||
| 582 | push @$nodes, $_next_node; | ||
| 583 | } | ||
| 584 | |||
| 585 | return $nodes; | ||
| 586 | } | ||
| 587 | |||
| 588 | =head2 get_linked_stations($station_name, $line_name) | ||
| 589 | |||
| 590 | Returns a ref to the list of the names of the linked stations from the given | ||
| 591 | C<$station_name> as strings. | ||
| 592 | |||
| 593 | The C<$line_name> param is optional. If passed, only stations linked via that | ||
| 594 | specific line are returned -- this respects any per-edge line restriction set | ||
| 595 | via the "A:x" style link syntax, so a link that only physically runs on one | ||
| 596 | line will not be listed as reachable via another line the two stations | ||
| 597 | otherwise share. | ||
| 598 | |||
| 599 | =cut | ||
| 600 | |||
| 601 | sub get_linked_stations { | ||
| 602 | my ($self, $station_name, $line_name) = @_; | ||
| 603 | |||
| 604 | my $nodes = $self->get_next_stations($station_name, $line_name); | ||
| 605 | my $linked_stations = []; | ||
| 606 | foreach my $node (@$nodes) { | ||
| 607 | push @$linked_stations, $node->name; | ||
| 608 | } | ||
| 609 | |||
| 610 | return $linked_stations; | ||
| 611 | } | ||
| 612 | |||
| 613 | =head2 bgcolor($color) | ||
| 614 | |||
| 615 | Set the background color for the map. Returns the new value. If called | ||
| 616 | without a value, returns the unchanged previous value. Setting this is | ||
| 617 | optional. Please set it before making a call to method | ||
| 618 | L<Map::Tube::Plugin::Graph/"as_image($line_name)">. If not set, it will | ||
| 619 | try to guess and may not be as good as you would expect.The C<$color> | ||
| 620 | can be a simply a color name or hash code (C<#RRGGBB>). | ||
| 621 | |||
| 622 | =head2 line_change_penalty($penalty) | ||
| 623 | |||
| 624 | When calculating shortest routes, each change from one line to another incurs | ||
| 625 | a penalty which is added to the number of hops on the route. The default penalty | ||
| 626 | is 0.5. This method can be used to query the current value or to set it to a new | ||
| 627 | value, which must be at least 0. (Values of 1 or higher probably do not make much | ||
| 628 | sense, since the number of hops should be the dominating factor.) If you just care | ||
| 629 | about the nnumber of hops but not for changes, set it to 0. | ||
| 630 | |||
| 631 | =cut | ||
| 632 | |||
| 633 | # | ||
| 634 | # | ||
| 635 | # DO NOT MAKE IT PUBLIC | ||
| 636 | |||
| 637 | sub get_map_data { | ||
| 638 | my ($self, $caller, $method) = @_; | ||
| 639 | |||
| 640 | my $data; | ||
| 641 | my $xml = $self->can('xml') ? $self->xml : ''; | ||
| 642 | if ($xml ne '') { | ||
| 643 | eval { | ||
| 644 | $data = XML::Twig->new->parsefile($xml)->simplify(keyattr => 'stations', forcearray => 0); | ||
| 645 | # Handle if there is only one line. | ||
| 646 | my $lines = $data->{lines}->{line}; | ||
| 647 | if (ref($lines) eq 'HASH') { | ||
| 648 | $data->{lines}->{line} = [ $lines ]; | ||
| 649 | } | ||
| 650 | }; | ||
| 651 | unless ($@) { | ||
| 652 | $self->_validate_map_structure($data, $caller); | ||
| 653 | return $data; | ||
| 654 | } | ||
| 655 | |||
| 656 | $@ =~ s/\s+at\s+\S*?\.pm\s+line\s+.*$//; | ||
| 657 | Map::Tube::Exception::MalformedMapData->throw({ | ||
| 658 | method => $method, | ||
| 659 | message => "ERROR: Malformed Map Data ($xml): $@", | ||
| 660 | filename => $caller->[1], | ||
| 661 | line_number => $caller->[2] }); | ||
| 662 | } | ||
| 663 | else { | ||
| 664 | my $json = $self->can('json') ? $self->json : ''; | ||
| 665 | if ($json ne '') { | ||
| 666 | eval { $data = to_perl($json) }; | ||
| 667 | unless ($@) { | ||
| 668 | $self->_validate_map_structure($data, $caller); | ||
| 669 | return $data; | ||
| 670 | } | ||
| 671 | |||
| 672 | $@ =~ s/\s+at\s+\S*?\.pm\s+line\s+.*$//; | ||
| 673 | Map::Tube::Exception::MalformedMapData->throw({ | ||
| 674 | method => $method, | ||
| 675 | message => "ERROR: Malformed Map Data ($json): $@", | ||
| 676 | filename => $caller->[1], | ||
| 677 | line_number => $caller->[2] }); | ||
| 678 | } | ||
| 679 | else { | ||
| 680 | if (!defined $caller) { | ||
| 681 | $method = __PACKAGE__.'::get_map_data'; | ||
| 682 | my @_caller = caller(0); | ||
| 683 | @_caller = caller(2) if $_caller[3] eq '(eval)'; | ||
| 684 | $caller = \@_caller; | ||
| 685 | } | ||
| 686 | |||
| 687 | Map::Tube::Exception::MissingMapData->throw({ | ||
| 688 | method => $method, | ||
| 689 | message => "ERROR: Missing Map Data.", | ||
| 690 | filename => $caller->[1], | ||
| 691 | line_number => $caller->[2] }); | ||
| 692 | } | ||
| 693 | } | ||
| 694 | } | ||
| 695 | |||
| 696 | =head1 PLUGINS | ||
| 697 | |||
| 698 | =head2 L<Map::Tube::Plugin::Graph> | ||
| 699 | |||
| 700 | The L<Map::Tube::Plugin::Graph> plugin adds support to generate the entire map | ||
| 701 | or a map for a particular line as a base64 encoded string of a PNG image. | ||
| 702 | For C<Map::Tube> v3.54 or above, you can set the background color explicitly. | ||
| 703 | |||
| 704 | use strict; use warnings; | ||
| 705 | use MIME::Base64; | ||
| 706 | use Map::Tube::London; | ||
| 707 | |||
| 708 | my $tube = Map::Tube::London->new; | ||
| 709 | |||
| 710 | # Optionally, you can override the default background color. | ||
| 711 | $tube->bgcolor("gray"); | ||
| 712 | |||
| 713 | # Entire map image | ||
| 714 | my $name = $tube->name; | ||
| 715 | open(my $MAP_IMAGE, ">", "$name.png") | ||
| 716 | or die "ERROR: Can't open [$name.png]: $!"; | ||
| 717 | binmode($MAP_IMAGE); | ||
| 718 | print $MAP_IMAGE decode_base64($tube->as_image); | ||
| 719 | close($MAP_IMAGE); | ||
| 720 | |||
| 721 | # Just a particular line map image | ||
| 722 | my $line = 'Bakerloo'; | ||
| 723 | open(my $LINE_IMAGE, ">", "$line.png") | ||
| 724 | or die "ERROR: Can't open [$line.png]: $!"; | ||
| 725 | binmode($LINE_IMAGE); | ||
| 726 | print $LINE_IMAGE decode_base64($tube->as_image($line)); | ||
| 727 | close($LINE_IMAGE); | ||
| 728 | |||
| 729 | Please refer to the L<documentation|Map::Tube::Plugin::Graph> for more details. | ||
| 730 | |||
| 731 | =head2 L<Map::Tube::Plugin::Formatter> | ||
| 732 | |||
| 733 | The L<Map::Tube::Plugin::Formatter> plugin adds support to format objects | ||
| 734 | supported by the plugin. | ||
| 735 | |||
| 736 | use strict; use warnings; | ||
| 737 | use Map::Tube::London; | ||
| 738 | |||
| 739 | my $tube = Map::Tube::London->new; | ||
| 740 | |||
| 741 | my $node = $tube->get_node_by_name('Baker Street'); | ||
| 742 | print $node->to_xml, "\n\n"; | ||
| 743 | print $node->to_json, "\n\n"; | ||
| 744 | print $node->to_yaml, "\n\n"; | ||
| 745 | print $node->to_string, "\n\n"; | ||
| 746 | |||
| 747 | my $line = $tube->get_line_by_name('Metropolitan'); | ||
| 748 | print $line->to_xml, "\n\n"; | ||
| 749 | print $line->to_json, "\n\n"; | ||
| 750 | print $line->to_yaml, "\n\n"; | ||
| 751 | print $line->to_string, "\n\n"; | ||
| 752 | |||
| 753 | my $route = $tube->get_shortest_route('Baker Street', 'Wembley Park'); | ||
| 754 | print $route->to_xml, "\n\n"; | ||
| 755 | print $route->to_json, "\n\n"; | ||
| 756 | print $route->to_yaml, "\n\n"; | ||
| 757 | print $route->to_string,"\n\n"; | ||
| 758 | |||
| 759 | Please refer to the L<documentation|Map::Tube::Plugin::Formatter> for more info. | ||
| 760 | |||
| 761 | =head2 L<Map::Tube::Plugin::FuzzyFind> | ||
| 762 | |||
| 763 | Gisbert W. Selke built the add-on for L<Map::Tube> to find stations and lines by | ||
| 764 | name, possibly partly or inexactly specified. The module is a Moo role which gets | ||
| 765 | plugged into the Map::Tube::* family automatically once it is installed. | ||
| 766 | |||
| 767 | use strict; use warnings; | ||
| 768 | use Map::Tube::London; | ||
| 769 | |||
| 770 | my $tube = Map::Tube::London->new(); | ||
| 771 | |||
| 772 | print 'line matches exactly: ', scalar($tube->fuzzy_find(search => 'erloo', objects => 'lines')), "\n"; | ||
| 773 | print 'line contains : ', scalar($tube->fuzzy_find(search => 'erloo', objects => 'lines', method => 'in')), "\n"; | ||
| 774 | |||
| 775 | Please refer to the L<documentation|Map::Tube::Plugin::FuzzyFind> for more info. | ||
| 776 | |||
| 777 | =head1 MAP DATA FORMAT | ||
| 778 | |||
| 779 | Map data can be represented in JSON or XML format. The preferred format is JSON. | ||
| 780 | C<Map::Tube v3.23> or above comes with a handy script C<map-data-converter>, that | ||
| 781 | can be used to change the data format of an existing map data.Below is how we can | ||
| 782 | represent the sample map: | ||
| 783 | |||
| 784 | A(1) ---- B(2) | ||
| 785 | / \ | ||
| 786 | C(3) -------- F(6) --- G(7) ---- H(8) | ||
| 787 | \ / | ||
| 788 | D(4) ---- E(5) | ||
| 789 | |||
| 790 | =head2 JSON | ||
| 791 | |||
| 792 | { | ||
| 793 | "name" : "sample map", | ||
| 794 | "lines" : { | ||
| 795 | "line" : [ | ||
| 796 | { "id" : "A", "name" : "A", "color" : "red" }, | ||
| 797 | { "id" : "B", "name" : "B", "color" : "#FFFF00" } | ||
| 798 | ] | ||
| 799 | }, | ||
| 800 | "stations" : { | ||
| 801 | "station" : [ | ||
| 802 | { "id" : "A1", "name" : "A1", "line" : "A", "link" : "B2,C3" }, | ||
| 803 | { "id" : "B2", "name" : "B2", "line" : "A", "link" : "A1,F6" }, | ||
| 804 | { "id" : "C3", "name" : "C3", "line" : "A,B", "link" : "A1,D4,F6" }, | ||
| 805 | { "id" : "D4", "name" : "D4", "line" : "A,B", "link" : "C3,E5" }, | ||
| 806 | { "id" : "E5", "name" : "E5", "line" : "B", "link" : "D4,F6" }, | ||
| 807 | { "id" : "F6", "name" : "F6", "line" : "B", "link" : "B2,C3,E5" }, | ||
| 808 | { "id" : "G7", "name" : "G7", "line" : "B", "link" : "F6,H8" }, | ||
| 809 | { "id" : "H8", "name" : "H8", "line" : "B", "link" : "G7" } | ||
| 810 | ] | ||
| 811 | } | ||
| 812 | } | ||
| 813 | |||
| 814 | =head2 XML | ||
| 815 | |||
| 816 | <?xml version="1.0" encoding="UTF-8"?> | ||
| 817 | <tube name="sample map"> | ||
| 818 | <lines> | ||
| 819 | <line id="A" name="A" color="red" /> | ||
| 820 | <line id="B" name="B" color="#FFFF00"/> | ||
| 821 | </lines> | ||
| 822 | <stations> | ||
| 823 | <station id="A1" name="A1" line="A" link="B2,C3" /> | ||
| 824 | <station id="B2" name="B2" line="A" link="A1,F6" /> | ||
| 825 | <station id="C3" name="C3" line="A,B" link="A1,D4,F6"/> | ||
| 826 | <station id="D4" name="D4" line="A,B" link="C3,E5" /> | ||
| 827 | <station id="E5" name="E5" line="B" link="D4,F6" /> | ||
| 828 | <station id="F6" name="F6" line="B" link="B2,C3,E5"/> | ||
| 829 | <station id="G7" name="G7" line="B" link="F6,H8" /> | ||
| 830 | <station id="H8" name="H8" line="B" link="G7" /> | ||
| 831 | </stations> | ||
| 832 | </tube> | ||
| 833 | |||
| 834 | =head1 MAP VALIDATION | ||
| 835 | |||
| 836 | =head2 DATA VALIDATION | ||
| 837 | |||
| 838 | The package L<Test::Map::Tube> can easily be used to validate raw map data. Anyone | ||
| 839 | building a new map using L<Map::Tube> is advised to have a unit test as a part of | ||
| 840 | their distribution. Just like in L<Map::Tube::London> package, there is a unit test | ||
| 841 | somewhat like below: | ||
| 842 | |||
| 843 | use strict; use warnings; | ||
| 844 | use Test::More; | ||
| 845 | use Map::Tube::London; | ||
| 846 | use Test::Map::Tube; | ||
| 847 | ok_map(Map::Tube::London->new); | ||
| 848 | |||
| 849 | =head2 FUNCTIONAL VALIDATION | ||
| 850 | |||
| 851 | The package L<Test::Map::Tube> can easily be used to validate map | ||
| 852 | basic functions provided by L<Map::Tube>. | ||
| 853 | |||
| 854 | use strict; use warnings; | ||
| 855 | use Test::More; | ||
| 856 | use Test::Map::Tube; | ||
| 857 | use Map::Tube::London; | ||
| 858 | ok_map_functions(Map::Tube::London->new); | ||
| 859 | |||
| 860 | It can also easily be used to validate map routing functions provided | ||
| 861 | by L<Map::Tube>: | ||
| 862 | |||
| 863 | use strict; use warnings; | ||
| 864 | use Test::More; | ||
| 865 | use Test::Map::Tube; | ||
| 866 | use Map::Tube::London; | ||
| 867 | my $map = Map::Tube::London->new; | ||
| 868 | my @routes = ( | ||
| 869 | "Route 1|Tower Gateway|Aldgate|Tower Gateway,Tower Hill,Aldgate", | ||
| 870 | "Route 2|Liverpool Street|Monument|Liverpool Street,Bank,Monument", | ||
| 871 | ); | ||
| 872 | ok_map_routes($map, \@routes); | ||
| 873 | |||
| 874 | =cut | ||
| 875 | |||
| 876 | # | ||
| 877 | # | ||
| 878 | # PRIVATE METHODS | ||
| 879 | |||
| 880 | sub _get_shortest_route { | ||
| 881 | my ($self, $from) = @_; | ||
| 882 | |||
| 883 | # Each line change adds this fractional penalty on top of the normal hop | ||
| 884 | # cost of 1. Must be < 1 so hop count always dominates, but large enough | ||
| 885 | # to distinguish zero-change routes from one-change routes. | ||
| 886 | |||
| 887 | $self->_init_table; | ||
| 888 | $self->_set_length($from, 0); | ||
| 889 | $self->_set_path($from, $from); | ||
| 890 | |||
| 891 | my $all_nodes = $self->{nodes}; | ||
| 892 | |||
| 893 | # Seed the start node with all of its own lines as the active lines. | ||
| 894 | if (defined $all_nodes->{$from}) { | ||
| 895 | my @ids = map { $_->{id} } @{$all_nodes->{$from}->{line}}; | ||
| 896 | $self->_set_current_lines($from, \@ids); | ||
| 897 | } | ||
| 898 | |||
| 899 | # BFS queue. We still use a plain FIFO queue (not a priority queue) so | ||
| 900 | # that the traversal order, and therefore tie-breaking, matches the | ||
| 901 | # original BFS as closely as possible. The only change is that the cost | ||
| 902 | # stored per node is penalty-weighted (fractional), so a same-hop path | ||
| 903 | # with zero line changes beats one with a change. | ||
| 904 | # | ||
| 905 | # "queued" replaces the old $seen: a node is added to the queue at most | ||
| 906 | # once per cost improvement. Unlike the original $seen, a node can be | ||
| 907 | # re-queued if a cheaper (penalty-aware) path is later discovered. | ||
| 908 | my $queued = {}; | ||
| 909 | my @queue = ($from); | ||
| 910 | $queued->{$from} = 1; | ||
| 911 | |||
| 912 | while (@queue) { | ||
| 913 | my $u = shift @queue; | ||
| 914 | my $u_cost = $self->_get_length($u); | ||
| 915 | my $u_node = $all_nodes->{$u}; | ||
| 916 | next unless defined $u_node; | ||
| 917 | |||
| 918 | $self->_set_active_links($u_node); | ||
| 919 | |||
| 920 | my %active_set = map { $_ => 1 } @{$self->_get_current_lines($u)}; | ||
| 921 | |||
| 922 | foreach my $v (split /\,/, $u_node->{link}) { | ||
| 923 | next if ($v eq $u); | ||
| 924 | |||
| 925 | my $v_node = $all_nodes->{$v}; | ||
| 926 | next unless defined $v_node; | ||
| 927 | |||
| 928 | my @v_line_ids = map { $_->{id} } @{$v_node->{line}}; | ||
| 929 | |||
| 930 | # If this specific edge (u -> v) is restricted to a subset of | ||
| 931 | # lines, only those lines are eligible to "continue" through it. | ||
| 932 | my $_u_restrictions = $self->{_link_lines}->{uc($u)}; | ||
| 933 | my $_restriction = defined($_u_restrictions) ? $_u_restrictions->{uc($v)} : undef; | ||
| 934 | if (defined $_restriction) { | ||
| 935 | my %_allowed = map { $_ => 1 } @$_restriction; | ||
| 936 | @v_line_ids = grep { $_allowed{uc($_)} } @v_line_ids; | ||
| 937 | } | ||
| 938 | |||
| 939 | my @continuing = grep { $active_set{$_} } @v_line_ids; | ||
| 940 | |||
| 941 | my $penalty = (@continuing == 0) ? $self->line_change_penalty : 0; | ||
| 942 | my $new_cost = $u_cost + 1 + $penalty; | ||
| 943 | |||
| 944 | # Update if unvisited or cheaper. "Unvisited" is path==undef | ||
| 945 | # (avoids the 0-cost ambiguity of the start node). | ||
| 946 | my $old_cost = $self->_get_length($v); | ||
| 947 | my $visited = defined $self->{tables}->{$v}->{path}; | ||
| 948 | |||
| 949 | if (!$visited || $new_cost < $old_cost) { | ||
| 950 | $self->_set_length($v, $new_cost); | ||
| 951 | $self->_set_path($v, $u); | ||
| 952 | my @next = @continuing ? @continuing | ||
| 953 | : (defined $_restriction ? @v_line_ids : $self->_capture_common_lines($u_node, $v_node)); | ||
| 954 | $self->_set_current_lines($v, \@next); | ||
| 955 | |||
| 956 | # Re-queue only if not already waiting in the queue. | ||
| 957 | unless ($queued->{$v}) { | ||
| 958 | push @queue, $v; | ||
| 959 | $queued->{$v} = 1; | ||
| 960 | } | ||
| 961 | } | ||
| 962 | } | ||
| 963 | |||
| 964 | # Allow re-queuing this node in future if a cheaper path is found. | ||
| 965 | delete $queued->{$u}; | ||
| 966 | } | ||
| 967 | } | ||
| 968 | |||
| 969 | sub _get_all_routes { | ||
| 970 | my ($self, $visited, $to) = @_; | ||
| 971 | |||
| 972 | my $last = $visited->[-1]; | ||
| 973 | my $nodes = $self->get_node_by_id($last)->link; | ||
| 974 | foreach my $id (split /\,/, $nodes) { | ||
| 975 | next if _is_visited($id, $visited); | ||
| 976 | |||
| 977 | if (is_same($id, $to)) { | ||
| 978 | push @$visited, $id; | ||
| 979 | $self->_set_routes($visited); | ||
| 980 | pop @$visited; | ||
| 981 | last; | ||
| 982 | } | ||
| 983 | } | ||
| 984 | |||
| 985 | foreach my $id (split /\,/, $nodes) { | ||
| 986 | next if (_is_visited($id, $visited) || is_same($id, $to)); | ||
| 987 | |||
| 988 | push @$visited, $id; | ||
| 989 | $self->_get_all_routes($visited, $to); | ||
| 990 | pop @$visited; | ||
| 991 | } | ||
| 992 | |||
| 993 | return $self->{routes}; | ||
| 994 | } | ||
| 995 | |||
| 996 | sub _map_node_name { | ||
| 997 | my ($self, $name, $id) = @_; | ||
| 998 | |||
| 999 | $self->{name_to_id}->{NFC(uc($name))} = $id; | ||
| 1000 | } | ||
| 1001 | |||
| 1002 | sub _validate_input { | ||
| 1003 | my ($self, $method, $from, $to) = @_; | ||
| 1004 | |||
| 1005 | my @caller = caller(0); | ||
| 1006 | @caller = caller(2) if $caller[3] eq '(eval)'; | ||
| 1007 | |||
| 1008 | Map::Tube::Exception::MissingStationName->throw({ | ||
| 1009 | method => __PACKAGE__."::$method", | ||
| 1010 | message => "ERROR: Missing Station Name.", | ||
| 1011 | filename => $caller[1], | ||
| 1012 | line_number => $caller[2] }) | ||
| 1013 | unless (defined($from) && defined($to)); | ||
| 1014 | |||
| 1015 | $from = trim($from); | ||
| 1016 | my $_from = $self->get_node_by_name($from); | ||
| 1017 | |||
| 1018 | $to = trim($to); | ||
| 1019 | my $_to = $self->get_node_by_name($to); | ||
| 1020 | |||
| 1021 | return ($_from->{id}, $_to->{id}); | ||
| 1022 | } | ||
| 1023 | |||
| 1024 | sub _xml_data { | ||
| 1025 | my ($self) = @_; | ||
| 1026 | |||
| 1027 | return $self->get_map_data; | ||
| 1028 | } | ||
| 1029 | |||
| 1030 | sub _init_map { | ||
| 1031 | my ($self) = @_; | ||
| 1032 | |||
| 1033 | my $_lines = {}; | ||
| 1034 | my $lines = {}; | ||
| 1035 | my $nodes = {}; | ||
| 1036 | my $tables = {}; | ||
| 1037 | my $_other_links = {}; | ||
| 1038 | my $_link_lines = {}; | ||
| 1039 | my $_seen_nodes = {}; | ||
| 1040 | |||
| 1041 | my @caller = caller(0); | ||
| 1042 | @caller = caller(2) if $caller[3] eq '(eval)'; | ||
| 1043 | |||
| 1044 | my $method = __PACKAGE__."::_init_map"; | ||
| 1045 | my $data = $self->get_map_data(\@caller, $method); | ||
| 1046 | $self->{name} = $data->{name}; | ||
| 1047 | |||
| 1048 | # Pull all lines detail first | ||
| 1049 | # So that we can check if a station has a valid line attached. | ||
| 1050 | my @lines; | ||
| 1051 | if (exists $data->{lines} && exists $data->{lines}->{line}) { | ||
| 1052 | @lines = (ref $data->{lines}->{line} eq 'HASH') | ||
| 1053 | ? ($data->{lines}->{line}) | ||
| 1054 | : @{$data->{lines}->{line}}; | ||
| 1055 | } | ||
| 1056 | my $master_line_data = {}; | ||
| 1057 | foreach (@lines) { | ||
| 1058 | $master_line_data->{NFC(lc $_->{id})} = 1; | ||
| 1059 | } | ||
| 1060 | |||
| 1061 | my $has_station_index = {}; | ||
| 1062 | foreach my $station (@{$data->{stations}->{station}}) { | ||
| 1063 | my $id = $station->{id}; | ||
| 1064 | |||
| 1065 | # Support per-link line restrictions in the 'link' attribute, e.g. | ||
| 1066 | # link="A:x,C" means the link to station A only runs on line 'x', | ||
| 1067 | # while the link to C is unrestricted (all lines common between the | ||
| 1068 | # two stations apply, as before). Multiple restricted lines for a | ||
| 1069 | # single link are pipe-separated, e.g. link="A:x|y,C". | ||
| 1070 | # This is fully backward compatible: a plain "A,C" with no colon is | ||
| 1071 | # untouched and behaves exactly as it always has. | ||
| 1072 | if (defined $station->{link} && $station->{link} =~ /\:/) { | ||
| 1073 | my @_clean_links = (); | ||
| 1074 | my $_restrictions_for_station = {}; | ||
| 1075 | foreach my $_raw_link (split /\,/, $station->{link}) { | ||
| 1076 | if ($_raw_link =~ /\:/) { | ||
| 1077 | my ($_target, $_line_list) = split /\:/, $_raw_link, 2; | ||
| 1078 | my @_restricted_lines = split /\|/, $_line_list; | ||
| 1079 | foreach my $_rline (@_restricted_lines) { | ||
| 1080 | my $_decoded_rline = _decode_utf8_if_needed($_rline); | ||
| 1081 | unless (exists $master_line_data->{NFC(lc $_decoded_rline)}) { | ||
| 1082 | Map::Tube::Exception::InvalidStationLineId->throw({ | ||
| 1083 | method => $method, | ||
| 1084 | message => "ERROR: Invalid restricted line [$_rline] for link to [$_target] at station [$id].", | ||
| 1085 | filename => $caller[1], | ||
| 1086 | line_number => $caller[2] }); | ||
| 1087 | } | ||
| 1088 | } | ||
| 1089 | $_restrictions_for_station->{uc($_target)} = [ map { uc(_decode_utf8_if_needed($_)) } @_restricted_lines ]; | ||
| 1090 | push @_clean_links, $_target; | ||
| 1091 | } | ||
| 1092 | else { | ||
| 1093 | push @_clean_links, $_raw_link; | ||
| 1094 | } | ||
| 1095 | } | ||
| 1096 | $station->{link} = join(",", @_clean_links); | ||
| 1097 | $_link_lines->{uc($id)} = $_restrictions_for_station; | ||
| 1098 | } | ||
| 1099 | |||
| 1100 | Map::Tube::Exception::DuplicateStationId->throw({ | ||
| 1101 | method => $method, | ||
| 1102 | message => "ERROR: Duplicate Station ID [$id].", | ||
| 1103 | filename => $caller[1], | ||
| 1104 | line_number => $caller[2] }) if (exists $_seen_nodes->{$id}); | ||
| 1105 | |||
| 1106 | $_seen_nodes->{$id} = 1; | ||
| 1107 | my $name = $station->{name}; | ||
| 1108 | $name = _decode_utf8_if_needed($name); | ||
| 1109 | Map::Tube::Exception::DuplicateStationName->throw({ | ||
| 1110 | method => $method, | ||
| 1111 | message => "ERROR: Duplicate Station Name [$name].", | ||
| 1112 | filename => $caller[1], | ||
| 1113 | line_number => $caller[2] }) if (defined $self->{name_to_id}->{NFC(uc($name))}); | ||
| 1114 | |||
| 1115 | $self->_map_node_name($name, $id); | ||
| 1116 | $tables->{$id} = Map::Tube::Table->new({ id => $id }); | ||
| 1117 | |||
| 1118 | my $_station_lines = []; | ||
| 1119 | foreach my $_line (split /\,/, $station->{line}) { | ||
| 1120 | if ($_line =~ /\:/) { | ||
| 1121 | $_line = $self->_capture_line_station($_line, $id); | ||
| 1122 | $has_station_index->{$_line} = 1; | ||
| 1123 | } | ||
| 1124 | |||
| 1125 | $_line = _decode_utf8_if_needed($_line); | ||
| 1126 | if (!exists $master_line_data->{NFC(lc $_line)}) { | ||
| 1127 | Map::Tube::Exception::InvalidStationLineId->throw({ | ||
| 1128 | method => $method, | ||
| 1129 | message => "ERROR: Invalid line [$_line] for station [$name].", | ||
| 1130 | filename => $caller[1], | ||
| 1131 | line_number => $caller[2] }); | ||
| 1132 | } | ||
| 1133 | |||
| 1134 | my $uc_line = uc($_line); | ||
| 1135 | my $line = $lines->{$uc_line}; | ||
| 1136 | $line = Map::Tube::Line->new({ id => $_line }) unless defined $line; | ||
| 1137 | $_lines->{$uc_line} = $line; | ||
| 1138 | $lines->{$uc_line} = $line; | ||
| 1139 | push @$_station_lines, $line; | ||
| 1140 | } | ||
| 1141 | |||
| 1142 | if (exists $station->{other_link} && defined $station->{other_link}) { | ||
| 1143 | my @link_nodes = (); | ||
| 1144 | foreach my $_entry (split /\,/, $station->{other_link}) { | ||
| 1145 | my ($_link_type, $_nodes) = split /\:/, $_entry, 2; | ||
| 1146 | my $uc_link_type = uc($_link_type); | ||
| 1147 | my $line = $lines->{$uc_link_type}; | ||
| 1148 | $line = Map::Tube::Line->new({ id => $_link_type, name => $_link_type }) unless defined $line; | ||
| 1149 | $_lines->{$uc_link_type} = $line; | ||
| 1150 | $lines->{$uc_link_type} = $line; | ||
| 1151 | $_other_links->{$uc_link_type} = 1; | ||
| 1152 | |||
| 1153 | push @$_station_lines, $line; | ||
| 1154 | push @link_nodes, (split /\|/, $_nodes); | ||
| 1155 | } | ||
| 1156 | |||
| 1157 | $station->{link} .= "," if $station->{link} ne ""; | ||
| 1158 | $station->{link} .= join(",", @link_nodes); | ||
| 1159 | } | ||
| 1160 | |||
| 1161 | $station->{line} = $_station_lines; | ||
| 1162 | my $node = Map::Tube::Node->new($station); | ||
| 1163 | $nodes->{$id} = $node; | ||
| 1164 | |||
| 1165 | foreach my $line (@{$_station_lines}) { | ||
| 1166 | next if exists $has_station_index->{$line->id}; | ||
| 1167 | push @{$line->{stations}}, $node; | ||
| 1168 | } | ||
| 1169 | } | ||
| 1170 | |||
| 1171 | foreach my $_line (@lines) { | ||
| 1172 | my $uc_line = uc($_line->{id}); | ||
| 1173 | my $line = $_lines->{$uc_line}; | ||
| 1174 | if (defined $line) { | ||
| 1175 | $line->{name} = $_line->{name}; | ||
| 1176 | $line->{color} = $_line->{color}; | ||
| 1177 | if ($has_station_index) { | ||
| 1178 | foreach (sort { $a <=> $b } keys %{$self->{_line_stations}->{$uc_line}}) { | ||
| 1179 | my $station_id = $self->{_line_stations}->{$uc_line}->{$_}; | ||
| 1180 | $line->add_station($nodes->{$station_id}); | ||
| 1181 | } | ||
| 1182 | } | ||
| 1183 | $_lines->{$uc_line} = $line; | ||
| 1184 | } | ||
| 1185 | } | ||
| 1186 | |||
| 1187 | $self->_order_station_lines($nodes); | ||
| 1188 | |||
| 1189 | $self->lines([ values %$lines ]); | ||
| 1190 | $self->_lines($_lines); | ||
| 1191 | $self->_other_links($_other_links); | ||
| 1192 | $self->_link_lines($_link_lines); | ||
| 1193 | |||
| 1194 | # Populate Node links as ref to Node object | ||
| 1195 | foreach my $node_id (keys %$nodes) { | ||
| 1196 | my $node_obj = $nodes->{$node_id}; | ||
| 1197 | foreach my $link (split /\,/,$node_obj->{link}) { | ||
| 1198 | push @{$node_obj->{links}}, $nodes->{$link}; | ||
| 1199 | } | ||
| 1200 | } | ||
| 1201 | |||
| 1202 | $self->nodes($nodes); | ||
| 1203 | $self->tables($tables); | ||
| 1204 | } | ||
| 1205 | |||
| 1206 | sub _decode_utf8_if_needed { | ||
| 1207 | my ($data) = @_; | ||
| 1208 | |||
| 1209 | if (!utf8::is_utf8($data) && utf8::valid($data)) { | ||
| 1210 | $data = decode_utf8($data); | ||
| 1211 | } | ||
| 1212 | |||
| 1213 | return $data; | ||
| 1214 | } | ||
| 1215 | |||
| 1216 | sub _is_directly_linked { | ||
| 1217 | my ($self, $start_station, $end_station) = @_; | ||
| 1218 | my $linked_stations = $self->get_linked_stations($start_station); | ||
| 1219 | |||
| 1220 | return grep { $_ eq $end_station } @$linked_stations; | ||
| 1221 | } | ||
| 1222 | |||
| 1223 | sub _init_table { | ||
| 1224 | my ($self) = @_; | ||
| 1225 | |||
| 1226 | foreach my $id (keys %{$self->{tables}}) { | ||
| 1227 | $self->{tables}->{$id}->{path} = undef; | ||
| 1228 | $self->{tables}->{$id}->{length} = 0; | ||
| 1229 | $self->{tables}->{$id}->{current_lines} = undef; | ||
| 1230 | } | ||
| 1231 | |||
| 1232 | $self->{_active_links} = undef; | ||
| 1233 | } | ||
| 1234 | |||
| 1235 | sub _load_plugins { | ||
| 1236 | my ($self) = @_; | ||
| 1237 | |||
| 1238 | $self->{plugins} = [ Map::Tube::Pluggable::plugins ]; | ||
| 1239 | foreach my $plugin (@{$self->plugins}) { | ||
| 1240 | # Only bother applying the approved plugins. | ||
| 1241 | next unless (exists $PLUGINS->{$plugin}); | ||
| 1242 | Role::Tiny->apply_roles_to_object($self, $plugin); | ||
| 1243 | } | ||
| 1244 | } | ||
| 1245 | |||
| 1246 | sub _capture_common_lines { | ||
| 1247 | my ($self, $from, $to) = @_; | ||
| 1248 | |||
| 1249 | my $from_lines = [ map { $_->id } @{$from->line} ]; | ||
| 1250 | my $to_lines = [ map { $_->id } @{$to->line} ]; | ||
| 1251 | |||
| 1252 | $self->{_common_lines} = [ common_lines($from_lines, $to_lines) ]; | ||
| 1253 | } | ||
| 1254 | |||
| 1255 | sub _get_common_lines { | ||
| 1256 | my ($nodes, $active_links) = @_; | ||
| 1257 | |||
| 1258 | my %_unique_links = (); | ||
| 1259 | foreach (@{$active_links}) { | ||
| 1260 | $_unique_links{$_} = 1; | ||
| 1261 | } | ||
| 1262 | |||
| 1263 | my %_common_lines = (); | ||
| 1264 | foreach my $_link (keys %_unique_links) { | ||
| 1265 | foreach my $_link_line (@{$nodes->{$_link}->line}) { | ||
| 1266 | $_common_lines{$_link_line->id} = 1; | ||
| 1267 | } | ||
| 1268 | } | ||
| 1269 | |||
| 1270 | return (keys %_common_lines); | ||
| 1271 | } | ||
| 1272 | |||
| 1273 | sub _get_next_link { | ||
| 1274 | my ($self, $from, $seen, $links) = @_; | ||
| 1275 | |||
| 1276 | my $nodes = $self->{nodes}; | ||
| 1277 | my $active_links = $self->{_active_links}; | ||
| 1278 | |||
| 1279 | # Revert changes as it breaks routing (v3.65) | ||
| 1280 | # Commit id: 49273fd2a0baaedbfc1d02ef7 | ||
| 1281 | # ------------------------------------------- | ||
| 1282 | # my @common_lines = _get_common_lines( | ||
| 1283 | # $nodes, [ @{$active_links->[0]}, @{$active_links->[1]} ] | ||
| 1284 | # ); | ||
| 1285 | |||
| 1286 | my @common_lines = common_lines($active_links->[0], $active_links->[1]); | ||
| 1287 | |||
| 1288 | if ($self->{experimental} && scalar(@{$self->{_common_lines}})) { | ||
| 1289 | @common_lines = (@{$self->{_common_lines}}, @common_lines); | ||
| 1290 | } | ||
| 1291 | |||
| 1292 | my $link = undef; | ||
| 1293 | foreach my $_link (@$links) { | ||
| 1294 | return (0, $_link) if ((exists $seen->{$_link}) || ($from eq $_link)); | ||
| 1295 | |||
| 1296 | my $node = $nodes->{$_link}; | ||
| 1297 | next unless defined $node; | ||
| 1298 | |||
| 1299 | my @lines = (); | ||
| 1300 | foreach (@{$node->{line}}) { push @lines, $_->{id}; } | ||
| 1301 | |||
| 1302 | my @common = common_lines(\@common_lines, \@lines); | ||
| 1303 | return (1, $_link) if (scalar(@common) > 0); | ||
| 1304 | |||
| 1305 | $link = $_link; | ||
| 1306 | } | ||
| 1307 | |||
| 1308 | return (defined($link), $link); | ||
| 1309 | } | ||
| 1310 | |||
| 1311 | sub _set_active_links { | ||
| 1312 | my ($self, $node) = @_; | ||
| 1313 | |||
| 1314 | my $active_links = $self->{_active_links}; | ||
| 1315 | my $links = [ split /\,/, $node->{link} ]; | ||
| 1316 | |||
| 1317 | if (defined $active_links) { | ||
| 1318 | shift @$active_links; | ||
| 1319 | push @$active_links, $links; | ||
| 1320 | } | ||
| 1321 | else { | ||
| 1322 | push @$active_links, $links; | ||
| 1323 | push @$active_links, $links; | ||
| 1324 | } | ||
| 1325 | |||
| 1326 | $self->{_active_links} = $active_links; | ||
| 1327 | } | ||
| 1328 | |||
| 1329 | sub _validate_map_structure { | ||
| 1330 | my ($self, $data, $caller) = @_; | ||
| 1331 | |||
| 1332 | unless (exists $data->{lines} | ||
| 1333 | && exists $data->{lines}->{line} | ||
| 1334 | && @{$data->{lines}->{line}}) { | ||
| 1335 | Map::Tube::Exception::InvalidLineStructure->throw({ | ||
| 1336 | method => __PACKAGE__."::_validate_map_structure", | ||
| 1337 | message => "ERROR: Invalid line structure in map data.", | ||
| 1338 | filename => $caller->[1], | ||
| 1339 | line_number => $caller->[2] }); | ||
| 1340 | } | ||
| 1341 | |||
| 1342 | unless (exists $data->{stations} | ||
| 1343 | && exists $data->{stations}->{station} | ||
| 1344 | && @{$data->{stations}->{station}}) { | ||
| 1345 | Map::Tube::Exception::InvalidStationStructure->throw({ | ||
| 1346 | method => __PACKAGE__."::_validate_map_structure", | ||
| 1347 | message => "ERROR: Invalid station structure in map data.", | ||
| 1348 | filename => $caller->[1], | ||
| 1349 | line_number => $caller->[2] }); | ||
| 1350 | } | ||
| 1351 | } | ||
| 1352 | |||
| 1353 | sub _capture_line_station { | ||
| 1354 | my ($self, $line, $station_id) = @_; | ||
| 1355 | |||
| 1356 | my ($line_id, $sequence) = split /\:/, $line, 2; | ||
| 1357 | $self->{_line_stations}->{uc($line_id)}->{$sequence} = $station_id; | ||
| 1358 | $self->{_line_station_index}->{uc($line_id)}->{$station_id} = $sequence; | ||
| 1359 | |||
| 1360 | return $line_id; | ||
| 1361 | } | ||
| 1362 | |||
| 1363 | sub _validate_multi_lined_nodes { | ||
| 1364 | my ($self, $caller, $node, $id) = @_; | ||
| 1365 | |||
| 1366 | my %lines = (); | ||
| 1367 | foreach (@{$node->{line}}) { $lines{$_->{id}}++; } | ||
| 1368 | |||
| 1369 | my $max_link = 1; | ||
| 1370 | foreach (keys %lines) { | ||
| 1371 | $max_link = $lines{$_} if ($max_link < $lines{$_}); | ||
| 1372 | } | ||
| 1373 | |||
| 1374 | if ($max_link > 1) { | ||
| 1375 | my $message = sprintf("ERROR: %s has multiple lines %s,", | ||
| 1376 | $id, join( ',', grep { $lines{$_} > 1 } keys %lines)); | ||
| 1377 | |||
| 1378 | Map::Tube::Exception::FoundMultiLinedStation->throw({ | ||
| 1379 | method => __PACKAGE__."::_validate_map_data", | ||
| 1380 | message => $message, | ||
| 1381 | filename => $caller->[1], | ||
| 1382 | line_number => $caller->[2] }); | ||
| 1383 | } | ||
| 1384 | } | ||
| 1385 | |||
| 1386 | sub _set_routes { | ||
| 1387 | my ($self, $routes) = @_; | ||
| 1388 | |||
| 1389 | my $_routes = []; | ||
| 1390 | my $nodes = $self->{nodes}; | ||
| 1391 | foreach my $id (@$routes) { | ||
| 1392 | push @$_routes, $nodes->{$id}; | ||
| 1393 | } | ||
| 1394 | |||
| 1395 | my $from = $_routes->[0]; | ||
| 1396 | my $to = $_routes->[-1]; | ||
| 1397 | my $route = Map::Tube::Route->new({ from => $from, to => $to, nodes => $_routes, link_lines => $self->_link_lines }); | ||
| 1398 | push @{$self->{routes}}, $route; | ||
| 1399 | } | ||
| 1400 | |||
| 1401 | sub _get_path { | ||
| 1402 | my ($self, $id) = @_; | ||
| 1403 | |||
| 1404 | return $self->{tables}->{$id}->{path}; | ||
| 1405 | } | ||
| 1406 | |||
| 1407 | sub _set_path { | ||
| 1408 | my ($self, $id, $node_id) = @_; | ||
| 1409 | |||
| 1410 | return unless (defined $id && defined $node_id); | ||
| 1411 | $self->{tables}->{$id}->{path} = $node_id; | ||
| 1412 | } | ||
| 1413 | |||
| 1414 | sub _get_length { | ||
| 1415 | my ($self, $id) = @_; | ||
| 1416 | |||
| 1417 | return 0 unless (defined $id && defined $self->{tables}->{$id}); | ||
| 1418 | return $self->{tables}->{$id}->{length}; | ||
| 1419 | } | ||
| 1420 | |||
| 1421 | sub _set_length { | ||
| 1422 | my ($self, $id, $value) = @_; | ||
| 1423 | |||
| 1424 | return unless (defined $id && defined $value); | ||
| 1425 | $self->{tables}->{$id}->{length} = $value; | ||
| 1426 | } | ||
| 1427 | |||
| 1428 | # Track the set of line IDs that were active when we arrived at a node. | ||
| 1429 | # This lets _get_shortest_route penalise line changes. | ||
| 1430 | sub _get_current_lines { | ||
| 1431 | my ($self, $id) = @_; | ||
| 1432 | |||
| 1433 | return [] unless (defined $id && defined $self->{tables}->{$id}); | ||
| 1434 | return $self->{tables}->{$id}->{current_lines} // []; | ||
| 1435 | } | ||
| 1436 | |||
| 1437 | sub _set_current_lines { | ||
| 1438 | my ($self, $id, $lines_ref) = @_; | ||
| 1439 | |||
| 1440 | return unless (defined $id && defined $lines_ref); | ||
| 1441 | $self->{tables}->{$id}->{current_lines} = $lines_ref; | ||
| 1442 | } | ||
| 1443 | |||
| 1444 | sub _get_table { | ||
| 1445 | my ($self, $id) = @_; | ||
| 1446 | |||
| 1447 | return $self->{tables}->{$id}; | ||
| 1448 | } | ||
| 1449 | |||
| 1450 | sub _get_node_id { | ||
| 1451 | my ($self, $name) = @_; | ||
| 1452 | |||
| 1453 | return unless defined $name; | ||
| 1454 | $name =~ s/^\s+//; | ||
| 1455 | $name =~ s/\s+$//; | ||
| 1456 | $name = _decode_utf8_if_needed($name); | ||
| 1457 | $name = NFC(uc($name)); | ||
| 1458 | return $self->{name_to_id}->{$name}; | ||
| 1459 | } | ||
| 1460 | |||
| 1461 | sub _get_line_object_by_name { | ||
| 1462 | my ($self, $name) = @_; | ||
| 1463 | |||
| 1464 | $name = _decode_utf8_if_needed($name); | ||
| 1465 | $name = NFC(uc($name)); | ||
| 1466 | foreach my $line_id (keys %{$self->{_lines}}) { | ||
| 1467 | my $line = $self->{_lines}->{$line_id}; | ||
| 1468 | if (defined $line && defined $line->name) { | ||
| 1469 | return $line if ($name eq uc($line->name)); | ||
| 1470 | } | ||
| 1471 | } | ||
| 1472 | |||
| 1473 | return; | ||
| 1474 | } | ||
| 1475 | |||
| 1476 | sub _get_line_object_by_id { | ||
| 1477 | my ($self, $id) = @_; | ||
| 1478 | |||
| 1479 | $id = uc($id); | ||
| 1480 | foreach my $line_id (keys %{$self->{_lines}}) { | ||
| 1481 | |||
| 1482 | my $line = $self->{_lines}->{$line_id}; | ||
| 1483 | if (defined $line && defined $line->name) { | ||
| 1484 | return $line if ($id eq uc($line->id)); | ||
| 1485 | } | ||
| 1486 | } | ||
| 1487 | |||
| 1488 | return; | ||
| 1489 | } | ||
| 1490 | |||
| 1491 | sub _order_station_lines { | ||
| 1492 | my ($self, $nodes) = @_; | ||
| 1493 | |||
| 1494 | return unless scalar(keys %$nodes); | ||
| 1495 | |||
| 1496 | foreach my $node (keys %$nodes) { | ||
| 1497 | my $_lines_h = {}; | ||
| 1498 | foreach (@{$nodes->{$node}->{line}}) { | ||
| 1499 | $_lines_h->{$_->id} = $_ if defined $_->name; | ||
| 1500 | } | ||
| 1501 | my $_lines_a = []; | ||
| 1502 | foreach (sort keys %$_lines_h) { | ||
| 1503 | push @$_lines_a, $_lines_h->{$_}; | ||
| 1504 | } | ||
| 1505 | $nodes->{$node}->line($_lines_a); | ||
| 1506 | } | ||
| 1507 | } | ||
| 1508 | |||
| 1509 | sub _is_visited { | ||
| 1510 | my ($id, $list) = @_; | ||
| 1511 | |||
| 1512 | foreach (@$list) { | ||
| 1513 | return 1 if is_same($_, $id); | ||
| 1514 | } | ||
| 1515 | |||
| 1516 | return 0; | ||
| 1517 | } | ||
| 1518 | |||
| 1519 | =head1 AUTHOR | ||
| 1520 | |||
| 1521 | Mohammad Sajid Anwar, C<< <mohammad.anwar at yahoo.com> >> | ||
| 1522 | |||
| 1523 | =head1 REPOSITORY | ||
| 1524 | |||
| 1525 | L<https://github.com/manwar/Map-Tube> | ||
| 1526 | |||
| 1527 | =head1 SEE ALSO | ||
| 1528 | |||
| 1529 | =over 2 | ||
| 1530 | |||
| 1531 | =item * L<Map::Tube::CLI> | ||
| 1532 | |||
| 1533 | =item * L<Map::Tube::API> | ||
| 1534 | |||
| 1535 | =item * L<Map::Tube::Server> | ||
| 1536 | |||
| 1537 | =item * L<Map::Metro> | ||
| 1538 | |||
| 1539 | =back | ||
| 1540 | |||
| 1541 | =head1 CONTRIBUTORS | ||
| 1542 | |||
| 1543 | =over 2 | ||
| 1544 | |||
| 1545 | =item * Michal Špaček, C<< <skim at cpan.org> >> | ||
| 1546 | |||
| 1547 | =item * Slaven Rezic, C<< <srezic at cpan.org> >> | ||
| 1548 | |||
| 1549 | =item * Gisbert W. Selke, C<< <gws at cpan.org> >> | ||
| 1550 | |||
| 1551 | =item * Toby Inkster, C<< <tobyink at cpan.org> >> | ||
| 1552 | |||
| 1553 | =item * Ed J, C<< <etj at cpan.org> >> | ||
| 1554 | |||
| 1555 | =back | ||
| 1556 | |||
| 1557 | =head1 BUGS | ||
| 1558 | |||
| 1559 | Please report any bugs or feature requests through the web interface at L<https://github.com/manwar/Map-Tube/issues>. | ||
| 1560 | I will be notified and then you'll automatically be notified of progress on your | ||
| 1561 | bug as I make changes. | ||
| 1562 | |||
| 1563 | =head1 SUPPORT | ||
| 1564 | |||
| 1565 | You can find documentation for this module with the perldoc command. | ||
| 1566 | |||
| 1567 | perldoc Map::Tube | ||
| 1568 | |||
| 1569 | You can also look for information at: | ||
| 1570 | |||
| 1571 | =over 4 | ||
| 1572 | |||
| 1573 | =item * BUG Report | ||
| 1574 | |||
| 1575 | L<https://github.com/manwar/Map-Tube/issues> | ||
| 1576 | |||
| 1577 | =item * Search MetaCPAN | ||
| 1578 | |||
| 1579 | L<https://metacpan.org/dist/Map-Tube/> | ||
| 1580 | |||
| 1581 | =back | ||
| 1582 | |||
| 1583 | =head1 LICENSE AND COPYRIGHT | ||
| 1584 | |||
| 1585 | Copyright (C) 2010 - 2026 Mohammad Sajid Anwar. | ||
| 1586 | |||
| 1587 | This program is free software; you can redistribute it and / or modify it under | ||
| 1588 | the terms of the the Artistic License (2.0). You may obtain a copy of the full | ||
| 1589 | license at: | ||
| 1590 | |||
| 1591 | L<http://www.perlfoundation.org/artistic_license_2_0> | ||
| 1592 | |||
| 1593 | Any use, modification, and distribution of the Standard or Modified Versions is | ||
| 1594 | governed by this Artistic License.By using, modifying or distributing the Package, | ||
| 1595 | you accept this license. Do not use, modify, or distribute the Package, if you do | ||
| 1596 | not accept this license. | ||
| 1597 | |||
| 1598 | If your Modified Version has been derived from a Modified Version made by someone | ||
| 1599 | other than you,you are nevertheless required to ensure that your Modified Version | ||
| 1600 | complies with the requirements of this license. | ||
| 1601 | |||
| 1602 | This license does not grant you the right to use any trademark, service mark, | ||
| 1603 | tradename, or logo of the Copyright Holder. | ||
| 1604 | |||
| 1605 | This license includes the non-exclusive, worldwide, free-of-charge patent license | ||
| 1606 | to make, have made, use, offer to sell, sell, import and otherwise transfer the | ||
| 1607 | Package with respect to any patent claims licensable by the Copyright Holder that | ||
| 1608 | are necessarily infringed by the Package. If you institute patent litigation | ||
| 1609 | (including a cross-claim or counterclaim) against any party alleging that the | ||
| 1610 | Package constitutes direct or contributory patent infringement,then this Artistic | ||
| 1611 | License to you shall terminate on the date that such litigation is filed. | ||
| 1612 | |||
| 1613 | Disclaimer of Warranty: THE PACKAGE IS PROVIDED BY THE COPYRIGHT HOLDER AND | ||
| 1614 | CONTRIBUTORS "AS IS' AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES. THE IMPLIED | ||
| 1615 | WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR | ||
| 1616 | NON-INFRINGEMENT ARE DISCLAIMED TO THE EXTENT PERMITTED BY YOUR LOCAL LAW. UNLESS | ||
| 1617 | REQUIRED BY LAW, NO COPYRIGHT HOLDER OR CONTRIBUTOR WILL BE LIABLE FOR ANY DIRECT, | ||
| 1618 | INDIRECT, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING IN ANY WAY OUT OF THE USE | ||
| 1619 | OF THE PACKAGE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | ||
| 1620 | |||
| 1621 | =cut | ||
| 1622 | |||
| 1623 | 1; # End of Map::Tube | ||