use std::collections::HashMap;
use std::collections::HashSet;

fn search_m<'a>(hashmap: HashMap<&str, Vec<&'a str>>) -> Option<&'a str> {
    let mut queue: Vec<&str> = Vec::new();
    let mut check_list = HashSet::new();
    if let Some(first) = hashmap.get("you") {
        for ele in first {
            queue.push(ele);
        }
    }
    while queue.len() > 0 {
        let c = queue.remove(0);
        if check_list.contains(c) {
            continue;
        }
        check_list.insert(c);
        if c.ends_with("m") {
            return Some(c);
        }
        if let Some(eles) = hashmap.get(c) {
            for ele in eles {
                queue.push(ele)
            }
        }
    }
    None
}

fn main() {
    let mut hashmap = HashMap::new();
    hashmap.insert("you", vec!["alice", "bob", "claire"]);
    hashmap.insert("bob", vec!["anuj", "peggy"]);
    hashmap.insert("alice", vec!["peggy"]);
    hashmap.insert("claire", vec!["you", "thom", "jonny"]);
    hashmap.insert("anuj", vec![]);
    hashmap.insert("peggy", vec![]);
    hashmap.insert("thom", vec![]);
    hashmap.insert("jonny", vec![]);

    let v = search_m(hashmap);
    match v {
        Some(i) => {
            println!("find mongoose! name {:?}", i);
        }
        None => {
            println!("not find mongoose");
        }
    }
}

fn q_srot(arr: &Vec<i32>) -> Vec<i32> {
    if arr.len() < 2 {
        return arr.clone();
    }
    let base = arr[0];
    let small: Vec<i32> = arr.into_iter().filter(|x| *x < &base).map(|x| *x).collect();
    let bigger: Vec<i32> = arr.iter().filter(|x| *x > &base).map(|x| *x).collect();
    let result: Vec<i32> = q_srot(&small)
        .into_iter()
        .chain(vec![base])
        .chain(q_srot(&bigger))
        .collect();
    return result;
}

// 分治，二分查找，Rust版本
fn mid_search(arr: Vec<i32>, search: i32) -> i32 {
    if arr.len() == 0 {
        return -1;
    }
    if arr[0] == search {
        return arr[0];
    }
    let mid = (arr.len() - 1) / 2;
    if arr[mid] > search {
        return mid_search(arr[0..mid].to_vec(), search);
    } else {
        return mid_search(arr[mid..arr.len()].to_vec(), search);
    }
}

fn selection_sort(arr: Vec<i32>) -> Vec<i32> {
    let mut min = std::i32::MIN;
    let mut result = vec![];
    for _i in &arr {
        let c_min = find_small(&arr, min);
        min = c_min;
        result.push(c_min);
    }
    result
}
fn find_small(arr: &Vec<i32>, min: i32) -> i32 {
    let mut c_min = std::i32::MAX;
    for i in arr {
        if *i <= min {
            continue;
        }
        if *i < c_min {
            c_min = *i;
        }
    }
    c_min
}

use std::{f32::MIN, vec};

struct MinStack {
    stack_a: Vec<i32>,
    stack_b: Vec<i32>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MinStack {
    /** initialize your data structure here. */
    fn new() -> Self {
        return MinStack {
            stack_a: vec![],
            stack_b: vec![],
        };
    }

    fn push(&mut self, x: i32) {
        self.stack_a.push(x);
        if self.stack_b.len() == 0 {
            self.stack_b.push(x);
        } else if self.min() >= x {
            self.stack_b.push(x);
        } else {
            self.stack_b.push(self.min());
        }
    }

    fn pop(&mut self) {
        self.stack_a.pop();
        self.stack_b.pop();
    }

    fn top(&self) -> i32 {
        let top: i32 = self.stack_a.last().unwrap().clone();
        top
    }

    fn min(&self) -> i32 {
        let min: i32 = self.stack_b.last().unwrap().clone();
        min
    }
}

use std::collections::VecDeque;

struct CQueue {
    stack: VecDeque<i32>,
}

impl CQueue {
    fn new() -> Self {
        CQueue {
            stack: VecDeque::new(),
        }
    }

    fn append_tail(&mut self, value: i32) {
        self.stack.push_front(value);
    }

    fn delete_head(&mut self) -> i32 {
        let v = self.stack.pop_back();
        match v {
            Some(v) => v,
            None => -1,
        }
    }
}

#[derive(Default)]
struct CQueue {
    stack1: Vec<i32>,
    stack2: Vec<i32>,
}

impl CQueue {
    fn new() -> Self {
        Self::default()
    }

    fn append_tail(&mut self, value: i32) {
        self.stack1.push(value);
    }

    fn delete_head(&mut self) -> i32 {
        if let Some(i) = self.stack2.pop() {
            return i;
        };
        while let Some(i) = self.stack1.pop() {
            self.stack2.push(i);
        }
        self.stack2.pop().unwrap_or(-1)
    }
}