This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Dec 7th, 2012  |  syntax: None  |  size: 4.43 KB  |  views: 44  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
This paste has a previous version, view the difference. Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. class HuffmanNode implements Comparable<HuffmanNode>{
  5. HuffmanNode right;
  6. HuffmanNode left;
  7. HuffmanNode parent;
  8. int count;          
  9. String letter;
  10.  
  11. public HuffmanNode(){}
  12.  
  13. public HuffmanNode (String letter, int count){
  14. this.letter = letter;
  15. this.count = count;
  16. }
  17. public HuffmanNode (String letter, int count, HuffmanNode parent, HuffmanNode left, HuffmanNode right){
  18.     this.letter = letter;
  19.     this.count = count;
  20.     this.left = left;
  21.     this.right = right;
  22.     this.parent = parent;
  23. }
  24.  
  25. public void setCount(int count){
  26. this.count = count;
  27. }
  28.  
  29. public int getCount(){
  30. return count;
  31. }
  32.  
  33. public void setRight(HuffmanNode right){
  34. this.right = right;
  35. }
  36.  
  37. public HuffmanNode getRight(HuffmanNode right){
  38. return right;
  39. }
  40.  
  41. public void setLeft(HuffmanNode left){
  42. this.left = left;
  43. }
  44.  
  45. public HuffmanNode getLeft(HuffmanNode left){
  46. return left;
  47. }      
  48. public void setParent(HuffmanNode right){
  49. this.left = left;
  50. }  
  51. public HuffmanNode getParent(HuffmanNode parent){
  52. return parent;
  53. }
  54.  
  55. public void buildTree(HuffmanNode node){
  56.     if (node.compareTo(this) <= 0 && left != null){
  57.     System.out.println(node.getCount() + ":" + this.count);
  58.     left.buildTree(node);
  59.     }
  60.     else if (node.compareTo(this) <= 0 && left == null){
  61.     this.left = node;
  62.     node.parent = this;
  63.     }
  64.     else if (node.compareTo(this) > 0 && right != null){
  65.     System.out.println(node.getCount() + ":" +this.count);
  66.     right.buildTree(node);
  67.     }
  68.     else if (node.compareTo(this) > 0 && right == null){
  69.     this.right = node;
  70.     node.parent = this;
  71.     }
  72. }
  73.  
  74.  
  75. public int compareTo(HuffmanNode x){
  76. return this.count - x.count;
  77. }
  78. public void genCode(String s){
  79.     if(left != null){
  80.     left.genCode(s + "0");
  81.     }
  82.     if(right != null){
  83.     right.genCode(s + "1");
  84.     }
  85.     if (left == null && right == null){
  86.     System.out.println(s);
  87.     }
  88. }
  89. }
  90.  
  91. public class hw4{
  92. public static void main (String []args)throws IOException{
  93.  
  94. //ask user to enter file name
  95. System.out.printf("Enter a file location and name to encode [press Enter]: ");
  96. Scanner input = new Scanner(System.in);
  97. String filename = input.next();
  98.  
  99. //Gets file name from Scanner and checks to see if valid
  100. File file = new File(filename);
  101. //if (!file.isFile()){
  102. //System.out.printf("Enter a file location and name to encode [press Enter]: ");
  103. //}
  104. Scanner text = new Scanner(file);
  105.  
  106. String[] letters = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
  107. int[] freq = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
  108.  
  109. String letter;
  110. String tempStr;
  111. int tempInt;
  112.  
  113.     while(text.hasNext()){
  114.         letter = text.next();
  115.         //System.out.printf("%s\n", letter);
  116.  
  117.                     char c = letter.charAt(0);
  118.         int index = c - 97;
  119.         freq[index]++;    
  120.     }
  121.  
  122.     for(int i=0; i <25; i++){
  123.     System.out.printf("%s:%d\n", letters[i], freq[i]);
  124.     }
  125.     System.out.printf("\n");
  126.  
  127.     for (int n=0; n <25; n++) {
  128.         for (int i=0; i <25; i++) {
  129.             if (freq[i] > freq[i+1]) {
  130.                 // exchange elements
  131.                 tempInt = freq[i];  
  132.                 tempStr = letters[i];
  133.                 freq[i] = freq[i+1];
  134.                 letters[i] = letters[i+1];  
  135.                 freq[i+1] = tempInt;
  136.                 letters[i+1] = tempStr;
  137.             }
  138.         }  
  139.        }
  140.  
  141.     PriorityQueue<HuffmanNode> huffmanList = new PriorityQueue<HuffmanNode>();
  142.  
  143.     for(int i=0; i <26; i++){
  144.     System.out.printf("%s:%d\n", letters[i], freq[i]);
  145.         if(freq[i] > 0){
  146.         huffmanList.add(new HuffmanNode(letters[i],freq[i]));
  147.         }
  148.     }
  149.  
  150.     HuffmanNode root = new HuffmanNode();
  151.  
  152.     while(huffmanList.size() > 1){
  153.     HuffmanNode x = huffmanList.poll();
  154.     HuffmanNode y = huffmanList.poll();
  155.     HuffmanNode result = new HuffmanNode("-", x.getCount() + y.getCount(), null, x, y);
  156.         if(root == null){
  157.         root = result;
  158.         }
  159.         else{
  160.         root.buildTree(result);
  161.         }
  162.     huffmanList.add(result);                    
  163.     }
  164.      root.genCode(" ");
  165. }
  166. }
  167.  
  168. input file data:
  169. a
  170. a
  171. a
  172. a
  173. d
  174. d
  175. d
  176. d
  177. d
  178. d
  179. d
  180. d
  181. k
  182. k
  183. k
  184. k
  185. k
  186. k
  187. f
  188. f
  189. f
  190. f
  191. f
  192. f
  193. h
  194. h
  195. h
  196. h
  197. h
  198. h
  199. b
  200. b
  201. b
  202. b
  203. b
  204. b
  205. b
  206. b
  207. n
  208. n
  209. n
  210. n
  211. n
  212. n
  213. n
  214. e
  215. e
  216. e
  217. e
  218. e
  219. i
  220. i
  221. i
  222. i
  223. i
  224. i
  225. i
  226. i
  227. l
  228. k
  229. j
  230. a
  231. n
  232. s
  233. g
  234. l
  235. k
  236. j
  237. a
  238. s
  239. v
  240. o
  241. i
  242. j
  243. a
  244. s
  245. d
  246. l
  247. k
  248. g
  249. k
  250. n
  251. m
  252. a
  253. s
  254. d
  255. k
  256. l
  257. o
  258. v
  259. h
  260. a
  261. s
  262. d
  263. g
  264. z
clone this paste RAW Paste Data