<commit_before>use std::iter;
use std::fmt;
use std::cmp::Ordering;
use super::{ST, OrderedST};

pub struct Node<K, V> {
    key: K,
    val: V,
    left:  Option<Box<Node<K, V>>>,
    right: Option<Box<Node<K, V>>>
}

impl<K, V> Node<K, V> {
    pub fn new(key: K, val: V) -> Node<K, V> {
        Node {
            key: key,
            val: val,
            left: None,
            right: None
        }
    }
}

impl<K: fmt::Debug, V: fmt::Debug> Node<K, V> {
    fn dump(&self, depth: usize, f: &mut fmt::Formatter) {
        if depth == 0 {
            writeln!(f, "{:?}[{:?}]", self.key, self.val).unwrap();
        } else {
            writeln!(f, "{}+--{:?}[{:?}]", iter::repeat("|  ").take(depth-1).collect::<Vec<&str>>().concat(),
                     self.key, self.val).unwrap();
        }
        if self.left.is_some() {
            self.left.as_ref().unwrap().dump(depth + 1, f);
        }
        if self.right.is_some() {
            self.right.as_ref().unwrap().dump(depth + 1, f);
        }
    }
}

fn put<K: Ord, V>(x: Option<Box<Node<K,V>>>, key: K, val: V) -> Option<Box<Node<K,V>>> {
    let mut x = x;
    if x.is_none() {
        return Some(Box::new(Node::new(key, val)));
    }
    let cmp = key.cmp(&x.as_ref().unwrap().key);
    match cmp {
        Ordering::Less => {
            let left = x.as_mut().unwrap().left.take();
            x.as_mut().unwrap().left = put(left, key, val)
        },
        Ordering::Greater => {
            let right = x.as_mut().unwrap().right.take();
            x.as_mut().unwrap().right = put(right, key, val)
        },
        Ordering::Equal => {
            x.as_mut().unwrap().val = val
        }
    }
    x
}


pub struct BST<K, V> {
    root: Option<Box<Node<K, V>>>
}

impl<K: Ord, V> ST<K, V> for BST<K, V> {
    fn new() -> BST<K, V> {
        BST { root: None }
    }

    fn get(&self, key: &K) -> Option<&V> {
        let mut x = self.root.as_ref();
        while x.is_some() {
            match key.cmp(&x.unwrap().key) {
                Ordering::Less => {
                    x = x.unwrap().left.as_ref();
                },
                Ordering::Greater => {
                    x = x.unwrap().right.as_ref();
                },
                Ordering::Equal  => {
                    return Some(&x.unwrap().val)
                }
            }
        }
        None
    }

    fn put(&mut self, key: K, val: V) {
        let root = self.root.take();
        self.root = put(root, key, val);
    }

    fn delete(&mut self, key: &K) {
        unimplemented!()
    }

    fn is_empty(&self) -> bool {
        self.root.is_none()
    }
    /// number of key-value pairs in the table
    fn size(&self) -> usize {
        unimplemented!()
    }
}

impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for BST<K, V> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if self.root.is_none() {
            write!(f, "<empty tree>")
        } else {
            self.root.as_ref().unwrap().dump(0, f);
            Ok(())
        }
    }
}



#[test]
fn test_binary_search_tree() {
    let mut t = BST::<char, usize>::new();
    for (i, c) in "SEARCHEXAMP".chars().enumerate() {
        t.put(c, i);
    }

    //println!("{:?}", t);
    assert_eq!(t.get('E'),  Some(&6));
}<commit_msg>symbol_tables/binary_search_tree: implement floor for BST<commit_after>use std::iter;
use std::fmt;
use std::cmp::Ordering;
use super::{ST, OrderedST};

pub struct Node<K, V> {
    key: K,
    val: V,
    left:  Option<Box<Node<K, V>>>,
    right: Option<Box<Node<K, V>>>
}

impl<K, V> Node<K, V> {
    pub fn new(key: K, val: V) -> Node<K, V> {
        Node {
            key: key,
            val: val,
            left: None,
            right: None
        }
    }
}

impl<K: fmt::Debug, V: fmt::Debug> Node<K, V> {
    fn dump(&self, depth: usize, f: &mut fmt::Formatter) {
        if depth == 0 {
            writeln!(f, "{:?}[{:?}]", self.key, self.val).unwrap();
        } else {
            writeln!(f, "{}+--{:?}[{:?}]", iter::repeat("|  ").take(depth-1).collect::<Vec<&str>>().concat(),
                     self.key, self.val).unwrap();
        }
        if self.left.is_some() {
            self.left.as_ref().unwrap().dump(depth + 1, f);
        }
        if self.right.is_some() {
            self.right.as_ref().unwrap().dump(depth + 1, f);
        }
    }
}

fn put<K: Ord, V>(x: Option<Box<Node<K,V>>>, key: K, val: V) -> Option<Box<Node<K,V>>> {
    let mut x = x;
    if x.is_none() {
        return Some(Box::new(Node::new(key, val)));
    }
    let cmp = key.cmp(&x.as_ref().unwrap().key);
    match cmp {
        Ordering::Less => {
            let left = x.as_mut().unwrap().left.take();
            x.as_mut().unwrap().left = put(left, key, val)
        },
        Ordering::Greater => {
            let right = x.as_mut().unwrap().right.take();
            x.as_mut().unwrap().right = put(right, key, val)
        },
        Ordering::Equal => {
            x.as_mut().unwrap().val = val
        }
    }
    x
}


pub struct BST<K, V> {
    root: Option<Box<Node<K, V>>>
}

impl<K: Ord, V> ST<K, V> for BST<K, V> {
    fn new() -> BST<K, V> {
        BST { root: None }
    }

    fn get(&self, key: &K) -> Option<&V> {
        let mut x = self.root.as_ref();
        while x.is_some() {
            match key.cmp(&x.unwrap().key) {
                Ordering::Less => {
                    x = x.unwrap().left.as_ref();
                },
                Ordering::Greater => {
                    x = x.unwrap().right.as_ref();
                },
                Ordering::Equal  => {
                    return Some(&x.unwrap().val)
                }
            }
        }
        None
    }

    fn put(&mut self, key: K, val: V) {
        let root = self.root.take();
        self.root = put(root, key, val);
    }

    fn delete(&mut self, key: &K) {
        unimplemented!()
    }

    fn is_empty(&self) -> bool {
        self.root.is_none()
    }
    /// number of key-value pairs in the table
    fn size(&self) -> usize {
        unimplemented!()
    }
}

fn floor<'a, K: Ord, V>(x: Option<&'a Box<Node<K,V>>>, key: &K) -> Option<&'a Node<K,V>> {
    if x.is_none() {
        return None;
    }

    match key.cmp(&x.unwrap().key) {
        Ordering::Equal => {
            return Some(&(**x.unwrap()));
        },
        Ordering::Less => {
            return floor(x.unwrap().left.as_ref(), key);
        },
        _ => (),
    }

    let t = floor(x.unwrap().right.as_ref(), key);
    if t.is_some() {
        return t
    } else {
        return Some(x.unwrap())
    }
}

impl<K: Ord, V> OrderedST<K, V> for BST<K, V> {
    /// smallest key
    fn min(&self) -> Option<&K> {
        unimplemented!()
    }

    /// largest key
    fn max(&self) -> Option<&K> {
        unimplemented!()
    }

    /// largest key less than or equal to key
    fn floor(&self, key: &K) -> Option<&K> {
        let x = floor(self.root.as_ref(), key);
        if x.is_none() {
            None
        } else {
            Some(&x.unwrap().key)
        }
    }

    /// smallest key greater than or equal to key
    fn ceiling(&self, key: &K) -> Option<&K> {
        unimplemented!()
    }

    /// number of keys less than key
    fn rank(&self, key: &K) -> usize {
        unimplemented!()
    }

    /// key of rank k
    fn select(&self, k: usize) -> Option<&K> {
        unimplemented!()
    }

    /// delete smallest key
    fn delete_min(&mut self) {
        unimplemented!()
    }

    /// delete largest key
    fn delete_max(&mut self) {
        unimplemented!()
    }
}

impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for BST<K, V> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if self.root.is_none() {
            write!(f, "<empty tree>")
        } else {
            self.root.as_ref().unwrap().dump(0, f);
            Ok(())
        }
    }
}



#[test]
fn test_binary_search_tree() {
    let mut t = BST::<char, usize>::new();
    for (i, c) in "SEARCHEXAMP".chars().enumerate() {
        t.put(c, i);
    }

    //println!("{:?}", t);
    assert_eq!(t.get(&'E'),  Some(&6));
    assert_eq!(t.floor(&'O'), Some(&'M'));
}
{'fraction_non_alphanumeric': 0.19723141002082567, 'fraction_numerical': 0.001470047776552738, 'mean_word_length': 1.6749672346002622, 'pattern_counts': {'":': 0, '<': 85, '<?xml version=': 0, '>': 121, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3505978', 'n_tokens_mistral': 2944, 'n_tokens_neox': 2942, 'n_words': 623}