dsa_rust/tgg/
tgg_04.rs

1#![allow(dead_code)]
2
3/*!
4This is a sandbox crate for Data Structures and Algorithm Analysis in Java by
5Tamassia, Goodrich, and Goldwasser
6
7// Ch 4 - Asymptotic Analysis
8/////////////////////////////
9*/
10
11// My first stab comparing the elements of two vectors for uniqueness
12/** Compares two vectors for unique elements in O(n * m) time */
13pub fn unique_0(a: &[i32], b: &[i32]) -> bool {
14    for j in a.iter() {
15        for k in b.iter() {
16            if *k == *j {
17                return false;
18            }
19        }
20    }
21    true
22}
23
24// My first ham-fisted attempt at checking a single array for uniqueness
25// Generally viewed as overly complicated an inefficient
26/** Checks a single array for uniqueness in O(n^2) time */
27pub fn unique_1(a: &[i32]) -> bool {
28    for (j, val) in a.iter().enumerate() {
29        let start = j + 1;
30        if start <= a.len() {
31            for k in &a[start..] {
32                if val == k {
33                    println!("{val} appears more than once");
34                    return false;
35                }
36            }
37        }
38    }
39    true
40}
41
42// Cheating to get a simpler, more elegant function of tgg::unique_1()
43pub fn unique_2(a: &[i32]) -> bool {
44    for j in 0..a.len() {
45        for k in j + 1..a.len() {
46            if a[j] == a[k] {
47                println!("{} appears more than once", a[j]);
48                return false;
49            }
50        }
51    }
52    true
53}
54
55// A reimplementation with a simple tweak, technically incorrect as this can
56// result in OOB panics
57/** A reimplementation of tgg::unique_2() that checks an array for uniqueness in
58 * O(n * log(n)) time */
59pub fn unique_3(a: &[i32]) -> bool {
60    a.to_owned().sort();
61    for j in 0..a.len() {
62        if (j + 1) < a.len() && a[j] == a[j + 1] {
63            println!("Found one! {}", a[j]);
64            return false;
65        }
66    }
67    true
68}
69
70// Another check (cheat) nets an even more elegant solution
71pub fn unique_4(a: &[i32]) -> bool {
72    a.to_owned().sort();
73    for j in 0..a.len() - 1 {
74        if a[j] == a[j + 1] {
75            println!("Found a duplicate: {}", a[j]);
76            return false;
77        }
78    }
79    true
80}
81
82#[test]
83fn uniqueness() {}
84
85/** Calculates a prefix average of an array in O(n) time */
86pub fn prefix_average_1(avg: &[f32]) -> Vec<f32> {
87    let mut total: f32 = 0.0;
88    let mut rtn = Vec::new();
89    //for i in 0..avg.len() {
90    //    total += avg[i];
91    //    avg[i] = total / (i as f32 + 1.0);
92    //}
93    for (i, val) in avg.iter().enumerate() {
94        total += *val;
95        rtn.push(total / (i as f32 + 1.0));
96    }
97    rtn
98}
99#[test]
100fn prefix_avg() {
101    let v = &[1.0, 2.0, 3.0, 4.0];
102    let avg = &[1.0, 1.5, 2.0, 2.5];
103    assert_eq!(prefix_average_1(v), avg);
104}
dsa_rust/tgg/tgg_04.rs

dsa_rust/tgg/
tgg_04.rs
