/******************************************************************************
 * Author:          Shawn Stoffer
 * 
 * Description:     This file is an auxilliary file meant to be included in a 
 *                  library.  This implements a growable array of characters.
 * 
 *****************************************************************************/

// Used for outputting the array to an output stream.
#include <iostream>

// Unfortunately, there is a bug in my copy of iostream, such that it does not
// allow access to some of the primitive types of the input and output streams,
// and therefore I have to use the ostream library (a subset of iostream) as 
// well as the iostream library.
#include <ostream.h>

// The definitions of the garray class.
#include "garray.h"

// We want to initialize the table using no chars, and use one char as the 
// table.
garray::garray() : _cur_size(0), _max_size(1) {
  _table = new char;
}


//  We allow people to initialize a garray using a primitive C character string,
// This is more so that the garray can be used as a string than anything else.
// All we do here is use Put to append each character onto the end of the
// garray.
garray::garray(const char* s) : _cur_size(0), _max_size(1) {
  _table = new char;
  for (int i = 0; *s != 0; i++, s++)
    Put(*s);
}

// We also allow people to initialize a garray as a copy of another garray.
garray::garray(const garray& G) : _cur_size(G.size()), _max_size(G.max_size()) {
  _table = new char[_max_size];
  for (int i = 0; i < size(); i++)
    _table[i] = G[i];
}

// Here we just append the character onto the end of the array, though if 
// the array is too small, it must be resized.  The resize function will double
// the array each time, therefore amortizing the running time of each Put to
// O(1). (a series of n Put() operations would cost O(n) guaranteed, though 
// that does not mean that the amortized cost of each insert is O(1), because
// that is an abuse of the defintion, it is nearly the same as saying so, and
// so I do.)
void garray::Put(int a) {
  if (_cur_size+1 > _max_size) {
    resize();
  }
  _table[_cur_size++] = a;
}


// resize doubles the table size every time it is called, so that the
// amortization of the running time will give us a O(n) time for n Put()s.
// The algorithm for doing this is to hold the old_table in reserve, increase
// the max_size of the new table, by doubling the old size, and then copying
// the old table into the new table.  This could be done more efficiently by
// using memcpy() but some systems do not implement this function, so in the
// interest of making the code portable, I have not used it.
void garray::resize() {
  char * old_table = _table;
  _max_size *= 2;
  _table = new char[_max_size];
  for (int i = 0; i < _cur_size; i++) _table[i] = old_table[i];
}


// This function will return the appropriate element of the array, for the 
// index given, though if the index is not in the array, then it will return
// the bogus value of 0, this is in-band signalling, but considering that this
// package is currently being used by me, as a VERY basic string class, the 
// signalling is acceptable.  
char& garray::operator[](int a) const {
  if (a < _cur_size)
    return _table[a];
  // In case someone changed our phantom via this particular operator 
  // previously.
  phantom = 0;
  return phantom;
}


// Remove the first a elements of the garray.  Another note is here we could 
// use memcpy(_table, _table+a, cur_size-a), but this is not implemented on
// all systems, and therefore in the interest of portability, I have not used
// that call.
// The current way that this is implemented is that if a is the current size
// of the array or larger, then clear the array, otherwise, reset the current
// size, and copy the table at the specified element on over the previous table.
garray& garray::operator-=(int a) {
  if (a >= _cur_size) clear();
  else {
    _cur_size -= a;
    for (int i=0; i<_cur_size; ++i)
      _table[i] = _table[i+a];
  }
  return *this;
}


// Find a substring in the garray, this is using the format of the old C string
// library call of the same name.
char* garray::strstr(garray& s) {
  for (int k=0; k < size(); k++)
     for (int i = k, j = 0; ((i < size()) && (j < s.size())); ) {
        if (_table[i++] != s[j++]) break;
        if (j >= s.size())
          return table_array()+k;
     }
  return 0;
}


// Compare two garrays, character by character, this functions very similarly 
// to a strcmp.
int garray::operator==(const garray& s) {
  int k; 
  if (size() == s.size()) {
    for (k = 0;
         k < size() && k < s.size() && _table[k] == s[k];
         k++);
    if (k == size())           return 1; // We got to the end...equal
    if (_table[k] > s[k])      return 0;
    else                       return 0;
  } 

  if (size() > s.size())       return 0;

                               return 0;
}
  

// Append one garray onto another, one character at a time, using Put.
garray& garray::operator+=(const garray& s) {
  for (int k = 0; k < s.size(); k++)
    Put(s[k]);
  return *this;
}

// clear out the array, this is very simple, we are just going to set the array
// size to 0.
void garray::clear() {
  _cur_size = 0;
}


// Puke the array.  
ostream & operator<<(ostream &o, const Xstring &x) {
  const char *p = x._table;
  for (int i=x._cur_size;i>0;--i) o.put(*p++);
  return o;
}