stalin_binary_search/
vec.rs

1use super::StalinFind;
2
3use std::cmp;
4
5impl<T: PartialOrd> StalinFind<T> for Vec<T> {
6  #[inline]
7  fn len(&self) -> usize {
8    self.len()
9  }
10
11  #[inline]
12  fn is_empty(&self) -> bool {
13    self.is_empty()
14  }
15
16  fn stalin(&mut self, i: T, l: usize, r: usize) -> Option<usize>
17    where T: cmp::PartialEq + cmp::PartialOrd {
18    let m = (l + r) / 2;
19    if self[m] == i {
20      Some(m)
21    } else {
22      self.remove(m);
23      if m == 0 || l > r {
24        if self.is_empty() {
25          None
26        } else {
27          self.stalin(i, 0, self.len() - 1)
28        }
29      } else if self[m - 1] < i {
30        self.stalin(i, m, r - 1)
31      } else {
32        self.stalin(i, l, m - 1)
33      }
34    }
35  }
36}
37
38#[cfg(test)]
39mod tests {
40  use super::*;
41  use rand::Rng;
42
43  #[test]
44  fn randomised_test() {
45    // generate a random vector of length 0-n
46    let n = 100; // n was supposed to be a paramer of the function but whatever
47    let mut rng = rand::thread_rng();
48    let sought = rng.gen_range(0..n);
49    let amount = rng.gen_range(0..n);
50    let range = rand::distributions::uniform::Uniform::new(0, n);
51    let mut vector: Vec<u64> = (0..amount).map(|_| rng.sample(&range)).collect();
52
53    // check if the value is within the array
54    let i = vector.iter().position(|x| x == &sought);
55    if i.is_some() {
56      if let Some(find) = vector.stalin_find(sought) {
57        assert_eq!(vector[find], sought)
58      }
59    } else {
60      let find = vector.stalin_find(sought);
61      assert_eq!(find, None)
62    }
63  }
64
65  #[test]
66  fn find_on_sorted() {
67    let mut sorted = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
68    let find = sorted.stalin_find(3);
69    assert!(find.is_some());
70    assert_eq!(
71      find,
72      Some(1),
73    );
74    assert_eq!(
75      sorted,
76      vec![1, 3, 4, 6, 7, 8, 9],
77    );
78    if let Some(find_3) = find {
79      assert_eq!(
80        3, sorted[find_3]
81      );
82    }
83  }
84
85  #[test]
86  fn find_on_unsorted() {
87    let mut unsorted = vec![33, 55, 3, 4, 7657, 6, 7, 8];
88    assert_eq!(
89      unsorted.stalin_find(3),
90      Some(0),
91    );
92    assert_eq!(
93      unsorted,
94      vec![3, 7657, 7, 8],
95    );
96    if let Some(find_7) = unsorted.stalin_find(7) {
97      assert_eq!(
98        7, unsorted[find_7]
99      );
100    }
101  }
102
103  #[test]
104  fn find_fail() {
105    let mut unsorted = vec![33, 55, 3, 4, 7657, 6, 7, 8];
106    assert_eq!(
107      unsorted.stalin_find(77),
108      None,
109    );
110    assert_eq!(
111      unsorted,
112      vec![],
113    );
114  }
115
116  #[test]
117  fn find_not_fail() {
118    let mut unsorted = vec![33, 55, 3, 4, 7657, 6, 7, 8, 2];
119    assert_eq!(
120      unsorted.stalin_find(2),
121      Some(0),
122    );
123    assert_eq!(
124      unsorted,
125      vec![2],
126    );
127  }
128
129  #[test]
130  fn find_not_fingon() {
131    let mut unsorted = vec![12, 11, 4, 5, 7, 8, 2];
132    assert_eq!(
133      unsorted.stalin_find(9),
134      None,
135    );
136    assert_eq!(
137      unsorted,
138      vec![],
139    );
140  }
141
142  #[test]
143  fn find_not_fingon2() {
144    let mut unsorted = vec![33, 55, 3, 4, 7657, 6, 33, 7, 8, 2];
145    assert_eq!(
146      unsorted.stalin_find(9),
147      None,
148    );
149    assert_eq!(
150      unsorted,
151      vec![],
152    );
153  }
154}
stalin_binary_search/vec.rs

stalin_binary_search/
vec.rs
