#include <iostream>

#include "dlist.h"

using namespace std;


void List::bubblesort()
{
  if ( empty() )
    return;

  if (leftmost->right == rightmost->left)
    return; // Only one single element

  bool sorted = false;
  while ( ! sorted )
  {
    // Go forward and swap elements out of order
    Node* current = leftmost->right;
    while (current->right != rightmost)
    {

      if (current->getData() > current->right->getData())
      {
        // Swap the two elements that are in wrong order
        // No special cases thanks to 'leftmost' and 'rightmost' nodes
        // Make sure 'current' do not skip one element in your swap!
        // Use the Node-members 'left' and 'right' to solve it!
        // Needless to say, const_cast's are strictly forbidden.
        
        // START OF SOLUTION
        Node* one = current->left;
        Node* two = current->right; // number two in new order
        Node* three = current;    // number three in new order
        Node* four = current->right->right;

        one->right = two;
        two->right = three;
        three->right = four;

        four->left = three;
        three->left = two;
        two->left = one;

        current = two;
        // END OF SOLUTION
      }
      current = current->right;
    }

    // Go back and check if it is in sorted order
    sorted = true;
    while (current->left != leftmost)
    {
      if (current->getData() < current->left->getData())
        sorted = false;
      current = current->left;
    }
  }
}

// A very basic test program
int main()
{
  List l;
  int number;

  cout << "Enter space separated numbers and finish with Ctrl+D" << endl;
  while (cin >> number)
    l.insert(number);

  cout << endl << "Left to right order:" << endl;
  l.printLR();
  cout << endl << "Right to left order:" << endl;
  l.printRL();

  l.bubblesort();

  cout << endl << "In increasing order:" << endl;
  l.printLR();
  cout << endl << "In decreasing order:" << endl;
  l.printRL();
  
  return 0;
}


//////////////////////////////////////////////////////////////////
//
//  REMAINING PARTS NEED *NOT* BE MODIFIED!
//
//////////////////////////////////////////////////////////////////


// List constructor
List::List()
{
  // Set up a new empty list with dummy elements
  leftmost = new Node();
  rightmost = new Node();

  leftmost->right = rightmost;
  rightmost->left = leftmost;
}


// List destructor
List::~List()
{
  delete leftmost;
}


// Insert one value first in list
void List::insert(int val)
{
  Data_Node* to_add = new Data_Node(val, leftmost, leftmost->right);
  leftmost->right->left = to_add;
  leftmost->right = to_add;
}


// Print the list from left to right
void List::printLR() const
{
  if (leftmost->left != nullptr || rightmost->right != nullptr)
    throw logic_error("ERROR: printLR: inconsistent list");
  
  Node* current = leftmost->right;
  
  cout << "[ ";
  if (current != rightmost)
  {
    cout << current->getData();
    current = current->right;
  }
  while (current != rightmost)
  {
    cout << " -> " << current->getData();
    current = current->right;
  }  
  cout << " ]" << endl;
}


// Print the list from right to left
void List::printRL() const
{
  if (leftmost->left != nullptr || rightmost->right != nullptr)
    throw logic_error("ERROR: printRL: inconsistent list");
  
  Node* current = rightmost->left;
  
  cout << "[ ";
  if (current != leftmost)
  {
    cout << current->getData();
    current = current->left;
  }
  while (current != leftmost)
  {
    cout << " -> " << current->getData();
    current = current->left;
  }  
  cout << " ]" << endl;
}


// Return true if list is empty and in a consistent state
bool List::empty() const
{
  if (leftmost->left != nullptr || rightmost->right != nullptr)
    throw logic_error("ERROR: empty: inconsistent list");
  
  if (leftmost->right == rightmost && rightmost->left == leftmost)
    return true; // correct empty list
  
  if (leftmost->right == rightmost || rightmost->left == leftmost)
    throw logic_error("ERROR: empty: inconsistent empty(?) list");
  
  return false;
}