Skip to content

Instantly share code, notes, and snippets.

@DarioAle
Created April 17, 2018 23:45
Show Gist options
  • Save DarioAle/dcf3a01049c6d0d15c551b2bb89f702b to your computer and use it in GitHub Desktop.
Save DarioAle/dcf3a01049c6d0d15c551b2bb89f702b to your computer and use it in GitHub Desktop.
package com.iteso.semana7;
import java.io.*;
import java.util.Arrays;
import java.io.Serializable;
public class Files {
public static void main(String args[]) throws IOException {
FileInputStream in = null, in2;
FileOutputStream out = null;
int [][] a = new int[2][128];
in = new FileInputStream("test.txt");
out = new FileOutputStream("output.bin");
ObjectOutputStream oos = new ObjectOutputStream(out);
int c;
while ((c = in.read()) != -1)
if(c < 128 && c != 13)
a[0][c]++;
int count = 0;
for(int e = 0; e < 128; e++)
if(a[0][e] != 0) {
//System.out.printf("%d, %d, (%c)\n",e, a[e], (char) e);
count++;
}
priorityQueue pq0 = new priorityQueue(count);
for(int e = 0; e < 128; e++)
if(a[0][e] != 0) {
Node n = new Node((char) e, a[0][e]);
pq0.offer(n);
}
System.out.println(Arrays.toString(pq0.minHeap));
oos.writeObject(pq0);
//Build huffman tree
while(pq0.size > 1) {
Node p = pq0.poll();
Node q = pq0.poll();
Node n = new Node('_', p.w + q.w);
n.left = p;
n.right = q;
pq0.offer(n);
}
Node root = pq0.poll();
print(root,0);
int r = 0;
//char[] charArray = new char[64];
encode(root, r, a,0);
in.close();
//read again document and create binary file
in2 = new FileInputStream("test.txt");
char buffer = 0;
byte AvailableBits = 7;
while ((c = in2.read()) != -1) {
if(c < 128 && c != 13) {
int temp = a[0][c];
for(int i = 0; i < a[1][c]; i++) {
System.out.printf("%d",temp & 1);
buffer |= (temp & 1) << AvailableBits;
if(--AvailableBits < 0) {
oos.write(buffer);
buffer = 0;
AvailableBits = 7;
}
temp >>= 1;
}
}
}
System.out.println();
System.out.println(Arrays.toString(a[0]));
//System.out.println(a[0][':']);
FileInputStream fis = new FileInputStream("output.bin");
ObjectInputStream ois = new ObjectInputStream(fis);
BufferedInputStream bis = new BufferedInputStream(fis);
//System.out.printf("hola 0x%x\n",fis.read());
try {
bis.mark(500);
priorityQueue result = (priorityQueue) ois.readObject();
System.out.println(Arrays.toString(result.minHeap));
bis.reset();
} catch (ClassNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
int ch;
System.out.println(bis.read());
while ((ch = bis.read()) != -1)
System.out.println(ch);
ois.close();
in2.close();
//out.close();
oos.close();
}
private static void print(Node node, int spaces) {
if(node.right != null)print(node.right, spaces + 1);
for(int i = 0; i < spaces; i++)System.out.printf("-");System.out.println(node);
if(node.left != null)print(node.left, spaces + 1);
}
private static void encode(Node node, int register, int[][] charArray, int length ) {
if(node.left == null && node.right == null) {
System.out.printf("%d, %c, %d, %d\n",register, node.s, length, reverse(length,register));
charArray[0][node.s] = reverse(length,register);
charArray[1][node.s] = length;
}
if(node.left != null)encode(node.left, register << 1, charArray, length + 1);
if(node.right != null)encode(node.right, (register << 1) | 1, charArray, length + 1);
}
private static int reverse(int n, int reverse) {
int aux = reverse;
reverse = 0;
for(int i = 0; i < n; i++) {
// System.out.printf("iteration %d, %d, %d\n",i,reverse, ((aux >> i) & 1));
reverse |= (aux >> i) & 1;
reverse <<= 1;
}
return reverse >> 1;
}
static class Node implements Comparable<Node>, Serializable{
private static final long serialVersionUID = 1L;
Node left = null, right = null;
int w = 0;
char s = 0x00;
public Node(char c, int w) {
s = c;
this.w = w;
}
@Override
public int compareTo(Node o) {
return this.w -
o.w;
}
@Override
public String toString() {
//return String.format("%d, %d, (%c)\n",(int)s, w, s);
return String.format("%d, (%c)\n", w, s);
}
}
static class priorityQueue implements Serializable{
private static final long serialVersionUID = 1L;
int capacity = 0;
int size = 0;
Node[] minHeap;
public priorityQueue(int c) {
this.capacity = c;
this.minHeap = new Node[this.capacity];
}
public void offer(Node e) {
int index = size;
minHeap[index] = e;
while(minHeap[index].compareTo(minHeap[(index - 1) / 2]) < 0 && index != 0){
Node temp = minHeap[(index - 1) / 2];
minHeap[(index - 1) / 2] = minHeap[index];
minHeap[index] = temp;
index = (index - 1) / 2;
}
size++;
}
public int min(int index) {
index <<= 1;
if(index + 1 >= size) return size;
if(index + 2 >= size) return index + 1;
return minHeap[index + 1].compareTo(minHeap[index + 2]) <= 0 ? index + 1 : index + 2;
}
public Node poll() {
Node root = minHeap[0];
minHeap[0] = minHeap[size - 1];
int index = 0;
int smallest = min(index);
while(minHeap[index].compareTo(minHeap[smallest]) > 0) {
Node temp = minHeap[smallest];
minHeap[smallest] = minHeap[index];
minHeap[index] = temp;
index = smallest;
smallest = min(index);
if(smallest >= size) break;
}
size--;
return root;
}
public Node peek() {
return minHeap[0];
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment