/*       CSC16/123/252 Assignment: Bubblesort    (SOLUTION)

The original program crashed because it didn't follow the "rule of three,"
"rule of five", or the "rule of zero".  The roster class contained a
custom destructor, but no custom copy/move constructor or 
copy/move = operator.  A a result, during bubblesort, the creation of
of the temporary variable for swapping, `T temp = A[k];` called the
default copy constructor, which copied the pointer (student*) inside
the roster but not what it pointed to.  Since `temp` is local to 
bubblesort, it's deallocated at the end of the call to bubblesort (popped
off the stack), at which time its destructor is called (the destructor for
struct roster), which destroyed the array of student names on the heap. 

The fix is to apply the "rule of zero" by getting rid of the custom
destructor and replace copy semantics with move semantics using
unique_ptr<student[]> in place of student*.  unique_ptr can't be
copied, and any structure that contain them also can't be copied
(unless they implement custom copy constructor/assignment).
Bubblesort must not assume that values can be copied, only moved. The
new swapping lines in Bubblesort:

          T temp = move(A[k]);
          A[k] = move(A[k+1]);
          A[k+1] = move(temp);

temporarily transferred ownership (of the student[]) to temp, but
it's transferred back into the array (A[k+1]) with the last line.
At this point, the unique pointer inside temp holds a nullptr, so when
temp is deallocated (by its default destructor) it cannot delete the
students.

It's important to remember that, if a and b are unique pointers, then 

               a = move(b);

involve the following steps:

      1. if a currently points heap-allocated data, it's deleted
      2. a is set to point to b
      3. b is set to nullptr (or invalidated some other way)

b's lifetime ends after the move, until it's assigned a new unique
pointer ("given new life").

It's also important to know that if a and b are of primitive type 
such as int, float, etc, then a=move(b) is the same as a=b. 

Unfortunately, since we don't know what `T` really is at compile time,
we don't know what kind of copy or move semantics it will have,
because C++ allows these to be customized arbitrarily.  We also don't
know how it will be destroyed.  That's why we should follow the rule
of zero, and hope that whoever wrote `T` also followed it.

=========================
*/

#include<iostream>
#include<memory>
#include<concepts>  // requires -std=c++20
using namespace std;

template<typename T> requires std::movable<T>
void bubblesort(T A[], int length) {
  for(int i=0;i<length-1;i++) 
    for(int k=0;k<length-i-1;k++)
      {
        if (A[k+1] < A[k]) { //swap
          T temp = move(A[k]);
          A[k] = move(A[k+1]);
          A[k+1] = move(temp);
        }
      }
}//MY BUBBLESORT CAN SORT ANYTHING (movable)

// including these ...
struct roster { 
  string class_name;
  //string* students;  // pointer to heap-allocated array of student names
  unique_ptr<string[]> students;
  unsigned int count; // number of students;
  
  roster(string n, std::initializer_list<string> R) { //constructor
    class_name = n;
    count = R.size();
    //students = new string[count];  // allocates array on heap
    students = make_unique<string[]>(count);
    int i =0;
    for(string n:R) students[i++] = n;
  }
  //~roster() { if (students) delete[] students; }  // destructor

  // rosters are ordered by the count of the number of students
  bool operator <(roster& other) {
    return count < other.count;
  }

  // print roster
  friend ostream& operator <<(ostream& out, roster& r) {
    int i;
    out << "roster for " << r.class_name << ": ";
    for(i=0;i+1<r.count;i++) out << r.students[i] << ", ";
    if (i<r.count) out << r.students[i]; // last student without trailing ,
    out << endl;
    return out;
  }
};  // modify this struct only as instructed

int main() {
  int A[] = {4,3,6,1};
  bubblesort(A,4);
  for(int x:A) cout << x << " ";  cout << endl;  // BUBBLESORT WORKS!

  roster classes[] = {
    roster("csc123",{"Bilbo","Frodo","Gandolf"}),
    roster("csc16",{"Nev Erstudy","Isa Taparty"})
  };

  bubblesort(classes,2);
  for(roster& r:classes) cout << r;
  return 0;
}// main

/* Expected output of corrected program:

1 3 4 6 
roster for csc16: Nev Erstudy, Isa Taparty
roster for csc123: Bilbo, Frodo, Gandolf
*/