/*  *** CRITICAL NOTES ON MEMORY MANAGEMENT IN MODERN C++ ***  */

#include<iostream>
#include<cstring>
#include<vector>
#include<memory>     /* requires -std=c++14 */
#include<concepts>   /* requires -std=c++20 */
using namespace std;
/*
  A smart pointer is a class/struct designed to encapsulate the management
of resources, including heap-allocated memory.  I will explain how to use 
them first, then describe what they are underneath.

Let's start with reviewing regular (raw) pointers and how they work:

int x; 
int *px = &x;         // px holds the memory address of x ("pointer to x")
int *mx = new int(1); // allocates an integer on the heap, returns a pointer
int *qx = px;         // multiple pointers can point to the same location. 
*qx += 1;             // de-references qx and assign it a value.
cout << *qx << *px << x;  // prints 222, *qx dereferences qx, refers to x
mx = new int(2);      // pointers can change where they're pointing to

There are no restrictions to where in memory (heap or stack) that raw
pointers can point to.  There are also no restrictions to how many
pointers are pointing to the same data, and there are no restrictions
to changing a pointer to point somewhere else.  These lack of
restrictions mean that we can get a variety of memory errors, including:

 o Returning a dangling pointer to a value that will be popped from the stack
 o Reassigning a pointer to heap to point somewhere else (memory leak)
 o Deleting the wrong data, or deleting too early
 o Deleting the same memory twice
 o Deleting memory not on the heap.

The following function contains many of these errors, yet IT COMPILES.
Only warnings for a few obvious errors can be expected (for `delete y`):
*/
int* verybad() {
  int x = 1;  // 1 allocated on stack
  int *y = new int(2); // 2 allocated on heap
  y = &x; // reassigns y to point to x on stack (memory leak)
  delete y; // deletes stack-allocated data, x will be deleted twice
  return y;  // returns dangling pointer
} // function with lots of memory errors but only one compiler warning

/*
When software consist of thousands of lines of code, it will be difficult 
even for experienced programmers to keep track of all raw pointers in the
code and make sure that these errors are avoided.  This is a main weakness
of programming in traditional C/C++.


   ********    std:unique_ptr   and   std:make_unique   *********

Although the idea of smart pointers originated in the 1990's, modern
C++ has been retooled to make them centerpiece.  New, general solutions 
to memory management were introduced in 2011 and 2014.  Once you
#include<memory> you will have access to a class std::unique_ptr and a
special operation/function std::make_unique.  Unique pointers
(unique_ptr) replace raw pointers and make_unique replaces the 'new'
operation.

unique_ptr<int> y = make_unique<int>(2); // replaces int* y= new int(2);
cout << *y; // prints 2, the * operator also dereferences unique pointers

Unique pointers are demonstrated in the following function, which allocates
two arrays of integers on the heap but contains no memory leaks or other
memory errors:
*/
void notbad() {
  unique_ptr<int[]> A = make_unique<int[]>(10); //allocates int[10] on heap
  for(int i=0;i<10;i++) A[i] = 10*i;  // use A like a "normal" pointer
  unique_ptr<int[]> B = make_unique<int[]>(20);
  for(int i=0;i<20;i++) B[i] = 20-i;
  //A = B;  not allowed as it destroys uniqueness (won't compile)
  A = move(B); // transfer of ownership
}//leaktest

/*
Please note that make_unique<int>(10) creates an integer with value 10
while make_unique<int[]>(10) creates an array of 10 integers.

  A unique_ptr is a "smart" pointer because, unlike raw pointers, it
tries to respect the rules of *lifetime* and *ownership*

           ********    LIFETIME AND OWNERSHIP    *********             

The lifetime of a value is how long it's guaranteed to stay in the
same location in memory. If the something is allocated globally, then its
lifetime is 'static', meaning that it's valid for the entire duration
of the program. The lifetime of something allocated on the stack ends
when it's popped off from the stack. The lifetime of something
allocated on the heap ends when delete is called on a pointer pointing
to it.  A lifetime can also end when data is *moved*.

A unique_ptr *owns* the data that it points to.  As the name suggests,
this ownership is intended to be exclusive: no other unique_ptr can
point to the same data.  In contrast, a raw pointer does not "own" the
data that it points to because it's not necessarily unique.  A 
unique_ptr is *uniquely responsible for managing the data that it
points to.* A unique_ptr is intended to only point to heap-allocated
data, never to global or stack-allocated data, because such data do
not require special management.  

A unique_ptr is itself a struct that's allocated on the stack or heap.
A piece of data owned by a unique_ptr cannot outlive the unique_ptr:
once the unique_ptr is deallocated, the data it owns is also
deallocated.  A unique_ptr should never be created on the heap with
'new', only with 'make_unique': 'new' returns a raw pointer while
make_unique returns a unique_ptr.  NEVER CALL delete on a unique_ptr:
delete can only be called on raw pointers.

The purpose of unique_ptr is to *equalize* the lifetimes of the pointer
and the data that it points to.  In addition, unique_ptr implements 
a *move semantics*:

           ********    TRANSFER OF OWNERSHIP    *********                  

You cannot assign a unique_ptr to another unique_ptr as that would violate
uniqueness by making a copy of the same pointer:

  unique_ptr<int> y = make_unique<int>(2);
  unique_ptr<int> z = make_unique<int>(3);
  //x = y;  // won't compile
  x = move(y); // TRANSFERS OWNERSHIP, data MOVED

Instead of x=y, which won't compile, you must call x=move(y);  During
such a "move assignment", the following occurs:

     1. the data that x previous owned is deallocated: 
        the lifetime of that data ends.
     2. x is now pointing to the data that y pointed to.
     3. y is set to nullptr: y now owns nothing

This sequence of events define the "move semantics" of unique_ptr.
Ownership is transferred from y to x: the data cannot be owned by two
unique pointers, and a unique pointer can only own one location at a
time.  After such an assignment, the unique pointer that was "moved"
*should* no longer be referred to, as it is now equivalent to a nullptr:
you will get a runtime memory error (segmentation fault and/or
coredump) if you continue to use y after the move: its lifetime has
ended.  However, y as a variable is still declared and you can assign
to it a new unique_ptr (give it new life).

Transfer of ownership also occurs when a unique_ptr is passed to a 
function and when a unqiue_ptr is returned from a function:
*/
unique_ptr<int> u1(unique_ptr<int> p) {
  // do stuff with p...
  *p += 1;
  unique_ptr<int> q = make_unique<int>(3);
  return q;
}
void q1() {
 unique_ptr<int> y = make_unique<int>(2);
 unique_ptr<int> z = u1(move(y)); 
 cout << *z; // should print 3
 cout << *y; // runtime memory error: y has MOVED! (lifetime ended).
}
/*      
When move(y) is passed to u1, the local unique pointer p, which is allocated
on the u1 function's runtime stack frame, now owns the data previously owned
by y.  When u1 returns, p is deallocated by being popped from the stack, and
at that point, the heap data it owns is also deallocated.  We cannot use it
again from the calling function.  However, a function can also transfer back
a locally owned memory location by returning a unique pointer. 

Note that "move" was also necessary when passing a unique pointer to a 
function, though not when assigning to a unique pointer returned from a 
function, because such a value is already a temporary that will die if 
not assigned to something (it's an R-value).  This also applies to the 
unique_ptr returned by make_unique.

Here's another example of unique pointers, this time pointing to structs.
*/
struct point {
  int x;
  int y;
  point(int a, int b) {x=a;y=b;}
};
unique_ptr<int> notbadatall() {
  unique_ptr<point> p1 = make_unique<point>(3,5);
  cout << p1->x << "," << p1->y << endl;  // prints 3,5
  p1 = make_unique<point>(8,2);
  cout << p1->x << "," << p1->y << endl; // and no leak  
  unique_ptr<point> p2 = nullptr;
  if (p2) cout << p2->x << "," << p2->y << endl; // and no leak
  p2 = move(p1); // transfer of ownership
  //cout << "p1->: " << p1->x << endl; // will crash, p1 now nullptr
  if (p2) cout << p2->x << "," << p2->y << endl; // and no leak  
  return make_unique<int>(99); // returns unique_ptr to 99 on heap
}//notbadatall

/*
In order to take full advantage of smart pointers, you should **not mix 
them with raw pointers**.
*/
unique_ptr<int> stillbad() {
  int x;
  int A[5];
  unique_ptr<int> p1(&x); // creating a unique_ptr from a raw pointer
  unique_ptr<int> p2(&x); // duplicate pointer to x ("uniquely not unique")
  unique_ptr<int> p3(A);  // raw pointer not pointing to heap!
  int* px = p2.get();     // gets the raw pointer inside the unique pointer
  unique_ptr<int>* pu = &p3; // LOL!  way to make things worse!
  return p3;              // uniquely dangling ..
}
/*
The problem with the above function is that unique pointers can lose
all their effectiveness when they're mixed with raw pointers.  The
expressions '&x' and 'A' are both raw pointers.  The unique pointers
p1 and p2 are not uniquely pointing to the same x, and they're
pointing to stack allocated data, not heap-allocated data.  If you
return such unique pointer, you'll still get a dangling pointer.  You
can even force a unique pointer to "give it up" with the call to
.get().  Mixing raw pointers with smart pointers can entirely defeat
their purpose and make matters even worse than before they were invented.

 *****  unique_ptr must be used in conjunction with make_unique  *****

ALWAYS CREATE UNIQUE POINTERS WITH make_unique, not by giving its
constructor a raw pointer like in the stillbad function.  make_unique
always allocates memory on the heap, not the stack, so you can't
possibly force a unique_ptr to point to stack memory, which it cannot
"own".  

        **** NEVER USE RAW POINTERS TO POINT TO HEAP ****

***The recommended way to allocate memory on the heap in modern C++ is to
create a unique_ptr with make_unique.***  But since C++ doesn't enforce
this rule, you will just have to observe it yourself.

  EASIER SAID THAN DONE ...

  Observing the protocol of using unique_ptr/make_unique exclusively
can be rather restrictive at times, and can change significantly your
approach to writing programs.  Sometimes, you may need to call
built-in functions such as 'memset' and 'memcpy' from old C, which
require raw pointers to be passed to them.  Using these functions will
require you to "get" the raw pointer from inside the unique_ptr, which
is why C++ provides such an operation.  C++ is an "expert" programming
language, which means it never stops you from doing anything.  It's 
entirely up to you to be as careful as possible when mixing unique pointers
with raw pointers, and to minimize and localize such mixtures.  

A careful understanding is crucical to avoid mistakes.  The memcpy function
from the cstring library copies whatever bytes it finds in memory from
one address to another.  It *does not respect move semantics*.  That is,
if you copy a unique_ptr using memcpy, you can create a real copy of it
that destroys its uniqueness.  When both copies are deallocated, the same
memory that they point to will be deallocated twice.  Mixing raw pointers
with unique_ptr is playing with fire.

If you're a beginner, it's best to just observe the strict protocal. Don't
use raw pointers yourself.  Call built-in functions that "experts" have 
defined for you (and hope they really are experts):
*/
template<typename TY> requires std::copyable<TY>
void memcpy_unique(unique_ptr<TY>& dst,unique_ptr<TY>& src,int count) {
  memcpy(dst.get(),src.get(),count*sizeof(TY));
}//manually defined memcpy_unique
/*

This template function, defined by me, only compiles if instantiated
with a type TY that do not also contain unique pointers, because they
can't be copied. It uses a built-in C++20 "concept" that restricts the
type TY to be copyable, which a unique_ptr is not.  If you don't have
a compiler that accepts -std=c++20, you'll have to remove the
`requires` clause and live dangerously.  Yet the function still might
not work properly if the structure (type TY) being copied is not
stored contiguously in memory.  That is, the copy semantics of C++ can
be redefined to do a lot of things: it's not required to keep things
contiguous:

  mystruct(const mystruct& myotherstruct) {  //custom copy constructor
    this->a = myotherstruct.a;
    this->b = new int(2);  // no longer contiguous
    cout << "too tired to copy the rest ...";
  }

The memcpy_unique function also uses an l-value references in
order to be efficient.  Unlike another pointer, a reference *does not
count* against uniqueness because a reference can't be used to manage
heap memory: this is one way that references are safer than pointers.
Ownership is *not* transfered when you assign (or pass) a unique_ptr
to a reference.  If you have two unique pointers p and q, say of type
int, that are pointing to contiguous data, you can call
'memcpy_unique<int>(p,q,count)' without using any raw pointers
yourself, because that usage was isolated in the function.

However, using references with respect to heap-allocated data is not always
safe either.  You can have:
*/
void badref() {
  unique_ptr<int> x = make_unique<int>(5);
  int& px = *x;  
  unique_ptr<int> y = move(x);
  cout << px << endl; // BUT the lifetime of x has ended (moved)
}
/*
This function compiles but will crash when called because x becomes nullptr
after the move.

Sometimes, not having multiple pointers pointing to the same data can be
too restricting.  Consider the following struct for a linked-list of integers
and a function to print every value in the list
*/
struct node {
  int item;
  node* next;
};
void printnodes(node* n) {
  node* current = n;
  while (current!=nullptr) {
    cout << current->item << " ";
    current = current->next;
  }
}//printnodes
/*
  The printnodes function relies on having ANOTHER POINTER, current, which
will be set to every node in the list.  Had we created this list using
unique pointers instead of raw pointers, then having this other pointer 
would violates uniqueness.  
*/
struct unode {
  int item;
  unique_ptr<unode> next;
};
void printunodes(unique_ptr<unode>& n) {
  unique_ptr<unode> current = move(n);
  while (current) {  // this means current is not nullptr
    cout << current->item << endl;
    current = move(current->next);
  }
}
/*
The printunodes function will also print the list, but ONLY once.  
The list would be destroyed by the printing: onwership of each node 
would be transferred one by one to current and are destroyed
when current is reassigned, and current itself is destroyed when 
the function returns.

Using a reference here is not an option because a reference, once set,
cannot be changed to reference something else: it is always locked to 
the original memory address that it was originally assigned to reference.
One way to get around this is to use a recursive function to print, which
*logically* recreates the reference each time it's called.  Be sure to 
make the function tail-recursive and use optimized compilation (otherwise,
it's generally a bad idea to use recursion on linked lists). 
*/
void rprint(unique_ptr<unode>& current) {
  if (current) {
    cout << current->item << endl;
    rprint(current->next);
  }
}// tail-recursive function that takes an L-value reference.

/*  
  For CSC16 students: in a "tail-recursive" function, no operation is 
executed after the recursive call, and an optimizing C++ compiler can 
eliminate the recursion and generate code that uses a loop instead.

But the best solution here?  Don't create a linked list using unique
pointers.  Linked lists shouldn't be used much in modern programming
anyway: they have horrible cache coherence characteristics.  If you need 
a data structure that contains unique pointers to other data, use a 
std::vector and the built-in "for-each-reference" loop
*/
void u2() {
  vector<unique_ptr<int>> V;
  V.push_back(make_unique<int>(2));
  V.push_back(make_unique<int>(4));
  for(unique_ptr<int>& x:V) cout << *x << endl;
}
/*
This form of for-each loop creates a separate reference to each unique
pointer in the vector, without violating uniqueness.


                BUT MEMORY LEAKS ARE STILL POSSIBLE.

Unfortunately, even if we observed the exclusive unique_ptr/make_unique
protocol, memory leaks are still sometimes possible.  We can illustrate 
this using the unode struct defined above.
*/
void u3() {
  unique_ptr<unode> first = make_unique<unode>();
  unique_ptr<unode> second = make_unique<unode>();
  unique_ptr<unode> third = make_unique<unode>();  
  third->item = 3;  third->next = nullptr;
  second->item = 2;  second->next = move(third);
  first->item = 1; first->next = move(second);

  first->next->next = move(first);  // this will still create a memory leak
}//u3

/*
The last line of function u3 creates a memory leak despite the fact
that this function uses exclusively unique_ptr/make_unique.  The data
owned by second and third were moved into the list pointed to by
first. Without the last line of the function there'd be no leak: when
first is popped from the stack it will also destroy its 'next', which
in turn destroys its 'next'.

The last line attempts to create a circular reference to first:
but the 'move' will destroy first as it does this, which means
that there will be nobody left who can manage the nodes with 2 and 3.

The origin of this problem stems from the fact that C++ does not control
how something is changed (mutated).  You can either designate something
as 'const', which means it can't be changed at all, or allow any changes
to be made at any time.  There's no finer way to control how thing change.

As a general principle, 

       **  changing something must be done exclusively  **

In other words, we should not read and change something at the same time.
Something also cannot be changed in two different ways at the same time.

There are many examples of this principle.  Your operating system will
not allow you to edit a file that's open in another application.  You
certainly can't open the same file in two different editors and change
it at the same time.  The principle applies even without multiple 
processes/programs.  In CSC16 we looked at a problem where we're
given a 2D array of values and we want to calculate a new value for
each location based on the average values of the 4-8 locations around
it.  We should not write the averages into the array as we're
calculating these averages as that will skew the data depending on the
order in which we traversed the array.  Instead, we should write the
new values into another array. Only at the end do we swap the pointers
to the two arrays for the next round of calculations.  Reading from, 
and writing to memory should be done in *stages* so they don't interfere
with eachother.

In the example above, we are changing first->next->next and first at
the same time (by moving it).  Changing one also affects the other as
they're part of the same structure.  When we mutate (change) a piece
of data, there shouldn't be anything that is still dependent on the
original form of the data.  This "rule of mutability" is even more
important than ownership and lifetimes, because when the lifetime of
something ends, *it is a kind of mutation.*  Unfortunately this
principle is not enforced in C++, not even with unique pointers.  The
C++ compiler does not check if this principle is violated at compile
time, and the cost of checking it at runtime (via software) is too high 
to be consistent with the principle of zero-overhead abstraction (it 
would have to traverse the entire linked list).

Unfortunately, unique_ptr and make_unique do not guarantee complete 
memory safety.  However, using them exclusively will still make it much 
easier to write programs that are free of memory errors. You won't have
to worry about pointers pointing to the stack and you won't have to worry
about calling delete exactly once at exactly the right time.  But you 
should try to remember to respect the principle of mutability 
described above, which is easier said than done.  If there was only a
way to force you to observe it ... but I'm getting ahead of myself ...
*/


/*  
     ********    std:shared_ptr   and   std:make_shared  *********

Some algorithms require that there are multiple pointers to the same memory
location.  Sometimes this is done for efficiency: it's much less expensive 
to copy the pointer than to copy the entire structure. For example, we can
have a data structure where all instances shared a common core of values that
are immutable: this data should be shared instead of being replicated.

Modern C++ provides another kind of smart pointer for such situations
called 'shared_ptr', with accompanying operation 'make_shared'.  A
shared pointer is sometimes called a **reference counter**, although
they're not C++ references.  Unlike a unique pointer, multiple shared
pointers can point to the same data.  However, shared pointers also
maintain a **shared counter** that counts how many pointers are
currently pointing to the same data.  Each time a copy (share) of the
pointer is made, the counter is incremented.  Each time a shared_ptr
is reassigned to something else, or goes out of scope (popped) the
counter is decremented.  The last live pointer to the data is responsible 
for deallocating the data.  That is, only when the counter goes to zero 
will the data be deallocated.  You can check the current value of the 
reference counter with .use_count():
*/
void s1() {
  shared_ptr<point> origin = make_shared<point>(0,0);
  shared_ptr<point> p1 = origin;  // no need to call move
  shared_ptr<point> p2 = origin;
  shared_ptr<point> p3 = origin;  
  shared_ptr<point> p4 = make_shared<point>(1,2);
  cout << "current reference counter: " << origin.use_count() << endl; //3
  p1 = p4; // re-assigns p1
  cout << "counter after reassignment:" << origin.use_count() << endl;
  p2 = p3; // this has no effect on the reference counter
  p2 = move(p3);  // this decreases the counter, p3 nolonger points to origin
  cout << "counter after move assignment:" << p2.use_count() << endl;
}//s1
/*
   When a shared pointer is assigned to another shared pointer, calling
"move" is optional, but it still has an effect.  Once move is called on a
shared_ptr, the pointer is no longer pointing to the data it was pointing to
(it's now nullptr): thus the reference counter is decreased by move.  But
making an assignment without move creates another pointer and increments the
counter.  Note that the line 'p2 = p3' has no cumulative effect on the counter,
although technically it was decremented and then incremented.

If a shared pointer is passed to a function, the counter is also incremented.
However, &-references do not affect the count.

shared_ptr and unique_ptr cannot mix: moving one into the other is not
allowed (compiler error).  

Using shared_ptr/make_shared is easier than unique_ptr/make_unqiue.  You
won't accidently destroy the data by moving it.  You normally won't have
to call move.  But it's very important that you understand that there
are two major problems with shared pointers:

 1.  They incur significantly greater runtime overhead than unique_ptr
 2.  They don't work when structures are pointing to each other.

Zero-overhead abstraction is not just a principle of the programming 
language; it must be followed by programmers.  The programming language
allows us to avoid costly abstractions when they're unnecessary, but we must
avoid them.  Using shared pointers throughout our program might make 
programming a little easier but it violates this principle if they're not
actually needed.  

If you have two structures, each with a pointer to the other, but
there's nothing else pointing to either of these structures, then their
reference counters will never go to zero and they never get deallocated,
resulting in a memory leak.  In such situations, you have to also use
std::weak_ptr.  A weak_ptr is a "downgraded" shared_ptr.  Having a
weak_ptr to a shared structure does not affect the reference counter.  If you
have structures with pointers pointing to eachother, one of those pointers
must be a weak_ptr.  In complex situations, when your memory allocations is
an arbitrary graph, figuring out which pointers to make weak could be tricky:
not enough will result in memory leaks while too many may result in things
getting deleted too early.

It's possible to assign a weak_ptr to a shared_ptr (there's no make_weak).
It's possible to upgrade a weak_ptr to a shared_ptr with the function .lock()

Here is an example of a doubly-linked list, where each "node" in the list
has a pointer to the 'next' node as well as a pointer to the previous node.
Each node in the middle of such a list will have a pointer pointing to 
it from both directions.  But if nothing points to the head of this list,
then none of the nodes will be deallocated.  This situation calls for 
one of the two pointers to be "weak".
*/
struct dnode { // doubly linked list using shared_ptr and weak_ptr
  int item;
  shared_ptr<dnode> next; // next node
  weak_ptr<dnode> previous; // previous node
  dnode(int x, shared_ptr<dnode>& next, shared_ptr<dnode>& rdc)  {
    item=x; next=next;
    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<dnode> w = previous;
    shared_ptr<dnode> upgraded = w.lock(); // upgrade to shared_ptr
    weak_ptr<dnode> downgraded = upgraded; // downgrade to weak_ptr
    while (w.lock()->previous.lock()) { w = w.lock()->previous; }
    return w.lock()->item;  //.lock() converts weak_ptr to a shared_ptr
  } // must use .lock() before dereferening weak_ptr
}; // dnode
/*
When a weak_ptr is assigned to a shared_ptr, the reference counter of
the shared data is *not* incremented.  Before we can use a weak_ptr to
access data we have call .lock() on it to upgrade it to a shared_ptr.
In this example, the calls to w.lock() create shared_ptr objects local
to the function 'first'.  When this function returns, all the tempoary
shared pointers will be deallocated, decreasing the reference counter
back to what it was before the function call.

So in principle, we should:

  1. use unique_ptr if possible
  2. use shared_ptr only when they're really necessary
  3. use weak_ptr to prevent cyclic shared pointers.

The reference counter approach to memory management is the default for
some programming languages, including Apple's Swift language.  Other
languages have active garbage collectors.  These languages do not
respect the principle of zero-overhead abstraction: we have to always
pay the overhead of their way of managing memory whether we need to or not.
*/

/*                 
                   DEFINING OUR OWN MOVE SEMANTICS

  If you define a struct that contains unique pointers, it will 
automatically inherit the *move semantics* of unique_ptr:
*/
struct smartstruct {
  unique_ptr<int[]> A;
  unsigned int length; // length of array A
  smartstruct(unsigned int n) : length{n} {
    A = make_unique<int[]>(n);
  } //constructor
  
  static void test() {
    smartstruct s(10);
    //smartstruct t = s; // won't compile
    smartstruct t = move(s); // compiles
  }
  /*
  Of course you cannot "copy" a smartstruct because doing so will include 
  copying the unqiue_ptr and destroy its uniqueness.  You can only "move"
  the smartstruct, just like with unique_ptr.  When a struct is moved, 
  those elements that can be copied (length) will still be copied, but 
  those that can't be (A) will be moved.  Technically, movable is a
  more general property than copyable.  If something can be copied then 
  it can also be moved, but not vice versa. In other words, integers, 
  which can be copied, can also be moved, but unique_ptr can only be moved.

  However, inheriting the move semantics of unique_ptr might not be
  enough.  After `t=move(s)`, the unique_ptr A in s becomes a nullptr
  but the moved struct still contains a length value that's set to 10!
  If we wish to set the length value of s to 0 after the move, we must
  define our own "move semantics" for this type.  This is done by
  defining our own *move constructor* and *move assignment operator* :
  */
  
  smartstruct(smartstruct&& other) {   // move constructor
    A = move(other.A);
    length = other.length;
    other.length = 0;
  }
  smartstruct& operator =(smartstruct&& other) { // move = operator
    A = move(other.A);
    length = other.length;
    other.length = 0;    
    return other; // = operator typically returns value assigned to
  }
  
};  // end of smartstruct

/*
                  L-Value and R-Value References

  If you defined a struct with all elements copyable, the system will 
provide it with a default "copy constructor" and "copy assignment
operator".  Since copyable things can also be moved, there is no need
to provide separate move operations.  The move constructor and move 
assignment operator are distinguished from the copy constructor and 
copy assignment operator by the type of their arguments: they take 
*R-value references* as opposed to L-value references.

Recall that an "l-value" is whatever can appear on the left-hand side
of the assignment operator (=).  An r-value can only appear on the
right-hand side.  R-values include constants and "temporaries", which
are values returned from functions and other operations, before
they're assigned to l-values.  A type such as `int&` is an "l-value
reference" while `int&&` is an "r-value reference".

  int y = 2;
  int& x = y; // allowed because y is an l-value
  int& x = 2; // not allowed because 2 is an r-value, not an l-value
  int&& x = 2; // allowed because this x is an r-value reference.
  int&& x = y; // not allowed because y is an l-value
  int&& x = move(y); // allowed: move invokes the move assignment operator

R-value reference were introduced to implement move semantics. The `move` 
operation itself doesn't do much except to trigger the move assignment, 
as opposed to the "copy assignment" operation.  It's the move assignment 
operation, and the move constructor that implement the move semantics.
Move assignment occurs with the `=` operator and move construction occurs
when objects are passed to or returned from functions.

With an understanding of these concepts and tools we can now define our own 
version of unique pointer.


                  DEFINING OUR OWN SMART POINTER

Our version of unique pointer will have an additional feature: the ability 
to temporarily lock it to prevent it from being moved.  We will have to 
call .lock() (not to be confused with .lock on a weak_ptr) function in the
right places.  Of course the feature incurs an increase in memory and 
runtime cost compared to unique_ptr.  If you don't need it, don't pay 
for it (aka "zero overhead abstraction").  Contrary to unique_ptr, the
constructor that takes a raw pointer as argument is private and can only
be called from "friend" function make_managed, the counterpart to make_unique.
However, the class only accommodate single object.  A specialization 
would be required for arrays (managed_ptr<T[]>).

The leaktest1m function at the end illustrates how they're used.  The
lock feature is designed to help us prevent memory leaks that can still occur
even if we completely avoid raw pointers when using heap-allocated memory.
*/

template<typename TY>
class managed_ptr;     // header required because no forward reference in C++
template<class TY, class... Args>
managed_ptr<TY> make_managed(Args&&... x); // header, to be defined later
  
template<typename TY>
class managed_ptr {
private:
  TY* ptr; // internal pointer to something of type TY
  bool locked; // prevent moving (runtime check, with overhead***)
  
  //private constructor discourages mixing with raw pointers:
  managed_ptr(TY* p) {ptr=p; locked=0;} // only called by "friends"
  
public:
  managed_ptr(): ptr{nullptr}, locked{0} {}
  ~managed_ptr() { if (ptr!=nullptr) delete ptr; }

  template<typename TT, class... Args>
  friend managed_ptr<TT> make_managed(Args&&...);  //declares friend function

  void lock() {locked=1;}
  void unlock() {locked = 0; }
  bool islocked() { return locked; }
  
  // overload operators so that a managed_ptr looks like a real pointer
  TY& operator *() { return *ptr; }
  TY* operator ->() { return ptr; }
  TY& operator [](int i) { return *(ptr+i); }
  operator bool() { return ptr==nullptr; }

  // overload the move assignment operator to TRANSFER OWNERSHIP.
  managed_ptr<TY>& operator=(managed_ptr<TY>&& other) {
    if (other.locked) {
      throw "memory mutation violation on managed_ptr";
    }    
    if (ptr) delete ptr; // prevent memory leaks before assignment
    ptr = other.ptr;     // takes over "ownership" of heap value
    other.ptr = nullptr; // ownership must be unqiue to prevent wrong deletes
    return *this;
  }// move assignment operator

  // traditional copy constructor must accept a 'const' argument:
  // managed_ptr(const managed_ptr<TY>& mptr) {}// defines how to copy
  
  // overload the "move constructor" so ownership is transferred when
  // when passing smartpointer to function, return from function
  managed_ptr(managed_ptr<TY>&& other) {
    if (other.locked) {
      cerr << "Memory mutation violation on managed_ptr\n";
      throw -1;
    }
    if (ptr) delete ptr; // prevent memory leaks before assignment
    ptr = other.ptr;     // takes over "ownership" of heap value
    other.ptr = nullptr;
  }// "move constructor"
  // the move constructor nullifies the copy constructor
}; // managed_ptr<TY>

// The following function, which uses an advanced C++ template with
// "variadic parameter packs", isolates the creation of managed pointers:
// it makes sure that they're only allocated on the heap.  Essentially
// it's the same as std::make_unique
template<class TY, class... Args>
managed_ptr<TY> make_managed(Args&&... args) {
  return managed_ptr<TY>(new TY(std::forward<Args>(args)...));
  // forward retains original l/r-value status of args
}// make_managed


struct mnode {  // linked list using managed_ptr's
  int item;
  managed_ptr<mnode> next;
  mnode() { item = {}; } // {} means default value
};


void leaktest1m() {
  managed_ptr<point> m1 = make_managed<point>(2,4);
  managed_ptr<point> m2 = make_managed<point>(2,4);
  m1 = move(m2);

  managed_ptr<mnode> first = make_managed<mnode>();
  managed_ptr<mnode> second = make_managed<mnode>();
  managed_ptr<mnode> third = make_managed<mnode>();

  // if we lose first, we won't be able to access the list, including
  // deleting it.  So we "lock" it to prevent it from being "moved"
  first.lock();  // not ->lock(), because then it's looking for mnode.lock
  
  third->item = 3;  //third->next = nullptr;
  second->item = 2;  second->next = move(third);
  first->item = 1; first->next = move(second);
  // add node to front of the list
  first.unlock();
  managed_ptr<mnode> mewnode = make_managed<mnode>();
  mewnode-> item = 4;  mewnode->next = move(first); // move ok after .unlock
  first = move(mewnode); // first changes.
  first.lock();

  //first->next->next = move(first);  // this would throw an exception
} // (no memory leaks)

int main()
{
  //verybad();
  //stillbad();  //will core dump
  notbad();
  auto x = notbadatall();
  cout << "x is " << *x << endl;

  //while (1) u3();  // still will leak

  /* while (1) */ leaktest1m();   // no memory leak

  s1();
  return 0;
}//main

// Chuck Liang, Hofstra University Computer Science