// Memory-safe Linked lists with std::shared_ptr (since C++ 11)

// std::shared_ptr uses a reference counter: unlike unique_ptr, there
// can be multiple shared_ptr's pointing to the same data. The data
// is deallocated when the reference counter decreases to zero.  Each
// share increases the counter.  This way of memory mangagement is quite
// common and is found in Swift and other languages.  But it's not
// capable of completely freeing the programmer from worrying about memory:
// cyclic pointers will never decrease the count, requiring the programmer
// to identify some pointers as "weak" (std:weak_ptr).  But this can be
// tricky, and in the worst case requires the construction of spanning tree.

#include<iostream>
#include<memory>
using namespace std;

/////////// linked list implementation using std::shared_ptr smart pointer
class scell
{
public:
  int car;
  shared_ptr<scell> cdr;  // shared pointer to another scell
  scell(int a, shared_ptr<scell> b)
  {
    car = a;
    cdr = b;   // automatically increases reference count
  }//constructor
};
  
shared_ptr<scell> scons(int a, shared_ptr<scell> b)
{
  return make_shared<scell>(a,b); // replaces new scell(a,b)
}

void sprint(shared_ptr<scell> slist)  // don't use &slist
{
  while (slist)
    {
      cout << slist->car << "(" << slist.use_count() << ") ";
      slist = slist->cdr;
    }
  cout << endl;
}//sprint

void noleak(shared_ptr<scell> L)
{
  shared_ptr<scell> R = scons(L->cdr->car+100,scons(200,scons(400,NULL)));
  L->cdr = R;  // will the original L->cdr be leaked?
}


int main()
{
  //// testing shared_ptr implementation
  shared_ptr<scell> A = scons(1,scons(2,scons(4,scons(8,scons(16,NULL)))));
  sprint(A);
  cout << A.use_count() << "," << A->cdr.use_count() << endl;
  shared_ptr<scell> B = scons(0, A->cdr->cdr); //not possible with unique_ptr
  // delete(A);  // do not call - won't compile
  sprint(B);

  cout<< "leaking? ...\n";
  for(int i=0;i<1000000000;i++) noleak(A); // smart pointer version
  
  return 0;
}//main

/// it may look like that shared_ptr is easier to use than unique_ptr but...

class dcell // doubly linked list
{
public:
  int car;
  shared_ptr<dcell> next; // next cell (cdr)
  weak_ptr<dcell> previous; // previous cell
  dcell(int x, shared_ptr<dcell> cdr, shared_ptr<dcell> rdc)
  {
    car=x; next=cdr;
    previous=rdc; // assigning shared_ptr to weak_ptr is ok
  }
  // function to get the first element of the list using the back pointer
  int first()
  {
    weak_ptr<dcell> w = previous;
    while (w.lock()->previous.lock()) { w = w.lock()->previous; }
    return w.lock()->car;  //.lock() converts weak_ptr to a shared_ptr
  } // must use .lock() before dereferening weak_ptr
  
};


class graphnode  // directed graph, possibly cyclic
{
  int nodeid;
  shared_ptr<graphnode> neighbors[]; // pointers to neighboring nodes....
};

// Which one to make weak?  Need to generate spanning tree (in your head).
// Make too few links weak: still get memory leaks
// Make too many links weak: get dangling pointers, deallocate legit memory.

/*
Verdict: shared_ptr is needed if multiple pointers must point to the
same data, but memory safety is not guaranteed if one shared pointer is
reachable from another.  Thus, this technique cannot provide the same
level of memory safety as a garbage collector.  But it may be the best
that we can do, unless we disallow sharing.  Even Rust may have to relay
on reference counters at times.  Python uses reference counting, but also
uses a full-fledged garbage collector when memory usage becomes high.

In C++, there is also no guarantee that shared_ptr and regular pointers
aren't mixed, which would make situation even worse than using just
regular pointers alone.
*/