From b03508ea5e20370de26c6faf23bbbdd4e89ab1a9 Mon Sep 17 00:00:00 2001
From: pacien
Date: Fri, 30 Nov 2018 16:38:17 +0100
Subject: isolate huffman tree construction
---
src/huffmantree.nim | 31 ++++--------------------------
src/huffmantreebuilder.nim | 44 +++++++++++++++++++++++++++++++++++++++++++
tests/thuffmantree.nim | 31 +-----------------------------
tests/thuffmantreebuilder.nim | 29 ++++++++++++++++++++++++++++
4 files changed, 78 insertions(+), 57 deletions(-)
create mode 100644 src/huffmantreebuilder.nim
create mode 100644 tests/thuffmantreebuilder.nim
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 .
+
+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 .
+
+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
--
cgit v1.2.3