/* Filename:  bubble.cpp

   Author:  Br. David Carlson

   Date:  January 19, 1997

   Revised:  March 8, 1998 to use a recursive bubblesort.

   Last Revised:  November 27, 2001

   This program creates an array of 100 random integers and prints it
   (just to see the data).  The program then sorts and prints this array,
   asks the user for an integer to find, and does a binary search
   for this integer in the sorted array.  The result (array index where
   it was found or a not found message) is printed on the screen.

   Tested with:
      Microsoft Visual C++ 6.0
      Microsoft Visual C++ .NET
      g++ under Linux
*/

#include <cstdlib>    // needed for srand, rand functions
#include <ctime>      // needed for time function
#include <iostream>
#include <iomanip>    // needed for setw
using namespace std;


const int Max = 100;

typedef int IntArrayType[Max];


// Function prototypes:

int GetSize(int MinSize, int MaxSize);

int BinarySearch(IntArrayType IntArray, int Low, int High, int Target);

void LoadArray(IntArrayType IntArray, int Count);

void PrintArray(IntArrayType IntArray, int Count);

void BubbleSort(IntArrayType IntArray, int Count);

bool BubbleUp(IntArrayType IntArray, int Count);


/* Given:   IntArray   Array of integers.
            Low        The low index of the range of integers to search.
            High       The top index of the range of integers to search.
            Target     The integer for which to search.
   Task:    To do a binary search for Target in the specified range of
            IntArray.
   Return:  In the function name, return the index of where Target was found
            or -1 if it was not found.
*/
int BinarySearch(IntArrayType IntArray, int Low, int High, int Target)
   {
   int Mid, Diff;

   while (Low <= High)
      {
      Mid = (Low + High) / 2;
      Diff = IntArray[Mid] - Target;

      if (Diff == 0)     // IntArray[Mid] == Target
         return Mid;
      else if (Diff < 0)     // IntArray[Mid] < Target
         Low = Mid + 1;
      else
         High = Mid - 1;
      }

   return -1;   // If reach here, Target was not found.
   }


/* Given:  IntArray   Array of integers.
           Count      The number of integers in IntArray.
   Task:   To print the integers from IntArray, with up to 15 per line.
   Return: Nothing.
*/
void PrintArray(IntArrayType IntArray, int Count)
   {
   int k;

   for (k = 0; k < Count; k++)
      {
      cout << setw(5) << IntArray[k];
      if (k % 15 == 14)
         cout << endl;
      }

   cout << endl;
   }


/* Given:   Count     The number of integers to be placed into IntArray.
   Task:    To place Count sorted integers into IntArray.
   Return:  IntArray  The array of sorted integers.
*/
void LoadArray(IntArrayType IntArray, int Count)
   {
   int k;

   srand(time(NULL));
   for (k = 0; k < Count; k++)
      IntArray[k] = (1000.0 * rand()) / RAND_MAX;
   }


/* Given:  First   An integer.
           Second  An integer.
   Task:   To swap the values in First and Second.
   Return: First   
           Second
   Note:   This is an "inline" function.  That means that the normal
           function call and return mechanism is not used.  Instead a copy
           of the function code replaces the function call.  This is 
           faster and is appropriate for very short functions (so as to
           not add greatly to the program's length by inserting the same
           code everywhere where the function is called).  An inline
           function can only be used AFTER this section where it is
           defined; function prototypes are not used.
*/
inline void Swap(int & First, int & Second)
   {
   int Temp;

   Temp = First;
   First = Second;
   Second = Temp;
   }


/* Given:  IntArray   An array of integers.
           Count      The number of items in IntArray.
   Task:   To bubble the largest item in IntArray to the top (that is,
           to index Count - 1).
   Return: IntArray   The modified array.
           Also returns in the function name a true if there were no
           swaps needed during this bubble up process, false otherwise.
*/
bool BubbleUp(IntArrayType IntArray, int Count)
   {
   int k;
   bool Done;

   Done = true;   // until we know better
   for (k = 0; k < Count - 1; k++)
      if (IntArray[k] > IntArray[k + 1])
         {
         Done = false;   // because we are making a swap
         Swap(IntArray[k], IntArray[k + 1]);
         }

   return Done;
   }


/* Given:  IntArray   The array of integers to be sorted.
           Count      The number of items in IntArray.
   Task:   To bubblesort IntArray into ascending order.
   Return: IntArray   The sorted array.
*/
void BubbleSort(IntArrayType IntArray, int Count)
   {
   bool Done;

   if (Count < 2)   // array must be sorted
      return;

   Done = BubbleUp(IntArray, Count);   // bubble up the top item
   if (! Done)                         // then bubblesort the rest
      BubbleSort(IntArray, Count - 1);
   }

   
/* Given:  Nothing.
   Task:   To prompt the user for an integer from MinSize to MaxSize
           and to insist on getting only that.
   Return: The user's number in the function name.
*/
int GetSize(int MinSize, int MaxSize)
   {
   int Num;

   cout << "Enter the size for the array, using an integer from "
      << MinSize << " to " << MaxSize << ":  ";
   cin >> Num;
   
   while ((Num < MinSize) || (Num > MaxSize))
      {
      cout << "Re-enter.  Use an integer from " << MinSize << " to " 
         << MaxSize << ":  ";
      cin >> Num;
      }

   return Num;
   }


int main(void)
   {
   IntArrayType IntArray;
   int Num, Position, Size;
   char Reply;

   Size = GetSize(2, Max);
   LoadArray(IntArray, Size);

   cout << endl << "The original unsorted array:" << endl;
   PrintArray(IntArray, Size);

   BubbleSort(IntArray, Size);

   // A simple way to pause output:
   cout << endl << "Enter the letter g to go on: ";
   cin >> Reply;
   cout << endl << "The sorted array:" << endl;
   PrintArray(IntArray, Size);

   cout << endl << "Enter a number to search for: ";
   cin >> Num;
   Position = BinarySearch(IntArray, 0, Size - 1, Num);

   if (Position == -1)
      cout << "Not found" << endl;
   else
      cout << "Found in position " << Position << endl;

   return 0;
   }