//=-- LinkedList.h - Define a doubly linked list data structure -----*- C++ -*-=
//
//  This file defines a template for a doubly linked list class.  It specifies 
//    three classes:
//
//  LLLink:  Class that represents a link in the linked list.  Should not have
//    to be dealt with by the user directly.
//
//  LinkedList:  Class that represents the list entity itself.  There are lots
//    of useful methods present here.
//
//  LinkedListIterator:  Iterator to loop through a linked list.  Returned by
//    the LinkedList::GetIterator method.  Note that you should never declare
//    an object of this type.  Instead, declare it as LinkedList<..>::Iterator
//
//=---------------------------------------------------------------------------=
//  This file is copyright (c) 1997-2000 Chris Lattner
//=---------------------------------------------------------------------------=

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include "Object.h"

#if defined(WIN32) || defined(_WIN32)         // It's Winderz!
#include "PlatformAbstraction.h"  // Include this to disable a warning. sucky
#endif

// Forward declare my iterator class...
template <class T> class MSAPI LinkedListIterator;

// LLLink - The class that represents a link in the linked list.  
//
template <class T> class MSAPI LLLink : public Object {
public :
  T Data;
  LLLink *next, *prev;   // Forward and backward link pointers

  inline LLLink<T>(const T &data) : Data(data) { next = prev = 0; }
  inline LLLink<T> *GetNext() const { return next; }
  inline LLLink<T> *GetPrev() const { return prev; }
  inline LLLink<T> *GetCopy() { return new LLLink<T>(Data); }

  // operator* - "Dereference" Iterator
  T &operator*() { return Data; }
  T &operator*() const { return Data; }

  // Operator ->, used to do stuff like LL->X where X is a member of Data.
  T *operator ->() const { return &Data; }
  T *operator ->() { return &Data; }

  int Compare(const Object &L) const { 
    if (Data > ((LLLink<T> &)L).Data)
      return 1;
    else if (Data == ((LLLink<T> &)L).Data)
      return 0;
    return -1;
  }

  ostream &print(ostream &o) const { return o << Data; }
};

template <class T> class MSAPI LinkedList : public Object {
  friend class LinkedListIterator<T>;
public : 
  // Typedefs for users to use so that they don't have to know the name of the
  // node and iterator classes explicitly...
  //
  typedef LinkedListIterator<T> Iterator;
  typedef LLLink<T> Node;

  inline LinkedList<T>() {  // Constructor - make a new empty list
    head = tail = 0;
    NumNodes = 0;
  }

  inline LinkedList<T>(const LinkedList<T> &L) : Object(L) {
    head = tail = 0;
    NumNodes = 0;
    CopyList(L);
  }

  int Compare(const Object &L) const { 
    if ((head == 0) || (((LinkedList<T> &)L).head == 0)) return 0;
    if (head->Data > ((LinkedList<T> &)L).head->Data)
      return 1;
    else if (head->Data == ((LinkedList<T> &)L).head->Data)
      return 0;
    return -1;
  }

  // Public accessor methods...
  inline Node *GetHead() const { return head; }
  inline Node *GetTail() const { return tail; }

  // Is the list empty?
  inline int IsEmpty() const { return head == 0; }
  inline int GetLength() const { return NumNodes; }

  // Add a node to the list
  void AddToHead(Node *Node);
  void AddToTail(Node *Node);

  // Add a data item to the list
  inline void AddToHead(const T &Data) { AddToHead(new Node(Data)); }
  inline void AddToTail(const T &Data) { AddToTail(new Node(Data)); }

  // Remove a node from the list
  void RemoveNode(Node *Node);
  inline void RemoveHead() { RemoveNode(head); }
  inline void RemoveTail() { RemoveNode(tail); }

  // Unlinks a node from the list.  Same as remove, except node is not deleted
  void UnlinkNode(Node *Node);

  int RemoveMatchingNodes(const Node &);
  int RemoveMatchingData(const T &Data) { return RemoveMatchingNodes(Node(Data)); }

  // Do a linear search for something
  Node *SearchList(const T &Data) const;
  inline Node *SearchList(const Node &Node) const {
    return SearchList(Node.Data);
  }

  // Append - Append a list to this one...
  //
  void Append(const LinkedList<T> &Appending);
  
  // operator+ - Synonym for Append.
  inline LinkedList<T> operator+(const LinkedList<T> &Right) {
    LinkedList<T> Result = *this;
    Result.Append(Right);
    return Result;
  }
  
  // Copy a linked list into "this" one...
  //
  inline void CopyList(const LinkedList<T> &LL) {
    ClearList();  // First, clear out this list...
    Append(LL);
  }

  inline void operator= (const LinkedList<T> &LL) { CopyList(LL); }

  void Sort(int (*CompareFN)(T *, T *) = &DefaultCompare);

  // Erase all of the nodes
  void ClearList();

  // Get an iterator pointing to the first element of the hashtable.  This 
  //   iterator steps through in the order of the list... 
  inline Iterator GetIterator() const { 
    return Iterator(*this);
  }
  
  // LinkedList destructor - Deletes all of the nodes...
  ~LinkedList() { 
    ClearList();
  }

  inline void Add(Node *Node) { AddToTail(Node); }
  inline void Add(const T &Data) { AddToTail(new Node(Data)); }
  ostream &print(ostream &stream) const ;

private :
  Node *head, *tail;
  int NumNodes;
  
  // Helper function for sort
  void MergeSort(LinkedList<T> &List, int (*CompareFN)(T *, T *));
};

// LinkedListIterator defines an iterator for stepping through a list in order
//
template <class T>
class MSAPI LinkedListIterator {
public :

  // Create an iterator starting at the first element...
  LinkedListIterator<T>(const LinkedList<T> &ll) {
    Link = 0;
    LL = &ll;
    operator++(0);
  }

  // Copy an iterator...
  LinkedListIterator<T>(const LinkedListIterator<T> &LLI) {
    LL = LLI.LL;
    Link = LLI.Link;
  }

  // Copy an iterator...
  LinkedListIterator<T> &operator=(const LinkedListIterator<T> &LLI) {
    LL = LLI.LL;
    Link = LLI.Link;
    return *this;
  }

  // Operator++ - Move to the next element of the list...
  LinkedListIterator<T> operator++(int) {
    if (Link != 0)
      Link = Link->next;
    else
      Link = LL->head;
    return *this;
  }

  // Remove - Remove the current node from the list, move to the next node.
  LinkedListIterator<T> Remove() {
    if (Link != 0) {
      LLLink<T> *OldLink = Link;
      Link = Link->next;
      ((LinkedList<T> *)LL)->RemoveNode(OldLink);
    } else {
      Link = LL->head;
    }
    return *this;
  }

  // Operator-- - Move to the previous element of the list...
  LinkedListIterator<T> operator--(int) {
    if (Link != 0)
      Link = Link->prev;
    else
      Link = LL->tail;
    return *this;
  }

  // Returns 0 at the end of the data structure...
  operator int() const {
    return Link != 0;
  }

  // operator* - "Dereference" Iterator
  T &operator*() {
    return Link->Data;
  }

  T operator*() const {
    return Link->Data;
  }

  const T *operator ->() const {
    return &Link->Data;
  }

  T *operator ->() {
    return &Link->Data;
  }

private :
  LLLink<T> *Link;
  const LinkedList<T> *LL;
};


// print - Prints out the entire linked list, by looping through each of the
//   links in the list.  The << operator is overloaded to call this method.
//
template <class T>
ostream &LinkedList<T>::print(ostream &stream) const {

  for (Node *K = GetHead(); K != 0; K = K->GetNext())
    stream << K->Data;

  return stream;
}

// AddToHead - Adds a node to the head of the list.  
//
template <class T>
void LinkedList<T>::AddToHead(LLLink<T> *Node) {
  if (head == 0) {               // There are no nodes yet.
    head = tail = Node;
    Node->prev = Node->next = 0;
  } else {  
    Node->prev = 0;
    Node->next = head;
    head->prev = Node;
    head = Node;
  }
  NumNodes++;
}

// AddToTail - Add a node to the end of the list
//
template <class T>
void LinkedList<T>::AddToTail(LLLink<T> *Node) {
  if (tail == 0) {
    AddToHead(Node);  // Empty linked list...
  } else {  
    Node->next = 0;
    Node->prev = tail;
    tail->next = Node;
    tail = Node;
    NumNodes++;
  }
}

// RemoveNode - Remove and delete a node from the list
//
template <class T>
void LinkedList<T>::RemoveNode(LLLink<T> *Node) {
  if (Node == 0) return;
  
  if (head == Node)
    head = Node->next;
  if (tail == Node)
    tail = Node->prev;
  if (Node->next != 0) 
    Node->next->prev = Node->prev;
  if (Node->prev != 0)
    Node->prev->next = Node->next;
  delete Node;
  NumNodes--;
}

// UnlinkNode - Remove a node from the linked list.  Does not delete node.
//
template <class T>
void LinkedList<T>::UnlinkNode(LLLink<T> *Node) {
  if (Node == 0) return;
  
  if (head == Node)
    head = Node->next;
  if (tail == Node)
    tail = Node->prev;
  if (Node->next != 0) 
    Node->next->prev = Node->prev;
  if (Node->prev != 0)
    Node->prev->next = Node->next;
  NumNodes--;
}

// RemoveMatchingNodes - Remove all nodes that are equal to the parameter
//
template <class T>
int LinkedList<T>::RemoveMatchingNodes(const LLLink<T> &Link) {
  LLLink<T> *Current = GetHead(), *Prev;
  int NodeNotFound = 1;

  while (Current) {
    if (*Current == Link) {
      Prev = Current->prev;
      RemoveNode(Current);
      if (!Prev) Prev = head;
      Current = Prev;
      NodeNotFound = 0;
      if (!Prev) break;
    }

    Current = Current->GetNext();
  }  

  return NodeNotFound;
}

// Append - Append a list to this one...
//
template <class T>
void LinkedList<T>::Append(const LinkedList<T> &Appending) {
  LLLink<T> *Current = Appending.GetHead();
  while (Current) {
    AddToTail(Current->GetCopy());
    Current = Current->GetNext();
  }  
}

// SearchList - Search for a link
//
template <class T>
LLLink<T> *LinkedList<T>::SearchList(const T &data) const {
  LLLink<T> *Result = GetHead();
                              
  while (Result != 0) {
    if (Result->Data == data) 
      break;

    Result = Result->GetNext();
  }

  return Result;
}

template <class T>
static int DefaultCompare(T *A, T *B) {
  return (*A) > (*B);
}

// Sort - Sorts a linked list with the recursive MergeSort algorithm
//
template <class T>
void LinkedList<T>::MergeSort(LinkedList<T> &List, int (*CompareFN)(T *, T *)) {
  int i, Length = List.GetLength();
  if (Length < 2) return;

  LinkedList<T> A, B;
  LLLink<T> *Node = 0, *NodeB = 0;
  
  for (i = 0; i < Length >> 1; i++) {  // Put the first half in A
    Node = List.GetHead();
    List.UnlinkNode(Node);
    A.AddToTail(Node);
  }

  while (List.GetHead() != 0) {        // Put the second half in B
    Node = List.GetHead();
    List.UnlinkNode(Node);
    B.AddToTail(Node);
  }

  MergeSort(A, CompareFN);             // Recursive calls
  MergeSort(B, CompareFN);

  while (((Node  = A.GetHead()) != 0) &&  // Merge lists together
         ((NodeB = B.GetHead()) != 0)) {

    if ((*CompareFN)(&NodeB->Data, &Node->Data)) {
      A.UnlinkNode(Node);
      List.AddToTail(Node);
    } else {
      B.UnlinkNode(NodeB);
      List.AddToTail(NodeB);
    }
  }

  while ((Node  = A.GetHead()) != 0) {
    A.UnlinkNode(Node);
    List.AddToTail(Node);
  }

  while ((NodeB = B.GetHead()) != 0) {
    B.UnlinkNode(NodeB);
    List.AddToTail(NodeB);
  }
}


// Sort - Sorts a linked list with the simple and efficient merge sort...
//
template <class T>
void LinkedList<T>::Sort(int (*CompareFN)(T *, T *)) {
  if (CompareFN == 0)   // Use the comparison operators as the defaults
    CompareFN = &DefaultCompare;

  MergeSort(*this, CompareFN);
}

// ClearList - Remove all of the nodes from the list
//
template <class T>
void LinkedList<T>::ClearList() {
  while (head != 0)
    RemoveHead();
}

#endif

