pub struct SemaPlusPlus<T> {
    queue_and_cv: Arc<(Mutex<VecDeque<T>>, Condvar)>,
}

impl<T> SemaPlusPlus<T> {
    pub fn send(&self, message: T) {
        let (queue_lock, cv) = &*self.queue_and_cv;
        let mut queue = queue_lock.lock().unwrap();
        let queue_was_empty = queue.is_empty();
        queue.push_back(message);
        // if a queue is not empty, then another thread must have notified and main()
        // must be awake
        if queue_was_empty {
            cv.notify_all();
        }
    }

    pub fn recv(&self) -> T {
        let (queue_lock, cv) = &*self.queue_and_cv;
        // wait_while dereferences the guard and pass the protected data to the closure,
        // when the condition is true, it releases the lock and sleep until another thread
        // notify_all
        let mut queue = cv
            .wait_while(queue_lock.lock().unwrap(), |queue| queue.is_empty())
            .unwrap();
        queue.pop_front().unwrap()
    }
}

fn main() {
    let sem: SemaPlusPlus<String> = SemaPlusPlus::new();
    let mut handlers = Vec::new();
    for i in 0..NUM_THREADS {
        let sem_clone = sem.clone();
        let handle = thread::spawn(move || {
            rand_sleep();
            sem_clone.send(format!("thread {} just finished!", i))
        });
        handlers.push(handle);
    }
    // main is the only consumer of the queue,
    // it wakes up when some thread notify_all, locks the queue, consume the message
    // and release the lock until it is notified again
    for _ in 0..NUM_THREADS {
        println!("{}", sem.recv())
    }

    for handle in handlers {
        handle.join().unwrap();
    }
}

/// Factor the number while receiving numbers from stdin
fn main() {
    let (sender, receiver) = crossbeam_channel::unbounded();
    let mut threads = Vec::new();
    for _ in 0..num_cpus::get() {
        // The channel maintains a reference counter for senders and for receivers
        // when receiver.clone(), the receiver counter increments.
        let receiver = receiver.clone();
        threads.push(thread::spawn(move || {
            while let Ok(next_num) = receiver.recv() {
                factor_number(next_num);
            }
        }));
    }

    let stdin = std::io::stdin();
    for line in stdin.lock().lines() {
        let num = line.unwrap().parse::<u32>().unwrap();
        sender.send(num).expect("Cannot send to channel when there is no receiver");
    }

    // decrement the sender counter, when no sender, the channel is closed
    drop(sender);

    for thread in threads {
        thread.join().expect("panic");
    }
}

/* standard trait
trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}
*/

#[derive(Default)]
struct MyVec<T> {  // we cannot directly implement Iterator for MyVec<T> as it does not store internal states.
    vec: Vec<T>
}

struct MyVecIter<'a, T> {
    vec: &'a Vec<T>,
    position: usize,
}

impl<'a, T> Iterator for MyVecIter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.position < self.vec.len() {
            let item = &self.vec[self.position];
            self.position += 1;
            Some(item)
        } else {
            None
        }
    }
}

impl<T> MyVec<T> {
    fn iter(&self) -> MyVecIter<'_, T> {  // this does not consume MyIter
        MyVecIter {
            vec: &self.vec,
            position: 0,
        }
    }
}

impl<'a, T> IntoIterator for &'a MyVec<T> {  // this consumes MyIter
    type Item = &'a T;
    type IntoIter = MyVecIter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

// usage
let my_vec = MyVec::<i32>::default();
let mut my_vec_iter = my_vec.into_iter();
my_vec_iter.next();

impl From<i32> for MyType {}

impl From<String> for MyType {}

impl<T> MyTrait for Vec<T> where T: Display {}

impl<T> MyTrait for Vec<T> where T: Debug {}

fn static_dispatch(item: impl MyTrait) {}  // or static_dispatch<T: MyTrait>(item: T) {}

fn dynamic_dispatch(item: &dyn MyTrait) {}

pub struct DynamicLogger {
    writer: Box<dyn Write>
}

pub struct StaticLogger<W: Write> {
    writer: W
}

// usage
let file = File::create("dynamic_log.txt")?;
let dynamic_logger = DynamicLogger { writer: Box::new(file) };  // Users are forced to use dynamic dispatch

// Both works for static dispatch
let file = File::create("static_log.txt")?;
let logger = Logger { writer: file };

let file: Box<dyn Write> = Box::new(File::create("static_log.txt")?);
let logger = Logger { writer: file };

fn collect_to_map<T, S>(items: impl IntoIterator<Item = T>) -> HashMap<T, usize, S>
where
   HashMap<T, usize, S>: FromIterator<(T, usize)>
{
   items
       .into_iter()
       .enumerate()
       .map(|(i, item)| (item, i))
       .collect()
}

impl Debug for AnyIterable
where
    // the reference to Self implements IntoIterator for any lifetime 'a
    for<'a> &'a Self: IntoIterator,
    // the item (associated type in Self) produced by iterating over the reference to Self implement Debug
    // We cannnot write <&'a Self>::Item because the associated type Item only exists in IntoIterator
    for<'a> <&'a Self as IntoIterator>::Item: Debug,
{
    // since fmt signature does not allow lifetime annotation,
    // we need to specify "the reference implements the trait for any lifetime"
    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
        f.debug_list()  // formats items, e.g., [item1, item2]
            .entries(self) // iterates over self and debug-formatted each item
            .finish()
    }
}

#![feature(impl_trait_in_assoc_type)] // require nightly

#[derive(Default)]
struct MyVec<T> {
    vec: Vec<T>,
}

impl<T> IntoIterator for MyVec<T> {
    type Item = T;
    type IntoIter = impl Iterator<Item = Self::Item>; // existential type

    fn into_iter(self) -> Self::IntoIter {
        let mut vec = self.vec;
        let position = 0;
        std::iter::from_fn(move || {
            if position < vec.len() {
                let item = vec.remove(position); // consume vec
                Some(item)
            } else {
                None
            }
        })
    }
}

fn main() {
    let mut my_vec = MyVec::<i32>::default().into_iter();
    println!("{:?}", my_vec.next());
}

use std::{cell::RefCell, collections::HashMap, rc::Rc};

type List = Option<Rc<RefCell<ListNode>>>;

struct ListNode {
    key: i32,
    value: i32,
    prev: List,
    next: List,
}

struct LRUCache {
    head: List,
    tail: List,
    data: HashMap<i32, Rc<RefCell<ListNode>>>,
    capacity: usize,
}

impl LRUCache {
    fn new(capacity: i32) -> Self {
        Self {
            head: None,
            tail: None,
            data: HashMap::new(),
            capacity: capacity as usize,
        }
    }

    fn move_to_front(&mut self, node: Rc<RefCell<ListNode>>) {
        // early return if the node is already the head
        if let Some(head) = &self.head {
            if Rc::ptr_eq(head, &node) {
                return;
            }
        }

        let prev = node.borrow().prev.clone();
        let next = node.borrow().next.clone();

        match (prev.as_ref(), next.as_ref()) {
            (None, None) => {
                // insert a new node only modifies the head,
                // the rest of the list is untouched.
            }
            (Some(prev), None) => {
                // get the tail node
                prev.borrow_mut().next = None;
                self.tail = Some(Rc::clone(prev));
            }
            (None, Some(_)) => {
                // get the head node is already handled
                return;
            }
            (Some(prev), Some(next)) => {
                // get a node in the middle of a list,
                // connect its prev and next
                prev.borrow_mut().next = Some(Rc::clone(next));
                next.borrow_mut().prev = Some(Rc::clone(prev));
            }
        }

        // update node to be the new head
        if let Some(old_head) = &self.head {
            node.borrow_mut().next = Some(Rc::clone(old_head));
            old_head.borrow_mut().prev = Some(Rc::clone(&node));
        } else {
            // insert a node to the empty list
            self.tail = Some(Rc::clone(&node));
        }
        node.borrow_mut().prev = None;
        self.head = Some(node);
    }

    fn get(&mut self, key: i32) -> i32 {
        let mut result = -1;
        if let Some(node) = self.data.get(&key) {
            result = node.borrow().value;
            self.move_to_front(Rc::clone(node));
        }
        result
    }

    fn put(&mut self, key: i32, value: i32) {
        if let Some(node) = self.data.get(&key) {
            let node = Rc::clone(node);
            node.borrow_mut().value = value;
            self.move_to_front(node);
        } else {
            let new_node = Rc::new(RefCell::new(ListNode {
                key,
                value,
                prev: None,
                next: None,
            }));
            // evict the tail node
            if self.data.len() >= self.capacity {
                if let Some(tail) = self.tail.take() {
                    // cannot simply take the prev as it breaks the list?
                    let prev = tail.borrow().prev.clone();
                    self.data.remove(&tail.borrow().key);
                    if let Some(prev) = prev {
                        prev.borrow_mut().next = None;
                        self.tail = Some(prev);
                    } else {
                        self.head = None;
                        self.tail = None;
                    }
                }
            }
            self.data.insert(key, Rc::clone(&new_node));
            self.move_to_front(new_node);
        }
    }
}