modules/io/src/main/java/net/multiphasicapps/io/HuffmanTreeInt.java
// -*- Mode: Java; indent-tabs-mode: t; tab-width: 4 -*-
// ---------------------------------------------------------------------------
// SquirrelJME
// Copyright (C) Stephanie Gawroriski <xer@multiphasicapps.net>
// ---------------------------------------------------------------------------
// SquirrelJME is under the Mozilla Public License Version 2.0.
// See license.mkd for licensing and copyright information.
// ---------------------------------------------------------------------------
package net.multiphasicapps.io;
import cc.squirreljme.runtime.cldc.debug.Debugging;
import java.io.IOException;
import java.util.NoSuchElementException;
/**
* This represents a mutable huffman tree.
*
* This class is not thread safe.
*
* Iteration of values goes through the internal value table in no particular
* order. The iterator is fail-fast.
*
* {@squirreljme.error BD12 The huffman tree was modified in the middle of
* iteration.}
*
* @since 2016/03/10
*/
public class HuffmanTreeInt
{
/** The huffman table. */
private volatile int[] _table;
/** Stored tree values. */
private volatile int[] _values;
/** Modification count. */
private volatile int _modcount;
/** Maximum used bits. */
private volatile int _maxbits;
/**
* Initializes a basic blank huffman tree.
*
* @since 2016/03/10
*/
public HuffmanTreeInt()
{
// Initially add table space so that it is always initially valid but
// points to nothing.
this.__addTableSpace();
}
/**
* Adds the specified object which is associated with the given symbol
* and mask.
*
* @param __v The value to add.
* @param __sym The bit representation of the symbol.
* @param __mask The mask of the symbol for its valid bits.
* @return The old value, or {@code null} if it is not set.
* @throws IllegalArgumentException If the specified symbol contains a bit
* which is outside of the mask or the mask does not start at shift zero
* or has zero gaps.
* @since 2016/03/28
*/
public final int add(int __v, int __sym, int __mask)
throws IllegalArgumentException
{
// Number of bits in the mask
int ibm = Integer.bitCount(__mask);
// Check mask and representation
/* {@squirreljme.error BD13 The symbol exceeds the range of the mask.
(The value; The mask)} */
if ((__sym & (~__mask)) != 0)
throw new IllegalArgumentException(String.format("BD13 %x %x",
__sym, __mask));
/* {@squirreljme.error BD14 The mask has a zero gap between bits or
at the least significant end. (The value; The mask)} */
if (ibm != (32 - Integer.numberOfLeadingZeros(__mask)) ||
(__mask & 1) == 0)
throw new IllegalArgumentException(String.format("BD14 %x %x",
__sym, __mask));
// Get the table
int[] table = this._table;
int n = table.length;
// Increase max bit count
this._maxbits = Math.max(this._maxbits, ibm);
// Find the spot to add it based on the bit depth
int at = 0;
for (int sh = (1 << (ibm - 1)); sh != 0; sh >>>= 1)
{
// Last bit set?
boolean last = (sh == 1);
// The array index to look at for the current position depends
// on which bit is set
int q = (((__sym & sh) != 0) ? 1 : 0);
// Get the jump value
int jump = table[at + q];
// If this points to a constant area but this is not the last
// bit, then trash it.
if (!last && jump < 0)
{
jump = Integer.MAX_VALUE;
table[at + q] = jump;
}
// Jumps off the table end? Needs more values to be added for
// the tree to be built
if (jump == Integer.MAX_VALUE)
{
// If this is the last entry then a value index needs to
// be created to store the value
if (last)
{
// Add space for a new variable
int vat = this.__addValueSpace();
// Place value there
this._values[vat] = __v;
// Set table index to point there
table[at + q] = -(vat + 1);
// Modified
this._modcount++;
// No old value exists
return 0;
}
// Otherwise, add some table space and jump to that
// instead on the next run.
else
{
// Add new location info
int jat = this.__addTableSpace();
// Correct vars
table = this._table;
n = table.length;
// Set jump to that position
// Use that position instead on the next read
table[at + q] = at = jat;
}
}
// Points to a constant area, return a value
else if (jump < 0)
{
// Calculate actual placement
int vat = (-jump) - 1;
// Get old value
int[] vals = this._values;
int old = vals[vat];
// Set new value
vals[vat] = __v;
// Modified
this._modcount++;
// Return the old value
return old;
}
// Points to another location in the array
else
at = jump;
}
// Should not occur
throw Debugging.oops();
}
/**
* Clears the huffman tree.
*
* @since 2017/02/25
*/
public void clear()
{
// Reset parameters
this._table = null;
this._values = null;
this._modcount = 0;
this._maxbits = 0;
// Setup initial tree
this.__addTableSpace();
}
/**
* Finds the bit sequence associated with the given value.
*
* @param __i The value to find the sequence for the given bit pattern.
* @return A {@code long} where the upper 32-bits is the bit mask while
* the lower 32-bits are the symbol.
* @throws NoSuchElementException If no sequence was found.
* @since 2016/08/24
*/
public final long findSequence(int __i)
throws NoSuchElementException
{
// Get values
int[] vals = this._values;
// No values? nothing will ever be found
if (vals == null)
throw new NoSuchElementException("NSEE");
// Look through all values
int n = vals.length;
for (int i = 0; i < n; i++)
if (vals[i] == __i)
return this.__recursiveMatch(0, 0, 0, -(i + 1));
// Not found
throw new NoSuchElementException("NSEE");
}
/**
* Returns the value obtained via the given bit source.
*
* @param __bs The source for bits.
* @return The value.
* @throws IOException On read errors.
* @throws NoSuchElementException If no value was found.
* @throws NullPointerException On null arguments.
* @since 2016/08/16
*/
public final int getValue(BitSource __bs)
throws IOException, NoSuchElementException, NullPointerException
{
// Check
if (__bs == null)
throw new NullPointerException("NARG");
// Get the jump table
int[] table = this._table;
if (table == null)
throw new NoSuchElementException("NSEE");
// Try to find a value
for (int at = 0;;)
{
// A value has been read?
if (at < 0)
return this._values[(-at) - 1];
/* {@squirreljme.error BD15 Key not found in tree.} */
else if (at == Integer.MAX_VALUE)
throw new NoSuchElementException("BD15");
// Set the new position to the table position
at = table[at + (__bs.nextBit() ? 1 : 0)];
}
}
/**
* Returns the maximum number of bits entries use.
*
* @return The maximum number of used bits.
* @since 2016/03/28
*/
public final int maximumBits()
{
return this._maxbits;
}
/**
* {@inheritDoc}
* @since 2016/03/10
*/
@Override
public final String toString()
{
// Setup
StringBuilder sb = new StringBuilder("[");
// Add elements in no particular order
int[] vals = this._values;
if (vals != null)
{
int n = vals.length;
for (int i = 0; i < n; i++)
{
// Comma?
if (i > 0)
sb.append(", ");
// Begin sequence data
sb.append('<');
// Get the sequence of it
int v = vals[i];
int seq = -1;
// Not found?
if (seq == -1L)
sb.append('?');
// Print bit pattern otherwise
else
{
// Get mask and value
int msk = (int)(seq >>> 32L);
int val = (int)(seq);
// Start from the highest bit first
int hib = Integer.bitCount(msk);
for (int b = hib - 1; b >= 0; b--)
sb.append(((0 == (val & (1 << b))) ? '0' : '1'));
}
// End sequence data
sb.append(">=");
// Add the value
sb.append(v);
}
}
// Build it
sb.append(']');
return sb.toString();
}
/**
* Adds more table space for a branch.
*
* @return The base index of the newly added space.
* @since 2016/03/28
*/
private int __addTableSpace()
{
// The returned value is the end of the table
int[] table = this._table;
int rv = (table == null ? 0 : table.length);
// Allocate some extra space
int[] becomes = new int[rv + 2];
// Copy the old array over
if (table != null)
System.arraycopy(table, 0,
becomes, 0, rv);
// The end bits become invalidated
becomes[rv] = Integer.MAX_VALUE;
becomes[rv + 1] = Integer.MAX_VALUE;
// Set new table
this._table = becomes;
// Return it
return rv;
}
/**
* Adds more value space to add a new value.
*
* @return The index where the value space was increased.
* @since 2016/03/28
*/
private int __addValueSpace()
{
// The returned value is the end of the table
int[] values = this._values;
int rv = (values == null ? 0 : values.length);
// Allocate some extra space
int[] becomes = new int[rv + 1];
// Copy the old array over
if (values != null)
System.arraycopy(values, 0,
becomes, 0, rv);
// Set new table
this._values = becomes;
// Return it
return rv;
}
/**
* Searches the huffman tree for the given raw match value.
*
* @param __at The index to look at.
* @param __huf The huffman index.
* @param __mask The mask of the input value.
* @param __match The value to match.
* @return The bit mask and the value for the given entry or {@code -1L} if
* not found.
* @since 2016/03/28
*/
private long __recursiveMatch(int __at, int __huf, int __mask, int __match)
{
// Get tree
int[] table = this._table;
// Get the left and right side jump values
int jl = table[__at];
int jr = table[__at + 1];
// Matches left or right side?
boolean left = (jl == __match);
if (left || jr == __match)
return (((long)((__mask << 1) | 1)) << 32L) |
((long)((__huf << 1) | (left ? 0 : 1)));
// Traverse left side
long rv;
if (jl >= 0 && jl != Integer.MAX_VALUE)
{
rv = this.__recursiveMatch(jl, __huf << 1, (__mask << 1) | 1,
__match);
if (rv != -1L)
return rv;
}
// Traverse right side
if (jr >= 0 && jr != Integer.MAX_VALUE)
{
rv = this.__recursiveMatch(jr, (__huf << 1) | 1, (__mask << 1) | 1,
__match);
if (rv != 1L)
return rv;
}
// Not found
return -1L;
}
}