// ***********************************************************
// Maysa Peterson       SE507       Formal Specifications
//			                         CS AP Specifications for C++
//                                 March 5,  1996
//***********************************************************


// ***********************************************************
// APCS queue class
// ***********************************************************
// ***********************************************************
// Specifications for queue functions
//
// Any violation of a function's precondition will result in an error message 
// followed by a call to abort.
//  ***********************************************************
template <class itemType>
class queue
{
	public:
//  ***********************************************************
// constructors/destructors - for initialing and  finalizing data structure of type queue
//  ***********************************************************
			queue( );     	// construct empty queue
			queue(queue q );  	// copy constructor 
			~queue( );	// destructor - queue is destroyed

//  ***********************************************************
// assignment -  normal assignment via copying is been performed below
//  ***********************************************************
			queue operator = (queue righthandside );
//  ***********************************************************
// accessors - "const" indicates that the original queue is not altered 
//  ***********************************************************

			itemType     front( )   const;	// return front item (no dequeue)

//  ***********************************************************
//		given queue is [a1, a2, ..., an] with n >= 1
//		function returns a1
//  ***********************************************************

			bool             isEmpty( ) const;	// return true if empty else false

//  ***********************************************************
//		function returns true if queue is empty, false otherwise
//  ***********************************************************

	int               length( )  const;	// return number of elements 
//  ***********************************************************
//		given queue is [a1, a2, ..., an] with n >= 0
//		function  returns n
//  ***********************************************************
// modifying procedures defined below
	enqueue(itemType item );	// insert item (at rear)

//  ***********************************************************
//		precondition: queue is [a1, a2, ..., an] with n >= 0
//		postcondition: queue is [a1, a2, ..., an, item]
//  ***********************************************************

	dequeue( );	// remove first element

//  ***********************************************************
//		precondition: queue is [a1, a2, ..., an] with n >= 1
//		postcondition: queue is [a2, ..., an]
//  ***********************************************************

			dequeue(itemType item );	// combine front and dequeue

//  ***********************************************************
//		precondition: queue is [a1, a2, ..., an] with n >= 1
//		postconditions:  queue is [a2, ..., an] and item == a1
//  ***********************************************************

	makeEmpty( );	// make queue empty

//  ***********************************************************
//		postcondition: queue is empty
//  ***********************************************************
		private:

// implementation will be supplied later
};

// ************************************************************
// APCS stack class
//************************************************************
// Specifications for stack function
// Any violation of a function's precondition will result in an error message
// followed by a call to abort.
//  ***********************************************************
template <class itemType>

class stack
{
	public:
//  ***********************************************************
// constructors/destructors - for initialing and  finalizing data structure of type queue
//  ***********************************************************	
			stack( );     	// construct empty queue
			stack(stack s);  	// copy constructor 
			~stack( );	// destructor - queue is destroyed


//  ***********************************************************
// assignment -  normal assignment via copying is been performed below
//  ***********************************************************
		stack operator = (stack righthandside);
//  ***********************************************************
// accessors - "const" indicates that the original queue is not altered 
//  ***********************************************************

		itemType  top( )      const;                      // return top element (NO pop)
//  ***********************************************************
//		given stack is [a1, a2, ..., an] with n >= 1
//		function returns an
//  ***********************************************************

		bool             isEmpty( )  const;               // return true if empty, else false
//  ***********************************************************
//		function returns true if queue is empty, false otherwise
//  ***********************************************************

		int              length( )   const;                
//  ***********************************************************
//		given queue is [a1, a2, ..., an] with n >= 0
//		function  returns n
//  ***********************************************************

// modifying procedures defined below:
		push(itemType  item );	// push item onto top of stack
//  ***********************************************************
//		precondition: stack is [a1, a2...an] with  n >= 0
//		postcondition: stack is [a1, a2, ... an, item]
//  ***********************************************************

		pop( );	// pop top element
//  ***********************************************************
//		precondition: stack is [a1, a2, ... an] with n >= 1
//		postcondition: stack is [a1, a2, ... a(n-1)]
//  ***********************************************************

		pop( itemType  item );	// combines pop and top
//  ***********************************************************
//		precondition: stack is [a1,a2,...an] with n >= 1
//		postcondition: stack is [a1,a2,...a(n-1)] and item == en
//  ***********************************************************

     makeEmpty( );	// make stack empty (no elements)
//  ***********************************************************
//		precondition: stack is [a1,a2,...an] with n >= 0
//		postcondition:  stack is empty
//  ***********************************************************
	
	private:
		// implementation will be supplied later

};
// ************************************************************
//  APCS string class
//
//  string class consistent with a subset of the standard C++ string class 
//  as defined in the draft ANSI standard
// ************************************************************
extern const int npos;         // used to indicate not a position in the string - range check
class string
{
	public:
string( );                                    // construct empty string "" 

// ************************************************************
//	postcondition: string is empty
//************************************************************

string( const char * s );            // construct from string literal

// ************************************************************
//  description:	     constructs a string object from a literal string
//                                           such as "abcd"
// precondition:  s is '\0'     -null terminated string as used in C
// postcondition: copy of s    has been constructed
// ************************************************************
 
string( const string & str );      // copy constructor

// ************************************************************
// description:    copy constructor
// postcondition: copy of str has been constructed
// ************************************************************

         string( char ch );

// ************************************************************
//	description:	constructs a string object from a character
//	postcondition: string of the single character ch has been constructed
// ************************************************************

         ~string( );                                  // destructor

// ************************************************************
// description:    destructor
// postcondition: string is destroyed
// ************************************************************

// assignment

const string & operator = ( const string & str );       // assign str

// ************************************************************
// string & operator = ( const string & rhs )
//postcondition: normal assignment via copying has been performed
// ************************************************************

const string & operator = ( const char * s );             // assign s 

// ************************************************************
//description:	assignment from literal string such as "abcd"
//precondition:  s is '\0'-terminated string as used in C
//postcondition: assignment via copying of s has been performed
// ************************************************************

 const string & operator = ( char ch );                        // assign ch                                                                                                                                      //assign ch         - where ch is an actual character value not a pointer to a character;
// ************************************************************
// accessors
//
// int length( ) const;
//	postcondition: returns # of chars in string
//
// int find( const string & str)  const;
//	description:	find the first occurrence of the string str within this
//		string and return the index of the first character.  If
//		str does not occur in this string, then return npos.
//	precondition:  this string represents c0, c1, ..., c(n-1)
//		str represents s0, s1, ...,s(m-1)
//	postcondition: if s0 == ck0, s1 == ck1, ..., s(m-1) == ck(m-1) and
//		there is no j < k0 such that s0 = cj, ...., sm == c(j+m-1),
//		then returns k0;
//		otherwise returns npos
//
// int find( char ch ) const;
//	description:	finds the first occurrence of the character ch within this
//		string and returns the index.  If ch does not occur in this
//		string, then returns npos.
//	precondition:  this string represents c0, c1, ..., c(n-1)
//	postcondition: if ch == ck, and there is no j < k such that ch == cj
//		then returns k;
//		otherwise returns npos
//
// string substr( int pos, int len ) const;
//	description:	extract and return the substring of length len starting
//		at index pos
//	precondition:  this string represents c0, c1, ..., c(n-1)
//		      0 <= pos <= pos + len - 1 < n.
//	postcondition: returns the string that represents
//		c(pos), c(pos+1), ..., c(pos+len-1)
//
// const char * c_str( ) const;
//	description:	convert string into a '\0'-terminated string as
//		used in C for use with functions
//		that have '\0'-terminated string parameters.
//	postcondition: returns the equivalent '\0'-terminated string
// ************************************************************
int    length( )                  const;	// number of chars
		int    find( const string & str ) const;	// index of first occurrence of str
		int    find( char ch )            const;	// index of first occurrence of ch
		string substr( int pos, int len ) const;	// substring of len chars 
			// starting at pos
		const char * c_str( )             const;	// explicit conversion to char *
// ************************************************************
// indexing
//
// char operator [ ]( int k ) const;
//	precondition:  0 <= k < length()
//	postcondition: returns copy of the kth character
//
// char & operator [ ]( int k ) 
//	precondition:  0 <= k < length()
//	postcondition: returns reference to the kth character
// ************************************************************

		char   operator[ ]( int k )       const;	// range-checked indexing
		char & operator[ ]( int k );	// range-checked indexing
// ************************************************************
// modifiers
//
// const string & operator += ( const string & str )
//	postcondition: concatenates a copy of str onto this string
//
// const string & operator += ( char ch )
//	postcondition: concatenates a copy of ch onto this string
// ************************************************************

const string & operator += ( const string & str );      // append str const string & operator += ( char ch );	 // append char
private:
// Implementation will be supplied later
};

// ************************************************************
// The following free (non-member) functions operate on strings
//
//  boolean comparison operators:
//  ************************************************************
bool operator == ( const string & lhs, const string & rhs );  
bool operator != ( const string & lhs, const string & rhs );  
bool operator <  ( const string & lhs, const string & rhs );  
bool operator <= ( const string & lhs, const string & rhs );  
bool operator >  ( const string & lhs, const string & rhs );  
bool operator >= ( const string & lhs, const string & rhs );  

// ************************************************************
// I/O functions
// ostream & operator << ( ostream & os, const string & str) 
//	postcondition: str is written to output stream os
//
// istream & operator >> ( istream & is, string & str )
//	precondition:  input stream is open for reading
//	postcondition: the next string from input stream is has been read
//		and stored in str
//
// istream & getline( istream & is, string & str )
//	description:	reads a line from input stream is into the string str
//	precondition:  input stream is open for reading
//	postcondition: chars from input stream is up to '\n' have been read
//		and stored in str; the '\n' has been read but not stored
//
// ***********************************************************

ostream & operator << ( ostream & os, const string & str );  // output to os 
istream & operator >> ( istream & is, string & str );           // input from is 
istream & getline( istream & is, string & str );                   // input full line from is
// ***********************************************************
// concatenation operators
//
// string operator + ( const string & lhs, const string & rhs )
//	postcondition: returns concatenation of lhs with rhs
//
// string operator + ( char ch, const string & str )
//	postcondition: returns concatenation of ch with str
//
// string operator + ( const string & str, char ch )
//	postcondition: returns concatenation of str with ch
// ***********************************************************

string operator + ( const string & lhs, const string & rhs );
string operator + ( char ch, const string & str );
string operator + ( const string & str, char ch );

 // ************************************************************
//  APCS vector class template
//
//  implements "safe" (range-checked) arrays
// examples are given at the end of this file
// ************************************************************
template <class itemType> 
class vector
{
	public:
// ************************************************************
//  Specifications for vector functions
//
//  The template parameter itemType must satisfy the following two conditions:
//   (1) itemType has a 0-argument constructor
//   (2) operator = is defined for itemType
//  Any violation of these conditions may result in compilation failure.
//
//  Any violation of a function's precondition will result in an error message
//  followed by a call to abort.
// ************************************************************

// ************************************************************
//  constructors/destructor
//
//   vector( )
//     postcondition: vector has a capacity of 0 items, and therefore it will
//                    need to be resized
//
//   vector( int size )
//     precondition: size >= 0
//     postcondition: vector has a capacity of size items
//
//   vector( int size, const itemType & fillValue )
//     precondition: size >= 0
//     postcondition: vector has a capacity of size items, all of which are set
//                    by assignment to fillValue after default construction
//
//		vector( const vector & vec )
//			postcondition: vector is a copy of vec
//
//		~vector( )
//			postcondition: vector is destroyed
// ***********************************************************

vector( );                                                             // default constructor (size==0) 
vector( int size );                                                // initial size of vector is size 
vector( int size, const itemType & fillValue );   // all entries == fillValue 
vector( const vector & vec );                               // copy constructor - const means vector 	//not modified
		~vector( );                                                           // destructor
// ***********************************************************
//  assignment
//
//		const vector & operator = ( const vector & rhs )
//			postcondition: normal assignment via copying has been performed;
//				if vector and rhs were different sizes, vector
//				has been resized to  match the size of rhs
// ************************************************************

		const vector & operator = ( const vector & vec );
// ************************************************************
//  accessor
//
//		int  length( ) const
//			postcondition: returns vector's size (number of memory cells 
//				allocated for vector)
// ************************************************************

		int  length( ) const;                                              // capacity of vector
// ************************************************************
//  indexing
//
//		itemType &	operator [ ] ( int k )       -- index into nonconst vector
//		const itemType & operator [ ] ( int k ) const -- index into const vector
//			description: range-checked indexing, returning kth item
//			precondition: 0 <= k < length
//			postcondition: returns the kth item
// ************************************************************

itemType &       operator [ ] ( int index );           // indexing with range checking
	
// ************************************************************
//  modifier
//
//		void resize( int newSize )
//			description:  resizes the vector to newSize elements
//			precondition: the current capacity of vector is length; newSize >= 0
//
//			postcondition: the current capacity of vector is newSize; for each k
//				such that 0 <= k <= min(length, newSize), vector[k]
//				is a copy of the original; other elements of vector are 
//				initialized using the 0-argument itemType constructor
//				Note: if newSize < length, elements may be lost
// ************************************************************

void resize( int newSize );	// change size dynamically; 
		// can result in losing values        private:
		// Implementation will be supplied later
};
// ************************************************************
//  examples of use
//			 vector<int> v1;         // 0-element vector
//			 vector<int> v2(4);      // 4-element vector
//			 vector<int> v3(4, 22);  // 4-element vector, all elements == 22.
// ************************************************************


// ********************************************************** // APCS matrix class
//
// extends vector.h to two dimensional "safe" (range-checked) matrices 
// examples are given at the end of this file
// **********************************************************
// **********************************************************
// Specifications for matrix functions
//
// To use this class, itemType must satisfy the same constraints
// as for vector class.
//
// Any violation of a function's precondition will result in an error  message
// followed by a call to abort.
// **********************************************************

template <class itemType>
class matrix
{
	public:
// ************************************************************
//  matrix( );
//     postcondition: matrix of size 0x0 is constructed, and therefore
//	 will need to be resized later
//
//  matrix( int rows, int cols );
//     precondition: 0 <= rows and 0 <= cols
//     postcondition: matrix of size rows x cols is constructed
//
//  matrix( int rows, int cols, const itemType & fillValue );
//     precondition: 0 <= rows and 0 <= cols
//		postcondition: matrix of size rows x cols is constructed
//			all entries are set by assignment to fillValue after
//			default construction
//
//  matrix( const matrix<itemType> & mat );
//		postcondition: matrix is a copy of mat
//
//  ~matrix( );
//		postcondition: matrix is destroyed
// ***********************************************************

		matrix( );	                                                // default size 0 x 0
		matrix( int rows, int cols );                     // size rows x cols
		matrix( int rows, int cols,
			const itemType & fillValue ); // all entries == fillValue
		matrix( const matrix & mat );                  // copy constructor
		~matrix( );                                                // destructor
// ***********************************************************
// assignment
//
//  const matrix & operator = ( const matrix & rhs );
//		postcondition: normal assignment via copying has been performed
//			(if matrix and rhs were different sizes, matrix has 
//			been resized to match the size of rhs)
// ***********************************************************

		const matrix & operator = ( const matrix & rhs );
// ***********************************************************
// accessors
//
//  int numrows( ) const;
//		postcondition: returns number of rows
//
//  int numcols( ) const;
//		postcondition: returns number of columns
// ***********************************************************

		int numrows( ) const;	       // number of rows
		int numcols( ) const;	       // number of columns
// ***********************************************************
// indexing
//
//  const vector<itemType> & operator [ ] ( int k ) const;
//		precondition: 0 <= k < number of rows
//		postcondition: returns k-th row
//
//  vector<itemType> & operator [ ] ( int k );
//		precondition: 0 <= k < number of rows
//		postcondition: returns k-th row
// ***********************************************************

const vector<itemType> & operator [ ] ( int k ) const;  // range-checked indexing vector<itemType> & operator [ ] ( int k );              // range-checked indexing
// ***********************************************************
// modifiers
//
//  void resize( int newRows, int newCol );
//		precondition: matrix size is rows X cols,
//		              0 <= newRows and 0 <= newCols
//		postcondition: matrix size is newRows X newCols;
//			for each 0 <= j <= min(rows,newRows) and
//			for each 0 <= k <= min(cols,newCols), matrix[j][k] is
//			a copy of the original; other elements of matrix are
//			initialized using the default constructor for itemType
//			Note: if newRows < rows or newCols < cols,
//			      elements may be lost
// ************************************************************

resize( int newRows, int newCols );                // resizes matrix to newRows x newCols
	                                                       // (can result in losing values)
// ************************************************************
//  Examples of use:
//
//		matrix<double> dmat( 100, 80 );       // 100 x 80 matrix of doubles
//		matrix<double> dzmat( 100, 80, 0.0 ); // initialized to 0.0
//		matrix<String> smat( 300, 1 );        // 300 strings
//		matrix<int> imat;                     // has room for 0 ints
// ************************************************************

private:
};