Replace unnecessary owned-type to borrowed-type (TheAlgorithms#525)

Watagon · web-flow · commit fea7725a73e7 · 2023-09-24T09:47:27.000+03:00
diff --git a/src/data_structures/lazy_segment_tree.rs b/src/data_structures/lazy_segment_tree.rs
@@ -114,7 +114,7 @@ impl<T: Debug + Default + Ord + Copy + Display + AddAssign + Add<Output = T>> La
             return;
         }
 
-        let lazy = self.lazy[idx].unwrap_or(T::default());
+        let lazy = self.lazy[idx].unwrap_or_default();
         self.lazy[idx] = None;
 
         let mid = (element_range.start + element_range.end) / 2;
diff --git a/src/data_structures/rb_tree.rs b/src/data_structures/rb_tree.rs
@@ -616,7 +616,7 @@ mod tests {
     #[test]
     fn find() {
         let mut tree = RBTree::<usize, char>::new();
-        for (k, v) in String::from("hello, world!").chars().enumerate() {
+        for (k, v) in "hello, world!".chars().enumerate() {
             tree.insert(k, v);
         }
         assert_eq!(*tree.find(&3).unwrap_or(&'*'), 'l');
@@ -628,7 +628,7 @@ mod tests {
     #[test]
     fn insert() {
         let mut tree = RBTree::<usize, char>::new();
-        for (k, v) in String::from("hello, world!").chars().enumerate() {
+        for (k, v) in "hello, world!".chars().enumerate() {
             tree.insert(k, v);
         }
         let s: String = tree.iter().map(|x| x.value).collect();
@@ -638,7 +638,7 @@ mod tests {
     #[test]
     fn delete() {
         let mut tree = RBTree::<usize, char>::new();
-        for (k, v) in String::from("hello, world!").chars().enumerate() {
+        for (k, v) in "hello, world!".chars().enumerate() {
             tree.insert(k, v);
         }
         tree.delete(&1);
diff --git a/src/data_structures/trie.rs b/src/data_structures/trie.rs
@@ -33,7 +33,7 @@ where
     {
         let mut node = &mut self.root;
         for c in key.into_iter() {
-            node = node.children.entry(c).or_insert_with(Node::default);
+            node = node.children.entry(c).or_default();
         }
         node.value = Some(value);
     }
diff --git a/src/dynamic_programming/is_subsequence.rs b/src/dynamic_programming/is_subsequence.rs
@@ -3,7 +3,7 @@
 // by deleting some (can be none) of the characters without disturbing the relative
 // positions of the remaining characters.
 // (i.e., "ace" is a subsequence of "abcde" while "aec" is not).
-pub fn is_subsequence(str1: String, str2: String) -> bool {
+pub fn is_subsequence(str1: &str, str2: &str) -> bool {
     let mut it1 = 0;
     let mut it2 = 0;
 
@@ -27,7 +27,7 @@ mod tests {
 
     #[test]
     fn test() {
-        assert!(is_subsequence(String::from("abc"), String::from("ahbgdc")));
-        assert!(!is_subsequence(String::from("axc"), String::from("ahbgdc")));
+        assert!(is_subsequence("abc", "ahbgdc"));
+        assert!(!is_subsequence("axc", "ahbgdc"));
     }
 }
diff --git a/src/dynamic_programming/longest_common_substring.rs b/src/dynamic_programming/longest_common_substring.rs
@@ -1,6 +1,6 @@
 // Longest common substring via Dynamic Programming
 // longest_common_substring(a, b) returns the length of longest common substring between the strings a and b.
-pub fn longest_common_substring(text1: String, text2: String) -> i32 {
+pub fn longest_common_substring(text1: &str, text2: &str) -> i32 {
     let m = text1.len();
     let n = text2.len();
 
@@ -32,74 +32,44 @@ mod tests {
 
     #[test]
     fn test1() {
-        assert_eq!(
-            longest_common_substring(String::from(""), String::from("")),
-            0
-        );
+        assert_eq!(longest_common_substring("", ""), 0);
     }
     #[test]
     fn test2() {
-        assert_eq!(
-            longest_common_substring(String::from("a"), String::from("")),
-            0
-        );
+        assert_eq!(longest_common_substring("a", ""), 0);
     }
     #[test]
     fn test3() {
-        assert_eq!(
-            longest_common_substring(String::from(""), String::from("a")),
-            0
-        );
+        assert_eq!(longest_common_substring("", "a"), 0);
     }
     #[test]
     fn test4() {
-        assert_eq!(
-            longest_common_substring(String::from("a"), String::from("a")),
-            1
-        );
+        assert_eq!(longest_common_substring("a", "a"), 1);
     }
     #[test]
     fn test5() {
-        assert_eq!(
-            longest_common_substring(String::from("abcdef"), String::from("bcd")),
-            3
-        );
+        assert_eq!(longest_common_substring("abcdef", "bcd"), 3);
     }
     #[test]
     fn test6() {
-        assert_eq!(
-            longest_common_substring(String::from("abcdef"), String::from("xabded")),
-            2
-        );
+        assert_eq!(longest_common_substring("abcdef", "xabded"), 2);
     }
     #[test]
     fn test7() {
-        assert_eq!(
-            longest_common_substring(String::from("GeeksforGeeks"), String::from("GeeksQuiz")),
-            5
-        );
+        assert_eq!(longest_common_substring("GeeksforGeeks", "GeeksQuiz"), 5);
     }
     #[test]
     fn test8() {
-        assert_eq!(
-            longest_common_substring(String::from("abcdxyz"), String::from("xyzabcd")),
-            4
-        );
+        assert_eq!(longest_common_substring("abcdxyz", "xyzabcd"), 4);
     }
     #[test]
     fn test9() {
-        assert_eq!(
-            longest_common_substring(String::from("zxabcdezy"), String::from("yzabcdezx")),
-            6
-        );
+        assert_eq!(longest_common_substring("zxabcdezy", "yzabcdezx"), 6);
     }
     #[test]
     fn test10() {
         assert_eq!(
-            longest_common_substring(
-                String::from("OldSite:GeeksforGeeks.org"),
-                String::from("NewSite:GeeksQuiz.com")
-            ),
+            longest_common_substring("OldSite:GeeksforGeeks.org", "NewSite:GeeksQuiz.com"),
             10
         );
     }
diff --git a/src/general/huffman_encoding.rs b/src/general/huffman_encoding.rs
@@ -28,7 +28,7 @@ impl<T> PartialEq for HuffmanNode<T> {
 
 impl<T> PartialOrd for HuffmanNode<T> {
     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
-        Some(self.frequency.cmp(&other.frequency).reverse())
+        Some(self.cmp(other))
     }
 }
 
diff --git a/src/graph/astar.rs b/src/graph/astar.rs
@@ -18,7 +18,7 @@ impl<V: Ord + Copy, E: Ord + Copy> PartialOrd for Candidate<V, E> {
     fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
         // Note the inverted order; we want nodes with lesser weight to have
         // higher priority
-        other.estimated_weight.partial_cmp(&self.estimated_weight)
+        Some(self.cmp(other))
     }
 }
 
@@ -111,8 +111,8 @@ mod tests {
     }
 
     fn add_edge<V: Ord + Copy, E: Ord>(graph: &mut Graph<V, E>, v1: V, v2: V, c: E) {
-        graph.entry(v1).or_insert_with(BTreeMap::new).insert(v2, c);
-        graph.entry(v2).or_insert_with(BTreeMap::new);
+        graph.entry(v1).or_default().insert(v2, c);
+        graph.entry(v2).or_default();
     }
 
     #[test]
diff --git a/src/graph/bellman_ford.rs b/src/graph/bellman_ford.rs
@@ -90,8 +90,8 @@ mod tests {
     use std::collections::BTreeMap;
 
     fn add_edge<V: Ord + Copy, E: Ord>(graph: &mut Graph<V, E>, v1: V, v2: V, c: E) {
-        graph.entry(v1).or_insert_with(BTreeMap::new).insert(v2, c);
-        graph.entry(v2).or_insert_with(BTreeMap::new);
+        graph.entry(v1).or_default().insert(v2, c);
+        graph.entry(v2).or_default();
     }
 
     #[test]
diff --git a/src/graph/dijkstra.rs b/src/graph/dijkstra.rs
@@ -56,8 +56,8 @@ mod tests {
     use std::collections::BTreeMap;
 
     fn add_edge<V: Ord + Copy, E: Ord>(graph: &mut Graph<V, E>, v1: V, v2: V, c: E) {
-        graph.entry(v1).or_insert_with(BTreeMap::new).insert(v2, c);
-        graph.entry(v2).or_insert_with(BTreeMap::new);
+        graph.entry(v1).or_default().insert(v2, c);
+        graph.entry(v2).or_default();
     }
 
     #[test]
diff --git a/src/graph/dinic_maxflow.rs b/src/graph/dinic_maxflow.rs
@@ -194,8 +194,8 @@ mod tests {
         let max_flow = flow.find_maxflow(i32::MAX);
         assert_eq!(max_flow, 23);
 
-        let mut sm_out = vec![0; 7];
-        let mut sm_in = vec![0; 7];
+        let mut sm_out = [0; 7];
+        let mut sm_in = [0; 7];
 
         let flow_edges = flow.get_flow_edges(i32::MAX);
         for e in flow_edges {
diff --git a/src/graph/floyd_warshall.rs b/src/graph/floyd_warshall.rs
@@ -71,7 +71,7 @@ mod tests {
     use std::collections::BTreeMap;
 
     fn add_edge<V: Ord + Copy, E: Ord + Copy>(graph: &mut Graph<V, E>, v1: V, v2: V, c: E) {
-        graph.entry(v1).or_insert_with(BTreeMap::new).insert(v2, c);
+        graph.entry(v1).or_default().insert(v2, c);
     }
 
     fn bi_add_edge<V: Ord + Copy, E: Ord + Copy>(graph: &mut Graph<V, E>, v1: V, v2: V, c: E) {
diff --git a/src/graph/graph_enumeration.rs b/src/graph/graph_enumeration.rs
@@ -27,11 +27,8 @@ pub fn enumerate_graph<V: Ord + Clone>(adj: &Graph<V>) -> Vec<Vec<usize>> {
 mod tests {
     use super::*;
     fn add_edge<V: Ord + Clone>(graph: &mut Graph<V>, a: V, b: V) {
-        graph
-            .entry(a.clone())
-            .or_insert_with(Vec::new)
-            .push(b.clone());
-        graph.entry(b).or_insert_with(Vec::new).push(a);
+        graph.entry(a.clone()).or_default().push(b.clone());
+        graph.entry(b).or_default().push(a);
     }
 
     #[test]
diff --git a/src/graph/prim.rs b/src/graph/prim.rs
@@ -5,8 +5,8 @@ use std::ops::Add;
 type Graph<V, E> = BTreeMap<V, BTreeMap<V, E>>;
 
 fn add_edge<V: Ord + Copy, E: Ord + Add + Copy>(graph: &mut Graph<V, E>, v1: V, v2: V, c: E) {
-    graph.entry(v1).or_insert_with(BTreeMap::new).insert(v2, c);
-    graph.entry(v2).or_insert_with(BTreeMap::new).insert(v1, c);
+    graph.entry(v1).or_default().insert(v2, c);
+    graph.entry(v2).or_default().insert(v1, c);
 }
 
 // selects a start and run the algorithm from it
diff --git a/src/graph/prufer_code.rs b/src/graph/prufer_code.rs
@@ -6,8 +6,7 @@ pub fn prufer_encode<V: Ord + Copy>(tree: &Graph<V>) -> Vec<V> {
     if tree.len() <= 2 {
         return vec![];
     }
-    let mut result: Vec<V> = Vec::new();
-    result.reserve(tree.len() - 2);
+    let mut result: Vec<V> = Vec::with_capacity(tree.len() - 2);
     let mut queue = BinaryHeap::new();
     let mut in_tree = BTreeSet::new();
     let mut degree = BTreeMap::new();
diff --git a/src/graph/topological_sort.rs b/src/graph/topological_sort.rs
@@ -25,7 +25,7 @@ pub fn topological_sort<Node: Hash + Eq + Copy>(
         incoming_edges_count.entry(*source).or_insert(0); // if we haven't seen this node yet, mark it as having 0 incoming nodes
         edges_by_source // add destination to the list of outgoing edges from source
             .entry(*source)
-            .or_insert_with(Vec::default)
+            .or_default()
             .push(*destination);
         // then make destination have one more incoming edge
         *incoming_edges_count.entry(*destination).or_insert(0) += 1;
diff --git a/src/math/fast_fourier_transform.rs b/src/math/fast_fourier_transform.rs
@@ -194,7 +194,7 @@ mod tests {
         let mut fft = fast_fourier_transform(&polynomial, &permutation);
         fft.iter_mut().for_each(|num| *num *= *num);
         let ifft = inverse_fast_fourier_transform(&fft, &permutation);
-        let expected = vec![1.0, 2.0, 1.0, 4.0, 4.0, 0.0, 4.0, 0.0, 0.0];
+        let expected = [1.0, 2.0, 1.0, 4.0, 4.0, 0.0, 4.0, 0.0, 0.0];
         for (x, y) in ifft.iter().zip(expected.iter()) {
             assert!(almost_equal(*x, *y, EPSILON));
         }
diff --git a/src/string/autocomplete_using_trie.rs b/src/string/autocomplete_using_trie.rs
@@ -18,7 +18,7 @@ impl Trie {
         Trie(HashMap::new())
     }
 
-    fn insert(&mut self, text: String) {
+    fn insert(&mut self, text: &str) {
         let mut trie = self;
 
         for c in text.chars().collect::<Vec<char>>() {
@@ -28,7 +28,7 @@ impl Trie {
         trie.0.insert(END, Box::new(Trie::new()));
     }
 
-    fn find(&self, prefix: String) -> Vec<String> {
+    fn find(&self, prefix: &str) -> Vec<String> {
         let mut trie = self;
 
         for c in prefix.chars().collect::<Vec<char>>() {
@@ -42,7 +42,7 @@ impl Trie {
 
         Self::_elements(trie)
             .iter()
-            .map(|s| prefix.clone() + s)
+            .map(|s| prefix.to_owned() + s)
             .collect()
     }
 
@@ -76,13 +76,13 @@ impl Autocomplete {
         Self { trie: Trie::new() }
     }
 
-    pub fn insert_words(&mut self, words: Vec<String>) {
+    pub fn insert_words<T: AsRef<str>>(&mut self, words: &[T]) {
         for word in words {
-            self.trie.insert(word);
+            self.trie.insert(word.as_ref());
         }
     }
 
-    pub fn find_words(&self, prefix: String) -> Vec<String> {
+    pub fn find_words(&self, prefix: &str) -> Vec<String> {
         self.trie.find(prefix)
     }
 }
@@ -99,28 +99,24 @@ mod tests {
 
     #[test]
     fn test_autocomplete() {
-        let words = vec![
-            "apple".to_owned(),
-            "orange".to_owned(),
-            "oregano".to_owned(),
-        ];
+        let words = vec!["apple", "orange", "oregano"];
 
         let mut auto_complete = Autocomplete::new();
-        auto_complete.insert_words(words);
+        auto_complete.insert_words(&words);
 
-        let prefix = "app".to_owned();
+        let prefix = "app";
         let mut auto_completed_words = auto_complete.find_words(prefix);
 
-        let mut apple = vec!["apple".to_owned()];
+        let mut apple = vec!["apple"];
         apple.sort();
 
         auto_completed_words.sort();
         assert_eq!(auto_completed_words, apple);
 
-        let prefix = "or".to_owned();
+        let prefix = "or";
         let mut auto_completed_words = auto_complete.find_words(prefix);
 
-        let mut prefix_or = vec!["orange".to_owned(), "oregano".to_owned()];
+        let mut prefix_or = vec!["orange", "oregano"];
         prefix_or.sort();
 
         auto_completed_words.sort();
diff --git a/src/string/burrows_wheeler_transform.rs b/src/string/burrows_wheeler_transform.rs
diff --git a/src/string/knuth_morris_pratt.rs b/src/string/knuth_morris_pratt.rs
diff --git a/src/string/rabin_karp.rs b/src/string/rabin_karp.rs
diff --git a/src/string/run_length_encoding.rs b/src/string/run_length_encoding.rs
diff --git a/src/string/suffix_tree.rs b/src/string/suffix_tree.rs

Original file line number	Diff line number	Diff line change
`@@ -114,7 +114,7 @@ impl<T: Debug + Default + Ord + Copy + Display + AddAssign + Add<Output = T>> La`
`114`	`114`	`return;`
`115`	`115`	`}`
`116`	`116`
`117`		`- let lazy = self.lazy[idx].unwrap_or(T::default());`
	`117`	`+ let lazy = self.lazy[idx].unwrap_or_default();`
`118`	`118`	`self.lazy[idx] = None;`
`119`	`119`
`120`	`120`	`let mid = (element_range.start + element_range.end) / 2;`
Original file line number	Diff line number	Diff line change
`@@ -33,7 +33,7 @@ where`
`33`	`33`	`{`
`34`	`34`	`let mut node = &mut self.root;`
`35`	`35`	`for c in key.into_iter() {`
`36`		`- node = node.children.entry(c).or_insert_with(Node::default);`
	`36`	`+ node = node.children.entry(c).or_default();`
`37`	`37`	`}`
`38`	`38`	`node.value = Some(value);`
`39`	`39`	`}`
Original file line number	Diff line number	Diff line change
`@@ -28,7 +28,7 @@ impl<T> PartialEq for HuffmanNode<T> {`
`28`	`28`
`29`	`29`	`impl<T> PartialOrd for HuffmanNode<T> {`
`30`	`30`	`fn partial_cmp(&self, other: &Self) -> Option<Ordering> {`
`31`		`- Some(self.frequency.cmp(&other.frequency).reverse())`
	`31`	`+ Some(self.cmp(other))`
`32`	`32`	`}`
`33`	`33`	`}`
`34`	`34`
Original file line number	Diff line number	Diff line change
`@@ -18,7 +18,7 @@ impl<V: Ord + Copy, E: Ord + Copy> PartialOrd for Candidate<V, E> {`
`18`	`18`	`fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {`
`19`	`19`	`// Note the inverted order; we want nodes with lesser weight to have`
`20`	`20`	`// higher priority`
`21`		`- other.estimated_weight.partial_cmp(&self.estimated_weight)`
	`21`	`+ Some(self.cmp(other))`
`22`	`22`	`}`
`23`	`23`	`}`
`24`	`24`
`@@ -111,8 +111,8 @@ mod tests {`
`111`	`111`	`}`
`112`	`112`
`113`	`113`	`fn add_edge<V: Ord + Copy, E: Ord>(graph: &mut Graph<V, E>, v1: V, v2: V, c: E) {`
`114`		`- graph.entry(v1).or_insert_with(BTreeMap::new).insert(v2, c);`
`115`		`- graph.entry(v2).or_insert_with(BTreeMap::new);`
	`114`	`+ graph.entry(v1).or_default().insert(v2, c);`
	`115`	`+ graph.entry(v2).or_default();`
`116`	`116`	`}`
`117`	`117`
`118`	`118`	`#[test]`
Original file line number	Diff line number	Diff line change
`@@ -90,8 +90,8 @@ mod tests {`
`90`	`90`	`use std::collections::BTreeMap;`
`91`	`91`
`92`	`92`	`fn add_edge<V: Ord + Copy, E: Ord>(graph: &mut Graph<V, E>, v1: V, v2: V, c: E) {`
`93`		`- graph.entry(v1).or_insert_with(BTreeMap::new).insert(v2, c);`
`94`		`- graph.entry(v2).or_insert_with(BTreeMap::new);`
	`93`	`+ graph.entry(v1).or_default().insert(v2, c);`
	`94`	`+ graph.entry(v2).or_default();`
`95`	`95`	`}`
`96`	`96`
`97`	`97`	`#[test]`
Original file line number	Diff line number	Diff line change
`@@ -56,8 +56,8 @@ mod tests {`
`56`	`56`	`use std::collections::BTreeMap;`
`57`	`57`
`58`	`58`	`fn add_edge<V: Ord + Copy, E: Ord>(graph: &mut Graph<V, E>, v1: V, v2: V, c: E) {`
`59`		`- graph.entry(v1).or_insert_with(BTreeMap::new).insert(v2, c);`
`60`		`- graph.entry(v2).or_insert_with(BTreeMap::new);`
	`59`	`+ graph.entry(v1).or_default().insert(v2, c);`
	`60`	`+ graph.entry(v2).or_default();`
`61`	`61`	`}`
`62`	`62`
`63`	`63`	`#[test]`