/*
In this sample program I demonstrate the following:

1. Implementing a shareable linked list.  That is, we want something like

   let m1 = cons(2,cons(4,cons(5,nil)));
   let m2 = cons(1,cdr(m1));

   The two lists m1 and m2 share a common tail.  Such structures are useful
   for .. implementing the stack environment for an interpreter.

   The sharing requires Rc (reference counter) pointers: a not-so-safe
   part of Rust; we have to be careful not to make the pointers cyclic.

2. Implementing an Iterator, a crucially important concept in Rust.

3. Using "interior mutability," a last-resort technique for circumventing
   the borrow checker.
*/
#![allow(dead_code, unused_variables)]
use std::rc::Rc;
use std::fmt;
use std::cell::{RefCell};  // for "interior mutability"

pub struct Cell<T> {
  item: T,
  next: List<T>,
}
pub enum List<T> {
  Nil,
  Node(Rc<Cell<T>>),
}
use List::*;   // without this line we'd have to write List::Nil, List::Node

pub fn cons<T>(x:T, m:&List<T>) -> List<T>
{
   match m {
     Nil => Node(Rc::new(Cell{item:x, next:Nil})),
     Node(rc) => Node(Rc::new(Cell{item:x, next:Node(Rc::clone(rc))})),
   }//match
}//cons

pub fn car<T>(m:&List<T>) -> Option<&T>
{
  match m {
    Nil => None,
    Node(rc) => Some(&rc.item),
  }//match
}//car

// zero-cost abstraction car
pub fn zar<T>(m:&List<T>) -> &T
{
  match m {
    Nil => panic!("no car in the garage"),  ///// PANIC!
    Node(rc) => &rc.item,
  }//match
}//zcar

pub fn cdr<T>(m:&List<T>) -> Option<&List<T>>
{
  match m {
    Nil => None,
    Node(rc) => Some(&rc.next),
  }//match
}

pub fn zdr<T>(m:&List<T>) -> &List<T>
{
  match m {
    Nil => m,                /////// change semantics, avoids panic
    Node(rc) => &rc.next,
  }//match
}//zcdr

// "pseudo oop" style  (so you can use the . notation)
impl<T> List<T>
{
  fn new() -> Self {  Nil  }  // "Self" refers to *this TYPE*
  
  fn len(&self) -> usize
  {  let mut current = self;
     let mut counter = 0;
     while let Node(rc) = current {
       counter += 1;
       current = &rc.next;
     }//while
     counter
  }//len: for better performance, create wrapper struct with size field.
}//impl List
 
//// implementing traits for List type:
impl<T> Default for List<T> {
  fn default() -> Self {Nil}
}

// describe how to print
impl<T: fmt::Display> fmt::Display for List<T> {  
  fn fmt(&self, f:&mut fmt::Formatter<'_>) -> fmt::Result 
  {
    let mut current = self;
    while let Node(rc) = current {
      write!(f,"{}, ",&rc.item)?;  // ?; is like monadic and_then (bind)
      current = &rc.next;
    }
    write!(f,"\n")    // returns final result
  }
}// impl Display

///////////////////////////////// Iterator implementation
pub struct ListIter<'lt,T> {
  current : &'lt List<T>
}//ListIter

impl<'lt,T> Iterator for ListIter<'lt,T> {
  type Item = &'lt T;
  fn next(&mut self) -> Option<Self::Item>
  {
    match self.current {
      Nil => None,
      Node(rc) => {
        self.current = &rc.next;
        Some(&rc.item)
      },
    }//match
  }//next
}// Iterator

impl<T> List<T> {
  pub fn iter<'lt>(&'lt self) -> ListIter<'lt,T>
  {
     ListIter { current : self }
  }
}// iter() impl for List

/// final trait:
impl<'lt, T> IntoIterator for &'lt List<T> {
  type Item = &'lt T;
  type IntoIter = ListIter<'lt,T>;
  fn into_iter(self) -> Self::IntoIter
  {
     self.iter()
  }
}//IntoIterator


fn main() {
  let primes = cons(2,&cons(3,&cons(5,&cons(7,&cons(11,&Nil)))));
  //println!("{}length {}",&primes,primes.len());
  println!("cadr: {}",zar(zdr(&primes)));
  println!("cddr: {}",zdr(zdr(&primes)));
  // create a share:
  let odds = cons(1,zdr(&primes));
  for x in primes.iter() { print!("{}, ",x); }  println!();
  for x in &odds { print!("{}, ",x); }  println!();
  
  println!("all primes are odd: {}", primes.iter().all(|x|x%2==1));
  println!("7 is prime: {}", primes.iter().any(|x|*x==7));
/*
Unlike Box, heap objects pointed to by Rc are not technically mutable, because
that would violate the most important rule of safe mutation: a mutable
reference cannot coexist with other references.  If we wish to modify objects
pointed to by Rc, we have to give up some of the compile-time guarantees
of Rust by moving the safety checks to runtime.  Of course, this also adds
runtime overhead.  This option is therefore less safe and less efficient.
Another option would be to use unsafe rust, which can retain the efficiency
but is .. unsafe.

The technique implemented here is called "interior mutability" which just
means that we're going to hide from the compiler the fact that we're going
to mutate something.  The key to this technique is a `RefCell`.  A RefCell
doesn't have to be declared 'mut' but we can mutate it by creating a
`RefMut` which to the compiler is not a mutable borrow, but it is...
*/

  let two = RefCell::new(2);    // not 'mut' but it is ... RefCell<i32>
  let three = RefCell::new(3);
  let five = RefCell::new(5);

  let m = cons(two,&cons(three,&cons(five,&Nil)));
  let m1 = cons(RefCell::new(1),zdr(&m)); // shared list  
  for refcell in &m {
    *refcell.borrow_mut() *= 10;  // borrow_mut returns a RefMut<i32>
  }
  for x in &m { print!("{}, ", &x.borrow()); }  println!();
  for x in &m1 { print!("{}, ", &x.borrow()); }  println!();
  let bar = zar(&m).borrow();  // .borrow returns a Ref<i32>
  //for r in &m { *r.borrow_mut() -= 5; };  // compiles but PANICS
  //println!("bar is {}", bar);  
}//main
/*
Uncommenting the last lines in main will result in runtime error:

thread 'main' panicked at sharedlist2.rs:169:20:
already borrowed: BorrowMutError

In keeping with the principles of compile-time memory safety, and of
zero overhead abstraction, interior mutability should be a last-resort
type of solution.  

Newcombers to Rust typically make the following mistakes:

  1. Over-reliance on calling .clone() to avoid ownership issues.
  2. Over-reliance on calling .unwrap() because of unfamiliarity with 
     monadic error handling and pattern matching.
  3. Over-reliance on RefCell to escape restrictions on mutation.

RefCell should only ever be used in conjunction with Rc, and only when
there's no other choice.
*/