wybr/tally/
vote_matrix.rs

1use crate::tally::Metadata;
2use std::collections::{HashMap, HashSet};
3
4#[derive(Clone)]
5pub struct VoteMatrix {
6    n: u32,
7    data: HashMap<(u32, u32), u64>,
8    meta: Metadata,
9}
10
11pub struct VoteMatrixPairIterator<'a> {
12    wrapped: std::collections::hash_map::Iter<'a, (u32, u32), u64>,
13    base: &'a VoteMatrix,
14}
15impl<'a> Iterator for VoteMatrixPairIterator<'a> {
16    type Item = ((u32, u32), (u64, u64));
17    fn next(&mut self) -> Option<Self::Item> {
18        if let Some((&(i, j), &v)) = self.wrapped.next() {
19            let alt = self.base[(j, i)];
20            Some(((i, j), (v, alt)))
21        } else {
22            None
23        }
24    }
25}
26
27impl VoteMatrix {
28    //TODO: Make an actual error here
29    //Panics on a wrong size of x
30    pub fn with_vector_bycol(x: &[u64]) -> VoteMatrix {
31        if x.is_empty() {
32            return VoteMatrix {
33                n: 0,
34                data: HashMap::new(),
35                meta: Metadata::empty(),
36            };
37        }
38        let s: f64 = x.len() as f64;
39        let ln = (1. + (1. + 4. * s).sqrt()) / 2.;
40        let mut data: HashMap<(u32, u32), u64> = HashMap::new();
41
42        if ln.fract() != 0. {
43            panic!("Cannot build VoteMatrix from a vector of such size");
44        }
45        let n: u32 = ln as u32;
46        let mut ii = x.iter();
47        for j in 0..n {
48            for i in 0..n {
49                if i != j {
50                    let ne = *ii.next().unwrap();
51                    if ne > 0 {
52                        data.insert((i, j), ne);
53                    }
54                }
55            }
56        }
57        VoteMatrix {
58            n,
59            data,
60            meta: Metadata::empty(),
61        }
62    }
63    pub fn pairs(&self) -> VoteMatrixPairIterator {
64        VoteMatrixPairIterator {
65            wrapped: self.data.iter(),
66            base: self,
67        }
68    }
69}
70
71use crate::tally::Tally;
72impl Tally for VoteMatrix {
73    fn get_meta(&self) -> &'_ Metadata {
74        &self.meta
75    }
76    fn get_candidates(&self) -> u32 {
77        self.n
78    }
79}
80
81use std::fmt;
82impl fmt::Debug for VoteMatrix {
83    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
84        write!(f, "/ {0}x{0} VoteMatrix:\n|", self.n)?;
85        for i in 0..self.n {
86            for j in 0..self.n {
87                if i != j {
88                    write!(f, "{:^5}", &self.data.get(&(i, j)).unwrap_or(&0))?;
89                } else {
90                    write!(f, "  -  ")?;
91                }
92            }
93            write!(f, "\n|")?
94        }
95        writeln!(f, ".\n")
96    }
97}
98
99//Index only (not IndexMut) on purpose; we don't like messing inside
100use std::ops::Index;
101impl Index<(u32, u32)> for VoteMatrix {
102    type Output = u64;
103    fn index(&self, ij: (u32, u32)) -> &u64 {
104        self.data.get(&ij).unwrap_or(&0)
105    }
106}
107
108use std::iter::FromIterator;
109impl FromIterator<(u32, u32, u64)> for VoteMatrix {
110    fn from_iter<I: IntoIterator<Item = (u32, u32, u64)>>(i: I) -> Self {
111        let data: HashMap<(u32, u32), u64> = i.into_iter().map(|(i, j, k)| ((i, j), k)).collect();
112        let n = if let Some(cmax) = data.keys().map(|&(i, j)| std::cmp::max(i, j)).max() {
113            cmax + 1
114        } else {
115            0
116        };
117        VoteMatrix {
118            n,
119            data,
120            meta: Metadata::empty(),
121        }
122    }
123}
124
125use self::VoteToken::*;
126use crate::tally::{VoteReadError, VoteToken};
127impl FromIterator<VoteToken> for Result<VoteMatrix, VoteReadError> {
128    fn from_iter<I: IntoIterator<Item = VoteToken>>(i: I) -> Self {
129        //Global state
130        let mut data: HashMap<(u32, u32), u64> = HashMap::new();
131        let mut withdrawn: HashSet<u32> = HashSet::new();
132        let mut candidates: Option<u32> = None;
133        let mut candidate_names: HashMap<u32, String> = HashMap::new();
134        let mut title: Option<String> = None;
135        let mut seats: Option<u32> = None;
136
137        //Per-ballot state
138        let mut ballot: HashMap<u32, i32> = HashMap::new();
139        let mut ballot_repeat: Option<u64> = None;
140
141        for token in i {
142            match token {
143                ReadFailure(x) => return Err(x),
144                DeclareCandidates(x) => candidates = candidates.or(Some(x)),
145                DeclareSeats(x) => seats = seats.or(Some(x)),
146                WithdrawCandidate(x) => {
147                    withdrawn.insert(x);
148                }
149                BallotRepeat(x) => ballot_repeat = Some(x),
150                Vote(pref, cand) => {
151                    ballot.insert(cand, pref);
152                }
153                EndBallot => {
154                    let cn = candidates.unwrap();
155                    //The following can be removed for unmentioned-indifferent case
156                    for cand in 0..cn {
157                        ballot.entry(cand).or_insert(i32::MAX);
158                    }
159                    for (&runner, &r_pref) in &ballot {
160                        for (&opponent, &o_pref) in &ballot {
161                            if r_pref < o_pref {
162                                *data.entry((runner, opponent)).or_insert(0) +=
163                                    ballot_repeat.unwrap(); //TODO: As above
164                            }
165                        }
166                    }
167                    //Clear the ballot cache
168                    ballot_repeat = None;
169                    ballot.clear();
170                }
171                ElectionTitle(x) => title = title.or(Some(x)),
172                CandidateName(cand, name) => {
173                    candidate_names.insert(cand, name);
174                }
175                _ => (),
176            }
177        }
178        if let Some(n) = candidates {
179            Ok(VoteMatrix {
180                n,
181                data,
182                meta: Metadata::new(seats, withdrawn, candidate_names, title),
183            })
184        } else {
185            Err(VoteReadError::InvalidMeta)
186        }
187    }
188}
189
190#[cfg(test)]
191mod tests {
192    use super::*;
193    #[test]
194    fn from_blt_and_idx() {
195        use crate::io::BltReader;
196        use std::collections::HashSet;
197        use std::io::Cursor;
198        const EASY_BLT: &'static [u8] =
199            b" 3  1\n -3 \n 7  1 =2  =3 0\n \n  17 2  3 1  0\n 0 17 8 0\n27 3 2  1 0\n 0 \n \"A\"\n  \n\"B\" \n\"C\"\n \"Title\" \n";
200        let mut cursor = Cursor::new(EASY_BLT);
201        let blt_reader = BltReader::new(&mut cursor);
202        let vc = blt_reader
203            .collect::<Result<VoteMatrix, VoteReadError>>()
204            .unwrap();
205        assert_eq!(vc[(1, 0)], 44);
206        assert_eq!(vc[(2, 0)], 44);
207        assert_eq!(vc[(0, 1)], 0);
208        assert_eq!(vc[(2, 1)], 27);
209        assert_eq!(vc[(0, 2)], 0);
210        assert_eq!(vc[(1, 2)], 17);
211        //As above, but without 0s
212        let ps = vc.pairs().collect::<HashSet<_>>();
213        assert!(ps.contains(&((2, 0), (44, 0))));
214        assert!(ps.contains(&((2, 1), (27, 17))));
215        assert!(ps.contains(&((1, 0), (44, 0))));
216        assert!(ps.contains(&((1, 2), (17, 27))));
217        assert_eq!(ps.len(), 4);
218    }
219}
wybr/tally/vote_matrix.rs

wybr/tally/
vote_matrix.rs
