#sorting-order #sorting #trie #retrieval-tree

treerder

Trie ordering for type implementing Orderable

28 stable releases (3 major)

new 4.0.1 Mar 27, 2025
3.0.6 Jan 19, 2025
3.0.5 Dec 15, 2024
2.0.4 Nov 28, 2024
1.0.7 Oct 31, 2024

#224 in Algorithms

Download history 273/week @ 2024-11-29 412/week @ 2024-12-06 208/week @ 2024-12-13 8/week @ 2024-12-20 1/week @ 2025-01-03 106/week @ 2025-01-17 3/week @ 2025-01-24 2/week @ 2025-01-31 2/week @ 2025-02-07 5/week @ 2025-02-14

1,464 downloads per month

MIT license

36KB
729 lines

treerder

  • retrieval tree orderer / ordering based on chars sequence representation
  • orders any type implementing Orderable trait
  • implementation for &str and String oob
  • English alphabet A–Za–z oob
  • customizable alphabet

asymptotic computational complexity

  • tc | Ο(s) where s is sum of all chars iterated over
  • sc | Θ(q) where q is number of unique nodes, i.e. chars in respective branches

basic usage

let mut test_1 = ["zzz", "ZZZ", "aaa", "AAA"];

let mut test_2 = test_1.map(|x| String::from(x));

let mut proof = test_1.clone();
proof.sort();

let mut orderer = Treerder::new();
orderer.order(&mut test_1);
orderer.order(&mut test_2);

for z in test_1.iter().zip(test_2.iter()) {
    assert_eq!(*z.0, z.1.as_str());
}

assert_eq!(proof, test_1);

Orderable implementation with custom alphabet

use treerder::{Orderable, Treerder};

#[derive(Debug, PartialEq)]
struct LocalUsize(usize);

struct LocalUsizeCharIterator {
    s: String,
    c: usize,
}

impl Iterator for LocalUsizeCharIterator {
    type Item = char;

    fn next(&mut self) -> Option<char> {
        let c = self.c;

        let opt = self.s.chars().nth(c);

        if opt.is_some() {
            self.c = c + 1;
        }

        opt
    }
}

impl Orderable for LocalUsize {
    type Shadow = usize;

    fn chars(&self) -> impl Iterator<Item = char> {
        LocalUsizeCharIterator {
            s: self.0.to_string(),
            c: 0,
        }
    }

    fn shadow(&self) -> Self::Shadow {
        self.0
    }

    fn steady(s: Self::Shadow) -> Self {
        LocalUsize(s)
    }
}

fn ix(c: char) -> usize {
    c.to_digit(10).unwrap() as usize
}


let mut nums = [999, 333, 33, 3, 0, 100, 10, 1].map(|x| LocalUsize(x));

let mut orderer = Treerder::new_with(ix, 10);
orderer.order(&mut nums);

let proof = [0, 1, 10, 100, 3, 33, 333, 999].map(|x| LocalUsize(x));
assert_eq!(proof, nums);

No runtime deps

Features