/*----------------------------------------------------------------------------
FILE NAME:     list.cpp
               BASIC DEFINITIONS FOR CLASS LIST AND MORE
               ECE 1320 Winter 2003

AUTHOR:        Stefano Basagni

CREATED:       February 2003

DESCRIPTION:   Example of a simple C++ program to test functions on lists.

---
Copyright (C) 2003 Stefano Basagni

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

To receive a copy of the GNU General Public License write to
the Free Software Foundation, Inc., 59 Temple Place - Suite
330, Boston, MA 02111-1307, USA.

Stefano Basagni can be contacted at basagni@ece.neu.edu.

----------------------------------------------------------------------------*/
// INCLUDE SECTION
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <ctime>
#include <cstdlib>

using namespace std;

// CONSTANT SECTION
const int MAXINT = 65536;

// CLASSES DEFS
// Def. of list's node
class lNode {
public:
  lNode();
  lNode( int eVal, lNode* nVal = NULL ) {
    elem = eVal; 
    next = nVal;
  }
  int getElem() const { return elem; }
  void setElem( int eVal ) { elem = eVal; }
  lNode* getNext() { return next; }
  void setNext( lNode* nVal = NULL ) { next = nVal; }

private:
  int elem;
  lNode* next;
};

// Def. of a list: Interfaces (methods)
class lList {
public:
  lList() { init(); }
  lList( int n );
  lList( lNode* i );
  ~lList() { removeAll(); }
  lNode* getHead() { return head; }
  void incL( int k = 1 ) { length += k; }
  void setHead( lNode* h ) { head = h; }
  void printList();
  void clear() { removeAll(); }
  bool isEmpty() const { return head == NULL; }
  int getLength() const { return length; }
  int lLength() const;
  void insert( const int e );
  void remove( const int e );

private:
  lNode* head;
  int length;
  void init() {
    head = NULL;
    length = 0;
  }
  void removeAll() { 
    while ( head != NULL ) {
      lNode* temp = head;
		head = head -> getNext();
      delete temp;
    }    
	 length = 0;
  }
};

// Def. of a list: Implementations
// Create a list with n (random) elements
// Here from 1 to 100 inclusive
lList::lList( int n ) {
  srand( time( 0 ) );
  init();
  for( int a = 0; a < n; a++ )
    insert( 1 + rand() % 101 );
}

// Create a list from a linked list of lNodes
lList::lList( lNode* i ) {
  head = i;
  length = 0;
  lNode* temp = i;
  while ( temp != NULL ) {
    length++;
    temp = temp -> getNext();
  }
}

// Print the list
void lList::printList() {
  lNode* temp = head;
  while ( temp != NULL ) {
    cout << temp -> getElem() << " -> ";
    temp = temp -> getNext();
  } 
  cout << "#" << endl;
}

// Provide the length of the list, computing it
// *without* using the private data 'length'
int lList::lLength() const {
  int l = 0;
  lNode* temp = head;
  while ( temp != NULL ) {
    l++;
    temp = temp -> getNext();
  }
  return l;
}

// Insert a new node as the head of the list
void lList::insert( const int e ) {
  lNode* temp = new lNode( e, head );
  head = temp;
  length++;
}

// Remove all occurrences of e in the list, if any
void lList::remove( const int e ) {
  if ( head != NULL )
    while ( ( head != NULL ) && ( head -> getElem() == e ) ) {
      lNode* tbd = head;
      head = head -> getNext();
      delete tbd;
      length--;
    }
  if ( head != NULL ) {
    lNode* temp = head -> getNext();
    lNode* chaser = head;
    while ( temp != NULL ) {
      if ( temp -> getElem() == e ) {
        lNode* tbd = temp;
        temp = temp -> getNext();
        chaser -> setNext( temp );
        delete tbd;
        length--;
      }
      else {
        chaser = temp;
        temp = temp -> getNext();
      }
    }
  }
}

// PROTOTYPES FOR HMW FUNCTIONS
void firstN( int n, int k, lList *l, lList *m );


//---------------------------------------------------------------------
// MAIN
int main() {

  int nn = 10;

  // Creating an empty list
  lList el;

  // Checking isEmpty
  if ( el.isEmpty() )
    cout << "The list just created is empty." << endl;

  // Creating a list with nn elements
  lList ll( nn );

  // Testing print list
  ll.printList();

  // Testing the lengths
  cout << "The length of the list is: " << ll.getLength() 
       << " (private data), namely, " << ll.lLength() 
       << " (computed)." << endl;

  // Inserting an element as head of the list
  int newEl;
  cout << "Type in the element that you want to insert: ";
  cin >> newEl;
  ll.insert( newEl );
  cout << "The list is now: " << endl;
  ll.printList();

  // Removing elements
  int remEl;
  cout << "Type in the element that you want to remove: ";
  cin >> remEl;
  ll.remove( remEl );
  cout << "The list is now: " << endl;
  ll.printList();  

  // Testing clear
  ll.clear();
  cout << "The list, after clearing, is: ";
  ll.printList();

  // Testing firstN
  lList L;
  lList M;

  int x = 0;
  while ( x < 1 ) {
    cout << "Insert a number >= 0: ";
    cin >> x;
  }
  firstN( x, 1, &L, &M );

  cout << "The first list is: " << endl;
  L.printList();
  cout << "The second list is: " << endl;
  M.printList();

  cout << "The length of the first list is: " << L.getLength() << endl;

  cout << "The length of the second list is: " << M.getLength() << endl;

  return 0;

}
  

//---------------------------------------------------------------------
// FUNCTION DEFS
//---------------------------------------------------------------------
// Constructs two lists, l with the first n integers in increasing
// order and m the reverse of l (Problem 6, HMW 4)
void firstN( int n, int k, lList *l, lList *m ) {
    if ( n > 0 ) {
      l -> insert( k );
      m -> insert( n );
      firstN( n - 1, k + 1, l, m );
    }
}