#include<iostream>
#include<vector>   
using namespace std;
// Simulation of Rust std::cell::{RefCell,Ref,RefMut}
// Academic experiment by Chuck Liang, Hofstra University

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

// 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, multiples for experiment
  void invalidate_borrows()
  {
    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
    imbv.clear();  mbv.clear();
  }
  void move()
  {
    if (owned==1) { invalidate_borrows(); owned=0; }
  }
  void return_borrowed(int index)
  {
    if (owned!=1) return;
    else imbv.erase(imbv.begin()+index,imbv.begin()+index+1);
  }
  void return_borrowedmut(int index)
  {
    if (owned!=1) return;
    else mbv.erase(mbv.begin()+index,mbv.begin()+index+1);    
  }  
  friend class Ref<T>; friend class RefMut<T>;  //friends have access to above
public:
  RefCell() { owned=0; }
  //  RefCell();
  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) { move();  delete(evp); }
  }//destructor

  bool owner() { return owned; }
  
  Ref<T>& borrow()
  {
    ASSERT(owned==1, "can't borrow moved object");
    ASSERT (mbv.size()==0, "mutable borrow already exists");
    // must be heap allocated
    Ref<T> *bp = new Ref<T>(this,imbv.size());
    //Ref<T> b(this,imbv.size());
    imbv.push_back(bp);
    return *(imbv[imbv.size()-1]);
  }
  void makesure(Ref<T>* r, int i)  // shouldn't need this, don't know why
  {  imbv[i] = r;  }
  void makesuremut(RefMut<T>* r, int i) // shouldn't need this, don't know why
  {    mbv[i] = r;  }

  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 && evp!=NULL) {invalidate_borrows();  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;
  friend class RefCell<T>;
public:
  Ref(RefCell<T>* r, int i)  {
    refc =r;
    valid = 1;
    index = i;
    assured = 0;
  }//constructor
  ~Ref()
  {
    if (refc && valid) refc->return_borrowed(index);
  }
  void invalidate() {valid=0;}

  T operator *()  // return value - read only
  {
    if (!assured) {refc->makesure(this,index); assured=1;}
    ASSERT(valid,"Reference no longer valid");
    return *(refc->evp);
    //return  +(*refc);  // make sure it's a copy, not mutable
  }
  T* operator -()  // return pointer
  {
    if (!assured) {refc->makesure(this,index); assured=1;}
    ASSERT(valid,"Reference no longer valid");
    return refc->evp;
  }
  T* operator ->()  
  {
    if (!assured) {refc->makesure(this,index); assured=1;}
    ASSERT(valid,"Reference no longer valid");
    return refc->evp;
  }
};

// mutable references as a subclass
template<typename T>
class RefMut : public Ref<T> 
{
  /*
private:
  RefCell<T>* refc;
  bool valid;
  int index;  // index into refc vectors
  bool assured;  
  //  friend class RefCell<T>;  
  //public:
  void invalidate() {valid=0;}
  friend class RefCell<T>;
  */
protected:
  using Ref<T>::refc;
  using Ref<T>::valid;
  using Ref<T>::index;
  using Ref<T>::assured;      
  friend class RefCell<T>;  
public:  
  RefMut(RefCell<T>* r, int i) : Ref<T>(r,i) {}
  ~RefMut()  {
    if (refc && valid) refc->return_borrowedmut(index);
    valid=0;
  }//destructor

  T& operator *() // overrides statically
  {
    if (!assured) {refc->makesuremut(this,index); assured=1;}    
    ASSERT(valid,"Referenced value has moved");
    return *(refc->evp);
    //return *(*refc);
  }
  T operator +() // result must be its operand?
  {
    if (!assured) {refc->makesuremut(this,index); assured=1;}        
    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 ->()
  {
    if (!assured) {refc->makesuremut(this,index); assured=1;}        
    ASSERT(valid,"Reference no longer valid");
    return refc->evp;
    //   return  -(*refc);
  }
  T*& operator -()  // read/write access to evp pointer in refcell
  {
    if (!assured) {refc->makesuremut(this,index); assured=1;}        
    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
  //*l = 500;
  cout << *l << endl;  
  //return l; //don't try; get compiler error about illegal lvalue
  rc = l;  // pass new object back by overloaded = copier
}

class cell;
void listtest();

int main(int argc, char* argv[])
{ if (argc>1) trace=1;
  RefCell<int> c(10);
  //RefCell<int> c2 = c; // copy constructor called
  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(0);

  d = c; // calls overloaded = operator, NOT the copy constructor
  //cout << *mrc << endl;
  
  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...

  // can't simulate 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 owned==1
  if (trace) cout << "about to call g\n";
  RefCell<int> e(100);
  g(e);
  cout << *e << endl;
  if (trace) cout << "returned from g\n";      

  listtest();
  
  return 0;
}//main

// try a more cenventional list, wrap whole list in RefCell:

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*
}

/*
//  More agreesive use of Refs, but doesn't quite work...
class icell
{
public:
  int item;
  RefCell<icell> next;   // end of list designated by non-owned icell with NULL
  icell(icell& c):next(NULL,0)  { item=c.item;  next=c.next; } 
  icell(int a, RefCell<icell> b) : next(NULL,0) // strange but works
  { item=a; next=b; }
  // default destructor should be enough with RefCell implementation
  void print()
  {
    icell* current = this;
    while (current!=NULL)
      {
	cout << item << " ";
	current = -(current->next);
      }
    cout << endl;
  }//print
};

RefCell<icell> cons(int x, RefCell<icell> &t) 
{
  icell* cp = new icell(x,t);
  RefCell<icell> nc(cp,1); // create icell with ownership
  return nc;
}

int car(RefCell<icell>& rcell)
{
  return rcell->item;  // -> overloaded (deref coercion in Rust)
}
RefCell<icell>& cdr(RefCell<icell>& rcell)
{
  return rcell->next;
}

void push(int x, RefMut<icell> &t) // destructive cons
{
  //if (trace) cout << "here3\n";      
//  icell* newcell = new icell(x,*t.refc);  // copy constructor should copy
//if (trace) cout << "here4\n";        
  //*t = newcell; 
}// doesn't work yet

  //RefCell<icell> m2 = cons(2,m);  // lvalue problem
  //push(2,m);  // m moved after first push
  //  push(2,rm);
  //pushon(2,&m);
  //m->print();

  */