/tmp/bucket

// Cargo.toml
// ...
[dependencies]
borsh = "0.9.3"
borsh-derive = "0.9.1"

// main.rs
use borsh::{BorshDeserialize, BorshSerialize};

#[derive(BorshSerialize, BorshDeserialize, Debug)]
struct Node {
    num: i32,
    str: String
}

fn main() {
    let uint:i32 = 256; // 2^8 -> 1 byte
    let node = Node{
        num: uint.pow(0) + uint.pow(1)*2 + uint.pow(2)*3 + uint.pow(3)*4, // [1, 2, 3, 4]
        str: String::from("好") // first 4 bytes represents how many bytes of this string
    };

    if let Ok(buf) = node.try_to_vec() {
        println!("serialized: {:?}", buf);

        if let Ok(deserz_node) = Node::try_from_slice(&buf) {
            println!("deserialized: {:?}", deserz_node);
        }
    }
}

impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let hay_vec: Vec<char> = haystack.chars().collect();
        let needle_vec: Vec<char> = needle.chars().collect();

        let mut i_hay: usize = 0;
        let mut i_needle: usize = 0;
        while i_hay < hay_vec.len() {
            while i_needle < needle_vec.len() {

                let offset_hay = i_hay + i_needle;
                if offset_hay >= hay_vec.len() {
                    break;
                }

                if hay_vec[offset_hay] != needle_vec[i_needle] {
                    i_needle = 0;
                    break;
                } else if hay_vec[offset_hay] == needle_vec[i_needle] && i_needle == needle_vec.len() - 1 {
                    return i_hay as i32;
                }

                i_needle += 1;
            }

            i_hay += 1;
        }

        return -1;
    }
}

impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let (hay_len, needle_len) = (haystack.len(), needle.len());

        if needle_len == 0 { return 0 }
        else if needle_len > hay_len { return -1 } // avoid hay: "aa", needle: "aaaa"

        for i in 0..=hay_len - needle_len {
            if haystack[i..i + needle_len] == needle {
                return i as i32;
            }
        }

        -1
    }
}

const MAGIC_NUM: u64 = 31; // can be any number but should not too big

pub fn str_str(haystack: String, needle: String) -> i32 {
    let (hay_len, needle_len) = (haystack.len(), needle.len());

    if needle_len == 0 { return 0 }
    else if needle_len > hay_len { return -1 } // avoid hay: "aa", needle: "aaaa"

    let hash_needle = hash(&needle);
    let mut hash_hay:u64 = 0;
    let highest_pow = MAGIC_NUM.pow(needle_len as u32 - 1);

    for i in 0..=hay_len - needle_len {
        if hash_hay == 0 { 
            hash_hay = hash(&haystack[i..i + needle_len]); 
        } else {
            /* rolling hash */ 
            // abc -> _bc
            let first_c = haystack.chars().nth(i-1).unwrap();
            hash_hay -= first_c as u64 * highest_pow;
            // _bc -> bc_
            hash_hay *= MAGIC_NUM;
            // bc_ -> bcd
            hash_hay += haystack.chars().nth(i + needle_len - 1).unwrap() as u64;
        }

        if hash_hay == hash_needle {
            return i as i32;
        }
    }

    -1
}

fn hash(str: &str) -> u64 {
    let mut buf:u64 = 0;

    for c in str.chars() {
        buf *= MAGIC_NUM;
        buf += c as u64;
    }

    buf
}

impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        if needle.is_empty() { return 0 }

        match &haystack.find(&needle) {
            Some(i) => *i as i32,
            None => -1
        }
    }
}

let str = String::from("好");
println!("{}", str.len()); // This will print out 3

impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        // Get length of chars instead of bytes
        let (hay_len, needle_len) = (
            haystack.chars().count(),
            needle.chars().count()
        );

        // Collect string into `Vec<char>`
        let (hay_chars, needle_chars) = (
            haystack.chars().collect::<Vec<char>>(),
            needle.chars().collect::<Vec<char>>()
        );

        // The rest are same
        if needle_len == 0 { return 0 }
        else if needle_len > hay_len { return -1 }

        for i in 0..=hay_len - needle_len {
            if hay_chars[i..i + needle_len] == needle_chars {
                return i as i32;
            }
        }

        -1
    }
}

pub struct Node {
    pub val: i32,
    pub left: Option<Box<Node>>,
    pub right: Option<Box<Node>>
}

impl Node {
    pub fn new(val: i32) -> Self {
        Node { 
            val,
            left: None,
            right: None
        }
    }

    pub fn inorder_traversal(&self) {
        if let Some(left) = &self.left {
            left.inorder_traversal();
        }

        println!("{}", &self.val);

        if let Some(right) = &self.right {
            right.inorder_traversal();
        }
    }

    pub fn preorder_traversal(&self) {

        println!("{}", &self.val);

        if let Some(left) = &self.left {
            left.preorder_traversal();
        }

        if let Some(right) = &self.right {
            right.preorder_traversal();
        }
    }
}

pub fn rebuild_tree(inord_arr: &Vec<i32>, preord_arr: &Vec<i32>) -> Node {
        
    let root_val = preord_arr[0];
    let mut root = Node::new(root_val);

    // Find the index of root from inorder result
    let inord_arr_root_i = inord_arr
        .iter()
        .position(|&x| x == root_val)
        .unwrap();

    let inord_left_sub_len = inord_arr_root_i;

    if inord_left_sub_len == 1 {
        root.left = Some(Box::new(Node::new(inord_arr[0])));
    } else if inord_left_sub_len > 1 {
        let preord_left_sub_vec = preord_arr[1..inord_left_sub_len+1].to_vec();
        let inord_left_sub_vec = inord_arr[..inord_arr_root_i].to_vec();
        root.left = Some(
            Box::new(rebuild_tree(
                &inord_left_sub_vec,
                &preord_left_sub_vec
            ))
        );
    }

    let inord_right_sub_len = inord_arr.len() - inord_left_sub_len - 1;
    if inord_right_sub_len == 1 {
        root.right = Some(Box::new(Node::new(inord_arr[inord_arr_root_i + 1])));
    } else if inord_right_sub_len > 1 {
        let preord_right_sub_vec = preord_arr[1+inord_left_sub_len..].to_vec();
        let inord_right_sub_vec = inord_arr[inord_arr_root_i+1..].to_vec();
        root.right = Some(
            Box::new(rebuild_tree(
                &inord_right_sub_vec,
                &preord_right_sub_vec
            ))
        );
    }

    root
}

fn main() {
    let inord_vec = vec![1,2,3,4,5,6,7];
    let preord_vec = vec![5,2,1,4,3,6,7];
    let rebuild_tree_n = rebuild_tree(&inord_vec, &preord_vec);

    rebuild_tree_n.inorder_traversal(); // 1,2,3,4,5,6,7
    println!("--------");
    rebuild_tree_n.preorder_traversal(); // 5,2,1,4,3,6,7
}

use std::cmp::Ordering;

impl Solution {
    pub fn min_eating_speed(piles: Vec<i32>, h: i32) -> i32 {
        let mut sorted_piles = piles.clone();
        sorted_piles.sort();
        Solution::min_eating_speed_inner(
            &sorted_piles,
            h,
            1,
            *sorted_piles.last().unwrap()
        )
    }

    fn min_eating_speed_inner(piles: &Vec<i32>, h: i32, min: i32, max: i32) -> i32 {
        // return codition
        if piles.len() == 0 || min > max {
            return -1;
        }

        // speeds arr is [min..max]
        // so the mid speed is (min + max) / 2
        let mid = min + (max - min) / 2;

        // piles divides speed return spend time
        let time = Solution::count_eating_time(&piles, mid);

        // find the matched speed or continue go down to sub tree
        match time.cmp(&h) {
            // spend too much time to eat, speed up
            Ordering::Greater => Solution::min_eating_speed_inner(piles, h, mid + 1, max),
            // match, try to find a better (slower) speed
            _ => {
                let new_speed = Solution::min_eating_speed_inner(piles, h, min, mid - 1);

                if new_speed > 0 {
                    return new_speed;
                }
                mid
            }
        }
    }

    fn count_eating_time(piles: &Vec<i32>, speed: i32) -> i32 {
        // count the time to eat each pile and return sum
        let sum = piles
            .into_iter()
            .map(|pile| {
                if pile % speed > 0 {
                    return pile / speed + 1
                }
                return pile / speed
            })
            .sum();

        sum
    }
}

impl Solution {
    pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
        if nums.len() == 0 {return vec![-1,-1]}
        bst_search_index_rec(&nums, target, 0, (nums.len()-1) as i32)
    }  
}

fn bst_search_index_rec(arr: &Vec<i32>, val: i32, start_i: i32, end_i: i32) -> Vec<i32> {
    if start_i > end_i {
        return vec![-1, -1];
    }

    let mut result: Vec<i32> = vec![-1, -1];

    let mid_i = (start_i + end_i)/2;

    if val == arr[mid_i as usize] {
        result[0] = mid_i as i32;
        result[1] = mid_i as i32;
        
        let tmp_left_result = bst_search_index_rec(&arr, val, start_i, (mid_i-1) as i32);
        if tmp_left_result[0] != -1 {
            result[0] = tmp_left_result[0];
        }

        let tmp_right_result = bst_search_index_rec(&arr, val, (mid_i+1) as i32, end_i);
        if tmp_right_result[1] != -1 {
            result[1] = tmp_right_result[1];
        }

    } else if val < arr[mid_i as usize] {
        result = bst_search_index_rec(&arr, val, start_i, (mid_i - 1) as i32);
    } else if val > arr[mid_i as usize] {
        result = bst_search_index_rec(&arr, val, (mid_i + 1) as i32, end_i);
    }

    return result;
}

use std::cmp::Ordering; // Don't forget to import this

impl Solution {
    pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {

        Solution::bst_search_index_inner(&nums, target, 0, nums.len() as i32 - 1)
    }
    
    fn bst_search_index_inner(arr: &Vec<i32>, val: i32, start_i: i32, end_i: i32) -> Vec<i32> {
        // return condition
        if start_i > end_i || arr.len() == 0 {
            return vec![-1, -1];
        }

        // avoid overflows rather than simply (start_i + end_i) / 2
        let mid_i = start_i + (end_i - start_i) / 2;

        match val.cmp(&arr[mid_i as usize]) {
            Ordering::Less => Solution::bst_search_index_inner(&arr, val, start_i, mid_i - 1),
            Ordering::Greater => Solution::bst_search_index_inner(&arr, val, mid_i + 1, end_i),
            Ordering::Equal => {
                let l = Solution::bst_search_index_inner(arr, val, start_i, mid_i - 1);
                let r = Solution::bst_search_index_inner(arr, val, mid_i + 1, end_i);

                match (l[0], r[1]) {
                    (-1, -1) => vec![mid_i, mid_i],
                    (-1, new_r) => vec![mid_i, new_r],
                    (new_l, -1) => vec![new_l, mid_i],
                    (new_l, new_r) => vec![new_l, new_r]
                }
            }
        }
    }
    
}

let mut num_u32: u32 = 0;
num_u32 -= 1; // overflow

let mut num_i32 = i32::MIN; // -2147483648
num_i32 -= 1; // overflow

let mut num_i32 = i32::MIN + 1; // -2147483648 + 1

num_i32 = num_i32.checked_sub(1).unwrap_or(i32::MIN); // -2147483648

num_i32 = num_i32.checked_sub(1).unwrap_or(100); // 100
// Since it overflows, it will return the default value 
// that we give to unwrap_or which is 100 for this example