public class LinkedIntList {
  private IntListNode head;
  private IntListNode tail;
  private int size;
  
  LinkedIntList(){
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  
  // returns the node at the head
  public IntListNode head(){
    return this.head;
  }
  
  // returns the node at the tail
  public IntListNode tail(){
    return this.tail;
  }
  
  // returns the size of the list
  public int size(){
    return this.size;
  }
  
  
  // adds a node with value == value at the tail of the list
  public void addToTail(int value){
    IntListNode node = new IntListNode(value);
    
    if(size == 0) {
      head = node;
      tail = node;
      size++;
    } else {
      tail.setNext(node);
      tail = node;
      size++;
    }
  }
  
  
  // adds a node with value == value at the head of the list
  public void addToHead(int value){
    IntListNode node = new IntListNode(value);
    
    if(size == 0) {
      head = node;
      tail = node;
      size++;
    } else {
      node.setNext(head);
      head = node;
      size++;
    }
    
  }
  
//returns true if a node in the list has has a value of value
 // otherwise returns false
 public boolean contains(int value){
   IntListNode current = head;
   
   while(current != null) {
     if(current.getValue() == value){
       return true;
     }
     
     current = current.getNext();
   }
   
   return false;
 }
  
  
  // adds a node with value == value at the indicated index
  public void addToPosition(int value, int index) {
    if(index == 0){
      addToHead(value);
      return;
    } else if(index == size){
      addToTail(value);
      return;
    }
    
    IntListNode node = new IntListNode(value);
    
    IntListNode current = head;
    
    // move current to right before position
    for(int pos = 1; pos < index; pos++) {
      current = current.getNext();
    }
    
    // change pointers
    node.setNext(current.getNext());
    current.setNext(node);
    
    size++;

  }
  
  
  
  // Should return first index that value appears at
  // if value is not in the list, returns -1
  public int indexOf(int value){
    int index = 0;
    
    IntListNode current = head;
    while(current != null) {
      
      if(current.getValue() == value){
        return index;
      }
      
      current = current.getNext();
      
      index++;
    }
    
    return -1;
  }
  
  // removes the first appearance of this value from the list
  public void delete(int value) {
    if(head != null && head.getValue() == value) {
      head = head.getNext();
      size--;
      return;
    }
    
    IntListNode current = head;
    IntListNode prev = null;
    
    while(current != null) {
      if(current.getValue() == value){
        prev.setNext(current.getNext());
        size--;
        return;
      }
      
      prev = current;
      current = current.getNext();
    }
    
  }
  
  // swap the nodes at these indices
  // return true when done
  // return false if they cannot be swapped for any reason
  public boolean swap(int indexOne, int indexTwo) {
    
    // check the inputs
    if(size == 0) {
      // list empty, nothing to do
      return true;
    } else if(indexOne >= size || indexOne >= size) {
      // trying to swap an index that is too large
      return false;
    } else if (indexOne < 0 || indexOne < 0) {
      // trying to swap an index that is too small
      return false;
    } else if (indexOne == indexTwo) {
      // tried to swap with self, no work required
      return true;
    }
    
    // want to know which is first
    int frontIndex = Math.min(indexOne, indexTwo);
    int backIndex = Math.max(indexOne, indexTwo);
    
    // There are a few cases now:
    // 1 - frontIndex is the head, nothing before it (non-adjacent)
    // 2 - Nodes are adjacent (backIndex - frontIndex == 1), neither at head
    // 3 - Nodes are adjacent and one is at head
    // 4 - Generic case, nodes are non adjacent and not at head
    
    // also need to keep track of if we'll need to change the tail pointer
    boolean swappingTail = (backIndex == size -1);
    
    if(backIndex - frontIndex == 1) {
      if(frontIndex == 0) {
        // in case 3
        
        if(swappingTail) {
          // we can just update the tail now if we need to
          tail = head;
        }
        
        // need to keep track of one node for the swap
        IntListNode secondNode = head.getNext();
        
        // now we can swap pointers
        head.setNext(secondNode.getNext());
        secondNode.setNext(head);
        
        // change head to point to second node (which is the new head)
        head = secondNode;
        
      } else {
        // in case 2
        
        IntListNode tracker = head;
        for(int i = 1; i < frontIndex; i++) {
          tracker = tracker.getNext();
        }
        // tracker now at node before first node to be swaped.
        
        if(swappingTail) {
          // we can just update the tail now if we need to
          tail = tracker.getNext();
        }
        
        // get the nodes we need to keep track of
        // going to be changing 3 pointers
        // 1 - Pointer to first node
        // 2 - Pointer between first and second node
        // 3 - pointer to stuff after second node
        
        // points to second node
        IntListNode secondNode = tracker.getNext().getNext();
        
        // start swapping pointers
        
        // first node points to after second
        tracker.getNext().setNext(secondNode.getNext());
        // second node now points to first node
        secondNode.setNext(tracker.getNext());
        // tracker points to second node (so second node comes first
        tracker.setNext(secondNode);
      }
    } else {
      if(frontIndex == 0) {
        // in case 1
        
        if(swappingTail) {
          // we can just update the tail now if we need to
          tail = head;
        }
        
        // get the nodes we need to track
        IntListNode afterHead = head.getNext();
        IntListNode beforeSecond = head;
        // advance this node to the right position
        for(int i = 1; i < backIndex; i++) {
          beforeSecond = beforeSecond.getNext();
        }
        IntListNode second = beforeSecond.getNext();
        
        // swap pointers
        
        // first gets pointed to after second
        head.setNext(second.getNext());
        // second gets pointed to after first
        second.setNext(afterHead);
        // what was pointing to the second now should point to the first
        beforeSecond.setNext(head);
        // set second to head
        head = second;
        
      } else {
        // in case 4 (generic)
        
        // get the nodes we need to track
        IntListNode beforeSecond = head;
        IntListNode beforeFirst = head;
        // advance this node to the right position
        for(int i = 1; i < backIndex; i++) {
          if(i < frontIndex) {
            // only advance this one as far as we need to
            // but faster to do both in one loop
            beforeFirst = beforeFirst.getNext();
          }
          beforeSecond = beforeSecond.getNext();
        }
        IntListNode first = beforeFirst.getNext();
        IntListNode second = beforeSecond.getNext();
        IntListNode afterFirst = first.getNext();
        
        if(swappingTail) {
          // we can just update the tail now if we need to
          tail = first;
        }

        
        // swap pointers
        
        // first gets pointed to after second
        first.setNext(second.getNext());
        // second gets pointed to after first
        second.setNext(afterFirst);
        // what was pointing to the second now should point to the first
        beforeSecond.setNext(first);
        // set what was before the first to point to the second
        beforeFirst.setNext(second);
      }
    }
    
    return true;
  }
  
  public String toString() {
    StringBuilder sb = new StringBuilder();
    IntListNode trace = head;
    sb.append("[");
    while(trace != null) {
      sb.append(trace.toString());
      sb.append(",");
      trace = trace.getNext();
    }
    if(this.size() > 0){
      sb.deleteCharAt(sb.length() - 1);
    }
    sb.append("]");
    
    return sb.toString();
  }
  
  public static void main(String[] args) {
    LinkedIntList ll = new LinkedIntList();
    System.out.println(ll); //  should be empty
    ll.addToHead(1);
    System.out.println(ll); //  should be [1]
    ll.addToHead(0);
    System.out.println(ll); //  should be [0,1]
    ll.addToTail(3);
    System.out.println(ll); //  should be [0,1,3]
    ll.addToPosition(2,2);
    System.out.println(ll); //  should be [0,1,2,3]
    System.out.println("Checking some methods:");
    System.out.println(ll.contains(1)); // should be true
    System.out.println(ll.contains(4)); // should be false
    System.out.println(ll.indexOf(1)); // should be 1
    System.out.println(ll.indexOf(4)); // should be -1
    System.out.println("Checking delete:");
    System.out.println(ll); // should be [0,1,2,3]
    ll.delete(1); 
    System.out.println(ll); // should be [0,2,3]
    ll.swap(0, 1);
    System.out.println(ll); // should be [2,0,3]
    ll.swap(1, 2);
    System.out.println(ll); // should be [2,3,0]
    ll.swap(0, 2);
    System.out.println(ll); // should be [0,3,2]
    ll.addToTail(4);
    System.out.println(ll); // should be [0,3,2,4]
    ll.swap(1, 3);
    System.out.println(ll); // should be [0,4,2,3]
  }

}