#ifndef _SPARSE_ARRAY_H_
#define _SPARSE_ARRAY_H_

#include <iostream.h>

template <class Object>
class SparseArray {
 public:

  /* ------- Creation/Deletion -------- */

  SparseArray(int nr, int nc, const Object & URV);
  /* SparseArray() creates an "empty" nr x nc sparse array of Objects
     whose unrepresented value is as specified */


  ~SparseArray();
  /* ~SparseArray() deletes the array, freeing all memory that is used
     to store its values */



  /* ------- Storage -------- */

  const Object & Read(int row, int col);
  /* Read() returns the value stored at index (row,col); 
     if it is not represented, it returns the URV */


  void Store(int row, int col, const Object & val);
  /* Store() stores the given value at (row,col).  If val == URV,
     the value should no longer by stored explicitly, but implicitly */



/* -------- I/O -------- */

  void WriteDense(ostream & outfile);
  /* WriteDense() should print out the sparse array to the specified
     output stream as though it was an nr x nc dense array (for
     example, like the 6 x 6 arrays in the assignment definition).
     This output format requires O(nr * nc) space. */


  void ReadDense(istream & infile);
  /* ReadDense() should read in a sparse array representation printed
     out in the dense array notation.  Values that are read in which
     are equal to the URV should obviously not be stored. */


  void WriteSparse(ostream & outfile);
  /* WriteSparse() should print out the sparse array in a compact
     format such that only the locations of the represented values
     and their values will be printed out in the format:
     "(row,col) val" where row and col are the row and column of the
     values and "val" is the value stored at that position.  This list
     of represented values should be terminated with the illegal entry
     "(-1,-1) -1".  This format requires O(r) disk space. */


  void ReadSparse(istream & infile);
  /* ReadSparse() should read in a sparse array in sparse array
     format.  */
     



/* -------- Iteration -------- */

  void SetupIteration(int firstdim, int seconddim);
  /* SetupIteration() should reset the cursor for a new iteration.
     "firstdim" and "seconddim" are used to indicate the order that
     the arrays elements should be visited.  Firstdim indicates
     whether the outer loop should be over the rows (+/-1) or columns
     (+/-2), Seconddim indicates which dimension the inner loop should
     be over, and must be different than the firstdim.  The sign of
     each value indicates whether you should loop from the low
     values to the high values (+) or from the high values to the
     low values (-).  

     So for example, SetupIteration(1,-2) means that the outer loop
     should iterate over the rows starting at the low row and
     iterating to the high one, while the inner loop should iterate
     over the columns starting at the high column and iterating to the
     low one.  For the tridiagonal sparse matrix in the assignment,
     this would set up the iteration to visit elements in the following
     order:

     (0,1), (0,0), (1,2), (1,1), (1,0), (2,3), (2,2) (2,1), ..., (5,4)

     The total time to iterate over an array's values in this way
     (using Advance() one element at a time) must take O(nr + nc)
     time.
  */


  void GetCursorPosition(int & row, int & col);
  /* returns to the user the current location of the cursor by
     reference.  If the cursor has fallen off the end of the array,
     this should return (-1,-1) as the current position.  */


  void Advance();
  /* moves the cursor to the next represented value according to the
     iteration order specified by SetupIteration() */



  /* -------- Misc -------- */

  double Density();  /* returns the array's density */
  
  int NumRepresented();  /* the # of represented elements */


 private:

  /* You should fill this part in */
  
};

#include "sparse.cpp"   // standard template stupidity

#endif