// File: ZoomTable.cpp
//
// by Prof. Richard Chang for Spring 2007 CMSC202 at UMBC.
// Students may base Project 5 on this code.
//

#include <iostream>
#include <cassert>
#include "ZoomTable.h"

using namespace std ;

//---------------------------------------------------------------
// Node constructors

// Default Constructor
//
Node::Node() :
   m_data(0), m_row(0), m_col(0), 
   up(NULL), down(NULL), left(NULL), right(NULL)
{
   // do nothing
}


// Alternate Constructor
//
Node::Node(int data, int row, int col) :
   m_data(data), m_row(row), m_col(col), 
   up(NULL), down(NULL), left(NULL), right(NULL)
{
   // do nothing
}


// Assign to the payload data
//
void Node::set(int data) {
   m_data = data ;
}


// Retrieve the payload data
//
int Node::get() const {
   return m_data ;
}


// Get this Node's row coordinate
//
int Node::row() const {
   return m_row ;
}


// Get this Node's column coordinate
//
int Node::col() const {
   return m_col ;
}


//---------------------------------------------------------------
// ZoomTable member functions


// Set up array of head and tail pointers.
// Precondition: num_rows and num_cols must already be set.
//
void ZoomTable::InitializeHeadsAndTails() {

   // Allocate memory for dummy heads and tails
   //
   row_heads = new Node[num_rows] ;
   row_tails = new Node[num_rows] ;

   for (int i=0 ; i < num_rows ; i++) {

      // Point head to tail in empty row
      // and use COL_MIN to indicate dummy head
      //
      row_heads[i].right = &row_tails[i] ;
      row_heads[i].m_row = i ;
      row_heads[i].m_col = COL_MIN ;

      // Point tail to head in empty row
      // and use COL_MAX to indicate dummy tail
      //
      row_tails[i].left  = &row_heads[i] ;
      row_tails[i].m_row = i ;
      row_tails[i].m_col = COL_MAX ;
   }

   // Now do the same for the columns
   //
   col_heads = new Node[num_cols] ;
   col_tails = new Node[num_cols] ;
   for (int i=0 ; i < num_cols ; i++) {
      col_heads[i].down  = &col_tails[i] ;
      col_heads[i].m_col = i ;
      col_heads[i].m_row = ROW_MIN ; 

      col_tails[i].up    = &col_heads[i] ;
      col_tails[i].m_col = i ;
      col_tails[i].m_row = ROW_MAX ;
   }
}


// Deallocate memory of this ZoomTable
//
void ZoomTable::clear() {
   Node *ptr, *next ;

   // Chase down every Node in the ZoomTable and delete it
   //
   for (int row=0 ; row < num_rows ; row++) {

      ptr = row_heads[row].right ;   
      assert(ptr != NULL) ;

      while (ptr->m_col < num_cols) {
         next = ptr->right ;
         delete ptr ;
         ptr = next ;
         assert(ptr != NULL) ;
      }
   }

   // Now deallocate the dummy heads and tails
   //
   delete [] row_heads ;
   delete [] row_tails ;
   delete [] col_heads ;
   delete [] col_tails ;

   // Tidy up
   row_heads = row_tails = col_heads = col_tails = NULL ;
}


// Copy ZoomTable in rhs to this ZoomTable
// Precondition: head and tail arrays have been initialized
//
void ZoomTable::copy(const ZoomTable& rhs) {
   int row ;
   Node *ptr ;

   // do it backwards for speedier insertion
   for (row = rhs.num_rows-1 ; row >= 0 ; row--) {

      ptr = rhs.row_tails[row].left ;  // backwards
      assert(ptr != NULL) ;
      
      while (ptr->m_col >= 0) {
         insert(row, ptr->m_col, ptr->m_data) ;
         ptr = ptr->left ;
         assert(ptr != NULL) ;
      }

   }
}



// Default Constructor
//
ZoomTable::ZoomTable() :
   num_rows(0), num_cols(0), row_heads(NULL), row_tails(NULL),
   col_heads(NULL), col_tails(NULL)
{
   // do nothing 
}


// Alternate Constructor
//
ZoomTable::ZoomTable(int rows, int cols) :
   num_rows(rows), num_cols(cols) 
{
   InitializeHeadsAndTails() ;
}


// Copy Constructor
//
ZoomTable::ZoomTable(const ZoomTable& rhs) :
   num_rows(rhs.num_rows), num_cols(rhs.num_cols)
{
   InitializeHeadsAndTails() ;
   copy(rhs) ;
}


// Destructor
//
ZoomTable::~ZoomTable() {
   clear() ;
}


// Assignment operator
//
ZoomTable& ZoomTable::operator=(const ZoomTable& rhs) {

   if (this != &rhs) {
      clear() ;
      num_rows = rhs.num_rows ;
      num_cols = rhs.num_cols ;
      InitializeHeadsAndTails() ;
      copy(rhs) ;
   }

   return *this ;
}


// This is an odd ball function. Its main purpose is to prevent searching
// for the same coordinates twice. 
//
// During an insert(i,j,x) we need to do two things:
//
//   1. if a Node with the coordinates (i,j) already exists, 
//      overwrite its data with x.
//   2. if no such Node exists, make a new Node with value x
//      and put it in position (i,j).
//
// The point is that after searching for a Node with coordinates (i,j)
// we either find it or have figured out where a new Node would go.
// If we find the Node, locate() returns a pointer to this Node.
// If we don't find the Node, locate() returns NULL, but row_pos
// and col_pos point to the Nodes in row i and column j that are
// right before where a new Node will be inserted.
//

Node *ZoomTable::locate(int row, int col, Node * &row_pos, Node * &col_pos) const
{

   // if out of bounds, return NULL
   if ( (row < 0) || (row >= num_rows) || (col < 0) || (col >= num_cols) ) {
      row_pos = col_pos = NULL ;
      return NULL ;
   }

   Node *ptr ;  

   // find position in row linked list
   ptr = &row_heads[row] ;
   assert(ptr->right != NULL) ;

   while (ptr->right->m_col < col) {
      ptr = ptr->right ;
      assert(ptr->right != NULL) ;
   }

   // check perhaps entry already exists
   if (ptr->right->m_col == col) {
      row_pos = col_pos = NULL ;
      return ptr->right ;
   }

   // No such entry found, so ptr is pointing to the Node
   // right before where new Node will be inserted.
   // Let's remember that fact.
   row_pos = ptr ;

   // Now we look for the column position.
   ptr = &col_heads[col] ; 
   assert(ptr->down != NULL) ;

   while (ptr->down->m_row < row) {
      ptr = ptr->down ;
      assert(ptr->down != NULL) ;
   }

   assert(ptr->down->m_row != row) ;  // sanity check

   // Now ptr is pointing to the Node in the same column
   // just above where the new Node will be inserted.
   col_pos = ptr ;

   // Say we didn't find an existing Node at given 
   // position.
   return NULL ;
}


// This function places a new Node in the ZoomTable. 
// The pointers row_pos and col_pos were found by locate().
// 
void ZoomTable::splice(Node *ptr, Node *row_pos, Node *col_pos) {

   assert( (ptr != NULL) && (row_pos != NULL) && (col_pos != NULL) ) ;

   // splice into row linked list
   ptr->left = row_pos ;
   ptr->right = row_pos->right ;
   row_pos->right = ptr ;
   ptr->right->left = ptr ;

   // splice into column linked list
   ptr->up = col_pos ;
   ptr->down = col_pos->down ;
   col_pos->down = ptr ;
   ptr->down->up = ptr ;
} 


// Implements insert() as specified by Project 3's description.
// It either overwrites the data of an existing Node with coordinates
// (row, col) or it adds a new Node.
//
Node *ZoomTable::insert(int row, int col, int data) {
   Node *row_pos, *col_pos, *ptr ;

   ptr = locate(row, col, row_pos, col_pos) ;

   if (ptr != NULL) {
      ptr->m_data = data ; 
   } else {

      ptr = new Node(data, row, col) ;
      splice(ptr, row_pos, col_pos) ;
   }

   return ptr ;
}


// Implements find() as specified by Project 3's description.
// The locate() function already does everything that find() has to.
//
Node *ZoomTable::find(int row, int col) const {
   Node *row_pos, *col_pos ;

   return locate(row, col, row_pos, col_pos) ;
}


// Implements remove() as specified by Project 3's description.
//
void ZoomTable::remove(Node *ptr) {

   if (ptr == NULL) return ;

   // Lots of sanity checks before we rip the Node out.
   //
   assert(ptr->left  != NULL) ;
   assert(ptr->right != NULL) ;
   assert(ptr->up    != NULL) ;
   assert(ptr->down  != NULL) ;

   // De-link Node from its row
   //
   ptr->left->right = ptr->right ;
   ptr->right->left = ptr->left ;

   // De-link Node from its column
   //
   ptr->up->down = ptr->down ;
   ptr->down->up = ptr->up ;

   // Free up the allocated memory
   //
   delete ptr ;
   ptr = NULL ;
}


// Implements other remove() as specified by Project 3's 
// description.
//
bool ZoomTable::remove(int row, int col) {

   Node *ptr = find(row, col) ;

   if (ptr == NULL) return false ;

   remove(ptr) ; 
   return true ;
}


// Implements at() as specified by Project 3's description.
// Note that at() returns an int r-value. You cannot assign
// a new value using at(). Call insert() for that.
//
int ZoomTable::at(int row, int col) const { 

   Node *ptr = find(row, col) ;

   if (ptr == NULL)  return 0 ; 

   return ptr->m_data ;
}


// Checks to see if ptr is pointing to a dummy head or tail.
// If so, return NULL. If not, return ptr.
// This is a handy function for ZoomLeft, ZoomRight, ...
//
Node *ZoomTable::ValidatedPtr(Node *ptr) const {
   int row, col ;

   if (ptr == NULL) return NULL ;

   row = ptr->m_row ;
   col = ptr->m_col ;

   if ((row < 0) || (row >= num_rows)) return NULL ;
   if ((col < 0) || (col >= num_cols)) return NULL ;

   return ptr ;
}


// Return pointer to the first Node in specified row.
// If the row is empty, ValidatePtr() will return NULL.
//
Node *ZoomTable::FirstInRow(int row) const {
   return ValidatedPtr(row_heads[row].right) ;
}

// Return pointer to the first Node in specified column.
// If the columhn is empty, ValidatePtr() will return NULL.
//
Node *ZoomTable::FirstInCol(int col) const {
   return ValidatedPtr(col_heads[col].down) ;
}


//----------------------------------------------------------------------
// Zooming around

Node *ZoomTable::ZoomLeft(Node *ptr) const {
   
   if (ptr == NULL) return NULL ;
   return ValidatedPtr(ptr->left) ;
}

Node *ZoomTable::ZoomRight(Node *ptr) const {
   
   if (ptr == NULL) return NULL ;
   return ValidatedPtr(ptr->right) ;
}

Node *ZoomTable::ZoomUp(Node *ptr) const {
   
   if (ptr == NULL) return NULL ;
   return ValidatedPtr(ptr->up) ;
}

Node *ZoomTable::ZoomDown(Node *ptr) const {
   
   if (ptr == NULL) return NULL ;
   return ValidatedPtr(ptr->down) ;
}

//----------------------------------------------------------------------


// Print out all the nodes. It's hard to be orderly.
//
//
void ZoomTable::dump() const {

   Node *ptr ;

   for (int row = 0 ; row < num_rows ; row++) {
      
      ptr = row_heads[row].right ;

      cout << "row " << row << ": " ; 
      while (ptr->m_col < num_cols) {
         cout << "[" << ptr->m_col << "]=" 
              << ptr->m_data << ", " ;
         ptr = ptr->right ;
      }
      cout << endl ;
   }
}


// Return number of rows in this ZoomTable.
//
int ZoomTable::rows() const {
   return num_rows ;
}

// Return number of columns in this ZoomTable.
//
int ZoomTable::cols() const {
   return num_cols ;
}