algorithms_fourth 0.1.10

use super::ST;
struct Node<K, V> {
    key: K,
    value: V,
    next: Link<K, V>,
}
type Link<K, V> = Option<Box<Node<K, V>>>;
#[derive(Default)]
pub struct SequentialSearchST<K: PartialOrd, V> {
    first: Link<K, V>,
}
pub struct IterMut<K, V> {
    first: Link<K, V>,
}

impl<K: PartialOrd, V> SequentialSearchST<K, V> {
    pub fn iter_mut(&mut self) -> IterMut<K, V> {
        IterMut {
            first: self.first.take(),
        }
    }
}

impl<K: PartialOrd, V> Iterator for IterMut<K, V> {
    type Item = (K, V);

    fn next(&mut self) -> Option<Self::Item> {
        let ans = self.first.take();
        ans.map(|mut f| {
            self.first = f.next.take();
            (f.key, f.value)
        })
    }
}

impl<K: PartialOrd, V> ST<K, V> for SequentialSearchST<K, V> {
    fn put(&mut self, key: K, value: V) {
        // println!("put:{:?}", &key);
        let first = self.first.as_deref_mut();
        match first {
            None => {
                self.first = Some(Box::new(Node {
                    key,
                    value,
                    next: self.first.take(),
                }));
            }
            Some(first) => {
                if first.key > key {
                    self.first = Some(Box::new(Node {
                        key,
                        value,
                        next: self.first.take(),
                    }));
                } else if first.key == key {
                    first.value = value;
                } else {
                    let mut p = first;
                    let mut current = p.next.as_deref_mut();
                    // println!("p:{:?} {}", &p.key, current.is_some());
                    if current.is_none() {
                        p.next = Some(Box::new(Node {
                            key,
                            value,
                            next: None,
                        }));
                        return;
                    }
                    while let Some(node) = current {
                        // println!("while:{:?}", &node.key);
                        if key == node.key {
                            node.value = value;
                            break;
                        } else if key < node.key {
                            p.next = Some(Box::new(Node {
                                key,
                                value,
                                next: p.next.take(),
                            }));
                            break;
                        } else {
                            let next = node.next.as_deref();
                            if next.is_none() {
                                node.next = Some(Box::new(Node {
                                    key,
                                    value,
                                    next: None,
                                }));
                                break;
                            } else {
                                current = node.next.as_deref_mut();
                            }
                        }
                    }
                }
            }
        }
    }

    fn get(&self, key: &K) -> Option<&V> {
        let mut current = self.first.as_deref();
        while let Some(node) = current {
            if &node.key == key {
                return Some(&node.value);
            } else {
                current = node.next.as_deref();
            }
        }
        None
    }

    fn delete(&mut self, key: &K) {
        let first = self.first.as_deref_mut();
        if first.is_none() {
            return;
        }
        let first = first.unwrap();
        if &first.key == key {
            self.first = first.next.take();
            return;
        }
        let mut p = first;
        let a = unsafe { (p as *mut Node<K, V>).as_mut() };
        let mut current = a.unwrap().next.as_deref_mut();
        while let Some(node) = current {
            if &node.key == key {
                p.next = node.next.take();
                break;
            } else {
                p = node;
                let a = unsafe { (p as *mut Node<K, V>).as_mut() };
                current = a.unwrap().next.as_deref_mut();
            }
        }
    }

    fn contains(&self, key: &K) -> bool {
        self.get(key).is_some()
    }

    fn is_empty(&self) -> bool {
        self.first.is_none()
    }

    fn size(&self) -> usize {
        let mut current = self.first.as_deref();
        let mut size = 0;
        while let Some(node) = current {
            size += 1;
            current = node.next.as_deref();
        }
        size
    }

    fn min(&self) -> Option<&K> {
        let mut current = self.first.as_deref();
        let mut result = None;
        while let Some(node) = current {
            if let Some(key) = result {
                if key > &node.key {
                    result = Some(&node.key)
                }
            } else {
                result = Some(&node.key);
            }
            current = node.next.as_deref();
        }
        result
    }

    fn max(&self) -> Option<&K> {
        let mut current = self.first.as_deref();
        let mut result = None;
        while let Some(node) = current {
            if let Some(key) = result {
                if key < &node.key {
                    result = Some(&node.key)
                }
            } else {
                result = Some(&node.key);
            }
            current = node.next.as_deref();
        }
        result
    }

    fn floor(&self, key: &K) -> Option<&K> {
        let mut current = self.first.as_deref();
        let mut result = None;
        while let Some(node) = current {
            let current_key = &node.key;
            if let Some(inner) = result {
                if key >= current_key && inner < current_key {
                    result = Some(current_key)
                }
            } else if key >= current_key {
                result = Some(current_key);
            }

            current = node.next.as_deref();
        }
        result
    }
    fn ceiling(&self, key: &K) -> Option<&K> {
        let mut current = self.first.as_deref();
        let mut result = None;
        while let Some(node) = current {
            let current_key = &node.key;
            if let Some(inner) = result {
                if key <= current_key && inner > current_key {
                    result = Some(current_key)
                }
            } else if key <= current_key {
                result = Some(current_key);
            }
            current = node.next.as_deref();
        }
        result
    }

    fn rank(&self, key: &K) -> usize {
        let mut current = self.first.as_deref();
        let mut size = 0;
        while let Some(node) = current {
            if &node.key < key {
                size += 1;
            }
            current = node.next.as_deref();
        }
        size
    }

    fn select(&self, k: usize) -> Option<&K> {
        let mut current = self.first.as_deref();
        let mut result = None;
        let mut i: usize = 0;
        while let Some(node) = current {
            if i == k {
                result = Some(&node.key);
                break;
            }
            current = node.next.as_deref();
            i += 1;
        }
        result
    }
}
#[cfg(test)]
mod test {
    use crate::search::ST;

    use super::SequentialSearchST;

    #[test]
    fn test() {
        let mut st = SequentialSearchST::default();
        assert!(st.is_empty());
        assert_eq!(st.size(), 0);
        st.put(1, "a");
        st.put(2, "b");
        st.put(3, "c");
        assert_eq!(st.size(), 3);
        assert_eq!(st.max(), Some(&3));
        assert_eq!(st.min(), Some(&1));
        assert_eq!(st.get(&1), Some(&"a"));
        assert_eq!(st.get(&2), Some(&"b"));
        assert_eq!(st.get(&3), Some(&"c"));
        assert_eq!(st.select(0), Some(&1));
        assert_eq!(st.select(2), Some(&3));
        assert_eq!(st.select(3), None);
        assert_eq!(st.floor(&2), Some(&2));
        assert_eq!(st.floor(&0), None);
        assert_eq!(st.ceiling(&2), Some(&2));
        assert_eq!(st.ceiling(&4), None);
        st.delete(&2);
        assert_eq!(st.get(&2), None);
        assert_eq!(st.ceiling(&2), Some(&3));
        assert_eq!(st.floor(&2), Some(&1));
        st.delete_min();
        assert_eq!(st.min(), Some(&3));
        st.put(2, "bb");
        st.delete_max();
        assert_eq!(st.max(), Some(&2));
        st.delete_max();
        st.delete_min();
        assert!(st.is_empty());
    }
}