bittree 0.1.0

A crate for O(1) find functions in a special data structure called a bit tree.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

use bittree::BitTree;

#[derive(Clone, Default)]
struct AccountInfo {
    email: String
}

impl bittree::getbytes::GetBytes for AccountInfo {
    fn get_bytes(&self) -> &[u8] {
        self.email.get_bytes()
    }
}

struct AccountDatabase {
    inner: BitTree<usize, BitTree<String, AccountInfo>>
}

impl AccountDatabase {
    fn get_account(&mut self, username: &str, password: &str) -> Option<&mut AccountInfo> {
        let istr = username.chars().chain(" ".chars()).chain(password.chars()).collect::<String>();

        let lengthset = &mut self.inner[&istr.len()];
        if let Some(lengthset) = lengthset {
            lengthset[&istr].as_mut()
        } else {
            None
        }
    }
}

fn main() {
    // Initialize the database.
    let mut db = AccountDatabase {
        inner: BitTree::new()
    };

    // Add the accounts.
    for x in 0..100_000 {
        let username = "username".to_string() + &x.to_string();
        let password = "password".to_string() + &x.to_string();
        let istr = username.chars().chain(" ".chars()).chain(password.chars()).collect::<String>();

        if db.inner[&istr.len()].is_none() {
            db.inner.add(&istr.len(), Some(BitTree::new()));
        }

        db.inner[&istr.len()].as_mut().unwrap().add(
            &istr, Some(AccountInfo::default())
        );
    }
    
    // Measure performance of finding the account. Should be O(1) with a high constant factor.
    let now = std::time::Instant::now();
    assert!(db.get_account("username1000", "password1000").is_some());
    println!("Found an account in a database of one hundred thousand accounts in {} microseconds.", now.elapsed().as_micros());

    // Change the email of an account for testing purposes.
    db.get_account("username1000", "password1000").unwrap().email = "example@example.com".to_string();
    assert_eq!(db.get_account("username1000", "password1000").unwrap().email, String::from("example@example.com"));
    println!("Changed email of found user to: example@example.com");
}