#include<iostream>
#include<vector>   
using namespace std;
// Simulation of Rust std::cell::{RefCell,Ref,RefMut}
// Academic experiment by Chuck Liang, Hofstra University.
// This program is not perfect and is only used to illustrate concepts.

bool trace = 0;
unsigned int traceid = 0; // global counter for tracing

// macro from Stack Overflow (Konrad Rudolph):
#ifndef NDEBUG
#   define ASSERT(condition, message) \
    do { \
        if (! (condition)) { \
	  std::cerr << "Assertion `" #condition "` failed in " << __FILE__ \
                      << " line " << __LINE__ << ": " << message << std::endl; \
	  std::terminate();						\
        } \
    } while (false)
#else
#   define ASSERT(condition, message) do { } while (false)
#endif
// dummy while loop allows ; to be placed at end of macro

template<typename T>  // for forward reference (back to the 80s)
class Ref;
template<typename T>
class RefMut;

template<typename T>
class RefCell
{
private:  // BS, but we'll pretend...
  T* evp;  // pointer to the encapsulated value, always on heap
  bool owned; // determine if v is owned by this refcell
  // should replace with hashset for better performance  
  vector<Ref<T>*> imbv;   // immutable borrows, num = imbv.size()
  vector<RefMut<T>*> mbv; // mutable borrows, allow multiples for experiment
  void invalidate_borrows(bool clear=0)  // invalidate but don't deallocate
  {
    if (!owned) return;
    for(int i=0;i<imbv.size();i++) // like in Observer design pattern
      if (imbv[i]) imbv[i]->invalidate();
    for(int i=0;i<mbv.size();i++)
      if (mbv[i]) mbv[i]->invalidate();
    //if (owned) delete(evp);  // called outside
  }
  void deleteborrows()
  {
    if (!owned) return;  // it's for the owner to delete refs
    for(int i=0;i<imbv.size();i++) 
      if (imbv[i]) delete(imbv[i]);
    for(int i=0;i<mbv.size();i++)
      if (mbv[i]) delete(mbv[i]);
    imbv.clear();  mbv.clear();    
  }
  
  friend class Ref<T>; friend class RefMut<T>;  //friends have access to above
public:
  RefCell() { owned=0; }
  RefCell(T* p, bool w=0) { evp=p; owned=w; }
  RefCell(T x)  {
    evp = new T(x);  // always allocate on stack
    owned = 1;
  }//constructor
  ~RefCell()  {
    if (trace) cout << "RefCell destructor called on heap addr " << evp <<
		 /*" val=" << *evp <<*/ " owned=" << owned << endl;
    if (owned==1 && evp!=NULL) { owned=0;  delete(evp); }
    deleteborrows();
  }//destructor

  bool owner() { return owned; }
  
  Ref<T>& borrow()
  {
    ASSERT(owned==1, "can't borrow moved object");
    ASSERT (mbv.size()==0, "mutable borrow already exists");
    // can't get it to work without heap-allocating it
    Ref<T> *bp = new Ref<T>(this,imbv.size());
    imbv.push_back(bp);
    /*Ref<T> &b = *(imbv[imbv.size()-1]);
    b.makesure();
    return b;*/
    return *imbv[imbv.size()-1]; 
  }//borrow

  RefMut<T>& borrow_mut()
  {
    ASSERT(owned==1, "can't borrowed moved object");
    ASSERT (mbv.size()==0, "mutable borrow already exists");
    invalidate_borrows();
    RefMut<T> *bp = new RefMut<T>(this,mbv.size());
    mbv.push_back(bp);
    return *mbv[mbv.size()-1];
  }

  // overloaded operators:  (deref coercion)
  T operator *()  // return by copy, read only access
  {
    ASSERT(owned==1,"data has moved");
    return *evp;
  }
    //Defining copy constructor with non-const argument.  why not?
  RefCell(RefCell<T>& rc) // copy constructor called when passed to function
  { if (trace) cout << "copy constructor called." << endl; cout.flush();
    ASSERT(rc.owned==1, "copying object already moved");
    //if (owned) {invalidate_borrows();  delete(evp);} 
    evp = rc.evp;
    imbv = rc.imbv;  mbv = rc.mbv; // copy vectors and clear
    imbv.clear();  mbv.clear();
    owned = 1;
    rc.invalidate_borrows();
    rc.owned = 0;
  }  //copy constructor

  // tests show the above copy constructor is not called when
  // using the assignment operator directly.
  T operator =(RefCell<T>& rc)  // overload assignment operator
  {
    if (trace) cout << "=copy, moving " << evp << endl;  
    ASSERT(rc.owned, "Object already moved");
    if (owned==1)
      {invalidate_borrows();  if (evp!=NULL) delete(evp);}
    evp = rc.evp;
    owned = 1;
    rc.owned = 0;  // comment out for duplicate delete (fun!)
    rc.invalidate_borrows();
    imbv = rc.imbv;  mbv = rc.mbv; // copy vectors and clear
    imbv.clear();  mbv.clear();
    return *evp;
 }// operator=
};// Refcell

  
// immutable references (superclass of mutable references)
template<typename T>
class Ref
{
protected:
  RefCell<T>* refc;
  bool valid;
  int index;  // index into refc vectors
  bool assured;
  void invalidate() {valid=0;}  
  void makesure(bool imm=1)
  { if (!assured) {
      if (imm) refc->imbv[index] =this;
      else refc->mbv[index] =(RefMut<T>*)this;
      assured=1;
      }
    if (!refc->owned) invalidate();
  }// makesure - because of copies created
  friend class RefCell<T>;
public:
  Ref(RefCell<T>* r, int i)  {
    refc =r;
    valid = 1;
    index = i;
    assured = 0;
  }//constructor
  //  ~Ref()  {  }
      
  T operator *()  // return value - read only
  { makesure();
    ASSERT(valid,"Reference no longer valid");
    return *(refc->evp);
  }
  T* operator ->()  
  { makesure();
    ASSERT(valid,"Reference no longer valid");
    return refc->evp;
  }
};

// mutable references as a subclass
template<typename T>
class RefMut : public Ref<T> 
{protected:
  using Ref<T>::refc;
  using Ref<T>::valid;
  using Ref<T>::index;
  using Ref<T>::assured;
  using Ref<T>::invalidate;
  using Ref<T>::makesure;
  friend class RefCell<T>;  
public:  
  RefMut(RefCell<T>* r, int i) : Ref<T>(r,i) { /*makesure(0);*/ }
  //  ~RefMut()  { }
  T& operator *() // overrides statically
  { makesure(0);
    ASSERT(valid,"Referenced value has moved");
    return *(refc->evp);
    //return *(*refc);
  }
  T operator +() // result must be its operand?
  { makesure(0);
    ASSERT(valid,"Referenced value has moved");
    return *(refc->evp); // make sure * is on cons*, not on RefCell*
    //    return +(*refc);  // *refc is passed to + operator: copy made
  }  
  T* operator ->()
  { makesure(0);
    ASSERT(valid,"Reference no longer valid");
    return refc->evp;
    //   return  -(*refc);
  }
  T*& operator -()  // read/write access to evp pointer in refcell
  { makesure(0);
    ASSERT(valid,"Reference no longer valid");
    return refc->evp;
    //return  -(*refc);  // this creates a temp but was dealloced
  }
};  // RefMut

void f(RefCell<int> rc) 
{
  // Takes ownership of value in rc via copy constructor (auto-called)
  cout << *rc << endl;
  //  rc deallocated here, like in Rust
}
void /*RefCell<int>*/ g(RefCell<int>& rc) 
{
  // does not take ownership
  RefCell<int> l = rc; // until declare calls copy constructor
  RefMut<int> lm = l.borrow_mut();
  *lm = 990;
  cout << *lm << endl;
  //return l; //don't try; get compiler error about illegal lvalue
  rc = l;  // change object ref by overloaded = copier
}

class cell;
void listtest();
void listtest2();

///////////////// MAIN /////////////////////
int main(int argc, char* argv[])
{ if (argc>1) trace=1;
  RefCell<int> c(10);
  //RefCell<int> c2 = c; // copy constructor called, transfers ownership
  Ref<int> rc = c.borrow(); // add * here? doesn't make a difference
  cout << "1: " << *rc << endl;
  //*rc = 19; // doesn't compile since *rc not allowed as lvalue

  RefMut<int> mrc = c.borrow_mut();
  *mrc = 20;
  cout << "2: " << *mrc << " and " << *c << endl;

  //Ref<int> rc2 = c.borrow();  // assertion worked
  //RefMut<int> mc2 = c.borrow_mut();  // assertion worked  
  //cout << "3: " << *rc << endl;  // assertion worked again, rc not valid

  RefCell<int> d; // if do =c; here, will call copy constructor
  d = c; // calls overloaded = operator, NOT the copy constructor
  //cout << *mrc << endl;  // assertion: mrc no longer valid
  
  cout << "4: " << *d << endl;
  //cout << "c: " << *c << endl;    //assertion worked
  //cout << "6: " << *rc << endl;  // assert worked, rc invalidated
  //*mrc = 40;  //failure because owner moved, so far so good...

  // move when c is passed to a function
  if (trace) cout << "about to call f\n";
  f(d); // tansfer ownership? yes
  if (trace) cout << "returned from f\n";
  //cout << *d << endl;  // assertion worked (d moved to f)
  if (trace) cout << "about to call g\n";
  RefCell<int> e(100);
  g(e);  // g takes ownership and gives it back through ref assignment
  if (trace) cout << "returned from g\n";      
  cout << *e << endl;  // e was changed by g, and ownership returned

  listtest();
  return 0;
}//main
///////////////// MAIN /////////////////////

class cons  // basic linked list class for experiment
{
 public:
  int car;
  cons *cdr;  
  cons(int a, cons* b) {car=a; cdr=b;}
  ~cons()
  {  
    if (trace) {
       cout << "deallocating list with car " << car << " cdr " << cdr << endl;
       cout.flush();
    }
    if (cdr!=NULL) delete(cdr); // not efficient but ok for this experiment
  }// destructor
  void print()                            
  {
    for (cons* i=this;i!=NULL;i=i->cdr) cout<< i->car << " ";
    cout << endl;
  }
};//cons class for linked lists


// We don't really need Ref and RefMut in C++ because we can just
// call by reference and distinguish between const and non-const
// params. But that doesn't impose Rust borrowing rules.  To simulate
// that accurately, we need to create borrows and pass them by
// reference.  RefCell itself should only be passed via our copy
// constructor, which transfers ownership.

void push(int x, RefMut<cons>& mutb)
{
  -mutb = new cons(x,-mutb);
}
int pop(RefMut<cons>& rm)
{
  int ax = rm->car;     
  -rm = rm->cdr;   // destructive assignment to encapsulated pointer
  //-rm = new cons(-1,NULL); // Uncomment if you like memory leaks
  return ax;       // *rm will return cons, but -rm returns cons*&
}

void consume(RefCell<cons> M) // move
{
  Ref<cons> rm = M.borrow();
  rm->print();
}

void listtest()
{
  cons* m = new cons(2,new cons(4,new cons(6,NULL)));
  RefCell<cons> L(m,1); // take ownership, sole responsibility for dealloc
  RefMut<cons> rmut = L.borrow_mut();  // create mutable borrow
  push(1,rmut);
  push(3,rmut);
  rmut->print();   // ok
  //(+rmut).print(); // core dump - temporary created => 2x delete
  (*rmut).print(); // ok, it's just + that causes problems (return type)
  cout << pop(rmut) << endl;
  cout << pop(rmut) << endl;
  push(100,rmut);
  cout << pop(rmut) << endl;
  push(200,rmut);  
  (*(-rmut)).print(); // also ok: the deref * is on cons*, not on RefCell*
}