algorithms_fourth 0.1.10

use std::cmp::Ordering;

use super::ST;

pub struct BinarySearchST<K, V> {
    keys: Vec<K>,
    vals: Vec<V>,
    n: usize,
}
impl<K: PartialOrd, V> BinarySearchST<K, V> {
    /// ```
    /// use algorithms_fourth::search::binary_search::BinarySearchST;
    /// let bst :BinarySearchST<usize,usize > = BinarySearchST::new(10);
    /// ```
    pub fn new(capacity: usize) -> Self {
        BinarySearchST {
            keys: Vec::with_capacity(capacity),
            vals: Vec::with_capacity(capacity),
            n: 0,
        }
    }
    fn rank_in(&self, key: &K, lo: usize, hi: usize) -> usize {
        if hi < lo {
            return lo;
        }
        let mid = lo + (hi - lo) / 2;
        match key
            .partial_cmp(unsafe { self.keys.get_unchecked(mid) })
            .unwrap()
        {
            Ordering::Less => {
                if mid > 0 {
                    self.rank_in(key, lo, mid - 1)
                } else {
                    0
                }
            }
            Ordering::Equal => mid,
            Ordering::Greater => self.rank_in(key, mid + 1, hi),
        }
    }
}
impl<K: PartialOrd, V> ST<K, V> for BinarySearchST<K, V> {
    fn put(&mut self, key: K, value: V) {
        let i = self.rank(&key);
        match self.keys.get(i) {
            Some(t) => {
                if t == &key {
                    self.vals[i] = value;
                } else {
                    self.keys.insert(i, key);
                    self.vals.insert(i, value);
                    self.n += 1;
                }
            }
            None => {
                self.keys.insert(i, key);
                self.vals.insert(i, value);
                self.n += 1;
            }
        }
    }

    fn get(&self, key: &K) -> Option<&V> {
        if self.is_empty() {
            None
        } else {
            let i = self.rank(key);
            if i < self.n && &self.keys[i] == key {
                Some(&self.vals[i])
            } else {
                None
            }
        }
    }

    fn delete(&mut self, key: &K) {
        let i = self.rank(key);
        if let Some(t) = self.keys.get(i) {
            if t == key {
                self.keys.remove(i);
                self.vals.remove(i);
                self.n -= 1;
            }
        }
    }

    fn is_empty(&self) -> bool {
        self.n == 0
    }

    fn size(&self) -> usize {
        self.n
    }

    fn min(&self) -> Option<&K> {
        self.keys.get(0)
    }

    fn max(&self) -> Option<&K> {
        if self.is_empty() {
            None
        } else {
            self.keys.get(self.n - 1)
        }
    }

    fn floor(&self, key: &K) -> Option<&K> {
        let i = self.rank(key);
        if i >= self.n {
            self.keys.get(i)
        } else {
            match self.keys.get(i) {
                Some(t) => {
                    if t == key {
                        Some(t)
                    } else if i > 0 {
                        self.keys.get(i - 1)
                    } else {
                        None
                    }
                }
                None => None,
            }
        }
    }

    fn ceiling(&self, key: &K) -> Option<&K> {
        let i = self.rank(key);
        return self.keys.get(i);
    }

    fn rank(&self, key: &K) -> usize {
        if self.n > 0 {
            self.rank_in(key, 0, self.n - 1)
        } else {
            0
        }
    }

    fn select(&self, k: usize) -> Option<&K> {
        Some(&self.keys[k])
    }
}
#[cfg(test)]
mod test {
    #[test]
    fn test_binary_search() {}
}