SLL06
[ Home ] [ Up ]

//file   SLL06.cpp
//date   11/08/2006
//author aou
//csis250.tripod.com

// SLL: Singly-linked list

/*
name:
description:
example:
preconditions:
postcondition:
side-effect:
protype:
algorithm:
code:
test-driver:
test-data:
test-results:
*/

///////////////////////////////////////////////////////////
//includes
///////////////////////////////////////////////////////////
#include <iostream>
using namespace std;


class CInfo
  {
  private:
    int value;
    CInfo *next;

  friend class CSLL;
  friend ostream & operator << (ostream & bob, const CSLL & list);
  };


class CSLL
  {
  private:
    int n;
    CInfo *first;  //essential
    CInfo *last;

  private:
    void initialize(void);

  public:
    CSLL(void);  //default constructor///////////////////////////////
    bool insert(int x);/////////////////////////////////////////////////
    friend ostream & operator << (ostream & bob, const CSLL & list);/////
    CSLL(char ch); //constructs based on value of ch ///////////////////
    CSLL(int low, int high); ////////////////////////////////////////  
    CSLL(int low, int high, int n);//////////////////////////////////
    bool operator == (const CSLL &list2);
    CSLL(const CSLL &list);
    void input(void);
    bool insert(const CSLL & list2);
  };


void main(void)
  {
  /*
  CSLL myList;
  cout << myList << endl;
  myList.insert(666);
  cout << myList << endl;

  myList.insert(555);
  cout << myList << endl;
  */

  /*
  for (int i=1; i<=10; i++)
    {
    CSLL myList('r');
    cout << myList << endl;
    }
  */

  /*
  for (int i=1; i<=10; i++)
    {
    CSLL myList(10, 20);
    cout << myList << endl;
    }
  */

  /*
  for (int i=1; i<=10; i++)
    {
    CSLL myList(10, 20, 5);
    cout << myList << endl;
    }
  */

  CSLL myList, yourList;
  cout << myList << endl << yourList << endl;

  if(myList == yourList)
    cout << "myList == yourList\n";
  else
    cout << "myList != yourList\n";

  myList.insert(5);
  yourList.insert(5);

  cout << myList << endl << yourList << endl;
  if(myList == yourList)
    cout << "myList == yourList\n";
  else
    cout << "myList != yourList\n";

  myList.insert(6);
  yourList.insert(7);

  cout << myList << endl << yourList << endl;
  if(myList == yourList)
    cout << "myList == yourList\n";
  else
    cout << "myList != yourList\n";


  myList.insert(66);
  myList.insert(56);
  yourList.insert(77);

  cout << myList << endl << yourList << endl;
  if(myList == yourList)
    cout << "myList == yourList\n";
  else
    cout << "myList != yourList\n";


  }


bool CSLL::operator == (const CSLL &list2)
  {
  if (this->n != list2.n)
    return false;

  CInfo *p1, *p2;
  
  p1 = this->first;
  p2 = list2.first;

  while (p1 != NULL)
    {
    if (p1->value != p2->value)
      return false;

    p1 = p1->next;
    p2 = p2->next;
    }

  return true;
  }


CSLL::CSLL(int low, int high, int n)
  {
  this->initialize();
  if (low > high)
    return;

  if (n<0)
    n = -n;
  
  int m = n;
  for (int i=1; i<=m; i++)
    {
    int x = low + rand()%(high-low+1);
    this->insert(x);
    }
  }


CSLL::CSLL(int low, int high)
  {
  this->initialize();
  if (low > high)
    return;

  int m = rand()%20;
  for (int i=1; i<=m; i++)
    {
    int x = low + rand()%(high-low+1);
    this->insert(x);
    }
  }


CSLL::CSLL(char ch)
  {
  this->initialize();
  if (ch == 'r')
    {
    int m = rand()%20;
    for (int i=1; i<=m; i++)
      {
      int x = rand()%100;
      this->insert(x);
      }
    }
  }

bool CSLL::insert(int x)
  {
  /*
  set agent to available block of type CInfo
  copy x to value part of new block
  set next part of new block to NULL
  set first to agent
  set last to agent
  */
  CInfo *agent;
  agent = new CInfo;
  agent->value = x;
  agent ->next = NULL;
  if (n == 0)
    {
    first = agent;
    last  = agent;
    }
  else
    {
    last->next = agent;
    last = agent;
    }


  this->n++;
  return true;
  }


ostream & operator << (ostream & bob, const CSLL & list)
  {
  bob << "SLL(" << list.n << "): ";

  CInfo *agent;

  agent = list.first;

  while (agent != NULL)
    {
    bob << agent->value << ' ';
    agent = agent->next;
    }

  return bob;
  }


CSLL::CSLL(void)
  {
  this->initialize();
  }

/*
name:         initialize
description:  initializes a new singly-linked list
example:      n/a
preconditions:list should not exist
postcondition:empty list
side-effect:  none
protype:      void initialize(void)
algorithm:    set n to 0, first and last to null
code:         follows
test-driver:  n/a
test-data:    n/a
test-results: n/a
*/
void CSLL::initialize(void)
  {
  //n = 0;
  //(*this).n = 0;
  this->n = 0;
  this->first = NULL;
  this->last = NULL;
  }