dsa_rust/algorithms/
list_processing.rs

1pub mod recursion {
2    pub fn recursion(n: i32) {
3        // Defines base case
4        if n >= 10 {
5            // Recursive call to self
6            recursion(n / 10);
7        }
8        // Prints the digit
9        println!("{}", n % 10)
10    }
11}
12
13pub mod binary_search {
14    /** My (iterative) version of a binary search implementation;
15     * Takes a sorted array and a key and returns either Some(index) or None */
16    pub fn binary_search(a: &[i32], key: i32) -> Option<i32> {
17        use std::cmp::Ordering;
18
19        // Sets initial position of the search boundaries
20        let mut left = 0;
21        let mut right = a.len() - 1;
22
23        // Loops until the search boundaries overlap;
24        // If the loop doesn't find the key, the function
25        // returns None
26        while left <= right {
27            let mid = (left + right) / 2;
28            match a[mid].cmp(&key) {
29                Ordering::Equal => return Some(mid as i32),
30                Ordering::Greater => right = mid - 1,
31                Ordering::Less => left = mid + 1,
32            }
33            //if a[mid] == key {
34            //    return Some(mid as i32);
35            //} else if a[mid] > key {
36            //    right = mid - 1;
37            //} else {
38            //    left = mid + 1;
39            //}
40            //match key {
41            //    val if val == a[mid] => Some(mid as i32),
42            //    _ => Some(0)
43            //};
44            println!("Guess index: {}", &mid);
45        }
46        None
47    }
48
49    #[test]
50    pub fn binary_search_test() {
51        // The target 73 exists at the 37th index
52        let target = 73;
53        let array: [i32; 39] = [
54            1, 4, 5, 6, 10, 12, 16, 21, 23, 24, 25, 27, 31, 32, 33, 35, 37, 39, 40, 41, 42, 43, 45,
55            47, 49, 50, 51, 52, 54, 56, 57, 60, 61, 67, 70, 71, 72, 73, 74,
56        ];
57        let result = binary_search(&array, target).unwrap_or_default();
58        assert_eq!(result, 37)
59    }
60}
61
62#[allow(dead_code)]
63pub mod substring_search {
64    use std::collections::HashMap;
65
66    fn longest_unique_substring(s: &str) -> usize {
67        let mut map = HashMap::new(); // As HashMap<char, i32>
68        let mut left = 0;
69        let mut max_len = 0;
70
71        let chars: Vec<char> = s.chars().collect();
72
73        for right in 0..chars.len() {
74            *map.entry(chars[right]).or_insert(0) += 1;
75
76            while map[&chars[right]] > 1 {
77                *map.get_mut(&chars[left]).unwrap() -= 1;
78                left += 1;
79            }
80
81            max_len = max_len.max(right - left + 1);
82        }
83
84        max_len
85    }
86
87    fn longest_unique_substring_print(s: &str) -> usize {
88        let mut map = HashMap::new();
89        let mut left = 0;
90        let mut max_len = 0;
91        let mut best_range = (0, 0); // To store (start, end)
92
93        let chars: Vec<char> = s.chars().collect();
94
95        for right in 0..chars.len() {
96            *map.entry(chars[right]).or_insert(0) += 1;
97
98            while map[&chars[right]] > 1 {
99                *map.get_mut(&chars[left]).unwrap() -= 1;
100                left += 1;
101            }
102
103            let current_len = right - left + 1;
104            if current_len > max_len {
105                max_len = current_len;
106                best_range = (left, right);
107            }
108        }
109
110        // Print the substring using the captured indices
111        let result: String = chars[best_range.0..=best_range.1].iter().collect();
112        println!("Longest substring found: \"{result}\" (length {max_len})");
113
114        max_len
115    }
116
117    #[test]
118    fn longest_unique_substring_test() {
119        let s = "this is a llama test.";
120        assert_eq!(longest_unique_substring(s), 6);
121        longest_unique_substring_print(s);
122        //panic!()
123    }
124}
dsa_rust/algorithms/list_processing.rs

dsa_rust/algorithms/
list_processing.rs
