/* SparseVector.hh | class SparseVector (header)  */

class SparseVector {

  /* nodes are the fundamental element of the linked list in which data of */
  /* SparseVector is stored.                                               */
  struct node {
    int k;       // vector index
    int value;   // stored value
    node *next;  // pointer to next node in vector

    node(int k, int value, node *next):
      k(k), value(value), next(next) {}
  };

private:

  int length;       // length of SparseVector
  node *firstNode;  // pointer to first node of non-emtpy SparseVector data

  void makenode(int k, int value, node *precedingNode);
  void killnode(int k);
  void copydata(const SparseVector &V);
  void killdata();

public:

  /* CONSTRUCTORS */
  SparseVector(const int n);            // gives empty vector of n elements
  SparseVector(const SparseVector &V);  // copy constructor

  /* MUTATOR METHODS */
  void setElem(const int k, const int value);  // sets value of element k

  /* ACCESSOR METHODS */
  int getLength() const;           // returns length of calling instance
  int getElem(const int k) const;  // returns value of element k

  int dotProduct(const SparseVector &V) const;  // dot product with V

  /* OVERLOADED OPERATORS */
  SparseVector &operator=(const SparseVector &V);  // assignment operator

  SparseVector &operator+=(const SparseVector &V);  // chainable plus/assign
  SparseVector &operator-=(const SparseVector &V);  // chainable minus/assign

  SparseVector operator+(const SparseVector &V) const;  // chainable add
  SparseVector operator-(const SparseVector &V) const;  // chainable subtract 

  bool operator==(const SparseVector &V) const;  // equals operator
  bool operator!=(const SparseVector &V) const;  // not equals operator

  /* DESTRUCTOR */
  ~SparseVector();  // destructor; frees allocated nodes
};