Tree(int elems,
    int minCodes,
    int maxLength) 
{
          
      this.minNumCodes = minCodes;
      this.maxLength  = maxLength;
      freqs  = new short[elems];
      bl_counts = new int[maxLength];
}

 public  void buildCodes() 
{
      int[] nextCode = new int[maxLength];
      int code = 0;
      codes = new short[freqs.length];
      if (DeflaterConstants.DEBUGGING)
	System.err.println("buildCodes: "+freqs.length);
      for (int bits = 0; bits <  maxLength; bits++) 
	{
	  nextCode[bits] = code;
	  code += bl_counts[bits] < <  (15 - bits);
	  if (DeflaterConstants.DEBUGGING)
	    System.err.println("bits: "+(bits+1)+" count: "+bl_counts[bits]
			       +" nextCode: "+Integer.toHexString(code));
	}
      if (DeflaterConstants.DEBUGGING && code != 65536)
	throw new RuntimeException("Inconsistent bl_counts!");
      for (int i=0; i <  numCodes; i++)
	{
	  int bits = length[i];
	  if (bits  > 0)
	    {
	      if (DeflaterConstants.DEBUGGING)
		System.err.println("codes["+i+"] = rev("
				   +Integer.toHexString(nextCode[bits-1])+"),"
				   +bits);
	      codes[i] = bitReverse(nextCode[bits-1]);
	      nextCode[bits-1] += 1 < <  (16 - bits);
	    }
	}
}

  void buildTree() 
{
      int numSymbols = freqs.length;
      /* heap is a priority queue, sorted by frequency, least frequent
       * nodes first.  The heap is a binary tree, with the property, that
       * the parent node is smaller than both child nodes.  This assures
       * that the smallest node is the first parent.
       *
       * The binary tree is encoded in an array:  0 is root node and
       * the nodes 2*n+1, 2*n+2 are the child nodes of node n.
       */
      int[] heap = new int[numSymbols];
      int heapLen = 0;
      int maxCode = 0;
      for (int n = 0; n <  numSymbols; n++)
	{
	  int freq = freqs[n];
	  if (freq != 0)
	    {
	      /* Insert n into heap */
	      int pos = heapLen++;
	      int ppos;
	      while (pos  > 0 &&
		     freqs[heap[ppos = (pos - 1) / 2]]  > freq) {
		heap[pos] = heap[ppos];
		pos = ppos;
	      }
	      heap[pos] = n;
	      maxCode = n;
	    }
	}
      /* We could encode a single literal with 0 bits but then we
       * don't see the literals.  Therefore we force at least two
       * literals to avoid this case.  We don't care about order in
       * this case, both literals get a 1 bit code.  
       */
      while (heapLen <  2)
	{
	  int node = maxCode <  2 ? ++maxCode : 0;
	  heap[heapLen++] = node;
	}
      numCodes = Math.max(maxCode + 1, minNumCodes);
      int numLeafs = heapLen;
      int[] childs = new int[4*heapLen - 2];
      int[] values = new int[2*heapLen - 1];
      int numNodes = numLeafs;
      for (int i = 0; i <  heapLen; i++)
	{
	  int node = heap[i];
	  childs[2*i]   = node;
	  childs[2*i+1] = -1;
	  values[i] = freqs[node] < <  8;
	  heap[i] = i;
	}
      /* Construct the Huffman tree by repeatedly combining the least two
       * frequent nodes.
       */
      do
	{
	  int first = heap[0];
	  int last  = heap[--heapLen];
	  /* Propagate the hole to the leafs of the heap */
	  int ppos = 0;
	  int path = 1;
	  while (path <  heapLen)
	    {
	      if (path + 1 <  heapLen 
		  && values[heap[path]]  > values[heap[path+1]])
		path++;
	      heap[ppos] = heap[path];
	      ppos = path;
	      path = path * 2 + 1;
	    }
	  /* Now propagate the last element down along path.  Normally
	   * it shouldn't go too deep.
	   */
	  int lastVal = values[last];
	  while ((path = ppos)  > 0
		 && values[heap[ppos = (path - 1)/2]]  > lastVal)
	    heap[path] = heap[ppos];
	  heap[path] = last;
	  int second = heap[0];
	  /* Create a new node father of first and second */
	  last = numNodes++;
	  childs[2*last] = first;
	  childs[2*last+1] = second;
	  int mindepth = Math.min(values[first] & 0xff, values[second] & 0xff);
	  values[last] = lastVal = values[first] + values[second] - mindepth + 1;
	  /* Again, propagate the hole to the leafs */
	  ppos = 0;
	  path = 1;
	  while (path <  heapLen)
	    {
	      if (path + 1 <  heapLen 
		  && values[heap[path]]  > values[heap[path+1]])
		path++;
	      heap[ppos] = heap[path];
	      ppos = path;
	      path = ppos * 2 + 1;
	    }
	  /* Now propagate the new element down along path */
	  while ((path = ppos)  > 0
		 && values[heap[ppos = (path - 1)/2]]  > lastVal)
	    heap[path] = heap[ppos];
	  heap[path] = last;
	}
      while (heapLen  > 1);
      if (heap[0] != childs.length / 2 - 1)
	throw new RuntimeException("Weird!");
      buildLength(childs);
}

  void calcBLFreq(DeflaterHuffman.Tree blTree) 
{
      int max_count;               /* max repeat count */
      int min_count;               /* min repeat count */
      int count;                   /* repeat count of the current code */
      int curlen = -1;             /* length of current code */
      int i = 0;
      while (i <  numCodes)
	{
	  count = 1;
	  int nextlen = length[i];
	  if (nextlen == 0) 
	    {
	      max_count = 138;
	      min_count = 3;
	    }
	  else
	    {
	      max_count = 6;
	      min_count = 3;
	      if (curlen != nextlen)
		{
		  blTree.freqs[nextlen]++;
		  count = 0;
		}
	    }
	  curlen = nextlen;
	  i++;
	  while (i <  numCodes && curlen == length[i])
	    {
	      i++;
	      if (++count  >= max_count)
		break;
	    }
	  if (count <  min_count)
	    blTree.freqs[curlen] += count;
	  else if (curlen != 0)
	    blTree.freqs[REP_3_6]++;
	  else if (count < = 10)
	    blTree.freqs[REP_3_10]++;
	  else
	    blTree.freqs[REP_11_138]++;
	}
}

 final  void checkEmpty() 
{
      boolean empty = true;
      for (int i = 0; i <  freqs.length; i++)
	if (freqs[i] != 0)
	  {
	    System.err.println("freqs["+i+"] == "+freqs[i]);
	    empty = false;
	  }
      if (!empty)
	throw new InternalError();
      System.err.println("checkEmpty suceeded!");
}

 int getEncodedLength() 
{
      int len = 0;
      for (int i = 0; i <  freqs.length; i++)
	len += freqs[i] * length[i];
      return len;
}

  void reset() 
{
      for (int i = 0; i <  freqs.length; i++)
	freqs[i] = 0;
      codes = null;
      length = null;
}

  void setStaticCodes(short[] stCodes,
    byte[] stLength) 
{
      codes = stCodes;
      length = stLength;
}

 final  void writeSymbol(int code) 
{
      if (DeflaterConstants.DEBUGGING)
 	{
 	  freqs[code]--;
//  	  System.err.print("writeSymbol("+freqs.length+","+code+"): ");
 	}
      pending.writeBits(codes[code] & 0xffff, length[code]);
}

  void writeTree(DeflaterHuffman.Tree blTree) 
{
      int max_count;               /* max repeat count */
      int min_count;               /* min repeat count */
      int count;                   /* repeat count of the current code */
      int curlen = -1;             /* length of current code */
      int i = 0;
      while (i <  numCodes)
	{
	  count = 1;
	  int nextlen = length[i];
	  if (nextlen == 0) 
	    {
	      max_count = 138;
	      min_count = 3;
	    }
	  else
	    {
	      max_count = 6;
	      min_count = 3;
	      if (curlen != nextlen)
		{
		  blTree.writeSymbol(nextlen);
		  count = 0;
		}
	    }
	  curlen = nextlen;
	  i++;
	  while (i <  numCodes && curlen == length[i])
	    {
	      i++;
	      if (++count  >= max_count)
		break;
	    }
	  if (count <  min_count)
	    {
	      while (count--  > 0)
		blTree.writeSymbol(curlen);
	    }
	  else if (curlen != 0)
	    {
	      blTree.writeSymbol(REP_3_6);
	      pending.writeBits(count - 3, 2);
	    }
	  else if (count < = 10)
	    {
	      blTree.writeSymbol(REP_3_10);
	      pending.writeBits(count - 3, 3);
	    }
	  else
	    {
	      blTree.writeSymbol(REP_11_138);
	      pending.writeBits(count - 11, 7);
	    }
	}
}