1 files changed, 52 insertions, 0 deletions
diff --git a/vendor/petgraph/src/scored.rs b/vendor/petgraph/src/scored.rs
new file mode 100644
index 000000000..b4da04b4b
--- /dev/null
+++ b/vendor/petgraph/src/scored.rs
@@ -0,0 +1,52 @@
+use std::cmp::Ordering;
+
+/// `MinScored<K, T>` holds a score `K` and a scored object `T` in
+/// a pair for use with a `BinaryHeap`.
+///
+/// `MinScored` compares in reverse order by the score, so that we can
+/// use `BinaryHeap` as a min-heap to extract the score-value pair with the
+/// least score.
+///
+/// **Note:** `MinScored` implements a total order (`Ord`), so that it is
+/// possible to use float types as scores.
+#[derive(Copy, Clone, Debug)]
+pub struct MinScored<K, T>(pub K, pub T);
+
+impl<K: PartialOrd, T> PartialEq for MinScored<K, T> {
+    #[inline]
+    fn eq(&self, other: &MinScored<K, T>) -> bool {
+        self.cmp(other) == Ordering::Equal
+    }
+}
+
+impl<K: PartialOrd, T> Eq for MinScored<K, T> {}
+
+impl<K: PartialOrd, T> PartialOrd for MinScored<K, T> {
+    #[inline]
+    fn partial_cmp(&self, other: &MinScored<K, T>) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
+impl<K: PartialOrd, T> Ord for MinScored<K, T> {
+    #[inline]
+    fn cmp(&self, other: &MinScored<K, T>) -> Ordering {
+        let a = &self.0;
+        let b = &other.0;
+        if a == b {
+            Ordering::Equal
+        } else if a < b {
+            Ordering::Greater
+        } else if a > b {
+            Ordering::Less
+        } else if a.ne(a) && b.ne(b) {
+            // these are the NaN cases
+            Ordering::Equal
+        } else if a.ne(a) {
+            // Order NaN less, so that it is last in the MinScore order
+            Ordering::Less
+        } else {
+            Ordering::Greater
+        }
+    }
+}