// C++ has MUCH better alternatives than this.  Why reinvent a flat wheel?

// this example simply illustrates what is needed to implement a linked list

// this really is not a complete linked list.

#include <iostream>

enum { nIsSmaller, nIsLarger, nIsSame };

// Data class to put into the linked list
// Any class in this linked list must support two methods:
// Show (displays the value) and Compare (returns relative position)
class Data
{
public:
    Data(long val) : myValue(val) { }
   ~Data() { }

public:
   long Compare(const Data&);

public:
   void Show() { std::cout << myValue << std::endl; }

private:
   long myValue;
};

// forward declarations
class Node;
class HeadNode;
class TailNode;
class InternalNode;

// ADT representing the node object in the list
// every derived class must override Insert and Show
class Node
{
public:
   Node() { }
   virtual ~Node() { }

public:
   virtual Node* Insert(Data* theData) = 0;

public:
   virtual void Show() = 0;
};

// This is the node which holds the actual object
// In this case the object is of type Data
// We'll see how to make this more general when
// we cover templates
class InternalNode : public Node
{
public:
   // all the constructor does is to initialize
   InternalNode(Data* theData, Node* next) : myData(theData), myNext(next) { }
   ~InternalNode() { delete myNext; delete myData; }

public:
   virtual Node* Insert(Data* theData);

public:
   virtual void Show()
   {
      myData->Show();   // delegate!
      myNext->Show();
   }

private:
   Data* myData; // the data itself
   Node* myNext; // points to next node in the linked list
};

// Tail node is just a sentinel
class TailNode : public Node
{
public:
   TailNode() { }
   ~TailNode() { }

public:
   virtual Node* Insert(Data* theData);
   virtual void Show() { }
};

// Head node has no data, it just points
// to the very beginning of the list
class HeadNode : public Node
{
public:
   HeadNode();
   ~HeadNode() { delete myNext; }

public:
   virtual Node* Insert(Data* theData);

public:
   virtual void Show() { myNext->Show(); }

private:
   Node* myNext;
};

// I get all the credit and do none of the work
class LinkedList
{
public:
   LinkedList();
   ~LinkedList() { delete myHead; }

public:
   void Insert(Data* theData);

public:
   void ShowAll() { myHead->Show(); }

private:
   HeadNode* myHead;
};

// test driver program
int main()
{
   Data* pData;
   int val;
   LinkedList ll;

   // ask the user to produce some values
   // put them in the list
   for (;;)
   {
      std::cout << "What value? (0 to stop): ";
      std::cin >> val;

      if (!val)
      {
         std::cout << "\n";
         break;
      }

      pData = new Data(val);
      ll.Insert(pData);
   }

   // now walk the list and show the data
   ll.ShowAll();

   // ll falls out of scope and is destroyed!
}

// Compare is used to decide where in the list
// a particular object belongs.
long Data::Compare(const Data& theOtherData)
{
   if (myValue < theOtherData.myValue)
   {
      return nIsSmaller;
   }

   if (myValue > theOtherData.myValue)
   {
      return nIsLarger;
   }
   else
   {
      return nIsSame;
   }
}

// the meat of the list
// when you put a new object into the list
// it is passed to the node which figures out
// where it goes and inserts it into the list
Node* InternalNode::Insert(Data* theData)
{
   // is the new guy bigger or smaller than me?
   int result = myData->Compare(*theData);

   switch (result)
   {
   default:
      // by convention if it is the same as me it comes first
   case nIsSame:   // fall through
   case nIsLarger: // new data comes before me
   {
      InternalNode* dataNode = new InternalNode(theData, this);
      return dataNode;
   }

   // it is bigger than I am so pass it on to the next
   // node and let HIM handle it.
   case nIsSmaller:
   {
      myNext = myNext->Insert(theData);
      return this;
   }
   }
}

// if data comes to me, it must be inserted before me
// as I am the tail and NOTHING comes after me
Node* TailNode::Insert(Data* theData)
{
   InternalNode* dataNode = new InternalNode(theData, this);
   return dataNode;
}

// As soon as the head is created
// it creates the tail
HeadNode::HeadNode()
{
   myNext = new TailNode;
}

// Nothing comes before the head so just
// pass the data on to the next node
Node* HeadNode::Insert(Data* theData)
{
   myNext = myNext->Insert(theData);
   return this;
}

// At birth, I create the head node
// It creates the tail node
// So an empty list points to the head which
// points to the tail and has nothing between
LinkedList::LinkedList()
{
   myHead = new HeadNode;
}

// Delegate, delegate, delegate
void LinkedList::Insert(Data* pData)
{
   myHead->Insert(pData);
}

#include "list.h"

int main()
{
    const int NO_LISTS{4}; // or create dynamically

    list array_of_lists[NO_LISTS];

    int list_no{2}; // for arguments sake, or prompt + cin
    int value_to_be_listed{78}; // // for arguments sake, or prompt + cin

    array_of_lists[list_no].insert(value);
    
    return 0;
}