/**
 * Headerless singly linked list, elements are ordered by key field.
 * @author Jaanus Poial
 * @version 0.9
 */
public class Element implements java.util.Iterator<Element>, 
                                Comparable<Element> {

   /** key, ordering is defined by the key */
   private String key;

   /** next element in the list */
   private Element next;

   /** Default constructor. */
   Element() { 
      this (null, null);
   }

   /** Constructor with key. 
    * @param v key
    */
   Element (String v){
      this (v, null);
   }

   /** Constructor with key and next. 
    * @param v key
    * @param e next
    */
   Element (String v, Element e) {
      setKey (v);
      setNext (e);
   }

   /** Getter method for <code> next </code> field.
    * @return next element in the list or <code> null </code>.
    */
   public Element getNext() {
      return next;
   }

   /** Setter method of the <code> next </code> field.
    * @param e value to be stored
    * @return "old" value of the field
    */
   public Element setNext (Element e) {
      Element tmp = next; 
      next = e;
      return tmp;
   }

   /** Getter method of the <code> key </code> field.
    * @return key
    */
   public String getKey() {
      return key;
   } 

   /** Setter method of the <code> key </code> field.
    * @param v key
    * @return "old" value of the field
    */
   public String setKey (String v) {
      String tmp = key;
      key = v;
      return tmp;
   }

   /** Comparison of elements. Delegated to comparison of keys.
    * @param element second element in comparison
    * @return int according to Comparable interface description
    */
   @Override
   public int compareTo (Element element) {
      return getKey().compareTo (element.getKey());
   }

//========================================================================
// Standard operations on the list - add, merge, delete, find
//========================================================================

   /** Add element to the list.
    * @param e element to be added
    * @return first element of the changed list
    */
   public Element add (Element e) {
      if (e == null) return this; // actually, it is an error
      if (e == this) return this; // it is an error, too
      if (e.getKey().compareTo (getKey()) < 0) { // e.key < this.key
         e.setNext (this); // add to the beginning of the list
         return e;
      }
      Element ptr = this; // let us find the right place after ptr
      while (ptr.getNext() != null) {
         if (e.getKey().compareTo (ptr.getNext().getKey()) < 0) {
            // add after ptr
            e.setNext (ptr.getNext());
            ptr.setNext (e);
            return this;
         }
         ptr = ptr.getNext();
      }
      ptr.setNext (e);  // add to the end
      e.setNext (null); // just in case ...
      return this;
   }

   /** Merge lists <code> this </code> and <code> e </code>.
    * The result consists of shallow copies of original elements.
    * @param e first element of the second list
    * @return first element of the resulting list
    */
   public Element merge (Element e) {
      Element j1 = this; // placeholder in the first list
      Element j2 = e;    // placeholder in the second list
      Element smaller = null; // element to be cloned and added
      if (j2 == null) {
         smaller = j1;
         j1 = j1.getNext(); // here j1 cannot be null
      } else if (j2.getKey().compareTo (j1.getKey()) < 0) {
         smaller = j2;
         j2 = j2.getNext();
      } else {
         smaller = j1;
         j1 = j1.getNext();
      }
      Element res = new Element (smaller.getKey(), null); // result
      Element j = res; // placeholder in the resulting list
      while ((j1 != null) && (j2 != null)) { // both lists are non-empty
         if (j2.getKey().compareTo (j1.getKey()) < 0) {
            smaller = j2;
            j2 = j2.getNext();
         } else {
            smaller = j1;
            j1 = j1.getNext();
         }
         j.setNext (new Element (smaller.getKey(), null));
         j = j.getNext();
      }
      if (j1 == null) j1 = j2; // j1 is the remaining part 
      while (j1 != null) {
         j.setNext (new Element (j1.getKey(), null));
         j1 = j1.getNext();
         j = j.getNext();
      }
      return res;
   }

   /** Delete an element from the list. 
    * @param e element to be deleted
    * @return first element of the changed list or <code> null </code>
    */
   public Element delete (Element e) { 
      if (e == null) return this;      // nothing to be deleted (error)
      if (e == this) return getNext(); // delete the first element
      Element ptr = this;
      while (ptr != null) {
         if (e == ptr.getNext()) {
            ptr.setNext (e.getNext());
         }
         ptr = ptr.getNext();
      }
      return this;
   }

   /** Find an element by the value of key. 
    * @param key key to use
    * @return element or <code> null </code>.
    */
   public Element find (String key) {
      Element ptr = this;
      while (ptr != null) {
         if (key.compareTo (ptr.getKey()) == 0) return ptr;
         ptr = ptr.getNext();
      }
      return null;
   }

   /** String representation uses keys. 
    * @return list of keys
    */
   @Override
   public String toString() {
      StringBuffer buffer = new StringBuffer();
      Element ptr = this;
      while (ptr != null) {
         buffer.append (ptr.getKey().toString()); // key
         if (ptr.getNext() != null)
            buffer.append (", ");        // delimiter in the middle
            else buffer.append (";");    // delimiter in the end
         ptr = ptr.getNext();
      }
      return buffer.toString();      // buffer -> String
   }

   /** Does there exist a next element.
    * @return true or false
    */
   @Override
   public boolean hasNext() {
      return getNext() != null;
   }

   /** The next element in iterator.
    * @return next element
    */
   @Override
   public Element next() throws java.util.NoSuchElementException {
      if (getNext() == null)
         throw new java.util.NoSuchElementException();
      else
         return getNext();
   }

   @Override
   public void remove() {
      this.delete (getNext());
   }

   /** Main method. 
    * @param param command line arguments
    */
   public static void main (String[] param) {
      System.out.println ("Start");
      Element myList = null;
      System.out.println (myList);                      // null
      myList = new Element ("e1");
      System.out.println (myList);                      // e1;
      myList = myList.add (null);
      System.out.println (myList);                      // e1;
      myList = myList.add (new Element ("e0"));
      System.out.println (myList);                      // e0, e1;
      myList = myList.add (new Element ("e3"));
      System.out.println (myList);                      // e0, e1, e3;
      myList = myList.add (new Element ("e2"));
      System.out.println (myList);                      // e0, e1, e2, e3;
      myList = myList.delete (myList.find ("e4"));
      System.out.println (myList);                      // e0, e1, e2, e3;
      myList = myList.delete (myList.find ("e0"));
      System.out.println (myList);                      // e1, e2, e3;
      myList = myList.delete (myList.find ("e2"));
      System.out.println (myList);                      // e1, e3;
      myList = myList.delete (myList.find ("e3"));
      System.out.println (myList);                      // e1;
      myList = myList.delete (myList.find ("e1"));
      System.out.println (myList);                      // null
      Element otherList = new Element ("7");
      myList = new Element ("5");
      myList = myList.add (new Element ("3"));
      otherList = otherList.add (new Element ("4"));
      Element y = myList.merge (otherList);
      System.out.println (y);                           // 3 4 5 7
      System.out.println (myList);                      // 3 5
      System.out.println (otherList);                   // 4 7
      System.out.println ("Finish");

   }
}