HW #2.6
a rough algorithm for discovering the bit patterns from the Huffman tree:
Algorithm postOrder(v, s)
     if (v is leaf)
arr[v.character] = s;
return;
postOrder (n.left, s+”0”)
postOrder (n.right, s+”1”)


implement that to build an array mapping letters to bit strings

in C++, a char takes up one byte
in Java, a byte takes up one byte

byte b = 0;

to set bit i to 1
b = b | (1 << i);

to set bit i to 0
b = b & ~(1 << i);

to find out if bit i is 1?
if (b & (1 << i) != 0)

to find out if bit i is =?
if (b & (1 << i) == 0)

assuming binary trees:
preorder traversal: SLR
postorder traversal: LRS
inorder traversal: LSR

Sample data structures midterm

See here.

some interesting, useful code

T arr[] = (T []) new Object [n];

int x[] = new int [n];

int front, rear;
front = 0;
rear = 0;

how insert?
arr[rear] = o;
rear++;

how remove?
arr[front] = null;
front++;

eventually, off end of array.
rather, how insert?
arr[rear] = o;
rear = (rear+1) % n;

and same thing for front.

class Person implements Comparable
{
// guts
int compareTo(Object b)
{
Person B = (Person)b;
if (this.age > B.age)
return 1;
else if (this.age < B.age)
return -1;
else
return 0;
}
}

class MyComparator<T> implements Comparator<T>
{
int compare(T a, T b)
{

}
}

main()
{
PriorityQueue<Person> pq = new PriorityQueue<Person> (new MyComparator());
}

class BTree <T extends Comparable> implements Comparable
{
 T element;
 BTree left, right;
 int compareTo(Object o)
 {
BTree<T> bt = (BTree<T>)o;
return this.element.compareTo(bt.element);
 }
}

class LetterAndFreq implements Comparable
{
char letter;
int freq;
int compareTo(Object o)
{
LetterAndFreq b = (LetterAndFreq)o;
if (this.freq > b.freq)
....
}
}

Sorry about Blackboard. Will be up soon.

let us pretend that I have an alphabet of 8 letters. ABCDEFGH
A = 000
B = 001
C = 010
D = 011
E = 100
F = 101
G = 110
H = 111

CAFE
010 000 101 100

AAAAAAAAAAAAAABAAAAAAAAAF

frequencies of these letters
A = 500
B = 10
C = 5
D = 18
E = 200
F = 7
G = 23
H = 2

HW 2.5: using all the data structures you have already created, implement a Huffman tree, which you can later use to encode and decode text.

http://en.wikipedia.org/wiki/Huffman_coding

tentative midterms date Mon, March 21
(two Mon from today)

HW:
implement a binary tree class.

class BTree implements Comparable
{
int element;
BTree left, right;
}
it should be either comparable, or else
you should write a comparator for it.

http://en.wikipedia.org/wiki/Huffman_coding

my own lazy implementation of List-based stack
public class NodeStack<E> implements Stack<E> {
   protected SLinkedList<E> mylist;
   // protected int size; // number of elements in the stack
   public NodeStack() { // constructs an empty stack mylist = SLinkedList<E>(); }
   public int size() { return mylist.size(); }
   public boolean isEmpty() {return mylist.isEmpty()}
   public void push(E elem) {      myList.insertFront(elem);}
   public E top() throws EmptyStackException {      if (isEmpty()) throw new EmptyStackException("empty");      return mylist.front(); }
   public E pop() throws EmptyStackException {      if (isEmpty()) throw new EmptyStackException("empty");      E temp = top(); myList.removeFront();      // link-out the former top node      return temp; } }

It is better, IMHO

class MyVeryOwnComparator implements Comparator<T>
{
boolean compare(T o, T p)
{ Person per1 = (Person) }
}

class PQueue<T>
{
private Comparator<T> comp;
PQueue(Comparator<T> c)
{
comp = c;
}
void pop()
{
if(comp.compare(elem1, elem2)
}
}

main()
{
PQueue<Person>(new MyVeryOwnComparator())
}

2.3:
take your priority queue, instead of ints, it should take Comparable objects. alternatively, you can make the constructor take a Comparator object of your own creation.
do both
*eventually*, it should implement Queue interface.

http://onjava.com/pub/a/onjava/2003/03/12/java_comp.html

if (a.compareTo(b) == 0)
// equivalent to: if (a == b)

if (a.compareTo(b) < 0)
// equivalent to: if (a < b)

if (a.compareTo(b) > 0)
// equivalent to: if (a > b)

Comparator
http://www.javadeveloper.co.in/java-example/java-comparator-example.html