//Htable.java
import java.util.Set;
import java.util.Map;
//import java.util.TreeSet;
import java.util.TreeMap;
import java.util.Iterator;
import java.io.*;

class Htable
{

  //TreeMap<RunHuff> htable = new TreeMap<RunHuff>();
  TreeMap<RunHuff, RunHuff>  htable = new TreeMap<RunHuff,RunHuff>();
 
  //use a set ( htable ) to collect all pre-calculated run-level and Huffman codewords
  void build_htable ()
  {
    short i, j, k, N = 10;    //N is the number of pre-calculated codewords of positive levels
    byte hlen[] = { 2, 3, 4, 4, 4, 5, 5, 5, 6, 7 };       //lengths of Huffman codewords ( not including sign-bit )
    //Huffman codewords, 0x60 is ESC
    short hcode[] = { 0x01, 0x3, 0x7, 0xf, 0xe, 0x16, 0x6, 0x1a, 0x2a, 0x60  };
    byte runs[] = {0, 1, 2, 0, 0, 3, 4, 5, 0, -1 };    //-1 signifies ESC
    short levels[] = {1, 1, 1, 2, 1, 1, 1, 1, 3, 0 };            //level of 3D run-level tuple 
    byte  lasts[] = {0, 0, 0, 0, 1, 0, 0, 0, 0, 0 };             //last  of 3D run-level tuple

    Run3D r = new Run3D();                //a 3D run-level codeword ( tuple )
    RunHuff rf[] = new RunHuff[128];      //table containing RunHuff objects

    k = 0; j = 0;
    for ( i = 0; i < N; ++i ) {
      r.run = runs[i];
      r.level = levels[i];
      r.last = lasts[i];
      rf[k++] = new  RunHuff ( r, hcode[i] << 1,  hlen[i], j++ );    //construct a RunHuff object, positive level, so sign=0
      r.level = (short) -r.level;                                       //do the same thing for negative level 
      rf[k++] = new RunHuff ( r, (hcode[i]<<1) | 1, hlen[i], j++ ); //level negative, so sign = 1
    }
    k = (short) ( 2 * N );               //insert all 2N ( positive and negative levels ) RunHuff objects into htable
    System.out.printf("\nk: %d  ",k );
    for ( i = 0; i < k; ++i )
      htable.put( rf[i], rf[i] ); 
      //htable.add( rf[i] ); 
  }

  void print_htable()
  {
    System.out.printf("\nNumber of elements in set: %d", htable.size() );
  //  TreeSet<RunHuff>htableSet = htable.entrySet();
    //TreeSet<Map.Entry<RunHuff, RunHuff>>htableSet = htable.entrySet();
 
    // Use an Iterator to traverse the mappings in the TreeMap.  Note
    // that the mappings are in sorted order (with respect to the keys). 
    Iterator itr = htable.entrySet().iterator();

     System.out.printf("\n(run, level, last), \tCodeword\tHuff Code Length, index");
     while ( itr.hasNext() )
     {
        //RunHuff rhuf = ( RunHuff ) itr.next();
        Map.Entry entry = (Map.Entry) itr.next();
        RunHuff rhuf = (RunHuff) entry.getValue();
	System.out.printf("\n(%4d, %4d, %d), \t%8x \t%x\t    %d, \t%4d", rhuf.r.run, rhuf.r.level, rhuf.r.last, rhuf.codeword, rhuf.codeword >> 1, rhuf.hlen, rhuf.index );
     }
  }

  void escape_encode ( BitOutputStream outputs, Run3D r )
  {
    try {
      if ( r.level < 0 ) {                  //value of level negative
        outputs.writeBit ( 1 );            //output sign-bit first
        r.level = (short) -r.level;                 //change level value to positive 
      } else
        outputs.writeBit ( 0 );            //value of level negative
      outputs.writeBits ( 0x60, 7 );       //ESCAPE code
      if ( r.run == 64 ) r.run = 63;        //r.level differentiates between if last element nonzero 
      outputs.writeBits ( r.run, 6 );      //6 bits for run value
      outputs.writeBits ( r.level, 8 );    //8 bits for level value
      outputs.writeBit ( r.last );         //1 bit for last value
    } catch (IOException e) {
       e.printStackTrace();
       System.exit(0);
    }
  }


/*
   Inputs: htable contains all the pre-calculated Huffman codewords of 3D run-level tuples
           runs[] contains the 3D run-level tuples of a macroblock of quantized DCT coefficients
   Outputs:bitstreams of codewords ( Huffman + sign or ESCAPE + 3D run-level ) to bitFileIO outputs
*/
  void huff_encode ( Run3D runs[], BitOutputStream outputs )
  {
    short i, j, k;

    k = 0;
  //  Set<Map.Entry<RunHuff, RunHuff>>htableSet = htable.entrySet();
  //  TreeSet<RunHuff>::iterator itr;                           //iterator to traverse htable
//    Iterator itr = htableSet.iterator();
    i = 0;
    while ( i < 64 ) {                //a macroblock has at most 64 samples
      try {
        RunHuff rf = new RunHuff( runs[k], 0, (byte) 0, (short) 0 ); //construct a RunHuff object; only runs[k] is relevant
                                       //as it is used for searching ( we've defined '<' in RunHuff class )
        if ( htable.containsKey ( rf ) ){
          RunHuff rhuf = htable.get( rf );
          outputs.writeBits( rhuf.codeword, rhuf.hlen + 1);
        } else                          //not in table
          escape_encode( outputs, rf.r );    //need to 'escape encode' the 3D run-level tuple
      } catch (IOException e) {
        e.printStackTrace();
        System.exit(0);
      }
      if ( runs[k].last != 0 ) break;        //end of run-level codewords
      i += ( runs[k].run + 1 );         //for handling the special case of whole block of run being 0
      k++;
    }
  }
};

