5 files changed, 160 insertions, 0 deletions
diff --git a/circuitpython/tools/huffman/tests/__init__.py b/circuitpython/tools/huffman/tests/__init__.py
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/circuitpython/tools/huffman/tests/__init__.py
diff --git a/circuitpython/tools/huffman/tests/test_codes.py b/circuitpython/tools/huffman/tests/test_codes.py
new file mode 100644
index 0000000..c316046
--- /dev/null
+++ b/circuitpython/tools/huffman/tests/test_codes.py
@@ -0,0 +1,33 @@
+from __future__ import absolute_import, print_function
+
+import collections
+import unittest
+
+import huffman
+
+class TestCodebookGeneration(unittest.TestCase):
+
+    def test_basic(self):
+        output = huffman.codebook([('A', 2), ('B', 4), ('C', 1), ('D', 1)])
+        expected = {'A': '10', 'B': '0', 'C': '110', 'D': '111'}
+
+        self.assertEqual(output, expected)
+
+    def test_counter(self):
+        input_ = sorted(collections.Counter('man the stand banana man').items())
+
+        output = huffman.codebook(input_)
+        expected = {
+            ' ': '111',
+            'a': '10',
+            'b': '0101',
+            'd': '0110',
+            'e': '11000',
+            'h': '0100',
+            'm': '0111',
+            'n': '00',
+            's': '11001',
+            't': '1101',
+         }
+
+        self.assertEqual(output, expected)
diff --git a/circuitpython/tools/huffman/tests/test_heapqo.py b/circuitpython/tools/huffman/tests/test_heapqo.py
new file mode 100644
index 0000000..6094264
--- /dev/null
+++ b/circuitpython/tools/huffman/tests/test_heapqo.py
@@ -0,0 +1,69 @@
+from __future__ import absolute_import, print_function
+
+import sys
+import random
+import unittest
+
+from huffman.heapqo import Heap
+
+from .util import is_sorted, popper
+
+
+class TestHeapPopAlwaysSorted(unittest.TestCase):
+
+    def test_heap_pops_always_sorted(self):
+        for _ in range(500):
+            nums = [random.randrange(10) for _ in range(random.randrange(1, 10))]
+            heap = Heap(nums)
+            assert is_sorted(popper(heap))
+
+    def test_heap_pushpops_always_min(self):
+        for _ in range(10):
+            nums = [random.randrange(10) for _ in range(random.randrange(1, 10))]
+            heap = Heap(nums)
+            for _ in range(500):
+                in_ = random.randrange(-5, 15)
+                lo = min(min(heap.heap), in_)
+                out = heap.pushpop(in_)
+                assert out == lo
+
+    def test_heap_replace(self):
+        """
+        similar to pushpop, but won't return input if that's lower. basically
+        a pop-push
+        """
+        for _ in range(10):
+            nums = [random.randrange(10) for _ in range(random.randrange(1, 10))]
+            heap = Heap(nums)
+            for _ in range(500):
+                in_ = random.randrange(-5, 15)
+                lo = min(heap.heap)
+                out = heap.replace(in_)
+                assert out == lo
+
+
+class TestHeapOrderableItems(unittest.TestCase):
+
+    def test_heap_complain_unorderable(self):
+        if sys.version_info < (3,):
+            raise unittest.SkipTest('Python 2 happily compares disparate types.')
+
+        heap = Heap([1, 2, 3])
+        try:
+            heap.push([])
+        except ValueError as e:
+            self.assertIn('order', str(e))
+        else:
+            self.fail('allowed insertion of unorderable type')
+
+    def test_heap_post_push_unorderable_not_broken(self):
+        heap = Heap([1, 2, 3])
+        try:
+            heap.push([])
+        except ValueError:
+            pass
+        else:
+            pass
+
+        for x in popper(heap):
+            pass # this should run fine and not see that list or Python 2 won't care
diff --git a/circuitpython/tools/huffman/tests/test_util.py b/circuitpython/tools/huffman/tests/test_util.py
new file mode 100644
index 0000000..099d009
--- /dev/null
+++ b/circuitpython/tools/huffman/tests/test_util.py
@@ -0,0 +1,39 @@
+from __future__ import absolute_import, print_function
+
+import random
+import unittest
+
+from .util import is_sorted, popper
+
+class TestIsSorted(unittest.TestCase):
+
+    def test_is_sorted(self):
+        assert is_sorted([1])
+        assert is_sorted([1, 2])
+        assert is_sorted([1, 2, 3])
+        assert is_sorted([1, 2, 2])
+        assert is_sorted([2, 2, 2])
+        assert is_sorted([])
+        assert is_sorted((1, 2, 3))
+        assert is_sorted('abc')
+        assert is_sorted('123')
+        assert is_sorted('eggs')
+        assert is_sorted(iter([1, 2, 3]))
+
+    def test_is_not_sorted(self):
+        assert not is_sorted([3, 2, 1])
+        assert not is_sorted([2, 2, 1])
+        assert not is_sorted('spam')
+
+
+class TestPopper(unittest.TestCase):
+
+    def test_popper(self):
+        for i in range(10):
+            x = list(range(i))
+
+            j = 0
+            for _ in popper(x):
+                j += 1
+
+            self.assertEqual(i, j)
diff --git a/circuitpython/tools/huffman/tests/util.py b/circuitpython/tools/huffman/tests/util.py
new file mode 100644
index 0000000..8ff3cbd
--- /dev/null
+++ b/circuitpython/tools/huffman/tests/util.py
@@ -0,0 +1,19 @@
+from __future__ import absolute_import, print_function
+
+
+def is_sorted(i):
+    i = iter(i)
+    try:
+        a = next(i)
+    except StopIteration:
+        # zero length iterable
+        return True
+    for b in i:
+        if a > b:
+            return False
+    return True
+
+
+def popper(heap):
+    while heap:
+        yield heap.pop()