repo_description: This is the Rust course used by the Android team at Google. It provides you the material to quickly teach Rust.
repo_topics: android classroom course google guide rust training training-materials
code: // Copyright 2023 Google LLC
  // SPDX-License-Identifier: Apache-2.0
  //
  // Licensed under the Apache License, Version 2.0 (the "License");
  // you may not use this file except in compliance with the License.
  // You may obtain a copy of the License at
  //
  //      http://www.apache.org/licenses/LICENSE-2.0
  //
  // Unless required by applicable law or agreed to in writing, software
  // distributed under the License is distributed on an "AS IS" BASIS,
  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  // See the License for the specific language governing permissions and
  // limitations under the License.
  #![allow(dead_code)]
  
  // ANCHOR: solution
  use std::cmp::Ordering;
  
  // ANCHOR: types
  /// A node in the binary tree.
  #[derive(Debug)]
  struct Node<T: Ord> {
      value: T,
      left: Subtree<T>,
      right: Subtree<T>,
  }
  
  /// A possibly-empty subtree.
  #[derive(Debug)]
  struct Subtree<T: Ord>(Option<Box<Node<T>>>);
  
  /// A container storing a set of values, using a binary tree.
  ///
  /// If the same value is added multiple times, it is only stored once.
  #[derive(Debug)]
  pub struct BinaryTree<T: Ord> {
      root: Subtree<T>,
  }
  
  impl<T: Ord> BinaryTree<T> {
      fn new() -> Self {
          Self { root: Subtree::new() }
      }
  
      fn insert(&mut self, value: T) {
          self.root.insert(value);
      }
  
      fn has(&self, value: &T) -> bool {
          self.root.has(value)
      }
  
      fn len(&self) -> usize {
          self.root.len()
      }
  }
  // ANCHOR_END: types
  
  impl<T: Ord> Subtree<T> {
      fn new() -> Self {
          Self(None)
      }
  
      fn insert(&mut self, value: T) {
          match &mut self.0 {
              None => self.0 = Some(Box::new(Node::new(value))),
              Some(n) => match value.cmp(&n.value) {
                  Ordering::Less => n.left.insert(value),
                  Ordering::Equal => {}
                  Ordering::Greater => n.right.insert(value),
              },
          }
      }
  
      fn has(&self, value: &T) -> bool {
          match &self.0 {
              None => false,
              Some(n) => match value.cmp(&n.value) {
                  Ordering::Less => n.left.has(value),
                  Ordering::Equal => true,
                  Ordering::Greater => n.right.has(value),
              },
          }
      }
  
      fn len(&self) -> usize {
          match &self.0 {
              None => 0,
              Some(n) => 1 + n.left.len() + n.right.len(),
          }
      }
  }
  
  impl<T: Ord> Node<T> {
      fn new(value: T) -> Self {
          Self { value, left: Subtree::new(), right: Subtree::new() }
      }
  }
  
  // ANCHOR: tests
  #[cfg(test)]
  mod tests {
      use super::*;
  
      #[test]
      fn len() {
          let mut tree = BinaryTree::new();
          assert_eq!(tree.len(), 0);
          tree.insert(2);
          assert_eq!(tree.len(), 1);
          tree.insert(1);
          assert_eq!(tree.len(), 2);
          tree.insert(2); // not a unique item
          assert_eq!(tree.len(), 2);
          tree.insert(3);
          assert_eq!(tree.len(), 3);
      }
  
      #[test]
      fn has() {
          let mut tree = BinaryTree::new();
          fn check_has(tree: &BinaryTree<i32>, exp: &[bool]) {
              let got: Vec<bool> =
                  (0..exp.len()).map(|i| tree.has(&(i as i32))).collect();
              assert_eq!(&got, exp);
          }
  
          check_has(&tree, &[false, false, false, false, false]);
          tree.insert(0);
          check_has(&tree, &[true, false, false, false, false]);
          tree.insert(4);
          check_has(&tree, &[true, false, false, false, true]);
          tree.insert(4);
          check_has(&tree, &[true, false, false, false, true]);
          tree.insert(3);
          check_has(&tree, &[true, false, false, true, true]);
      }
  
      #[test]
      fn unbalanced() {
          let mut tree = BinaryTree::new();
          for i in 0..100 {
              tree.insert(i);
          }
          assert_eq!(tree.len(), 100);
          assert!(tree.has(&50));
      }
  }
  // ANCHOR_END: tests
  