aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorpacien2018-11-29 21:48:54 +0100
committerpacien2018-11-29 21:48:54 +0100
commitccc45ad33b3da9e415ef35a393930cde1136ae99 (patch)
tree9d4958f48eb1038c44377070bf17d9be5ba28693 /src
parent1524ab71168b7c214a531f796c94962776e9d88a (diff)
downloadgziplike-ccc45ad33b3da9e415ef35a393930cde1136ae99.tar.gz
memoise submaximum
Diffstat (limited to 'src')
-rw-r--r--src/huffmantree.nim10
1 files changed, 7 insertions, 3 deletions
diff --git a/src/huffmantree.nim b/src/huffmantree.nim
index adcaec7..c57b55c 100644
--- a/src/huffmantree.nim
+++ b/src/huffmantree.nim
@@ -27,12 +27,16 @@ type HuffmanTreeNode*[T: SomeUnsignedInt] = ref object
27 case kind: HuffmanTreeNodeKind 27 case kind: HuffmanTreeNodeKind
28 of branch: 28 of branch:
29 left, right: HuffmanTreeNode[T] 29 left, right: HuffmanTreeNode[T]
30 maxChildValue: T
30 of leaf: 31 of leaf:
31 value: T 32 value: T
32 weight: int 33 weight: int
33 34
34proc huffmanBranch*[T](left, right: HuffmanTreeNode[T]): HuffmanTreeNode[T] = 35proc huffmanBranch*[T](left, right: HuffmanTreeNode[T]): HuffmanTreeNode[T] =
35 HuffmanTreeNode[T](kind: branch, left: left, right: right, weight: left.weight + right.weight) 36 HuffmanTreeNode[T](
37 kind: branch, left: left, right: right,
38 maxChildValue: max(left.maxValue(), right.maxValue()),
39 weight: left.weight + right.weight)
36 40
37proc huffmanLeaf*[T](value: T, weight = 0): HuffmanTreeNode[T] = 41proc huffmanLeaf*[T](value: T, weight = 0): HuffmanTreeNode[T] =
38 HuffmanTreeNode[T](kind: leaf, value: value, weight: weight) 42 HuffmanTreeNode[T](kind: leaf, value: value, weight: weight)
@@ -57,7 +61,7 @@ proc `<`*[T](left, right: HuffmanTreeNode[T]): bool =
57 61
58proc maxValue*[T](node: HuffmanTreeNode[T]): T = 62proc maxValue*[T](node: HuffmanTreeNode[T]): T =
59 case node.kind: 63 case node.kind:
60 of branch: max(node.left.maxValue(), node.right.maxValue()) 64 of branch: node.maxChildValue
61 of leaf: node.value 65 of leaf: node.value
62 66
63proc deserialise*[T](bitReader: BitReader, valueType: typedesc[T]): HuffmanTreeNode[T] = 67proc deserialise*[T](bitReader: BitReader, valueType: typedesc[T]): HuffmanTreeNode[T] =
@@ -90,4 +94,4 @@ proc symbolQueue*[T](stats: CountTableRef[T]): HeapQueue[HuffmanTreeNode[T]] =
90proc buildHuffmanTree*[T: SomeUnsignedInt](stats: CountTableRef[T]): HuffmanTreeNode[T] = 94proc buildHuffmanTree*[T: SomeUnsignedInt](stats: CountTableRef[T]): HuffmanTreeNode[T] =
91 var symbolQueue = symbolQueue(stats) 95 var symbolQueue = symbolQueue(stats)
92 while symbolQueue.len > 1: symbolQueue.push(huffmanBranch(symbolQueue.pop(), symbolQueue.pop())) 96 while symbolQueue.len > 1: symbolQueue.push(huffmanBranch(symbolQueue.pop(), symbolQueue.pop()))
93 result = symbolQueue[0] 97 symbolQueue[0]