aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorpacien2018-11-30 16:38:17 +0100
committerpacien2018-11-30 16:38:17 +0100
commitb03508ea5e20370de26c6faf23bbbdd4e89ab1a9 (patch)
tree92539b9f20783f9c82dd5e74399b958a336e9971 /src
parent4361a9e9c918bc4feff4d04e47dbe686b1d31a6c (diff)
downloadgziplike-b03508ea5e20370de26c6faf23bbbdd4e89ab1a9.tar.gz
isolate huffman tree construction
Diffstat (limited to 'src')
-rw-r--r--src/huffmantree.nim31
-rw-r--r--src/huffmantreebuilder.nim44
2 files changed, 48 insertions, 27 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
30 maxChildValue: T 30 maxChildValue: T
31 of leaf: 31 of leaf:
32 value*: T 32 value*: T
33 weight: int
34 33
35proc huffmanBranch*[T](left, right: HuffmanTreeNode[T]): HuffmanTreeNode[T] = 34proc huffmanBranch*[T](left, right: HuffmanTreeNode[T]): HuffmanTreeNode[T] =
36 HuffmanTreeNode[T]( 35 HuffmanTreeNode[T](
37 kind: branch, left: left, right: right, 36 kind: branch, left: left, right: right,
38 maxChildValue: max(left.maxValue(), right.maxValue()), 37 maxChildValue: max(left.maxValue(), right.maxValue()))
39 weight: left.weight + right.weight)
40 38
41proc huffmanLeaf*[T](value: T, weight = 0): HuffmanTreeNode[T] = 39proc huffmanLeaf*[T](value: T): HuffmanTreeNode[T] =
42 HuffmanTreeNode[T](kind: leaf, value: value, weight: weight) 40 HuffmanTreeNode[T](kind: leaf, value: value)
43 41
44proc `==`*[T](a, b: HuffmanTreeNode[T]): bool = 42proc `==`*[T](a, b: HuffmanTreeNode[T]): bool =
45 if a.kind != b.kind or a.weight != b.weight: return false
46 case a.kind:
47 of branch: a.left == b.left and a.right == b.right
48 of leaf: a.value == b.value
49
50proc `~=`*[T](a, b: HuffmanTreeNode[T]): bool =
51 if a.kind != b.kind: return false 43 if a.kind != b.kind: return false
52 case a.kind: 44 case a.kind:
53 of branch: a.left ~= b.left and a.right ~= b.right 45 of branch: a.left == b.left and a.right == b.right
54 of leaf: a.value == b.value 46 of leaf: a.value == b.value
55 47
56proc `!~`*[T](a, b: HuffmanTreeNode[T]): bool =
57 not (a ~= b)
58
59proc `<`*[T](left, right: HuffmanTreeNode[T]): bool =
60 left.weight < right.weight
61
62proc maxValue*[T](node: HuffmanTreeNode[T]): T = 48proc maxValue*[T](node: HuffmanTreeNode[T]): T =
63 case node.kind: 49 case node.kind:
64 of branch: node.maxChildValue 50 of branch: node.maxChildValue
@@ -86,12 +72,3 @@ proc serialise*[T](tree: HuffmanTreeNode[T], bitWriter: BitWriter) =
86 bitWriter.writeBits(valueBitLength, node.value) 72 bitWriter.writeBits(valueBitLength, node.value)
87 bitWriter.writeBits(valueLengthFieldBitLength, valueBitLength.uint8) 73 bitWriter.writeBits(valueLengthFieldBitLength, valueBitLength.uint8)
88 writeNode(tree) 74 writeNode(tree)
89
90proc symbolQueue*[T](stats: CountTableRef[T]): HeapQueue[HuffmanTreeNode[T]] =
91 result = newHeapQueue[HuffmanTreeNode[T]]()
92 for item, count in stats.pairs: result.push(huffmanLeaf(item, count))
93
94proc buildHuffmanTree*[T: SomeUnsignedInt](stats: CountTableRef[T]): HuffmanTreeNode[T] =
95 var symbolQueue = symbolQueue(stats)
96 while symbolQueue.len > 1: symbolQueue.push(huffmanBranch(symbolQueue.pop(), symbolQueue.pop()))
97 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 @@
1# gzip-like LZSS compressor
2# Copyright (C) 2018 Pacien TRAN-GIRARD
3#
4# This program is free software: you can redistribute it and/or modify
5# it under the terms of the GNU Affero General Public License as
6# published by the Free Software Foundation, either version 3 of the
7# License, or (at your option) any later version.
8#
9# This program is distributed in the hope that it will be useful,
10# but WITHOUT ANY WARRANTY; without even the implied warranty of
11# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12# GNU Affero General Public License for more details.
13#
14# You should have received a copy of the GNU Affero General Public License
15# along with this program. If not, see <https://www.gnu.org/licenses/>.
16
17import tables, heapqueue
18import huffmantree, lzssencoder
19
20type WeighedHuffmanTreeNode[T] = ref object
21 weight: int
22 huffmanTreeNode: HuffmanTreeNode[T]
23
24proc weighedHuffmanBranch[T](left, right: WeighedHuffmanTreeNode[T]): WeighedHuffmanTreeNode[T] =
25 WeighedHuffmanTreeNode[T](
26 weight: left.weight + right.weight,
27 huffmanTreeNode: huffmanBranch(left.huffmanTreeNode, right.huffmanTreeNode))
28
29proc weighedHuffmanLeaf[T](value: T, weight: int): WeighedHuffmanTreeNode[T] =
30 WeighedHuffmanTreeNode[T](
31 weight: weight,
32 huffmanTreeNode: huffmanLeaf(value))
33
34proc `<`*[T](left, right: WeighedHuffmanTreeNode[T]): bool =
35 left.weight < right.weight
36
37proc symbolQueue[T](stats: CountTableRef[T]): HeapQueue[WeighedHuffmanTreeNode[T]] =
38 result = newHeapQueue[WeighedHuffmanTreeNode[T]]()
39 for item, count in stats.pairs: result.push(weighedHuffmanLeaf(item, count))
40
41proc buildHuffmanTree*[T: SomeUnsignedInt](stats: CountTableRef[T]): HuffmanTreeNode[T] =
42 var symbolQueue = symbolQueue(stats)
43 while symbolQueue.len > 1: symbolQueue.push(weighedHuffmanBranch(symbolQueue.pop(), symbolQueue.pop()))
44 symbolQueue[0].huffmanTreeNode