#include <iostream>
using namespace std;
const int MAX=50;
class SortedList
{ int length;
int data[MAX];
void BinSearch ( int item, bool& found, int& position ) const;
public:
SortedList ( ) // empty
{ length = 0; }
int Length ( ) const
{ return length; }
bool IsFull ( ) const
{ return ( length == MAX ); }
bool IsEmpty ( ) const
{ return ( length == 0 ); }
void Print ( ) const // as a row
{
cout << endl;
for ( int k=0; k<length; k++ )
cout << data[k] << ' ';
cout << endl;
}
/* chose one of the two ways
void Insert ( int item )
{ int i;
for ( i=length-1; i>=0 && item<data[i]; i-- )
data[i+1] = data[i];
// shift data right until data[i]<item
data[i+1]=item; // insert item to next position
length ++;
}
*/
void Insert ( int item ) // Richard's code
{ bool found=false;
int spot;
for( spot=0; spot<length&&!found; spot++ )
// find the location
{ if(item<data[spot])
{ found=true;
spot --;
}
}
for(int i=length; i!=spot; i--)
data[i] = data[i-1]; // shift right
data[spot]=item;
length ++;
}
void Delete ( int item )
{ bool found;
int position;
BinSearch ( item, found, position );
if (!found)
cout << "Error -- no " << item
<< " in the list.\n";
else
{ for (int i=position; i<length-1; i++)
data[i] = data[i+1];
// shift data left
cout << item << " is deleted from the list.\n";
length --;
}
}
bool IsPresent ( int item ) const
{ bool found;
int position;
BinSearch ( item, found, position );
return found;
}
};
void SortedList :: BinSearch ( int item, bool& found, int& position )
const
{ int first = 0; // index: 0 to length-1
int last = length - 1;
int middle;
found = false;
while ( last >=first && !found )
{ middle = ( first + last ) / 2;
if ( item < data[middle] ) // located first half
last = middle - 1;
else if ( item > data[middle] ) // located last half
first = middle + 1;
else found = true;
} // found or not find (last < first)
if ( found ) position = middle;
}
void menu ();
void process ( char, SortedList& );
int main()
{
SortedList myList; // empty object
char ch;
menu(); // read first data
cin >> ch; // ch: i, f, p, s, q
while ( tolower(ch) != 'q' )
{
process(ch, myList);
menu(); // read next data
cin >> ch; // ch: i, f, p, s
}
getchar();
return 0;
}
void menu ()
{
cout << "i insert an integer\n";
cout << "f find an integer\n";
cout << "p print the list\n";
cout << "d delete an integer from the list\n";
cout << "q quit the operation\n";
cout << "\nYou choose: ";
}
void process ( char ch, SortedList& myList )
{
int datum;
switch ( tolower(ch) )
{ case 'i':
cout <<"Input a integer to be inserted: ";
cin >> datum;
myList.Insert(datum);
// for debug
cout << "The list is: ";
myList.Print();
cout << "Type any key to continue ..";
getchar();
break;
case 'd':
cout <<"Input an integer to be delete: ";
cin >> datum;
myList.Delete(datum);
// for debug
cout << "The list is: ";
myList.Print();
cout << "\n\nType any key to continue ..";
getchar();
break;
case 'p':
cout << "The list is: ";
myList.Print();
cout << "\n\nType any key to continue ..";
getchar();
break;
case 'f':
cout << "Input an item to be found: ";
cin >> datum;
if ( myList.IsPresent(datum) )
cout << datum << " is in the list.\n";
else
cout << datum
<< " isn't in the list.\n";
cout << "\n\nType any key to continue ..";
getchar();
break;
default:
cout << "\nInvalid input.\n" ;
cout << "\n\nType any key to continue ..";
getchar();
}
return;
}