//////////////////////////////////////////////////////////////////////
//
// Table.h
//
// My template table class : a plain self-expanding table.

#ifndef TABLE_H
#define TABLE_H

// The type T is assumed to have the (correct) copy constructor,
//   operator = , operator ==, operator != and other comparison operators  

#include "quicksort.h"

const int DEFAULT_TABLE_SIZE = 100;   

template< class T >
class Table {

  int capacity;                       
  int size;             // the number of actual entries
  T * values;           // a pointer to dyn. alloc. memory 
 
public:
  Table( int init_capacity = DEFAULT_TABLE_SIZE );
  ~Table();

  void add( const T& new_val );       // add a value
  bool includes( const T& val );      // true if val occurs in the
                                      //    table, false otherwise.
  void print();                       // print all values
  void sort();                        // sort in-place

  inline int length() const { return size; }  // see below about const
					   
  // operator[] has two versions, for the sake of the so-called 
  // "const correctness" the const version (which promises not to 
  // change the object on which it is called) is required if ever 
  // a const Table comes our way (see the example below), or the result 
  // is used in another const function. You may disregard this issue for 
  // the time being, and think only about  T& operator[](int)  but STL 
  // addresses it.
  
  T& operator[]( int index );
  const T& operator[] ( int index ) const;

};

template< class T >
Table<T>::Table( int init_cap ) :
  capacity( init_cap ), 
  size( 0 ), 
  values( new T[init_cap] ) 
{}

template< class T >
Table<T>::~Table() 
{ 
  delete[] values; 
}
  
template< class T >
void Table<T>::add(const T& s)
{
  if( size == capacity ){   // capacity exhausted -- expand
    
    T * new_val_ptr = new T[ capacity*2 ];  // allocate new array
    
    for( int i=0; i < size; i++ )           // copy over 
      new_val_ptr[i] = values[i];     

    delete[] values;                        // delete old array

    values = new_val_ptr;
    capacity *= 2;
  }

  values[ size ] = s;    // now we can insert
  size++;
}

template< class T >
void Table<T>::print()
{
  for( int i=0; i < size; i++ )
    cout << values[i] << " " << endl;
}

template< class T >
bool Table<T>::includes( const T& val )
{
  for( int i=0; i < size; i++ )
    if( values[i] == val ) return true;  
  return false;     
} 

template< class T >
void Table<T>::sort( )
{
  quicksort( values, 0, size-1 );
}

template< class T >
T& Table<T>::operator[]( int index )
{
  if( index >= size )
    cerr << "Warning: index " << index << " is out of bounds!\n";
  return values[index];
}

// this version will be called, for example, when a inside a function
//    foo( const Table<T>& tbl )  
// tbl[i] is called. The parameter  tbl is guaranteed to be const,
// hence  const T& operator[](int) const  will be chosen, by the type
// of tbl, which is const.   

template< class T >
const T& Table<T>::operator[] ( int index ) const
{
  cout << "operator[] const called\n";
  if( index >= size )
    cerr << "Warning: index " << index << " is out of bounds!\n";
  return values[index];
}

#endif // TABLE_H

///////////////////////////////////////////////////////////////////////
//
// table-test.cc
//
//    Test of a plain table of strings, and some discussion of
//    consts  and  "const correctness"
//

#include <iostream.h>
#include <string>
#include <fstream.h>

// same old example
// You can skip the discussion of consts at first reading.

#include "table.h"

// both foo and bar count the number of different words in the already
// sorted Table, but one takes its parameter by const reference, the
// other just by reference. This determines the choice of operator[] .

int foo( const Table<string> & T );
int bar( Table<string> & T );


int main()
{
  ifstream f( "alice-proc.txt" );
  if( ! f ) {
    cerr << "Error opening file\n";
    exit(-1);
  }

  Table<string> words;

  string s;
  while( f >> s )   
     words.add( s );
 
  words.sort();
  words.print();  // now the words are printed in alphabetical order

  // you can write a loop that asks the user for a word and then
  // replies if the word occurs in the text, and if so, how many
  // times. You might want to extend the class with an 
  // int count_occurances( const T& )  member function for this.  

  // testing the operator[], both versions
 
  cout << "------- calling foo( const Table<string> & ) -------\n";  
  cout << "foo found " << foo( words ) << " different strings\n";
  cout << "------- calling bar( Table<string> & ) -------\n";  
  cout << "bar found " << bar( words ) << " different strings\n";
  
}
  

int foo( const Table<string> & t){
  if( t.length() == 0 ) return 0;   // the table is empty
  int count = 1;
  string w = t[0];
  for( int i=0; i < t.length(); i++ ){
    if( w != t[i] ) 
      count++;
    w = t[i];
  }
  return count;
}

// Note: in foo() t is const. Thus length() is expected to be
//       a const member function as well. If you remove const
//       in the definition of  
//           Table<T>::length() const { return size; }, 
//       you will get a compiler warning about "discarding const" .

// No such issues in bar, because its argument is not const, so const
// is not expected on any member function.

int bar( Table<string> & t ){
  if( t.length() == 0 ) return 0;   // the table is empty
  int count = 1;
  string w = t[0];
  for( int i=0; i < t.length(); i++ ){
    if( w != t[i] ) 
      count++;
    w = t[i];
  }
  return count;
}