#ifndef BUBBLESORT_H
#define BUBBLESORT_H
/////////////////////////////////////////////////////////////////////////
// BubbleSort.h - Solution to Lab #1                                  //
// ver 2                                                               //
// Jim Fawcett, CSE382 - Algorithms and Data Structures, Fall 2008     //
/////////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////
//  Pseudo Code for Bubble Sort of array of values
/////////////////////////////////////////////////////////////////////
//  Sort : T data[] with SIZE members
//
//  for(int i=0; i<SIZE; ++i)
//  {
//    swapped = false;
//    for(int j=0; j<SIZE-i-1; ++j)
//    {
//      if data[j] > data[j+1]
//      {
//        Swap data[j] and data[j+1];
//      }
//    }
//    if (swapped == false)
//      stop;
//  }
/////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////
//  Pseudo Code for Bubble Sort if array pointers to values
/////////////////////////////////////////////////////////////////////
//  Sort : T* data[] with SIZE members
//
//  for(int i=0; i<SIZE; ++i)
//  {
//    swapped = false;
//    for(int j=0; j<SIZE-i-1; ++j)
//    {
//      if *data[j] > *data[j+1]
//      {
//        // can swap either values or pointers, both work
//        // both are 32 bit types so it doesn't matter which
//
//        Swap *data[j] and *data[j+1];
//      }
//    }
//    if (swapped == false)
//      stop;
//  }
/////////////////////////////////////////////////////////////////////

#include "iostream"

namespace CSE382
{
  template<typename T>
  class BubbleSort
  {
  private:
    bool ascending;
    bool swapped;

  public:
    BubbleSort();
    void Assending(bool up);

    // value-based sort
    bool Compare(T left, T right);
    void Swap(T& left, T& right);
    void Sort(T* data, int size);
    void Display(T* data, int size);

    // pointer based specialization
    bool Compare(T* left, T* right);
    void Swap(T*& left, T*& right);
    void Sort(T** data, int size);
    void Display(T** data, int size);
  };
  //----< initialize application >--------------------------------

  template<typename T>
  BubbleSort<T>::BubbleSort() : ascending(true), swapped(false) {}

  //----< sort in assending order? >-------------------------------

  template<typename T>
  void BubbleSort<T>::Assending(bool up)
  {
    ascending = up;
  }
  //----< Compare values of two T types >--------------------------

  template<typename T>
  bool BubbleSort<T>::Compare(T left, T right)
  {
    bool predicateValue = (left <= right);
    if(ascending)
      return predicateValue;
    return !predicateValue;
  }
  //----< Compare values of two T* types >-------------------------

  template<typename T>
  bool BubbleSort<T>::Compare(T* left, T* right)
  {
    bool predicateValue = (*left <= *right);
    if(ascending)
      return predicateValue;
    return !predicateValue;
  }
  //----< swap values of two T types >-----------------------------

  template<typename T>
  void BubbleSort<T>::Swap(T& left, T& right)
  {
    T temp = left;
    left = right;
    right = temp;
    swapped = true;
  }
  //----< swap values of two T* types >----------------------------

  template<typename T>
  void BubbleSort<T>::Swap(T*& left, T*& right)
  {
    T temp = *left;
    *left = *right;
    *right = temp;
    //////////////////// this works too
    //T* temp = left;
    //left = right;
    //right = temp;
    swapped = true;
  }
  //----< sort array of T using BubbleSort algorithm >-------------

  template<typename T>
  void BubbleSort<T>::Sort(T* data, int size)
  {
    for(int i=0; i<size; ++i)
    {
      swapped = false;
      for(int j=0; j<size-i-1; ++j)
      {
        if(!Compare(data[j], data[j+1]))
        {
          Swap(data[j], data[j+1]);
        }
      }
      if (swapped == false)
        return;
    }
  }
  //----< sort array of T* using BubbleSort algorithm >------------

  template<typename T>
  void BubbleSort<T>::Sort(T** data, int size)
  {
    for(int i=0; i<size; ++i)
    {
      swapped = false;
      for(int j=0; j<size-i-1; ++j)
      {
        if(!Compare(data[j], data[j+1]))
        {
          Swap(data[j], data[j+1]);
        }
      }
      if (swapped == false)
        return;
    }
  }
  //----< show the values in T array >-------------------------------

  template<typename T>
  void BubbleSort<T>::Display(T* data, int size)
  {
    std::cout << "\n  ";
    for(int i=0; i<size; ++i)
      std::cout << " " << data[i];
    std::cout << "\n";
  }
  //----< show the values in T* array >------------------------------

  template<typename T>
  void BubbleSort<T>::Display(T** data, int size)
  {
    std::cout << "\n  ";
    for(int i=0; i<size; ++i)
      std::cout << " " << *data[i];
    std::cout << "\n";
  }
}
#endif