isolate huffman tree construction

4 files changed, 78 insertions, 57 deletions

diff --git a/src/huffmantree.nim b/src/huffmantree.nim
index 44c9990..0266dfb 100644
--- a/src/huffmantree.nim
+++ b/src/huffmantree.nim
@@ -30,35 +30,21 @@ type HuffmanTreeNode*[T: SomeUnsignedInt] = ref object
       maxChildValue: T
     of leaf:
       value*: T
-  weight: int
 
 proc huffmanBranch*[T](left, right: HuffmanTreeNode[T]): HuffmanTreeNode[T] =
   HuffmanTreeNode[T](
     kind: branch, left: left, right: right,
-    maxChildValue: max(left.maxValue(), right.maxValue()),
-    weight: left.weight + right.weight)
+    maxChildValue: max(left.maxValue(), right.maxValue()))
 
-proc huffmanLeaf*[T](value: T, weight = 0): HuffmanTreeNode[T] =
-  HuffmanTreeNode[T](kind: leaf, value: value, weight: weight)
+proc huffmanLeaf*[T](value: T): HuffmanTreeNode[T] =
+  HuffmanTreeNode[T](kind: leaf, value: value)
 
 proc `==`*[T](a, b: HuffmanTreeNode[T]): bool =
-  if a.kind != b.kind or a.weight != b.weight: return false
-  case a.kind:
-    of branch: a.left == b.left and a.right == b.right
-    of leaf: a.value == b.value
-
-proc `~=`*[T](a, b: HuffmanTreeNode[T]): bool =
   if a.kind != b.kind: return false
   case a.kind:
-    of branch: a.left ~= b.left and a.right ~= b.right
+    of branch: a.left == b.left and a.right == b.right
     of leaf: a.value == b.value
 
-proc `!~`*[T](a, b: HuffmanTreeNode[T]): bool =
-  not (a ~= b)
-
-proc `<`*[T](left, right: HuffmanTreeNode[T]): bool =
-  left.weight < right.weight
-
 proc maxValue*[T](node: HuffmanTreeNode[T]): T =
   case node.kind:
     of branch: node.maxChildValue
@@ -86,12 +72,3 @@ proc serialise*[T](tree: HuffmanTreeNode[T], bitWriter: BitWriter) =
         bitWriter.writeBits(valueBitLength, node.value)
   bitWriter.writeBits(valueLengthFieldBitLength, valueBitLength.uint8)
   writeNode(tree)
-
-proc symbolQueue*[T](stats: CountTableRef[T]): HeapQueue[HuffmanTreeNode[T]] =
-  result = newHeapQueue[HuffmanTreeNode[T]]()
-  for item, count in stats.pairs: result.push(huffmanLeaf(item, count))
-
-proc buildHuffmanTree*[T: SomeUnsignedInt](stats: CountTableRef[T]): HuffmanTreeNode[T] =
-  var symbolQueue = symbolQueue(stats)
-  while symbolQueue.len > 1: symbolQueue.push(huffmanBranch(symbolQueue.pop(), symbolQueue.pop()))
-  symbolQueue[0]
diff --git a/src/huffmantreebuilder.nim b/src/huffmantreebuilder.nim
new file mode 100644
index 0000000..5b33d34
--- /dev/null
+++ b/src/huffmantreebuilder.nim
@@ -0,0 +1,44 @@
+# gzip-like LZSS compressor
+# Copyright (C) 2018  Pacien TRAN-GIRARD
+#
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU Affero 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 Affero General Public License for more details.
+#
+# You should have received a copy of the GNU Affero General Public License
+# along with this program.  If not, see <https://www.gnu.org/licenses/>.
+
+import tables, heapqueue
+import huffmantree, lzssencoder
+
+type WeighedHuffmanTreeNode[T] = ref object
+  weight: int
+  huffmanTreeNode: HuffmanTreeNode[T]
+
+proc weighedHuffmanBranch[T](left, right: WeighedHuffmanTreeNode[T]): WeighedHuffmanTreeNode[T] =
+  WeighedHuffmanTreeNode[T](
+    weight: left.weight + right.weight,
+    huffmanTreeNode: huffmanBranch(left.huffmanTreeNode, right.huffmanTreeNode))
+
+proc weighedHuffmanLeaf[T](value: T, weight: int): WeighedHuffmanTreeNode[T] =
+  WeighedHuffmanTreeNode[T](
+    weight: weight,
+    huffmanTreeNode: huffmanLeaf(value))
+
+proc `<`*[T](left, right: WeighedHuffmanTreeNode[T]): bool =
+  left.weight < right.weight
+
+proc symbolQueue[T](stats: CountTableRef[T]): HeapQueue[WeighedHuffmanTreeNode[T]] =
+  result = newHeapQueue[WeighedHuffmanTreeNode[T]]()
+  for item, count in stats.pairs: result.push(weighedHuffmanLeaf(item, count))
+
+proc buildHuffmanTree*[T: SomeUnsignedInt](stats: CountTableRef[T]): HuffmanTreeNode[T] =
+  var symbolQueue = symbolQueue(stats)
+  while symbolQueue.len > 1: symbolQueue.push(weighedHuffmanBranch(symbolQueue.pop(), symbolQueue.pop()))
+  symbolQueue[0].huffmanTreeNode
diff --git a/tests/thuffmantree.nim b/tests/thuffmantree.nim
index 705ac17..bc6a505 100644
--- a/tests/thuffmantree.nim
+++ b/tests/thuffmantree.nim
@@ -18,39 +18,20 @@ import unittest, streams, sequtils, tables, heapqueue
 import bitreader, bitwriter, huffmantree
 
 suite "huffmantree":
-  let stats = newCountTable(concat(repeat(1'u, 3), repeat(2'u, 1), repeat(3'u, 2)))
   let tree = huffmanBranch(
     huffmanLeaf(1'u),
     huffmanBranch(
       huffmanLeaf(2'u),
       huffmanLeaf(3'u)))
 
-  test "equivalence":
-    check huffmanLeaf(12'u) ~= huffmanLeaf(12'u)
-    check huffmanLeaf(12'u) ~= huffmanLeaf(12'u, 2)
-    check huffmanLeaf(12'u) !~ huffmanLeaf(21'u)
-    check huffmanLeaf(12'u) !~ huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(12'u))
-    check huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(21'u)) ~= huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(21'u))
-    check huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(21'u)) !~ huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(1'u))
-    check huffmanBranch(huffmanLeaf(12'u, 1), huffmanLeaf(21'u, 1)) ~= huffmanBranch(huffmanLeaf(12'u, 1), huffmanLeaf(21'u, 2))
-    check huffmanBranch(huffmanLeaf(12'u, 1), huffmanLeaf(21'u, 1)) !~ huffmanBranch(huffmanLeaf(12'u, 1), huffmanLeaf(12'u, 2))
-
   test "equality":
     check huffmanLeaf(12'u) == huffmanLeaf(12'u)
     check huffmanLeaf(12'u) != huffmanLeaf(21'u)
     check huffmanLeaf(12'u) != huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(12'u))
     check huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(21'u)) == huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(21'u))
     check huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(21'u)) != huffmanBranch(huffmanLeaf(12'u), huffmanLeaf(1'u))
-    check huffmanBranch(huffmanLeaf(12'u, 1), huffmanLeaf(21'u, 1)) == huffmanBranch(huffmanLeaf(12'u, 1), huffmanLeaf(21'u, 1))
-    check huffmanBranch(huffmanLeaf(12'u, 1), huffmanLeaf(21'u, 1)) != huffmanBranch(huffmanLeaf(12'u, 1), huffmanLeaf(21'u, 2))
     check tree == tree
 
-  test "weight comparison":
-    check huffmanLeaf(12'u, 1) < huffmanLeaf(12'u, 2)
-    check huffmanLeaf(12'u, 2) > huffmanLeaf(12'u, 1)
-    check huffmanLeaf(12'u, 1) < huffmanLeaf(12'u, 1) == false
-    check huffmanBranch(huffmanLeaf(12'u, 1), huffmanLeaf(21'u, 1)) < huffmanBranch(huffmanLeaf(12'u, 1), huffmanLeaf(21'u, 2))
-
   test "maxValue":
     check tree.maxValue() == 3
 
@@ -71,7 +52,7 @@ suite "huffmantree":
 
     stream.setPosition(0)
     let bitReader = stream.bitReader()
-    check huffmantree.deserialise(bitReader, uint) ~= tree
+    check huffmantree.deserialise(bitReader, uint) == tree
 
   test "serialise":
     let stream = newStringStream()
@@ -91,13 +72,3 @@ suite "huffmantree":
     check bitReader.readBits(2, uint8) == 2
     check bitReader.readBool() == true   # 3 leaf
     check bitReader.readBits(2, uint8) == 3
-
-  test "symbolQueue":
-    var symbolQueue = symbolQueue(stats)
-    check symbolQueue.len == 3
-    check symbolQueue.pop() == huffmanLeaf(2'u, 1)
-    check symbolQueue.pop() == huffmanLeaf(3'u, 2)
-    check symbolQueue.pop() == huffmanLeaf(1'u, 3)
-
-  test "buildHuffmanTree":
-    check buildHuffmanTree(stats) ~= tree
diff --git a/tests/thuffmantreebuilder.nim b/tests/thuffmantreebuilder.nim
new file mode 100644
index 0000000..f782b37
--- /dev/null
+++ b/tests/thuffmantreebuilder.nim
@@ -0,0 +1,29 @@
+# gzip-like LZSS compressor
+# Copyright (C) 2018  Pacien TRAN-GIRARD
+#
+# This program is free software: you can redistribute it and/or modify
+# it under the terms of the GNU Affero 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 Affero General Public License for more details.
+#
+# You should have received a copy of the GNU Affero General Public License
+# along with this program.  If not, see <https://www.gnu.org/licenses/>.
+
+import unittest, tables, sequtils
+import huffmantree, huffmantreebuilder
+
+suite "huffmantreebuilder":
+  let stats = newCountTable(concat(repeat(1'u, 3), repeat(2'u, 1), repeat(3'u, 2)))
+  let tree = huffmanBranch(
+    huffmanLeaf(1'u),
+    huffmanBranch(
+      huffmanLeaf(2'u),
+      huffmanLeaf(3'u)))
+
+  test "buildHuffmanTree":
+    check buildHuffmanTree(stats) == tree