From 2d127740cf30cfbd3875a406ecc42ef6ebde60e4 Mon Sep 17 00:00:00 2001
From: Lia Lenckowski <lialenck@protonmail.com>
Date: Wed, 20 Sep 2023 13:34:35 +0200
Subject: ~3x speed improvement: replace priority queues and prim's algoritm
 with sorted vectors and krushkal's algorithm

---
 Cargo.lock | 44 +++++++++++++++++---------------------------
 1 file changed, 17 insertions(+), 27 deletions(-)

(limited to 'Cargo.lock')

diff --git a/Cargo.lock b/Cargo.lock
index 3871c28..235df0d 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -77,6 +77,12 @@ dependencies = [
  "serde",
 ]
 
+[[package]]
+name = "bit-vec"
+version = "0.5.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f59bbe95d4e52a6398ec21238d31577f2b28a9d86807f06ca59d191d8440d0bb"
+
 [[package]]
 name = "bit_field"
 version = "0.10.2"
@@ -289,8 +295,8 @@ dependencies = [
  "image",
  "indicatif",
  "multiset",
+ "partitions",
  "pathdiff",
- "priority-queue",
  "rayon",
  "reflink-copy",
  "serde",
@@ -428,12 +434,6 @@ dependencies = [
  "crunchy",
 ]
 
-[[package]]
-name = "hashbrown"
-version = "0.12.3"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "8a9ee70c43aaf417c914396645a0fa852624801b24ebb7ae78fe8272889ac888"
-
 [[package]]
 name = "heck"
 version = "0.4.1"
@@ -465,16 +465,6 @@ dependencies = [
  "tiff",
 ]
 
-[[package]]
-name = "indexmap"
-version = "1.9.3"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "bd070e393353796e801d209ad339e89596eb4c8d430d18ede6a1cced8fafbd99"
-dependencies = [
- "autocfg",
- "hashbrown",
-]
-
 [[package]]
 name = "indicatif"
 version = "0.17.6"
@@ -673,6 +663,16 @@ dependencies = [
  "winapi",
 ]
 
+[[package]]
+name = "partitions"
+version = "0.2.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9249745fe5a60e2ebd69cc649af1baf28fa3f4606b24146490124405401510d8"
+dependencies = [
+ "bit-vec",
+ "rayon",
+]
+
 [[package]]
 name = "pathdiff"
 version = "0.2.1"
@@ -718,16 +718,6 @@ version = "1.4.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "31114a898e107c51bb1609ffaf55a0e011cf6a4d7f1170d0015a165082c0338b"
 
-[[package]]
-name = "priority-queue"
-version = "1.3.2"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "fff39edfcaec0d64e8d0da38564fad195d2d51b680940295fcc307366e101e61"
-dependencies = [
- "autocfg",
- "indexmap",
-]
-
 [[package]]
 name = "proc-macro2"
 version = "1.0.66"
-- 
cgit v1.2.3-70-g09d2