Python 3.x Complete HuffmanHeap

THE ONLY THING THAT SHOULD BE FILLED OUT RIGHT NOW IS HUFFMAN HEAP, Please do not touch any of the other code that was given:

Huffmanheap.py:

class HuffmanHeap(object): def __init__(self, leafs): """  Purpose:  Creates a new HuffmanHeap object.  Pre-conditions:  leafs: a list of HuffmanTree leaf nodes.  Post-conditions:  The heap is created and initialized.  Return:  None  """  self.leafs = leafs def enqueue(self, tree): """  Purpose:  Adds the tree to the Heap.  This is an O(1) operation.  Pre-conditions:  tree is a HuffmanTree object  Post-conditions:  the heap increases in size by 1  Return:  None  """   def dequeue(self): """  Purpose:  Return the smallest value in the queue.  This is an O(1) operation.  Pre-conditions:  None  Post-conditions:  The heap decreases in size by 1  Return:  A HuffmanTree object, with the lowest frequency  """  return None def __len__(self): """  Purpose:  Return the number of data values stored in the heap.  This method allows Python scripts to call len(hh)  if hh is a HuffmanHeap object.  Pre-conditions:  None  Post-conditions:  None  Return:  The number of values stored in the heap  """  return 0 def display(self): """  Purpose:  Display the data for debugging.  Pre-conditions:  None  Post-conditions:  None  Return:  None  """  print('Add code to HuffmanHeap.display() to help you debug.') 

None of this code below needs to be touched. So please do not give me something that requires an import, no importing no importing json, or anything like that the below code works, and I have highlighted what needs to be completed

HuffmanTree.py:

# Defines the Huffman Tree data structure # # A Huffman tree-node has a character and a frequency. # some strings to avoid long lines later _INIT_ASSERT_MESSAGE_NONLEAF = 'Invalid Huffman tree construction attempted.' _GETCH_ASSERT_MESSAGE_NONLEAF = 'Method get_char() called on non-leaf node' class HuffmanTree(object): def __init__(self, freq=0, char=None, left=None, right=None): """  Purpose:  Initializes the HuffmanTree object.  To create a leaf node  aleaf = HuffmanTree(freq=10, char='A')  bleaf = HuffmanTree(freq=15, char='E')  To create an internal node:  node = HuffmanTree(left=aleaf,right=bleaf)   Pre-conditions:  :param freq: a positive integer  :param char: a character  :param left: another Huffman Tree  :param right: another HuffmanTree  """  self.__char = char self.left = left self.right = right if left is None and right is None: # leaf node: assign the frequency as given self.__freq = freq else: assert left is not None and right is not None, _INIT_ASSERT_MESSAGE_NONLEAF # non-leaf node: calculate the frequency from the given subtrees self.__freq = left.__freq + right.__freq def is_leaf(self): """  Purpose:  Check if the node is a leaf.  Simplifies some of the other methods with an abstraction.  Return:  True if the node is a leaf node  """  return self.left is None and self.right is None def get_freq(self): """  Purpose:  Return the frequency data stored in the node.  Return:  :return: the frequency  """  return self.__freq def get_char(self): """  Purpose:  Return the character stored at a leaf node.  Return:  :return: the character at a leaf node  """  assert self.is_leaf(), _GETCH_ASSERT_MESSAGE_NONLEAF return self.__char def display(self, level=0): """  Purpose:  For debugging, display the tree.  The structure of the tree is represented by indentation  No other real purpose.  Preconditions:  :param level: indentation amount for subtrees.  Return  :return: None  """  if self.is_leaf(): print(' '*level+'Leaf:', self.__char, self.__freq) else: print(' '*level+'Node:', self.__freq, 'Children:') self.left.display(level+1) self.right.display(level+1) def build_codec(self): """  Purpose:  Build a dictionary of char-code pairs from the Huffman tree.  Return:  :return: a dictionary with character as key, code as value  """  codes = {} def encoder(tree, code): if tree.is_leaf(): codes[tree.get_char()] = code else: encoder(tree.left, code+'0') encoder(tree.right, code+'1') if self.is_leaf(): codes[self.__char] = '0' else: encoder(self,'') return codes def __lt__(self, other): return self.__freq Encoder.py:

import sys as sys import HuffmanTree as HT import HuffmanHeap as HH DEFAULT_OUTPUT_FILE = 'encoded.txt' def main(): """  Purpose:  Application to read and encode a file using Huffman codes.  Usage: python3 Encoder.py  Sends output to DEFAULT_OUTPUT_FILE  Return:  :return: None  """  if len(sys.argv) != 2: print('Usage: python3', sys.argv[0], '') print('-- sends output to', DEFAULT_OUTPUT_FILE, '-- ') return fname = sys.argv[1] lines = read_file(fname) freqs = count_characters(lines) codec = build_codec(freqs) coded = encode(lines, codec) write_file(DEFAULT_OUTPUT_FILE, coded) def read_file(fname): """  Purpose:  Read a file and return contents in a list of strings.  Preconditions:  :param fname: the name of a text file  Return:  :return: a list of strings, one string for each line  """  tfile = open(fname) lines = [l.rstrip() for l in tfile] tfile.close() return lines def write_file(fname, lines): """  Purpose:  Write the data in lines to the named file.  Warning: this will over-write any data in the named file!  Preconditions:  :param fname: the name of a text file  :param lines: a list of strings  Post-condition:  The named file is created or over-written.  Return:  :return: None  """  tfile = open(fname, 'w') for line in lines: tfile.write(line + ' ') tfile.close() def count_characters(contents): """  Purpose:  Count the characters in the contents.  Pre-conditions:  :param contents: a list of strings.  Return:  :return: a list of (character,frequency) tuples  """  freqs = dict() for line in contents: for char in line: if char in freqs: freqs[char] += 1 else: freqs[char] = 1 return list(freqs.items()) def build_codec(freq_list): """  Purpose:  Build a codec from the frequency list.  Pre-conditions:  :param freq_list: A list of (char,frequency) tuples.  Return:  :return: a dictionary mapping characters to codes  """  freq_list.sort(key=lambda p: p[1]) hq = HH.HuffmanHeap([HT.HuffmanTree(freq=f,char=c) \ for c,f in freq_list]) while len(hq) > 1: t1 = hq.dequeue() t2 = hq.dequeue() hq.enqueue(HT.HuffmanTree(left=t1, right=t2)) survivor = hq.dequeue() return survivor.build_codec() def encode(strings, codec): """  Purpose:  Use the codec to create the data to be sent to the output file.  Pre-conditions:  :param strings: A list of strings to encode.  :param codec: A dictionary containing character-code pairs  Return:  :return: a list of strings including:  the number of codes the number of coded lines,  the codes  the coded lines  """  output = [] output.append(str(len(codec)) + ' ' + str(len(strings))) for char in codec: output.append(codec[char] + ':' + "'" + char + "'") for s in strings: encoded = [] for char in s: encoded.append(codec[char]) output.append(''.join(encoded)) return output if __name__ == '__main__': main() 

Purpose: To implement an ADT to support efficient execution of a HuffmanTree encoder Degree of Difficulty: Easy to Moderate Phoenix right, ace attorney, loves being lazy - erm, efficient. Phoenix is also short on money. He has heard of text compression, and thinks it might be a good idea to compress all his text files to save on valuable disk space (disk space is expensive for him!). Larry Butz, his useless IT friend, wrote most of the code for text compression using Huffman trees, but did not finish the job (surprising no one). On the Assignment 10 Moodle page, you'll find a program named Encoder.py. The program follows a simple design, and is well-documented. All the pieces should be familiar to you, as they are similar to discussion in class The Encoder.py program imports two supporting ADIS . HuffmanTree.py Defines the Huf fmanTree class . Huf fmanHeap.py Defines the Huf fmanHeap class The HuffmanTree class was discussed in lecture, and its definition should be familiar. There is one change that you should note: the function build_codec ) that builds the codec from a HuffmanTree object is now a method in the HuffmanTree class. The ADT HuffmanHeap, was also discussed in lecture, though the code was not given. A heap is a kind of queue that guarantees that the dequeue operation always removes and returns the smallest value in the queue (this is not the FIFO protoco). The HuffmanHeap stores Huf fmanTree objects, and has the following methods: .init__(self, leaf s): Creates a new HuffmanHeap object. enqueue (self, tree) the given HuffmanTree to the heap, dequeue (self): Removes and returns the smallest HuffmanTree in the heap. ..len__(self): Returns the number of HuffmanTrees in the heap. Defining this method allows pro- l enen BoS POP grammers to call len on Huff manHe ap objects