From 1524ab71168b7c214a531f796c94962776e9d88a Mon Sep 17 00:00:00 2001
From: pacien
Date: Thu, 29 Nov 2018 12:41:59 +0100
Subject: add generic huffman tree builder

---
 src/huffmantree.nim | 31 +++++++++++++++++++++++++++----
 1 file changed, 27 insertions(+), 4 deletions(-)

(limited to 'src/huffmantree.nim')

diff --git a/src/huffmantree.nim b/src/huffmantree.nim
index 1711879..adcaec7 100644
--- a/src/huffmantree.nim
+++ b/src/huffmantree.nim
@@ -14,6 +14,7 @@
 # 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 integers, bitreader, bitwriter
 
 const valueLengthFieldBitLength* = 6  # 64
@@ -28,19 +29,32 @@ type HuffmanTreeNode*[T: SomeUnsignedInt] = ref object
       left, right: HuffmanTreeNode[T]
     of leaf:
       value: T
+  weight: int
 
 proc huffmanBranch*[T](left, right: HuffmanTreeNode[T]): HuffmanTreeNode[T] =
-  HuffmanTreeNode[T](kind: branch, left: left, right: right)
+  HuffmanTreeNode[T](kind: branch, left: left, right: right, weight: left.weight + right.weight)
 
-proc huffmanLeaf*[T](value: T): HuffmanTreeNode[T] =
-  HuffmanTreeNode[T](kind: leaf, value: value)
+proc huffmanLeaf*[T](value: T, weight = 0): HuffmanTreeNode[T] =
+  HuffmanTreeNode[T](kind: leaf, value: value, weight: weight)
 
 proc `==`*[T](a, b: HuffmanTreeNode[T]): bool =
-  if a.kind != b.kind: return false
+  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 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: max(node.left.maxValue(), node.right.maxValue())
@@ -68,3 +82,12 @@ 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()))
+  result = symbolQueue[0]
-- 
cgit v1.2.3