Huffman-Encoding/letter.java at master · Nour-Benmohamed/Huffman-Encoding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.TreeMap;
/**
 *
 * @author Nour Benmohamed
 * problem set 3
 * 5/3/2018
 *
 *
 */

public class letter {
	//these two mins will be the extracted two trees with the smallest freqency value in the root
	protected BinaryTree<typeE> Min1 ;
	protected BinaryTree<typeE> Min2 ;
	// this pq is what is going to be used to create the huffman code tree
	protected PriorityQueue<BinaryTree<typeE>> pq;
	protected String pathsofar = "";
	// this map will hold every character and its code
	protected Map<Character, String> charactercode;
	protected BinaryTree<typeE> huffman;


	// constructor
	public letter() {
		pq = new PriorityQueue<BinaryTree<typeE>>((BinaryTree<typeE> T1, BinaryTree<typeE> T2) -> T1.getData().getN()-T2.getData().getN());
		Min1 = new BinaryTree<typeE>(null);
		Min2 = new BinaryTree<typeE>(null);

	}

// letter is the type passed onto the binary tree nodes
	// will have method that builds the code tree
// will have method that traverses the tree and returns a map with the code words
	 /**
	  *
	  * @param fmap this method takes the frequency map as parameter and creates a huffman code tree
	  * the huffman tree will be the only element in the pq
	  */
	public void Queue(Map<Character, Integer> fmap) {
		//TODO create a root node of each caracter as a binary tree type and add it to the queue
		Set<Character> keys = fmap.keySet();
		for (Character c : keys) {
			typeE data = new typeE(c,fmap.get(c));
			BinaryTree<typeE> root= new BinaryTree<typeE>(data);
			pq.add(root);
		}
		while (pq.size()>1) {
			Min1 = pq.remove();
			Min2 = pq.remove();
			typeE data = new typeE('x',Min1.getData().getN()+Min2.getData().getN());
			BinaryTree<typeE> root = new BinaryTree<typeE>(data,Min1,Min2);
			pq.add(root);
		}
		huffman= pq.remove();
		//System.out.println(huffman);

	}

	/**
	 * this method returns a tree of the codes of each character in the text
	 *
	 */

	public void codeMap() {
		charactercode = new TreeMap<Character, String>();
		pathsofar="";
		addToMap(huffman, charactercode, pathsofar);
		System.out.println(charactercode);
	}
	public void addToMap (BinaryTree<typeE> T, Map<Character, String> charactercode, String pathsofar) {
		/**
		 * this is a helper function to traverse the tree and get all the codes and add them to a map
		 */
		//System.out.println("method called");
		if (T.isLeaf()) {
			charactercode.put( T.getData().getC(), pathsofar);
			//System.out.println( T.getData().getC()+pathsofar);
		}

			if (T.hasLeft()) {
				addToMap(T.getLeft(), charactercode,pathsofar+"0");
				//System.out.println(pathsofar);
			}
			if (T.hasRight()) {
				addToMap(T.getRight(), charactercode,pathsofar+"1");
			}

	}

	// code map getter

	public  Map<Character, String> getCharactercodes(){
		return charactercode;
	}

	// gets the huffman code tree

	public BinaryTree<typeE> getCodeTree(){
		return huffman;
	}


}