// CS2604 : Data Structures
// Hussein Suleman
// 22 July 1999

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

#include <iostream.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

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

// general storage area for data
// note that the data space is now static to make shifting of the nodes easier

class Node
{
public:
   Node ( char *s );
   ~Node ();
   char data[33];
   union {
      Node *next;
      long int fnext;
   };
};

Node::Node ( char *s )
{
   if (strlen (s) <= 32)
      strcpy (data, s);
}

Node::~Node ()
{
}

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

// linked list of nodes with procedures to save to disk and search on disk

class LinkedList
{
public:
   Node *head;
   LinkedList ();
   ~LinkedList ();
   void AddNode ( Node *aNode );
   long int SaveList ( Node *xhead );
   void Save ( char *filename );
   FILE *f;
   int DiskSearch2 ( char *s, long int filepos );
   int DiskSearch ( char *s, char *filename );
};

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

// initialize linked list

LinkedList::LinkedList ()
{
   head = NULL;
}

// destroy linked nodes

LinkedList::~LinkedList ()
{
   while (head != NULL)
   {
      Node *p = head;
      head = head->next;
      delete p;
   }
}

// add a new node to the list

void LinkedList::AddNode ( Node *aNode )
{
   aNode->next = head;
   head = aNode;
}

// save the list from a particular node to disk

long int LinkedList::SaveList ( Node *xhead )
{
   if (xhead == NULL)
      return -1;              // use -1 as a disk equivalent or NULL

   long int NextLocation = SaveList (xhead->next);
                     // save rest of list and remember file position of head

   long int NodeLocation = ftell (f); // get current position
   Node *tnext = xhead->next;         // save next pointer temporarily 
   xhead->fnext = NextLocation; 
            // convert next pointer to file location of next node
   fwrite (xhead, 1, sizeof (Node), f);  // write node to file
   xhead->next = tnext;               // restore next pointer

   return NodeLocation;   // return file position of xhead node
}

// front-end to manage files while saving linked list

void LinkedList::Save ( char *filename )
{
   f = fopen (filename, "wb");
   SaveList (head);
   fclose (f);
}

// search for a linked list entry on disk

int LinkedList::DiskSearch2 ( char *s, long int filepos )
{
   Node p("");       // create a blank node
   while (filepos != -1)   // while the list has not ended
   {
      fseek (f, filepos, SEEK_SET);   // move to the nodes position in the file
      fread (&p, 1, sizeof (Node), f); // and read the node into p
      if (strcmp (s, p.data) == 0)     // check if its the value we want
         return 1;                     // and return a flag if so
      filepos = p.fnext; // otherwise move to next node
   }
   return 0;                // if we get here, the list has ended ...
}

// front-end to manage files while searching on disk

int LinkedList::DiskSearch ( char *s, char *filename )
{
   f = fopen (filename, "rb");
   fseek (f, 0, SEEK_END);
   return DiskSearch2 (s, ftell (f)-sizeof (Node));
   fclose (f);
}

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

char *e[] = {"not found!", "found"};

int main ()
{
   LinkedList ll;

   cout << "Adding Nodes :\n\n";
   ll.AddNode (new Node ("Programming"));
   ll.AddNode (new Node ("can"));
   ll.AddNode (new Node ("be"));
   ll.AddNode (new Node ("a"));
   ll.AddNode (new Node ("pain"));
   ll.AddNode (new Node ("in"));
   ll.AddNode (new Node ("the"));
      
   cout << "Outputting to disk:\n\n";
   ll.Save ("data2.out");

   cout << "Node Search:\n\n";
   cout << "Searching for [a] : " << e[ll.DiskSearch ("a", "data2.out")];
   cout << "\n";

   cout << "Searching for [rear] : " << e[ll.DiskSearch ("rear", "data2.out")]; 
   cout << "\n";
   cout << "Searching for [pain] : " << e[ll.DiskSearch ("pain", "data2.out")]; 
   cout << "\n";

   return 0;
}