n18route 0.1.0

Searches 18xx maps for optimal route combinations.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

//! # Overview
//!
//! This module solves the problem of finding the set of routes that can be
//! run by a company to yield the highest possible revenue.
//!
//! See the [route-finding documentation](crate::doc) for details.

use std::collections::BTreeSet;

use n18map::HexAddress;
use n18tile::Connection;

use crate::conflict::RouteConflicts;
use crate::Conflict;

/// A single step in a path.
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct Step {
    pub addr: HexAddress,
    pub conn: Connection,
}

/// The different locations at which a train may stop and earn revenue.
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum StopLocation {
    City { ix: usize },
    Dit { ix: usize },
}

impl StopLocation {
    pub fn is_city(&self) -> bool {
        matches!(self, StopLocation::City { .. })
    }

    pub fn is_dit(&self) -> bool {
        matches!(self, StopLocation::Dit { .. })
    }
}

/// A location on a path that, if the train stops here, may earn revenue.
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct Visit {
    /// The tile on which this stop occurs.
    pub addr: HexAddress,
    /// The base revenue for this location.
    pub revenue: usize,
    /// The city or dit associated with this visit.
    pub visits: StopLocation,
}

/// A path that a train may travel along.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct Path {
    pub steps: Vec<Step>,
    pub conflicts: BTreeSet<Conflict>,
    pub route_conflicts: RouteConflicts,
    pub visits: Vec<Visit>,
    pub num_visits: usize,
    pub num_cities: usize,
    pub num_dits: usize,
    pub num_hexes: usize,
    pub revenue: usize,
}

impl Path {
    /// Returns the location at which this path starts.
    pub fn start(&self) -> &Visit {
        self.visits.first().unwrap()
    }

    /// Returns the location at which this path ends.
    pub fn end(&self) -> &Visit {
        self.visits.last().unwrap()
    }

    /// Joins two paths, which must start from the same location.
    pub(crate) fn append(&self, other: &Path) -> Path {
        // NOTE: ensure that the first step of both paths is the same.
        if self.steps[0] != other.steps[0] {
            panic!(
                "Paths don't start from the same location: {:?} and {:?}",
                self.steps[0], other.steps[0]
            );
        }
        let mut steps = self.steps.clone();
        let mut other_steps: Vec<_> =
            other.steps[1..].iter().copied().collect();
        steps.append(&mut other_steps);
        let mut visits = self.visits.clone();
        let mut other_visits: Vec<_> =
            other.visits[1..].iter().copied().collect();
        // NOTE: ensure the visits are in order, so start from the end of
        // self's path and travel to the self's start, which is also other's
        // start, and continue on to other's end.
        visits.reverse();
        visits.append(&mut other_visits);
        let conflicts: BTreeSet<_> =
            self.conflicts.union(&other.conflicts).copied().collect();
        let route_conflicts =
            self.route_conflicts.merge(&other.route_conflicts);
        let start_revenue = self.visits[0].revenue;
        let revenue = self.revenue + other.revenue - start_revenue;
        let num_visits = visits.len();
        let num_cities = self.num_cities + other.num_cities - 1;
        let num_dits = self.num_dits + other.num_dits;
        let num_hexes = self.num_hexes + other.num_hexes - 1;
        Path {
            steps,
            conflicts,
            route_conflicts,
            visits,
            num_visits,
            num_cities,
            num_dits,
            num_hexes,
            revenue,
        }
    }
}