import java.util.Iterator;

public class UnrolledDoublyLinkedList<Item extends Comparable<Item>> implements Iterable<Item> {
  
  private class Node {
  
    final static int MAX_ELEMENTS = 4;  // NOTE: we will require MAX_ELEMENTS to be even, so as 
                                        //       to avoid separate cases for splitting arrays
                                        //       when it is odd
    
    //////////////////////////////////////////////////
    // DO NOT ADD ANY ADDITIONAL INSTANCE VARIABLES //
    // FOR THE Node CLASS, BEYOND THE BELOW FOUR.   //
    //////////////////////////////////////////////////
    
    Item[] items;  // which must stay sorted least to greatest in accordance with item.compareTo()
                   // importantly, only the items in each node are sorted -- but from node to node, 
                   // things need not be that way.  For example, if MAX_ELEMENTS was 4, this would be ok
                   // H->[12,13]->[5,7,9,10]->[2,5,7,8]->[1,6,11,15]->
    
    int numItems;  // the number of items in this node
    Node next;  
    Node prev;
    
    Node() {
      ////////////////////////////////////////////////////////////////////////
      // ADD THE NEEDED CODE TO COMPLETE THE CONSTRUCTOR FOR THE Node CLASS // 
      ////////////////////////////////////////////////////////////////////////
    }
    
    public String toString() {
      String s = "[";
      for (int i = 0; i < this.numItems; i++) {
        s += items[i] + (i < this.numItems - 1 ? "," : "");
      }
      s += "]";
      return s;
    }
    
    public void insertInOrderPresumingRoomExists(Item item) {
      // presuming there is room in the node's (sorted) array, insert item in the first available cell, 
      // and then swap it from there with elements to its left (i.e., smaller indices) until the array 
      // is again in order -- much like the "insertion" step in an insertion sort

      //////////////////////////////////////////////////////////////////////////////////////
      // ADD CODE HERE TO ACCOMPLISH THE DESCRIPTION FOR THIS METHOD GIVEN DIRECTLY ABOVE //
      //////////////////////////////////////////////////////////////////////////////////////
    }
    
    public int binarySearch(Item item) {
       // returns index of item in items array when it exists there
       // otherwise, it returns the negative of one more than the index where it should appear

      //////////////////////////////////////////////////////////////////////////////////////
      // ADD CODE HERE TO ACCOMPLISH THE DESCRIPTION FOR THIS METHOD GIVEN DIRECTLY ABOVE //
      //////////////////////////////////////////////////////////////////////////////////////
    }
    
    // utility method for exchanging items at positions i and j:
    private void exch(int i, int j) {
      Item tmpItem = items[i];
      items[i] = items[j];
      items[j] = tmpItem;
    }
  }
  
  
  ///////////////////////////////////////////////////////////
  // DO NOT ADD ANY ADDITIONAL INSTANCE VARIABLES FOR THE  //
  // UnrolledDoublyLinkedList CLASS, BEYOND THE BELOW TWO. //
  ///////////////////////////////////////////////////////////
  
  private Node head;    // DO NOT ADD ANY ADDITIONAL INSTANCE VARIABLES
  private int size;     // BEYOND THESE TWO
  
  
  public boolean isEmpty() {
  
    ///////////////////////////////////////////////
    // ADD CODE APPROPRIATE FOR THIS METHOD HERE //
    ///////////////////////////////////////////////
  }
  
  public void add(Item item) {
    // generally, add at head node except when it is full.  
    // when full, insert a new node following the head node and then 
    // move the second half of the head node's elements and the new element to this new node
    
    //////////////////////////////////////////////////////////////////////////////////////
    // ADD CODE HERE TO ACCOMPLISH THE DESCRIPTION FOR THIS METHOD GIVEN DIRECTLY ABOVE //
    // HINT : THERE ARE 3 CASES TO CONSIDER                                             //
    //////////////////////////////////////////////////////////////////////////////////////
  }
  
  public Item remove(Item item) {
    // if item is not in this list, do nothing. otherwise...
    // use the above binarySearch() method repeatedly to find the node item is in (this item will ultimately be returned by this method)
    // then delete the item from this node's items[] array, decrementing appropriate things.
    // if this node becomes less than or equal to half-full, and the next node exists and has an array less than or equal to half full,
    // move all the next node's remaining elements to this node and delete the next node.
    // if this node becomes less than or equal to half-full, and the next node exists and is greater than half full,
    // move just one item from next node's array (the last one) to this node and stop (do not continue to do this down the rest of the list)
    // if all these changes leaves this node's items[] array empty, remove this node from the list
    
    
    ////////////////////////////////////////////////////////////////////////////
    // ADD CODE HERE TO FIND AND STORE THE ITEM SOUGHT (THIS INCLUDES FINDING //
    // BOTH THE NODE AND THE ARRAY POSITION)                                  //
    ////////////////////////////////////////////////////////////////////////////
    
    
    //////////////////////////////////////////////////////////////////////////
    // ADD CODE HERE TO DELETE THE ITEM FROM THIS NODE'S ARRAY,             //
    // SHIFTING IT'S ARRAY ELEMENTS AND DECREMENTING THINGS, AS APPROPRIATE //
    //////////////////////////////////////////////////////////////////////////
    
    
    ////////////////////////////////////////////////////////////////////////////
    // ADD CODE HERE TO DEAL WITH ANY ELEMENTS MOVED FROM ONE NODE TO ANOTHER //
    // AND TO ACCOMPLISH ANY NODE REMOVALS OR "REWIRING" NEEDED               //
    ////////////////////////////////////////////////////////////////////////////
  }

  @Override
  public Iterator<Item> iterator() {
  
    //////////////////////////////////////////////////////////////////////
    // ADD CODE, AS NEEDED TO ITERATE THROUGH THE ELEMENTS IN THE LIST. //
    // IN ORDER, AS THEY APPEAR IN THE NODE ARRAYS, STARTING WITH THE.  //
    // HEAD ARRAY AND PROCEEDING TO THE NEXT, AND THE NEXT, ETC.        //
    //////////////////////////////////////////////////////////////////////
  }
  
  public String toString() {
    String s = "H->";
    Node n = head;
    while (n != null) {
      s += n + "->";
      n = n.next;
    }
    return s;
  }
  
  public static void main(String[] args) {
    int[] numsToAdd = {3,7,0,11,13,2,1,9,10,8,4,5,6,12};
    int[] numsToRemove = {1,8,13,11,7,15,6,5,4,9,12,3,2,0,20,10,14};  // note a is a subset of b
    UnrolledDoublyLinkedList<Integer> list = new UnrolledDoublyLinkedList<Integer>();
    
    for (int i = 0; i < 13; i++) {  
      int num = numsToAdd[i];
      System.out.print(String.format("+ %2s : ", num));
      list.add(num);
      System.out.println(list);
    }
    
    System.out.println();
    for (Integer num : list) {
      System.out.print(num + " ");
    }
    System.out.println(System.lineSeparator());

    for (Integer num : numsToRemove) {
      System.out.print(String.format("- %2s : ", num));
      if (!list.isEmpty())
        list.remove(num);
      System.out.println(list);
    }
  }
}