////////////////////////////////////////////////////////////////////////////
//
// search.h
//
// This file is the specification of the searching and sorting
// functions. It must be included in any C++ file that uses these
// functions.
//
////////////////////////////////////////////////////////////////////////////


// For readability within the program
typedef int Boolean;
const Boolean TRUE = 1;
const Boolean FALSE = 0;      

const int MAX_LENGTH = 500;  // The max size of the lists
typedef int ItemType;        // The type of data in the lists


/////////////////////////////////////////////////////////////////////////////
// Function: ReadData
//
//           This function reads integers from a text file.
//           
//   Inputs: filename - the name of the file that contains the integers
//
//  Outputs: list    - the array representing the list of items
//           count   - the number of integers read in
//           success - a Boolean indicating if the function successfully
//                      read in the integers
//
void ReadData(const char filename[], ItemType list[], int& count, 
              Boolean& success);


/////////////////////////////////////////////////////////////////////////////
// Function: LinearSearch
//
//           This function searches  sequentially for an item in an unsorted 
//           list.
//           
//   Inputs: list   - the array representing the list of items
//           item   - the item to search for (type is ItemType)
//           length - an integer representing the length of the list
//
//  Outputs: index    - an integer representing the item's position (if found) 
//           found    - a Boolean indicating if the item was found
//           compares - an integer representing the number of compares.
//
void LinearSearch(const ItemType list[],
                  ItemType item,
                  int length,
                  int& index,
                  Boolean& found,
                  int& compares);

 
/////////////////////////////////////////////////////////////////////////////
// Function: LinearSearchOrd
//
//   This function searches sequentially for an item in an sorted list.
//           
//   Inputs: list   - the array representing the list of items
//           item   - the item to search for (type is ItemType)
//           length - an integer representing the length of the list
//
//  Outputs: index    - an integer representing the item's position (if found) 
//           found    - a Boolean indicating if the item was found
//           compares - an integer representing the number of compares.
//
void LinearSearchOrd(const ItemType list[],
                     ItemType item,
                     int length,
                     int& index,
                     Boolean& found,
                     int& compares);


////////////////////////////////////////////////////////////////////////////
// Function: BinarySearch
//
//           This function uses a binary search method to find an item in a
//           sorted list.
//           
//   Inputs: list   - the array representing the list of items
//           item   - the item to search for (type is ItemType)
//           length - an integer representing the length of the list
//
//  Outputs: index    - an integer representing the item's position (if found) 
//           found    - a Boolean indicating if the item was found
//           compares - an integer representing the number of compares.
//
void BinarySearch(const ItemType list[],
                  ItemType item,
                  int length,
                  int& index,
                  Boolean& found,
                  int& compares);


/////////////////////////////////////////////////////////////////////////////
// Function: Sort
//
//   This function sorts a list of items. When the function returns, 
//   the array will be sorted.
//           
//   Inputs: list   - the array representing the list of items
//           length - an integer representing the length of the list
//
//  Outputs: list - the sorted array 
//
void Sort(ItemType list[], int length);


////////////////////////////////////////////////////////////////////////////
// Function: DeleteOne
//
//   This function deletes one item from an unsorted list
//           
//   Inputs: list   - the array representing the list of items 
//           length - an integer representing the length of the list
//           item   - the item to delete 
//
//  Outputs: list   - the array with one occurrence of item removed 
//           length - the length of the updated list
//
void DeleteOne(ItemType list[], int &length, ItemType item);


/////////////////////////////////////////////////////////////////////////////
// Function: DeleteAll
//
//           This function deletes all elements from an unsorted list that 
//           match a certain item.
//           
//   Inputs: list   - the array representing the list of items 
//           length - an integer representing the length of the list
//           item   - the item to search for 
//
//  Outputs: list - the array with all occurrences of 'item' removed 
//           length - the length of the updated list
//
void DeleteAll(ItemType list[], int &length, ItemType item);