diff options
Diffstat (limited to 'src/main.rs')
-rw-r--r-- | src/main.rs | 32 |
1 files changed, 17 insertions, 15 deletions
diff --git a/src/main.rs b/src/main.rs index 26e2b4e..f34413a 100644 --- a/src/main.rs +++ b/src/main.rs @@ -48,11 +48,13 @@ fn process_embedder<E>(mut e: E, args: Args) -> Result<Vec<PathBuf>, String> impl Eq for DownOrd {} impl PartialOrd for DownOrd { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { - self.0.partial_cmp(&other.0).map(|e| e.reverse()) + Some(self.cmp(other)) } } impl Ord for DownOrd { - fn cmp(&self, other: &Self) -> Ordering {self.partial_cmp(other).unwrap()} + fn cmp(&self, other: &Self) -> Ordering { + self.0.partial_cmp(&other.0).unwrap().reverse() + } } let num_ims = args.images.len(); @@ -65,42 +67,42 @@ fn process_embedder<E>(mut e: E, args: Args) -> Result<Vec<PathBuf>, String> .into_iter() .collect(); - let mut possibleEdges = + let mut possible_edges = PriorityQueue::with_capacity((num_ims * num_ims - num_ims) / 2); - let mut visitedImages = HashMap::with_capacity(num_ims); + let mut mst = HashMap::with_capacity(num_ims); // here, we start at 0. // we might get a better result in the end if we started with a vertex next // to the lowest-cost edge, but we don't know which one that is (though we // could compute that without changing our asymptotic complexity) - visitedImages.insert(0, Vec::new()); + mst.insert(0, Vec::new()); for i in 1..num_ims { - possibleEdges.push((0, i), DownOrd(embeds[0].dist(&embeds[i]))); + possible_edges.push((0, i), DownOrd(embeds[0].dist(&embeds[i]))); } // prims algorithm or something like that - while visitedImages.len() < num_ims { + while mst.len() < num_ims { // find the edge with the least cost that connects us to a new vertex let (new, old) = loop { - let ((a, b), _) = possibleEdges.pop().unwrap(); - if !visitedImages.contains_key(&a) { + let ((a, b), _) = possible_edges.pop().unwrap(); + if !mst.contains_key(&a) { break (a, b); } - else if !visitedImages.contains_key(&b) { + else if !mst.contains_key(&b) { break (b, a); } }; - visitedImages.insert(new, Vec::new()); + mst.insert(new, Vec::new()); // insert all the new edges we could take - visitedImages.entry(old).and_modify(|v|v.push(new)); + mst.entry(old).and_modify(|v|v.push(new)); for i in 0..num_ims { // don't consider edges taking us to nodes we already visited - if visitedImages.contains_key(&i) { + if mst.contains_key(&i) { continue; } - possibleEdges.push((new, i), DownOrd(embeds[new].dist(&embeds[i]))); + possible_edges.push((new, i), DownOrd(embeds[new].dist(&embeds[i]))); } } @@ -110,7 +112,7 @@ fn process_embedder<E>(mut e: E, args: Args) -> Result<Vec<PathBuf>, String> t.get(&cur).unwrap().iter().for_each(|c| dfs(*c, t, into)); } let mut tsp_path = Vec::with_capacity(num_ims); - dfs(0, &visitedImages, &mut tsp_path); + dfs(0, &mst, &mut tsp_path); Ok(tsp_path.iter().map(|i| args.images[*i].clone()).collect()) } |