// From the software distribution accompanying the textbook
// "A Practical Introduction to Data Structures and Algorithm Analysis,
// Third Edition" by Clifford A. Shaffer, Prentice Hall, 2007.
// Source code Copyright (C) 2006 by Clifford A. Shaffer.

// This is the file to include in your code if you want access to the
// complete AList template class

// First, get the declaration for the base list class
#include "list.h"

// This is the declaration for AList.
template <class Elem> // Array-based list implementation
class AList : public List<Elem> {
private:
  int maxSize;        // Maximum size of list
  int listSize;       // Actual number of elements in list
  int fence;          // Position of fence
  Elem* listArray;    // Array holding list elements

public:
  AList(int size=DefaultListSize) { // Constructor
    maxSize = size;
    listSize = fence = 0;
    listArray = new Elem[maxSize];
  }

  ~AList() { delete [] listArray; } // Destructor

  void clear() {                    // Reinitialize the list
    delete [] listArray;            // Remove the array
    listSize = fence = 0;           // Reset the size
    listArray = new Elem[maxSize];  // Recreate array
  }

  bool insert(const Elem&); // insert an Elem into list
  bool append(const Elem&); // append an Elem to list
  bool remove(Elem&);       // delete an Elem from list

  void setStart() { fence = 0; }        // Reset fence
  void setEnd()   { fence = listSize; } // Reset fence
  void prev()     { if (fence != 0) fence--; }
  void next()     { if (fence < listSize) fence++; }
  int leftLength() const  { return fence; }
  int rightLength() const { return listSize - fence; }

  bool setPos(int pos) {    // Reset list position
    if ((pos >= 0) && (pos <= listSize)) fence = pos;
    return (pos >= 0) && (pos <= listSize);
  }

  bool getValue(Elem& it) const { // Return an Elem
    if (rightLength() == 0) return false;
    else { it = listArray[fence]; return true; }
  }

  void print() const;             // Print list contents
};

// This is the implementation for the remaining function members
// of AList.

// Insert Elem at front of right partition
template <class Elem>
bool AList<Elem>::insert(const Elem& item) {
  if (listSize == maxSize) return false; // List is full
  for(int i=listSize; i>fence; i--)      // Shift Elems up
    listArray[i] = listArray[i-1];       //   to make room
  listArray[fence] = item;
  listSize++;                       // Increment list size
  return true;
}

// Append Elem to end of the list
template <class Elem>
bool AList<Elem>::append(const Elem& item) {
  if (listSize == maxSize) return false;
  listArray[listSize++] = item;
  return true;
}

// Remove and return first Elem in right partition
template <class Elem> bool AList<Elem>::remove(Elem& it) {
  if (rightLength() == 0) return false; // Nothing in right
  it = listArray[fence];                // Copy removed Elem
  for(int i=fence; i<listSize-1; i++)   // Shift them down
    listArray[i] = listArray[i+1];
  listSize--;                           // Decrement size
  return true;
}

// Print out the list
template <class Elem> void AList<Elem>::print() const {
  int temp = 0;
  cout << "< ";
  while (temp < fence) cout << listArray[temp++] << " ";
  cout << "| ";
  while (temp<listSize) cout << listArray[temp++] << " ";
  cout << ">\n";
}