class Run implements Comparable<Run> {
  public byte symbol;
  public int runLen;
  public int freq;

  // 트르의 노드로 사용하기 위해서 왼쪽 자식과 오른쪽 자식 노드 필드를 추가한다.

  // 노드에 부여된 codeword를 지정하기 위한 필드들을 다음과 같이 추가한다.

  public int codeword;    //부여된 codeword를 32비트 정수로 저장
  public int codewordLen; // 부여된 codeword의 길이. 즉 codeword의
                          // 하위 codewordLen비트가 실제 codeword
}

public class Test {
  public static void main(String args[]){
    int a = 60;   // 60 = 0011 1100
    int b = 13;   // 13 = 0000 1101
    int c =0;

    c = a & b;        // 12 = 0000 1100
    System.out.println("a & b = " + c);
    c = a | b;        // 61 = 0011 1101
    System.out.println("a | b = " + c);
    c = a ^ b;        // 49 = 0011 0001
    System.out.println("a ^ b = " + c);
    c = ~a;           // -61 = 1100 0011
    System.out.println("~a = " + c);
    c = a << 1;       // 120 = 0111 1000
    System.out.println("a << 1 = " + c);
    c = (a << 1) + 1; // 121 = 0111 1001
    System.out.println("(a << 1) + 1 = " + c);
    c = a << 2;       // 240 = 1111 0000
    System.out.println("a << 2 = " + c);
  }
}

public class HuffmanCoding {
  ...

  public void compressFile(RandomAccessFile fIn) {
    collectRuns(fIn);
    createHuffmanTree();
    assignCodewords(theRoot, 0, 0);
  }

  static public void main(String args[]){
    HuffmanCoding app = new HuffmanCoding();
    RandomAccessFile fIn;
    try{
      fIn = new RandomAccessFile("sample.txt","r");
      app.compressFile(fIn);
      fIn.close();
    } catch(IOException io){
      System.err.println("Cannot open " + fileName);
    }
  }
}

class Run implements Comparable<Run> {
  public byte symbol;
  public int runLen;
  public int freq;
  // 트리의 노드로 사용하기 위해서 왼쪽 자식과 오른쪽 자식 노드 필드를 추가한다.

  // 두 run의 크기관계를 비교하는 compareTo 메서드를 overriding하라.
  // 비교의 기준은 freq이다.
}

public class HuffmanCoding {
  private ArrayList<Run> runs = new ArrayList<Run>();

  private Heap<Run> heap; // minimum heap이다.
  private Run theRoot = null; // root of the Huffman tree

  private void createHuffmanTree() {
    heap = new Heap<Run>();

    // 1. store all runs into the heap.
    // 2. while the heap size > 1 do
    //    (1) perform extractMin two times
    //    (2) make a combined Tree
    //    (3) insert the combined tree into the heap.
    // 3. Let the Root be the root of the tree.
  }
}

private void printHuffmanTree() {
  preOrderTraverse(threRoot, 0);
}

private void preOrderTraverse(Run node, int depth) {
  for (int i=0; i<depth; i++)
    System.out.print("  ");
  if (node == null){
    System.out.println("null");
  } else {
    System.out.println(node.toString());
    preOrderTraverse(node.left, depth + 1);
    preOrderTraverse(node.right, depth + 1);
  }
}

// 읽을 데이터 파일을 연다
RandomAccessFile fIn = new RandomAccessFile(fileName, "r");

// 한 byte를 읽어 온다. 읽어온 byte는 0~255사이의 정수로 반환된다.
// 파일의 끝에 도달하면 -1을 반환한다.
int ch = fIn.read();

// 필요하다면 byte로 casting해서 저장한다.
byte symbol = (byte)ch;

public class HuffmanCoding {
  // 인식한 run들을 저장할 ArrayList를 만든다.
  private ArrayList<Run> runs = new ArrayList<Run>();

  private void collectRuns(RandomAccessFile fIn) throws IOException {
    // 데이터 파일 fIn에 등장하는 모든 run들과 각각의 등장횟수를 count하여
    // ArrayList runs에 저장한다.
  }

  static public void main(String args[]){
    HuffmanCoding app = new HuffmanCoding();
    RandomAccessFile fIn;
    try {
      fIn = new RandomAccessFile("sample.txt","r");
      app.collectRuns(fIn);
      fIn.close();
    } catch (IOException io) {
      System.err.println("Cannot open " + fileName);
    }
  }
}