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

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

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

#include "dir.h"

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

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

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

Node::~Node ()
{
}

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

class Directory
{
public:
   Node *head;
   Directory ( char *dir );
   ~Directory ();
   void Erase ( Node *root );
   Node *Build ( char *dir );
   void Print ();
   void Print2 ( Node *xhead, int level );
   Node *Find ( char *s, char *output );
   Node *Find2 ( char *s, Node *xhead, char *output );
   long int SaveTree ( Node *root );
   void Save ( char *filename );
   FILE *f;
   int DiskSearch2 ( char *s, long int filepos, char *output );
   int DiskSearch ( char *s, char *output, char *filename );
};

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

Directory::Directory ( char *dir )
{
   head = Build (dir);
}

Directory::~Directory ()
{
   Erase (head);
}

void Directory::Erase ( Node *root )
{
   while (root != NULL)
   {
      Node *p = root;
      root = root->next;
      Erase (p->directory);
      delete p;
   }
}

Node *Directory::Build ( char *dir )
{
   char s[2048];
   int state;
   Node *xhead = NULL;

   DirectoryReader A (dir);
   while ((state = A.GetName (s, sizeof (s))))
   {
      if ((strcmp (s, ".") != 0) && (strcmp (s, "..") != 0))
      {
         Node *p = new Node (s);
         p->next = xhead;
         xhead = p;
         if (state == 2)
            p->directory = Build (s);
         else
            p->directory = NULL;            
      }
   }
   return xhead;
}

void Directory::Print ()
{
   Print2 (head, 0);
}

void Directory::Print2 ( Node *xhead, int level )
{
   Node *p = xhead;
   while (p != NULL)
   {
      for ( int i=0; i<=level; i++ )
         cout << "---";
      cout << p->data << "\n";
      if (p->directory != NULL)
         Print2 (p->directory, level+1);
      p = p->next;
   }
}

Node *Directory::Find ( char *s, char *output )
{
   return Find2 (s, head, output);
}

Node *Directory::Find2 ( char *s, Node *xhead, char *output )
{
   Node *p = xhead;
   while (p!=NULL)
   {
      if (strcmp (s, p->data) == 0)
      {
         strcpy (output, s);
         return p;
      }
      else if (p->directory != NULL)
      {
         char output2[2048];
         Node *d = Find2 (s, p->directory, output2);
         if (d)
         {
            strcpy (output, p->data);
            strcat (output, "/");
            strcat (output, output2);
            return d;
         }
      }   
      p = p->next;
   }
   return NULL;
}

long int Directory::SaveTree ( Node *root )
{
   if (root == NULL)
      return -1;

   long int NextLocation = SaveTree (root->next);
   long int DirLocation = SaveTree (root->directory);

   long int NodeLocation = ftell (f);
   Node *tnext = root->next, *tdir = root->directory;
   root->fnext = NextLocation;
   root->fdirectory = DirLocation;
   fwrite (root, 1, sizeof (Node), f);
   root->next = tnext; root->directory = tdir;

   return NodeLocation;
}

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

int Directory::DiskSearch2 ( char *s, long int filepos, char *output )
{
   Node p("");
   while (filepos != -1)
   {
      fseek (f, filepos, SEEK_SET);
      fread (&p, 1, sizeof (Node), f);
      if (strcmp (s, p.data) == 0)
      {
         strcpy (output, s);
         return 1;
      }
      else if (p.fdirectory != -1)
      {
         char output2[2048];
         int Result = DiskSearch2 (s, p.fdirectory, output2);
         if (Result == 1)
         {
            strcpy (output, p.data);
            strcat (output, "/");
            strcat (output, output2);
            return Result;
         }
      }   
      filepos = p.fnext;
   }
   return 0;
}

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

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

class DirectorySearch
{
public:
   Directory *dy;
   char Result[2048];
   DirectorySearch ( char *s );
   char *Locate ( char *s );
   char *DLocate ( char *s, char *filename );
   void Print ();
   void Save ( char *filename ) { dy->Save (filename); };
};

DirectorySearch::DirectorySearch ( char *s )
{
   dy = new Directory (s);
}

char *DirectorySearch::Locate ( char *s )
{
   strcpy (Result, "");
   Node *n = dy->Find (s, Result);
   if (n)
      return Result;
   else
      return "Not Found";
}

char *DirectorySearch::DLocate ( char *s, char *filename )
{
   strcpy (Result, "");
   int n = dy->DiskSearch (s, Result, filename);
   if (n)
      return Result;
   else
      return "Not Found";
}

void DirectorySearch::Print ()
{
   dy->Print ();
}

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

int main ()
{
   cout << "File Listing:\n\n";
   DirectorySearch ds ("..");
   ds.Print ();

   cout << "\nSearch:\n\n";
   cout << "Searching for [Makefile] : " << ds.Locate ("Makefile") << "\n"; 
   cout << "Searching for [main.cc] : " << ds.Locate ("ll") << "\n";
   cout << "Searching for [test.cc] : " << ds.Locate ("test.cc") << "\n";
   cout << "Searching for [dir.o] : " << ds.Locate ("dir.o") << "\n";

   ds.Save ("data.out");

   cout << "Test ptr size : " << sizeof (void *) << " vs " << sizeof (long int ) << "\n";

   cout << "\nDisk Search:\n\n";
   cout << "Searching for [Makefile] : " << ds.DLocate ("Makefile", "data.out") << "\n"; 
   cout << "Searching for [main.cc] : " << ds.DLocate ("ll", "data.out") << "\n";
   cout << "Searching for [test.cc] : " << ds.DLocate ("test.cc", "data.out") << "\n";
   cout << "Searching for [dir.o] : " << ds.DLocate ("dir.o", "data.out") << "\n";

   return 0;
}