Data Structures, Algorithms, & Applications in Java
Chapter 14, Exercise 27

To implement the next fit strategy using the pseudocode of Section 14.5.2, we must extend the class ExtendedCWTree to include the method parent(i), which returns the internal node that is the parent if the external node i. The code for parent(i) is given below. 

public class ExtendedCWTree2 extends ExtendedCWTree
{
   /** @return parent of the external node i */
   public int parent(int i)
   {
      if (i < 1 || i >= player.length)
         throw new IllegalArgumentException
                   ("tree does not have an external node " + i);

      if (i <= lowExt)
         return (i + offset) / 2;
      else
         return (i - lowExt + player.length) / 2;
   }
}


The code for nextFitPack is given below. This code follows the pseudocode fairly closely. 
public class NextFit
{
   /** output next fit packing into bins of size c
     * @param s[1:s.length-1] gives object size */
   public static void nextFitPack(int s[], int c)
   {
      int n = s.length - 1;         // number of objects
      FirstFit.Bin [] bin = new FirstFit.Bin [n + 1]; // bins
      ExtendedCWTree2 winTree = new ExtendedCWTree2();
      
      
      // initialize n bins and winner tree
      for (int i = 1; i <= n; i++)
         bin[i] = new FirstFit.Bin(c);  // initial unused capacity
      winTree.initialize(bin);

      int last = 0; // bin used for last object packed
      
      // put objects in bins
      for (int i = 1; i <= n; i++)
      {// put s[i] in a bin
         // see if there is a nonempty bin to the
         // right of bin last that has enough capcity
   
         // set j to next bin with enough capacity
         int j = last + 1;
         if (bin[j].unusedCapacity < s[i])
            // there must be another bin j+1
            if (bin[j + 1].unusedCapacity >= s[i])
               j++;
            else
            {// move up the tree
               // set p to parent of bin j
               int p = winTree.parent(j);
               boolean done = false;
               if (p == n - 1)
               {// special case
                  int q;
                  if (j % 2 == 1)
                     q = j + 1;
                  else
                     q = j + 2;

                  // q must be <= n
                  if (bin[q].unusedCapacity >= s[i])
                  {
                     j = q;
                     done = true;
                  }
               }
               
               if (!done)
               {// move to nearest ancestor of p with enough capacity
                  p /= 2;
                  while (bin[winTree.getWinner(p)].unusedCapacity < s[i])
                     p /= 2;
   
                  // now move to leftmost child of p that has enough capacity
                  p *= 2;  // start search at left child
                  while (p < n)
                  {
                     int winp = winTree.getWinner(p);
                     if (bin[winp].unusedCapacity < s[i])
                        // first bin is in right subtree
                        p++ ;                   
                     p *= 2;   // move to left child
                  }
            
                  p /= 2;  // undo last left child move
                  if (p < n)
                  {// at a tree node
                     j = winTree.getWinner(p);
                     // if j is right child, need to check
                     // bin j-1.  No harm done by checking
                     // bin j-1 even if j is left child.
                     if (j > 1 && bin[j - 1].unusedCapacity >= s[i])
                        j--;
                  }
                  else  // arises when n is odd
                     j = winTree.getWinner(p / 2);
               }
            }  
   
         // see if bin j is nonempty
         if (bin[j].unusedCapacity == c)
         {// empty bin, execute step 2
            // find leftmost bin with enough capacity
            int p = 2;  // start search at left child of root
            while (p < n)
            {
               int winp = winTree.getWinner(p);
               if (bin[winp].unusedCapacity < s[i])
                  // first bin is in right subtree
                  p++ ; 
               p *= 2;   // move to left child
            }
      
            p /= 2;  // undo last left child move
            if (p < n)
            {// at a tree node
               j = winTree.getWinner(p);
               // if j is right child, need to check
               // bin j-1.  No harm done by checking
               // bin j-1 even if j is left child.
               if (j > 1 && bin[j - 1].unusedCapacity >= s[i])
                  j--;
            }
            else  // arises when n is odd
               j = winTree.getWinner(p / 2);
         }
   
         System.out.println("Pack object " + i + " in bin " + j);
         bin[j].unusedCapacity -= s[i]; 
         winTree.rePlay(j);
         last = j;
      }
   }
}