/**
* A binary tree node for use in a Huffman tree.
* <p>
* Each node has both a left or right child, which can be null.
* <p>
* Each node may store data (if a leaf node) or the data field might be null
* (for internal nodes).
* <p>
* When building a Huffman tree, it is handy to track to the counts of each
* node's contained value or the sum of the values of its subtrees. This
* count value defaults to 0. HuffmanNodes can be sorted based on this count
* value, with smaller counts coming before larger. This count is not
* self-managing, so it should be updated manually if any of the node's
* children change.
*
* @author Zach Tomaszewski
*/
public class HuffmanNode<E> implements Comparable<HuffmanNode<E>> {
private E data;
private int count;
private HuffmanNode<E> left;
private HuffmanNode<E> right;
/**
* Constructs a new node with the given data, count, and references to the
* given left and right nodes.
*/
public HuffmanNode(E data, int count,
HuffmanNode<E> left, HuffmanNode<E> right) {
this.data = data;
this.count = count;
this.left = left;
this.right = right;
}
/**
* Constructs a new node containing the given data and count.
* Its left and right references will be set to null.
*/
public HuffmanNode(E data, int count) {
this(data, count, null, null);
}
/**
* Constructs a new internal node with the given two children.
* The new node's data will be null and its count will be the sum of
* that in its two children.
*/
public HuffmanNode(HuffmanNode<E> left, HuffmanNode<E> right) {
this(null, 0, left, right);
count += (this.getLeft() == null) ? 0 : this.getLeft().getCount();
count += (this.getRight() == null) ? 0 : this.getRight().getCount();
}
/**
* Constructs a new node with no data, a count of 0, and no children.
* Since data is null, this will be an internal node.
*/
public HuffmanNode() {
this(null, 0, null, null);
}
/** Returns the count stored in this node. */
public int getCount() {
return count;
}
/** Updates the count stored in this node. */
public void setCount(int count) {
this.count = count;
}
/** Returns the item currently stored in this node. May be null. */
public E getData() {
return data;
}
/** Overwrites the item stored in this Node with the given data item. */
public void setData(E data) {
this.data = data;
}
/**
* Returns this Node's left child.
* If there is no left left, returns null.
*/
public HuffmanNode<E> getLeft() {
return left;
}
/** Causes this Node to point to the given left child Node. */
public void setLeft(HuffmanNode<E> left) {
this.left = left;
}
/**
* Returns this nodes right child.
* If there is no right child, returns null.
*/
public HuffmanNode<E> getRight() {
return right;
}
/** Causes this Node to point to the given right child Node. */
public void setRight(HuffmanNode<E> right) {
this.right = right;
}
/** True if both of this node's children are null. */
public boolean isLeaf() {
return this.left == null && this.right == null;
}
@Override
public int compareTo(HuffmanNode<E> other) {
//smaller counts before larger
return this.count - other.count;
}
/**
* Returns this node's value (if any; "*" if not) and its count in
* parentheses. If E is Byte, will also include a 'char' view of any
* printable byte value.
*/
@Override
public String toString() {
String str = "";
if (this.data == null) {
str += "*";
}else {
//in standard printable ASCII range
str += this.data;
if (this.data instanceof Byte) {
byte b = (Byte) this.data;
if (b >= 32 && b < 127) {
str += " '" + (char) b + "'";
}else if (b == 9) {
str += " 'TAB'"; //tab
}else if (b == 10) {
str += " 'LF'"; //line feed (\n)
}else if (b == 13) {
str += " 'CR'"; //carriage return (\r)
}
}
}
str += " (x " + this.count + ")";
return str;
}
/**
* Returns a multi-line string showing this node as the root of a tree.
* Each node is on its own line, displayed as per {@link #toString()},
* but preceded by the given prefix. The prefix is extend by "<" for
* each recursive call on a left child and by ">" for each call to a
* right child.
*/
public String toFullString(String prefix) {
String str = prefix + this.toString() + "\n";
if (this.getLeft() != null) {
str += this.getLeft().toFullString(prefix + "<");
}
if (this.getRight() != null) {
str += this.getRight().toFullString(prefix + ">");
}
return str;
}
}