Start writing an implementation of algorithm L
- ID
05e93a8- date
2025-01-09 22:18:36+00:00- author
Alex Chan <alex@alexwlchan.net>- message
Start writing an implementation of algorithm L- changed files
5 files, 346 additions
Changed files
.gitignore (0) → .gitignore (8)
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..ea8c4bf
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+/target
Cargo.lock (0) → Cargo.lock (6532)
diff --git a/Cargo.lock b/Cargo.lock
new file mode 100644
index 0000000..bd5be36
--- /dev/null
+++ b/Cargo.lock
@@ -0,0 +1,237 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "anstream"
+version = "0.6.18"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8acc5369981196006228e28809f761875c0327210a891e941f4c683b3a99529b"
+dependencies = [
+ "anstyle",
+ "anstyle-parse",
+ "anstyle-query",
+ "anstyle-wincon",
+ "colorchoice",
+ "is_terminal_polyfill",
+ "utf8parse",
+]
+
+[[package]]
+name = "anstyle"
+version = "1.0.10"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "55cc3b69f167a1ef2e161439aa98aed94e6028e5f9a59be9a6ffb47aef1651f9"
+
+[[package]]
+name = "anstyle-parse"
+version = "0.2.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3b2d16507662817a6a20a9ea92df6652ee4f94f914589377d69f3b21bc5798a9"
+dependencies = [
+ "utf8parse",
+]
+
+[[package]]
+name = "anstyle-query"
+version = "1.1.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "79947af37f4177cfead1110013d678905c37501914fba0efea834c3fe9a8d60c"
+dependencies = [
+ "windows-sys",
+]
+
+[[package]]
+name = "anstyle-wincon"
+version = "3.0.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2109dbce0e72be3ec00bed26e6a7479ca384ad226efdd66db8fa2e3a38c83125"
+dependencies = [
+ "anstyle",
+ "windows-sys",
+]
+
+[[package]]
+name = "clap"
+version = "4.5.26"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a8eb5e908ef3a6efbe1ed62520fb7287959888c88485abe072543190ecc66783"
+dependencies = [
+ "clap_builder",
+ "clap_derive",
+]
+
+[[package]]
+name = "clap_builder"
+version = "4.5.26"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "96b01801b5fc6a0a232407abc821660c9c6d25a1cafc0d4f85f29fb8d9afc121"
+dependencies = [
+ "anstream",
+ "anstyle",
+ "clap_lex",
+ "strsim",
+]
+
+[[package]]
+name = "clap_derive"
+version = "4.5.24"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "54b755194d6389280185988721fffba69495eed5ee9feeee9a599b53db80318c"
+dependencies = [
+ "heck",
+ "proc-macro2",
+ "quote",
+ "syn",
+]
+
+[[package]]
+name = "clap_lex"
+version = "0.7.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f46ad14479a25103f283c0f10005961cf086d8dc42205bb44c46ac563475dca6"
+
+[[package]]
+name = "colorchoice"
+version = "1.0.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5b63caa9aa9397e2d9480a9b13673856c78d8ac123288526c37d7839f2a86990"
+
+[[package]]
+name = "heck"
+version = "0.5.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2304e00983f87ffb38b55b444b5e3b60a884b5d30c0fca7d82fe33449bbe55ea"
+
+[[package]]
+name = "is_terminal_polyfill"
+version = "1.70.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7943c866cc5cd64cbc25b2e01621d07fa8eb2a1a23160ee81ce38704e97b8ecf"
+
+[[package]]
+name = "proc-macro2"
+version = "1.0.92"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "37d3544b3f2748c54e147655edb5025752e2303145b5aefb3c3ea2c78b973bb0"
+dependencies = [
+ "unicode-ident",
+]
+
+[[package]]
+name = "quote"
+version = "1.0.38"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0e4dccaaaf89514f546c693ddc140f729f958c247918a13380cccc6078391acc"
+dependencies = [
+ "proc-macro2",
+]
+
+[[package]]
+name = "randline"
+version = "0.1.0"
+dependencies = [
+ "clap",
+]
+
+[[package]]
+name = "strsim"
+version = "0.11.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7da8b5736845d9f2fcb837ea5d9e2628564b3b043a70948a3f0b778838c5fb4f"
+
+[[package]]
+name = "syn"
+version = "2.0.95"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "46f71c0377baf4ef1cc3e3402ded576dccc315800fbc62dfc7fe04b009773b4a"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "unicode-ident",
+]
+
+[[package]]
+name = "unicode-ident"
+version = "1.0.14"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "adb9e6ca4f869e1180728b7950e35922a7fc6397f7b641499e8f3ef06e50dc83"
+
+[[package]]
+name = "utf8parse"
+version = "0.2.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "06abde3611657adf66d383f00b093d7faecc7fa57071cce2578660c9f1010821"
+
+[[package]]
+name = "windows-sys"
+version = "0.59.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1e38bc4d79ed67fd075bcc251a1c39b32a1776bbe92e5bef1f0bf1f8c531853b"
+dependencies = [
+ "windows-targets",
+]
+
+[[package]]
+name = "windows-targets"
+version = "0.52.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9b724f72796e036ab90c1021d4780d4d3d648aca59e491e6b98e725b84e99973"
+dependencies = [
+ "windows_aarch64_gnullvm",
+ "windows_aarch64_msvc",
+ "windows_i686_gnu",
+ "windows_i686_gnullvm",
+ "windows_i686_msvc",
+ "windows_x86_64_gnu",
+ "windows_x86_64_gnullvm",
+ "windows_x86_64_msvc",
+]
+
+[[package]]
+name = "windows_aarch64_gnullvm"
+version = "0.52.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "32a4622180e7a0ec044bb555404c800bc9fd9ec262ec147edd5989ccd0c02cd3"
+
+[[package]]
+name = "windows_aarch64_msvc"
+version = "0.52.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "09ec2a7bb152e2252b53fa7803150007879548bc709c039df7627cabbd05d469"
+
+[[package]]
+name = "windows_i686_gnu"
+version = "0.52.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8e9b5ad5ab802e97eb8e295ac6720e509ee4c243f69d781394014ebfe8bbfa0b"
+
+[[package]]
+name = "windows_i686_gnullvm"
+version = "0.52.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0eee52d38c090b3caa76c563b86c3a4bd71ef1a819287c19d586d7334ae8ed66"
+
+[[package]]
+name = "windows_i686_msvc"
+version = "0.52.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "240948bc05c5e7c6dabba28bf89d89ffce3e303022809e73deaefe4f6ec56c66"
+
+[[package]]
+name = "windows_x86_64_gnu"
+version = "0.52.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "147a5c80aabfbf0c7d901cb5895d1de30ef2907eb21fbbab29ca94c5b08b1a78"
+
+[[package]]
+name = "windows_x86_64_gnullvm"
+version = "0.52.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "24d5b23dc417412679681396f2b49f3de8c1473deb516bd34410872eff51ed0d"
+
+[[package]]
+name = "windows_x86_64_msvc"
+version = "0.52.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "589f6da84c646204747d1270a2a5661ea66ed1cced2631d546fdfb155959f9ec"
Cargo.toml (0) → Cargo.toml (132)
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..bfa0d23
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,7 @@
+[package]
+name = "randline"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+clap = { version = "4.5.26", features = ["derive"] }
src/main.rs (0) → src/main.rs (918)
diff --git a/src/main.rs b/src/main.rs
new file mode 100644
index 0000000..1051b3f
--- /dev/null
+++ b/src/main.rs
@@ -0,0 +1,40 @@
+#![deny(warnings)]
+
+use std::iter::Iterator;
+
+mod sampling;
+
+fn main() {
+ // Read the user's command line arguments (if any)
+ //
+ // 0 arguments = get a single random line
+ // 1 argument N = get that number of lines
+ // >1 arguments = error
+ //
+ let args: Vec<_> = std::env::args().collect();
+
+ let n = match args.len() {
+ 1 => 0,
+ 2 => match args[1].parse::<usize>() {
+ Ok(parsed_n) => parsed_n,
+ Err(_) => {
+ eprintln!("Usage: randline [N]");
+ std::process::exit(1)
+ }
+ },
+ _ => {
+ eprintln!("Usage: randline [N]");
+ std::process::exit(1)
+ }
+ };
+
+ // Read the first N lines from stdout
+ // let stdin = io::stdin();
+
+ let a = [1, 2, 3];
+ let iter = a.iter();
+
+ println!("{:?}", sampling::reservoir_sample(iter, n));
+
+ println!("n = {:?}", n);
+}
src/sampling.rs (0) → src/sampling.rs (1634)
diff --git a/src/sampling.rs b/src/sampling.rs
new file mode 100644
index 0000000..4433c05
--- /dev/null
+++ b/src/sampling.rs
@@ -0,0 +1,61 @@
+pub fn reservoir_sample<T: std::fmt::Debug>(
+ mut items: impl Iterator<Item = T>,
+ n: usize
+) -> Vec<T> {
+
+ // Create an empty reservoir.
+ let mut reservoir: Vec<T> = Vec::with_capacity(n);
+
+ // Fill the reservoir with the first n items. If there are less
+ // than n items, we can exit immediately.
+ for _ in 1..=n {
+ match items.next() {
+ Some(this_item) => reservoir.push(this_item),
+ None => return reservoir,
+ };
+ }
+
+ vec![]
+}
+
+#[cfg(test)]
+mod reservoir_sample_tests {
+ use crate::sampling::reservoir_sample;
+
+ // If there are no items, then the sample is empty.
+ #[test]
+ fn it_returns_an_empty_sample_for_an_empty_input() {
+ let items: Vec<usize> = vec![];
+ let sample = reservoir_sample(items.iter(), 5);
+
+ assert_eq!(sample.len(), 0);
+ }
+
+ // If there are less items than the sample size, then the sample is
+ // the complete set.
+ #[test]
+ fn it_returns_complete_sample_if_less_items_than_sample_size() {
+ let items = vec!["a", "b", "c"];
+ let sample = reservoir_sample(items.iter(), 5);
+
+ assert_eq!(sample.len(), 3);
+ assert_eq!(*sample[0], "a");
+ assert_eq!(*sample[1], "b");
+ assert_eq!(*sample[2], "c");
+ }
+
+ // If there's an equal number of items to the sample size, then the
+ // sample is the complete set.
+ #[test]
+ fn it_returns_complete_sample_if_item_count_equal_to_sample_size() {
+ let items = vec!["a", "b", "c"];
+ let sample = reservoir_sample(items.iter(), 3);
+
+ println!("AWLC = {:?}", sample);
+
+ assert_eq!(sample.len(), 3);
+ assert_eq!(*sample[0], "a");
+ assert_eq!(*sample[1], "b");
+ assert_eq!(*sample[2], "c");
+ }
+}
\ No newline at end of file