lowered cpu usage while browsing using binary search

5 files changed, 52 insertions, 36 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 3d4e69b..d2f3c59 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -22,11 +22,6 @@ dependencies = [
 ]
 
 [[package]]
-name = "alphanumeric-sort"
-version = "1.0.11"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-
-[[package]]
 name = "ansi_term"
 version = "0.11.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -595,7 +590,6 @@ dependencies = [
 name = "hunter"
 version = "1.3.5"
 dependencies = [
- "alphanumeric-sort 1.0.11 (registry+https://github.com/rust-lang/crates.io-index)",
  "async_value 0.2.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "base64 0.10.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "chrono 0.4.10 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -616,6 +610,7 @@ dependencies = [
  "lscolors 0.6.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "mime 0.3.16 (registry+https://github.com/rust-lang/crates.io-index)",
  "mime_guess 2.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "natord 1.0.9 (registry+https://github.com/rust-lang/crates.io-index)",
  "nix 0.17.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "notify 4.0.15 (registry+https://github.com/rust-lang/crates.io-index)",
  "osstrtools 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -862,6 +857,11 @@ version = "0.2.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "natord"
+version = "1.0.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "net2"
 version = "0.2.33"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1690,7 +1690,6 @@ dependencies = [
 "checksum adler32 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "5d2e7343e7fc9de883d1b0341e0b13970f764c14101234857d2ddafa1cb1cac2"
 "checksum aho-corasick 0.5.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ca972c2ea5f742bfce5687b9aef75506a764f61d37f8f649047846a9686ddb66"
 "checksum aho-corasick 0.7.6 (registry+https://github.com/rust-lang/crates.io-index)" = "58fb5e95d83b38284460a5fda7d6470aa0b8844d283a0b614b8535e880800d2d"
-"checksum alphanumeric-sort 1.0.11 (registry+https://github.com/rust-lang/crates.io-index)" = "f37ce94154d73f6961f87571a3ab7814e1608f373bd55a933e3e771b6dd59fc4"
 "checksum ansi_term 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ee49baf6cb617b853aa8d93bf420db2383fab46d314482ca2803b40d5fde979b"
 "checksum ansi_term 0.12.1 (registry+https://github.com/rust-lang/crates.io-index)" = "d52a9bb7ec0cf484c551830a7ce27bd20d67eac647e1befb56b0be4ee39a55d2"
 "checksum argon2rs 0.2.5 (registry+https://github.com/rust-lang/crates.io-index)" = "3f67b0b6a86dae6e67ff4ca2b6201396074996379fba2b92ff649126f37cb392"
@@ -1781,6 +1780,7 @@ dependencies = [
 "checksum mio-extras 2.0.6 (registry+https://github.com/rust-lang/crates.io-index)" = "52403fe290012ce777c4626790c8951324a2b9e3316b3143779c72b029742f19"
 "checksum miow 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "8c1f2f3b1cf331de6896aabf6e9d55dca90356cc9960cca7eaaf408a355ae919"
 "checksum muldiv 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "0419348c027fa7be448d2ae7ea0e4e04c2334c31dc4e74ab29f00a2a7ca69204"
+"checksum natord 1.0.9 (registry+https://github.com/rust-lang/crates.io-index)" = "308d96db8debc727c3fd9744aac51751243420e46edf401010908da7f8d5e57c"
 "checksum net2 0.2.33 (registry+https://github.com/rust-lang/crates.io-index)" = "42550d9fb7b6684a6d404d9fa7250c2eb2646df731d1c06afc06dcee9e1bcf88"
 "checksum nix 0.17.0 (registry+https://github.com/rust-lang/crates.io-index)" = "50e4785f2c3b7589a0d0c1dd60285e1188adac4006e8abd6dd578e1567027363"
 "checksum nodrop 0.1.14 (registry+https://github.com/rust-lang/crates.io-index)" = "72ef4a56884ca558e5ddb05a1d1e7e1bfd9a68d9ed024c21704cc98872dae1bb"
diff --git a/Cargo.toml b/Cargo.toml
index bf4a32f..426ab91 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -17,7 +17,7 @@ default-run = "hunter"
 termion = "1.5"
 unicode-width = "0.1.5"
 lazy_static = "1"
-alphanumeric-sort = "1.0.11"
+natord = "1.0.9"
 lscolors = { version = "0.6.0", features = [ "ansi_term" ]  }
 tree_magic_fork = "0.2.2"
 rayon = "1.3"
diff --git a/src/files.rs b/src/files.rs
index 87690eb..0cd71d4 100644
--- a/src/files.rs
+++ b/src/files.rs
@@ -22,7 +22,7 @@ use users::{get_current_username,
 use chrono::TimeZone;
 use failure::Error;
 use rayon::{ThreadPool, ThreadPoolBuilder};
-use alphanumeric_sort::compare_str;
+use natord::compare;
 use mime_guess;
 use rayon::prelude::*;
 use nix::{dir::*,
@@ -526,7 +526,7 @@ impl Files {
 
     pub fn get_file_mut(&mut self, index: usize) -> Option<&mut File> {
         // Need actual length of self.files for this
-        let hidden_in_between = self.hidden_in_between(index, self.files.len());
+        let hidden_in_between = self.files_in_between(index, self.files.len());
 
         self.files.get_mut(index + hidden_in_between)
     }
@@ -547,7 +547,7 @@ impl Files {
             .filter(move |&f| filter_fn(f))
     }
 
-    pub fn hidden_in_between(&self, pos: usize, n_before: usize) -> usize {
+    pub fn files_in_between(&self, pos: usize, n_before: usize) -> usize {
         let filter_fn = self.filter_fn();
 
         self.files[..pos].iter()
@@ -562,22 +562,23 @@ impl Files {
 
     pub fn iter_files_from(&self, from: &File, n_before: usize) -> impl Iterator<Item=&File> {
         let fpos = self.find_file(from).unwrap_or(0);
-        let hidden_in_between = self.hidden_in_between(fpos, n_before);
+
+        let files_in_between = self.files_in_between(fpos, n_before);
 
         let filter_fn = self.filter_fn();
 
-        self.files[fpos.saturating_sub(hidden_in_between)..]
+        self.files[fpos.saturating_sub(files_in_between)..]
             .iter()
             .filter(move |f| filter_fn(f))
     }
 
     pub fn iter_files_mut_from(&mut self, from: &File, n_before: usize) -> impl Iterator<Item=&mut File> {
         let fpos = self.find_file(from).unwrap_or(0);
-        let hidden_in_between = self.hidden_in_between(fpos, n_before);
+        let files_in_between = self.files_in_between(fpos, n_before);
 
         let filter_fn = self.filter_fn();
 
-        self.files[fpos.saturating_sub(hidden_in_between)..]
+        self.files[fpos.saturating_sub(files_in_between)..]
             .iter_mut()
             .filter(move |f| filter_fn(f))
     }
@@ -628,7 +629,7 @@ impl Files {
                 false => (a, b),
             };
 
-            compare_str(&a.name, &b.name)
+            compare(&a.name, &b.name)
         };
 
         let reverse = self.reverse;
@@ -643,7 +644,7 @@ impl Files {
                     let a_meta = a_meta.as_ref().unwrap();
                     let b_meta = b_meta.as_ref().unwrap();
                     match a_meta.size() == b_meta.size() {
-                        true => compare_str(&b.name, &a.name),
+                        true => compare(&b.name, &a.name),
                         false => b_meta.size().cmp(&a_meta.size())
                     }
                 }
@@ -663,7 +664,7 @@ impl Files {
                     let a_meta = a_meta.as_ref().unwrap();
                     let b_meta = b_meta.as_ref().unwrap();
                     match a_meta.mtime() == b_meta.mtime() {
-                        true => compare_str(&b.name, &a.name),
+                        true => compare(&b.name, &a.name),
                         false => b_meta.mtime().cmp(&a_meta.mtime())
                     }
                 }
@@ -801,9 +802,13 @@ impl Files {
 
     pub fn find_file(&self, file: &File) -> Option<usize> {
         let comp = self.sorter();
-        self.files
+        let pos = self.files
             .binary_search_by(|probe| comp(probe, file))
-            .ok()
+            .ok()?;
+
+        debug_assert_eq!(file.path, self.files[pos].path);
+
+        Some(pos)
     }
 
     pub fn find_file_with_name(&self, name: &str) -> Option<&File> {
diff --git a/src/listview.rs b/src/listview.rs
index 7cddfbf..3a40289 100644
--- a/src/listview.rs
+++ b/src/listview.rs
@@ -52,7 +52,7 @@ impl Acting for ListView<Files> {
         }
 
         if pos != self.get_selection() {
-            self.update_selected_file();
+            self.update_selected_file(pos);
         }
 
         Ok(())
@@ -82,7 +82,7 @@ impl Acting for ListView<Files> {
         }
 
         if pos != self.get_selection() {
-            self.update_selected_file();
+            self.update_selected_file(pos);
         }
 
         Ok(())
@@ -357,15 +357,26 @@ impl ListView<Files>
         FileListBuilder::new(core, source)
     }
 
-    pub fn update_selected_file(&mut self) {
-        let pos = self.selection;
+    pub fn update_selected_file(&mut self, oldpos: usize) {
+        let newpos = self.get_selection();
+        let skip =
+            match newpos > oldpos {
+                true => newpos - oldpos,
+                false => 0
+            };
+
+        let seek_back =
+            match newpos < oldpos {
+                true => oldpos - newpos,
+                false => 0
+            };
 
         let file = self.content
-            .iter_files()
-            .nth(pos)
-            .map(|f| f.clone());
+                       .iter_files_from(self.selected_file(), seek_back)
+                       .skip(skip)
+                       .nth(0);
 
-        self.current_item = file;
+        self.current_item = file.cloned();
     }
 
     pub fn selected_file(&self) -> &File {
@@ -376,11 +387,11 @@ impl ListView<Files>
     }
 
     pub fn selected_file_mut(&mut self) -> &mut File {
-        let selection = self.selection;
+        let selected_file = self.selected_file().clone();
 
         let file = self.content
-            .iter_files_mut()
-            .nth(selection)
+            .iter_files_mut_from(&selected_file, 0)
+            .nth(0)
             .map(|f| f as *mut File);
 
 
@@ -838,12 +849,12 @@ impl ListView<Files>
     fn render(&self) -> Vec<String> {
         let render_fn = self.render_line_fn();
         let ysize = self.get_coordinates().unwrap().ysize_u();
+        let files_above_selection = self.get_selection() - self.offset;
+        let selected_file = self.selected_file();
+
         self.content
-            .iter_files()
-            .skip(self.offset)
+            .iter_files_from(selected_file, files_above_selection)
             .take(ysize+1)
-            // .collect::<Vec<_>>()
-            // .into_par_iter()
             .map(|file| render_fn(file))
             .collect()
     }
diff --git a/src/main.rs b/src/main.rs
index 1823428..72f1d3b 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -9,7 +9,7 @@ extern crate unicode_width;
 extern crate lazy_static;
 extern crate failure;
 extern crate failure_derive;
-extern crate alphanumeric_sort;
+extern crate natord;
 extern crate dirs_2;
 extern crate lscolors;
 extern crate users;