dsa_rust/maw/
maw_01.rs

1/*!
2This is a sandbox crate for chapter 1 of Data Structures and Algorithm Analysis in Java by Mark Allen Weiss
3*/
4
5#![allow(dead_code)]
6
7pub fn recursion(n: i32) {
8    // Defines base case
9    if n >= 10 {
10        // Recursive call to self
11        recursion(n / 10);
12    }
13    // Prints the digit
14    println!("{}", n % 10)
15}
16
17/** My (iterative) version of a binary search implementation;
18 * Takes a sorted array and a key and returns either Some(index) or None */
19pub fn binary_search(a: &[i32], key: i32) -> Option<i32> {
20    use std::cmp::Ordering;
21
22    // Sets initial position of the search boundaries
23    let mut left = 0;
24    let mut right = a.len() - 1;
25
26    // Loops until the search boundaries overlap;
27    // If the loop doesn't find the key, the function
28    // returns None
29    while left <= right {
30        let mid = (left + right) / 2;
31        match a[mid].cmp(&key) {
32            Ordering::Equal => return Some(mid as i32),
33            Ordering::Greater => right = mid - 1,
34            Ordering::Less => left = mid + 1,
35        }
36        //if a[mid] == key {
37        //    return Some(mid as i32);
38        //} else if a[mid] > key {
39        //    right = mid - 1;
40        //} else {
41        //    left = mid + 1;
42        //}
43        //match key {
44        //    val if val == a[mid] => Some(mid as i32),
45        //    _ => Some(0)
46        //};
47        println!("Guess index: {}", &mid);
48    }
49    None
50}
51
52#[test]
53pub fn binary_search_test() {
54    // The target 73 exists at the 37th index
55    let target = 73;
56    let array: [i32; 39] = [
57        1, 4, 5, 6, 10, 12, 16, 21, 23, 24, 25, 27, 31, 32, 33, 35, 37, 39, 40, 41, 42, 43, 45, 47,
58        49, 50, 51, 52, 54, 56, 57, 60, 61, 67, 70, 71, 72, 73, 74,
59    ];
60    let result = binary_search(&array, target).unwrap_or_default();
61    assert_eq!(result, 37)
62}
63
64use std::collections::HashMap;
65
66fn 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
87fn 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]
118fn 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}
dsa_rust/maw/maw_01.rs

dsa_rust/maw/
maw_01.rs
