142 lines
4.4 KiB
Python
142 lines
4.4 KiB
Python
#
|
|
# Sam Hadow - Huffman-py
|
|
# Copyright (C) 2023
|
|
#
|
|
# This program is free software: you can redistribute it and/or modify
|
|
# it under the terms of the GNU General Public License as published by
|
|
# the Free Software Foundation, either version 3 of the License, or
|
|
# (at your option) any later version.
|
|
#
|
|
# This program is distributed in the hope that it will be useful,
|
|
# but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
# GNU General Public License for more details.
|
|
#
|
|
# You should have received a copy of the GNU General Public License
|
|
# along with this program. If not, see <http://www.gnu.org/licenses/>.
|
|
#
|
|
|
|
import unittest
|
|
from huffman_py.Node import *
|
|
from huffman_py.Tree import *
|
|
from huffman_py.functions.encode import *
|
|
from huffman_py.functions.decode import *
|
|
from huffman_py.functions.occurence import *
|
|
|
|
# Tu run unit tests:
|
|
# python -m unittest discover
|
|
|
|
class TestUtils(unittest.TestCase):
|
|
def test_Tree_id(self):
|
|
a = Node(10, 'a')
|
|
b = Node(8,'b')
|
|
r1 = Node(18,'',left=b,right=a)
|
|
|
|
tree1 = Tree(r1)
|
|
|
|
# unique identifier check
|
|
id_list = []
|
|
check_id = True
|
|
for elem in tree1.nodes:
|
|
id_list.append(elem.identifier)
|
|
if len(id_list) > len(set(id_list)):
|
|
check_id = False
|
|
|
|
self.assertTrue(check_id)
|
|
|
|
def test_Tree_fusion(self):
|
|
# tree merge
|
|
# we must find elements in initial trees + a root
|
|
# identifiers must be unique
|
|
a = Node(10, 'a')
|
|
b = Node(8,'b')
|
|
r1 = Node(18,'',left=b,right=a)
|
|
c = Node(15, 'c')
|
|
d = Node(20,'d')
|
|
r2 = Node(18,'',left=d,right=c)
|
|
|
|
tree1 = Tree(r1)
|
|
tree2 = Tree(r2)
|
|
|
|
l1 = len(tree1.nodes)
|
|
l2 = len(tree2.nodes)
|
|
tree1 += tree2
|
|
check_fusion = True
|
|
if l1+l2+1 != len(tree1.nodes):
|
|
check_fusion = False
|
|
|
|
id_list2 = []
|
|
check_id2 = True
|
|
for elem in tree1.nodes:
|
|
id_list2.append(elem.identifier)
|
|
if len(id_list2) > len(set(id_list2)):
|
|
check_id2 = False
|
|
|
|
self.assertTrue(check_fusion)
|
|
self.assertTrue(check_id2)
|
|
|
|
def test_Tree_seek(self):
|
|
# seek a node
|
|
a = Node(10, 'a')
|
|
b = Node(8,'b')
|
|
r1 = Node(18,'',left=b,right=a)
|
|
|
|
tree1 = Tree(r1)
|
|
|
|
self.assertEqual(tree1.seek(a),a)
|
|
self.assertNotEqual(tree1.seek(b),a)
|
|
|
|
def test_Tree_delete(self):
|
|
a = Node(10, 'a')
|
|
b = Node(8,'b')
|
|
r1 = Node(18,'',left=b,right=a)
|
|
r2 = Node(18,'',left=None,right=r1)
|
|
|
|
tree1 = Tree(r2)
|
|
|
|
tree1 -= r1
|
|
self.assertEqual(tree1.seek(a),None)
|
|
self.assertEqual(tree1.seek(b),None)
|
|
self.assertEqual(tree1.seek(r1),None)
|
|
self.assertEqual(tree1.seek(r2),r2)
|
|
|
|
def test_occurences(self):
|
|
o1 = calcul_occurence('aaabcc')
|
|
o2 = calcul_occurence('bacaac')
|
|
# Same dictionary in both case
|
|
# 3 for a, 2 for c, 1 for b
|
|
self.assertEqual(o1,o2)
|
|
self.assertEqual(o1['c'],2)
|
|
self.assertEqual(o1['b'],1)
|
|
self.assertEqual(o1['a'],3)
|
|
|
|
|
|
def test_huffman_encode(self):
|
|
string = 'sheep'
|
|
string2 = 'cow'
|
|
(encodedOutput, root, huffmanEncoding) = huffman_encode(string)
|
|
(encodedOutput2, root2, huffmanEncoding2) = huffman_encode(string2)
|
|
# encoding must be different
|
|
self.assertNotEqual(huffmanEncoding, huffmanEncoding2)
|
|
self.assertNotEqual(encodedOutput, encodedOutput2)
|
|
self.assertNotEqual(Tree(root),Tree(root2))
|
|
|
|
def test_decodage_huffman(self):
|
|
string = 'chicken'
|
|
(encodedOutput, root, huffmanEncoding) = huffman_encode(string)
|
|
# We must be able to decode a binary from its tree root/dict
|
|
self.assertEqual(string,huffman_decode(encodedOutput,root))
|
|
self.assertEqual(string,decode_from_dict(encodedOutput,huffmanEncoding))
|
|
|
|
# we must be able to detect if tree/dict isn't the correct one to decode a binary
|
|
string2 = 'pig'
|
|
(encodedOutput2, root2, huffmanEncoding2) = huffman_encode(string2)
|
|
with self.assertRaises(ValueError):
|
|
decode_from_dict(encodedOutput2,huffmanEncoding)
|
|
with self.assertRaises(ValueError):
|
|
huffman_decode(encodedOutput2,root)
|
|
|
|
|
|
if __name__ == '__main__':
|
|
unittest.main()
|