// To get rid of the warning about Node  use Node<T> - I didn't since the book did not

/**
   A class that implements the ADT sorted list by using a chain of linked nodes.
   Uses an array of headers (firstNode).

   @author CSIT265 (see textbook for outline)
   @version 3.0
*/
public class SortedLinkedList<T extends Comparable<? super T>>
    implements SortedListInterface<T>
{

   private int  numberOfHeaders;  // number of chains
   private Headers[] firstNodeOnChain; // reference to first node of chain
   private int[] numberOfEntriesOnChain;  // number entries per chain


   public SortedLinkedList(int maxKeys)  // constructor number of keys
   {
       numberOfEntriesOnChain = new int[maxKeys];
       firstNodeOnChain = new Headers[maxKeys];
       for (int index=0; index < maxKeys; index ++)
       {
           numberOfEntriesOnChain[index] = 0;
           firstNodeOnChain[index] = new Headers();
       }

       numberOfHeaders = 0;
   } // end default constructor

   public void add(T newEntry, String entryKey)  // object and key
   {
      Node newNode = new Node(newEntry, null);
      int chain;
      int resp;

      chain = findHeader(firstNodeOnChain, numberOfHeaders, entryKey);  // binary search array of headers

      if (chain == -1)  // no header
      {
          chain = addNewHeader(firstNodeOnChain, numberOfEntriesOnChain, numberOfHeaders, entryKey); // insert key into header array
          firstNodeOnChain[chain].setFirst(newNode);  // set link to node
          numberOfHeaders ++;

      }

      else
      {
          Node nodeBefore = getNodeBefore(newEntry, chain);

          if (isEmpty(chain+1) || (nodeBefore == null)) // add at beginning
          {
              newNode.setNextNode(firstNodeOnChain[chain].getFirst());
              firstNodeOnChain[chain].setFirst(newNode);
          }
          else                                   // add after nodeBefore
          {
              Node nodeAfter = nodeBefore.getNextNode();
              newNode.setNextNode(nodeAfter);
              nodeBefore.setNextNode(newNode);
          }  // end else not first

      } // end walk chain

      numberOfEntriesOnChain[chain]++;

   } // end add


   /* Uses binary search to determine if the searchArg is in the list

   @param headers the list, length of list, and search argument

   @return position in the list or -1  */

   public int findHeader(Headers[] headers, int length, String searchArg)
   {
       int first = 0;
       int last = length-1;
       int mid = 0;
       boolean found = false;

       while (first <= last && !found)
       {
           mid = (first + last) / 2;
           if (headers[mid].getKey().equals(searchArg))
               found = true;
           else
               if (headers[mid].getKey().compareTo(searchArg) < 0)
                   first = mid + 1;
               else
                   last = mid - 1;
       }

       if (found)
           return mid;

       else
           return -1;
   }//end findHeader

   public T[] getObjectsForKey (String key)
   {

       int index = findHeader(firstNodeOnChain, numberOfHeaders, key);
       int size = getLength(index);
       T[] fly = (T[])new Comparable[size];
       if (index != -1)
       {
           Node currentNode = firstNodeOnChain[index].getFirst();
           int cnt = 0;
           while(currentNode != null)
               {
               fly[cnt] = (T)currentNode.getData();
               ++cnt;
               currentNode = currentNode.getNextNode();

               }
                return fly;
        }       else
                return fly;
       }
 /* Inserts into ordered header list the new element

   @param headers the list, length of list, and new key */

   public int addNewHeader(Headers[] headers, int[] numberOfEntriesOnChain, int length, String newKey)
   {
       int index = length-1;
       boolean found = false;
       String tempKey;
       Node tempNode;

       while (index >= 0 && ! found)
       {
           tempKey = headers[index].getKey();
           if (tempKey.compareTo(newKey) > 0)
           {
               // move down
               tempNode = headers[index].getFirst();
               headers[index+1].setInfo(tempKey, tempNode);
               numberOfEntriesOnChain[index+1] = numberOfEntriesOnChain[index];
               index --;
           }
           else
               found = true;
       }
       index ++;

       headers[index].setKey(newKey);
       headers[index].setFirst(null);
       numberOfEntriesOnChain[index] = 0;

       return index;
   }


   /* Finds the node that is before the node that
      should or does contain a given entry.
      @param anEntry  the object to be located and the chain #
      @return either a reference to the node that is before the node
              that contains or should contain anEntry, or null if
              no prior node exists (that is, if anEntry belongs at
              the beginning of the list) */
   private Node<T> getNodeBefore(T anEntry, int chain)
   {
      Node nodeBefore = null;

      if (numberOfEntriesOnChain[chain] > 0) // there is a list
      {
          Node currentNode = firstNodeOnChain[chain].getFirst();

          if (currentNode != null)
          {
              while ( (currentNode != null) &&
                      (anEntry.compareTo((T)currentNode.getData()) > 0) )
              {
                  nodeBefore = currentNode;
                  currentNode = currentNode.getNextNode();
              } // end while
          }

      }

      return nodeBefore;
   } // end getNodeBefore


   /* Removes entry
   @param anEntry  the object to be removed and the key
   @return true/false */
   public boolean remove(T anEntry, String entryKey)
   {
      boolean found = false;

      if (numberOfHeaders > 0)
      {

          int chain = findHeader(firstNodeOnChain, numberOfHeaders, entryKey);
          if (chain != -1)  // there is a chain
          {
              Node nodeToRemove;
              Node nodeBefore = getNodeBefore(anEntry, chain);

              if (nodeBefore == null)  // first node on list
                  nodeToRemove = firstNodeOnChain[chain].getFirst();
              else
                  nodeToRemove = nodeBefore.getNextNode();

              if ((nodeToRemove != null) && anEntry.compareTo((T)nodeToRemove.getData()) == 0 )  // fields match
              {
                  found = true;

                  if (nodeBefore == null)
                      firstNodeOnChain[chain].setFirst(nodeToRemove.getNextNode());  // new first node
                  else
                  {
                      Node nodeAfter = nodeToRemove.getNextNode();
                      nodeBefore.setNextNode(nodeAfter);    // node before linked to node after
                  } // end if
              }
              numberOfEntriesOnChain[chain]--;

        } // end if  there is a chain
      } // end if  there is a list

      return found;
   } // end remove

   /* Removes entry
   @param position on chain and the chain
   @return object removed  */
   public T remove(int givenPosition, int chain)
   {
       T result = null;                           // return value
       chain--;
       if (numberOfEntriesOnChain[chain] >= 0) // there is a chain
       {
           if ((givenPosition >= 1) && (givenPosition <= numberOfEntriesOnChain[chain])) // within limit
           {
               assert !isEmpty(chain+1);

               if (givenPosition == 1)                 // case 1: remove first entry
               {
                   result = (T)firstNodeOnChain[chain].getFirst().getData();        // save entry to be removed
                   firstNodeOnChain[chain].setFirst(firstNodeOnChain[chain].getFirst().getNextNode());
               }
               else                                    // case 2: givenPosition > 1
               {
                   Node nodeBefore = getNodeAt(givenPosition-1, chain+1);
                   Node nodeToRemove = nodeBefore.getNextNode();
                   Node nodeAfter = nodeToRemove.getNextNode();
                   nodeBefore.setNextNode(nodeAfter);   // disconnect the node to be removed
                   result = (T)nodeToRemove.getData();     // save entry to be removed
               } // end if

               numberOfEntriesOnChain[chain]--;
           } // end if
       } // end if there is a chain
       return result;                             // return removed entry, or
                                                 // null if operation fails
   } // end remove

   /* Tests position of object on the chain
   @param objec and  key
   @return position (1 to numberOfEntriesOnChain  */



   public int getPosition(T anEntry, String entryKey)
   {
       int position = 0;
       boolean found = false;

       if (numberOfHeaders > 0)  // there are chains
       {
           int chain = findHeader(firstNodeOnChain, numberOfHeaders, entryKey);
           if (chain != -1)  // there is a chain for the key
           {
               Node currentNode = firstNodeOnChain[chain].getFirst();

               position = 1;

               while ( (currentNode != null) && !found) // sequential walk
               {
                   if (anEntry.compareTo((T)currentNode.getData()) == 0)
                       found = true;
                   else
                   {
                       currentNode = currentNode.getNextNode();
                       position++;
                   }
               } // end while

               if ( (currentNode == null) || anEntry.compareTo((T)currentNode.getData()) != 0)  // not found
                   position = -position;
           }
           return position;
       }
       else
           return -1;
   } // end getPosition

   /* Clears all headers and sets numberOfEntriesOnChain to 0
     */
   public final void clear()
   {
      for (int index=0; index < numberOfHeaders; index++)
      {
          firstNodeOnChain[index].setFirst(null);
          firstNodeOnChain[index].setKey("");
          numberOfEntriesOnChain[index] = 0;
      }
      numberOfHeaders = 0;

   } // end clear

   /* gets object in a specific position on a specific chain
   @param position and chain
   @return object  */
   public T getEntry(int givenPosition, int chain)
   {
      T result = null;  // result to return

      if ((givenPosition >= 1) && (givenPosition <= numberOfEntriesOnChain[chain-1]))  // in bounds
      {
         assert !isEmpty(chain);
         result = (T)getNodeAt(givenPosition, chain).getData();
      } // end if

      return result;
   } // end getEntry

   /* List contains object with specific key
   @param Object and Key
   @return true/false  */
   public boolean contains(T anEntry, String entryKey)
   {
      boolean found = false;
      int chain = findHeader(firstNodeOnChain, numberOfHeaders, entryKey);

      if (chain == -1)
      {
          return false;
      }

      Node currentNode = firstNodeOnChain[chain].getFirst();

      while (!found && (currentNode != null))  // sequentially walk the chain
      {
          if (anEntry.compareTo((T)currentNode.getData()) == 0)
          {
              found = true;
          }
          else
          {
              currentNode = currentNode.getNextNode();
          }
      } // end while

      return found;
   } // end contains

   /* gets length of list
      @return count of nodes  */
   public int getLength()
   {
       int num = 0;

       for (int index=0; index < numberOfHeaders; index++)
          num = num + numberOfEntriesOnChain[index];

       return num;
   } // end getLength

   /* gets length of specific chain
     @param chain
   @return count of nodes on chain  */
   public int getLength(int chain)
   {
       return numberOfEntriesOnChain[chain-1];
   } // end getLength

   /* List empty
    @return true/false  */
   public boolean isEmpty()
   {
      if (numberOfHeaders == 0)
      {
         return true;
      }
      else
      {
          return false;
      }
   } // end isEmpty

   /* Specific chain empty
    * @param chain
   @return true/false  */
   public boolean isEmpty(int chain)
   {
      if (numberOfEntriesOnChain[chain-1] == 0)
      {
         return true;
      }
      else
      {
         return false;
      } // end if

   } // end isEmpty

   /* List full
   @return false  */
   public boolean isFull()
   {
      return false;
   } // end isFull

   /* Get Node at specific position on specific chain
   @param position and chain
   @return Object*/
   private Node getNodeAt(int givenPosition, int chain)
   {
       // chain exists and within bounds
      assert !isEmpty(chain) && (1 <= givenPosition) && (givenPosition <= numberOfEntriesOnChain[chain-1]);
      Node currentNode = firstNodeOnChain[chain-1].getFirst();

         // traverse the list to locate the desired node
      for (int counter = 2; counter <= givenPosition; counter++)  // sequentially walk list
         currentNode = currentNode.getNextNode();

      assert currentNode != null;
      return currentNode;
   } // end getNodeAt

   public T[] toArray()
   {
      // the cast is safe because the new array contains null entries
      @SuppressWarnings("unchecked")
      int chain, index = 0;
      int num = 0;
      int count = 0;

      for (chain=0; chain < numberOfHeaders; chain ++)
      {
          num = num + numberOfEntriesOnChain[chain] ;
      }

      T[] result = (T[])new Comparable[num]; // warning: [unchecked] unchecked cast

      for (chain = 0; chain < numberOfHeaders; chain ++)
      {
          Node currentNode = firstNodeOnChain[chain].getFirst();
          System.out.println(chain + " " + currentNode.getData().toString());
          index = 0;
          while ((index < numberOfEntriesOnChain[chain]) && (currentNode != null))
          {
              result[count] = (T)currentNode.getData();
              currentNode = currentNode.getNextNode();
              index++;
              count++;
          } // end while next on specific chain
      }  // end of for - next chain
      return result;
   } // end toArray

 } // end SortedLinkedList