// ------------------------------- //
// -------- Start of File -------- //
// ------------------------------- //
// ----------------------------------------------------------- // 
// C++ Source Code File Name: llist.cpp 
// Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
// Produced By: Doug Gaer 
// File Creation Date: 04/05/1996 
// Date Last Modified: 03/17/1999
// ----------------------------------------------------------- // 
// ------------- Program Description and Details ------------- // 
// ----------------------------------------------------------- // 
/*
THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
CORRECTION.

The LList class is a C++ version of a doubly linked list used
to manipulate character strings in memory.
*/
// ----------------------------------------------------------- // 
#include <string.h>

class LListData
{
public:
  LListData() { Next =  Prior= 0; Data = 0; }
  
public:
  LListData *GetNext() { return Next; }   // Get the next link
  LListData *GetPrior() { return Prior; } // Get the previous link
  char *Get() { return Data; }            // Get the current element
  void Change(char *str) { Data = str; }  // Change an element

public:
  char *Data;
  LListData *Next;
  LListData *Prior;
};

class LList : public LListData
{
public:
  LList() { Start = End = 0; }
  ~LList() { UnLoad(); }

public:
  void Store(char *str);      // Store a single entry
  void Remove(LListData *ob); // Delete a single entry
  LListData *Find(char *str); // returns a pointer to the matching element
  int RmvData(char *c); // Remove the head of the list and free memory
  void UnLoad();        // Empty the list
  LListData *GetStart() { return Start; }
  LListData *GetEnd() { return End; }
  
private:
  LListData *Start;
  LListData *End;
};

void LList::Store(char *str)
{
  LListData *prt;

  // Allocate memory for data elements 
  prt = new LListData;

  // Copy data elements into non-contiguous memory
  prt->Data = str;

  if(Start==0) {
    // First element in list
    End = Start = prt;
  }
  else {
    // Put element on the end of the list
    prt->Prior = End;
    End->Next = prt;
    End = prt;
  }
}

void LList::Remove(LListData *ob)
{
  if(ob->Prior) { // Not deleting first element
    ob->Prior->Next = ob->Next;
    if(ob->Next) // Not deleting last element
      ob->Next->Prior = ob->Prior;
    else // Otherwise, we are deleting last element
      End = ob->Prior; // Update end pointer
  }
  else { // Deleting first element
    if(ob->Next) { // List not empty
      ob->Next->Prior = 0;
      Start = ob->Next;
    }
    else // List is now empty
      Start = End = 0;
  }
}

LListData *LList::Find(char *str)
{
  for(LListData *prt = Start; prt; prt = prt->GetNext())
    if(strcmp(prt->Data, str) == 0) return prt; // Found the item

  // Return a NULL if the item is not found
  return 0;
}

int LList::RmvData(char *c)
// Remove Data string starting from the head from the list, and set
// next node as the head.
{
  if (Start) {
     c = Start->Data;
     LListData *ptr = Start;
     Start = Start->Next;
     delete ptr;
     return 1;
  }
  else return 0;
}

void LList::UnLoad()
{
  // Remove all nodes from the list.
  char *dmy;
  int r;

  do {
    r = RmvData(dmy);
  } while(r);

  // Reset the Start and End pointers
  Start = End = 0;
}

// Test program code starts here
// *********************************************************** //
#include <iostream.h>

void pause()
{
  // Pause the program until enter is pressed
  cout << endl;
  cout << "Press Enter to continue...\n";
  cin.get();
}

void ScrollForward(LList &list)
{
  LListData *ptr = list.GetStart();

  // Walk through the list in a foward direction
  do {
    cout << ptr->Data << endl;
    ptr = ptr->GetNext();
  }while(ptr);

  cout << endl;
}

void RewindList(LList &list)
{
  LListData *ptr = list.GetEnd();

  // Walk through the list in a backward direction
  do {
    cout << ptr->Data << endl;
    ptr = ptr->GetPrior();
  } while(ptr);

  cout << endl;
}

int main()
{
  LList list;
  LListData *ptr;
  
  cout << "Loading data elements into linked list..." << endl;
  list.Store("The Quick Brown Fox Jumps Over The Lazy Dog");
  list.Store("0123456789");
  list.Store("abcdefghijklmnopqrstuvwxyz");
  list.Store("!@#$%^&*()_+");
 
  cout << "Walking through the list in a foward direction..." << endl;
  ScrollForward(list);

  cout << "Walking through the list in a backward direction..." << endl;
  RewindList(list);

  pause();
  
  cout << "Looking for alphabet string..." << endl;
  ptr = list.Find("abcdefghijklmnopqrstuvwxyz");
  if(ptr) cout << "Found: " << ptr->Get() << " string." << endl;
  
  pause();

  cout << "Removing item: " << ptr->Get() << endl;
  list.Remove(ptr);

  pause();

  cout << "Walking through the list in a foward direction..." << endl;
  ScrollForward(list);

  cout << "Adding another item named TEST_X to the list..." << endl;
  list.Store("TEST_X");

  pause();

  cout << "Walking through the list in a foward direction..." << endl;
  ScrollForward(list);

  // Change an item 
  ptr=list.Find("The Quick Brown Fox Jumps Over The Lazy Dog");
  if(!ptr) return 1; // Item was not found
  
  cout << "Changing item: " << ptr->Get() << " to: XYZ" << endl;
  ptr->Change("XYZ");

  pause();

  cout << "Walking through the list in a foward direction..." << endl;
  ScrollForward(list);

  cout << "Removing the head of the list..." << endl;
  ptr = list.GetStart();
  list.Remove(ptr);

  pause();

  cout << "Walking through the list in a foward direction..." << endl;
  ScrollForward(list);

  cout << "Removing the tail of the list..." << endl;
  ptr = list.GetEnd();
  list.Remove(ptr);

  pause();

  cout << "Walking through the list in a foward direction..." << endl;
  ScrollForward(list);

  cout << "Clearing all the list items..." << endl;
  list.UnLoad();

  cout << endl;
  
  return 0;
}
// ----------------------------------------------------------- // 
// ------------------------------- //
// --------- End of File --------- //
// ------------------------------- //

