From dfd868ecf9e37a5e6954a073c3ba43a970f7ca54 Mon Sep 17 00:00:00 2001
From: Pixel <>
Date: Mon, 5 Mar 2001 01:30:36 +0000
Subject: Projet quasi fini...

---
 lib/FHeap.cc    |  3 +--
 lib/HTree.cc    | 29 ++++++++++++++++++++++++++++-
 lib/Huffman.cc  | 31 +++++++++++++++++++++++++++++++
 lib/Makefile.am |  3 ++-
 lib/PCommon.cc  |  1 +
 lib/SList.cc    |  1 +
 6 files changed, 64 insertions(+), 4 deletions(-)
 create mode 100644 lib/Huffman.cc

(limited to 'lib')

diff --git a/lib/FHeap.cc b/lib/FHeap.cc
index 9f3dc24..158a1e5 100644
--- a/lib/FHeap.cc
+++ b/lib/FHeap.cc
@@ -136,8 +136,6 @@ Father(NULL), Child(NULL), Left(this), Right(this), Degree(0), Mark(false)
 
 FHeap::~FHeap(void)
 {
-	FHeap *T;
-
 	if (Child) {
 		delete Child;
 	}
@@ -277,6 +275,7 @@ bool FHeap::Lower_Key(Cell x, Key_t NKey)
 	}
 	if (NKey < Child->Key)
 		Child = tx;
+	return true;
 }
 
 Key_t FHeap::Delete(Datas_t & Datas, Cell x)
diff --git a/lib/HTree.cc b/lib/HTree.cc
index b8731e4..682ac14 100644
--- a/lib/HTree.cc
+++ b/lib/HTree.cc
@@ -30,10 +30,18 @@ HTree::~HTree()
 ostream & HTree::Trace(ostream & os, int d)
 {
 	static char cmpr[MAX_HDEPTH + 1];
+	static int tsize;
+	static int rsize;
+	static int dsize;
+
+	if (!d) tsize = rsize = dsize = 0;
 
 	if (objet) {
 		cmpr[d] = '\0';
-		os << objet << " = " << cmpr << endl;
+		os << objet << " (" << freq << ") = " << cmpr << endl;
+		tsize += freq * strlen(cmpr);
+		rsize += freq * strlen(objet);
+		dsize += ((strlen(cmpr) >> 3) + (strlen(cmpr) & 7 ? 1 : 0)) + strlen(objet) + 2;
 	} else {
 		if (left) {
 			cmpr[d] = '0';
@@ -44,5 +52,24 @@ ostream & HTree::Trace(ostream & os, int d)
 			right->Trace(os, d + 1);
 		}
 	}
+	
+	if (!d) {
+	  os << _("Bitstream length           : ") << tsize << _(" bits (= ") << ((tsize >> 3) + (tsize & 7 ? 1 : 0)) << _(" bytes)\n");
+	  os << _("Real size input            : ") << (rsize << 3) << _(" bits (= ") << rsize << _(" bytes)\n");
+	  os << _("Size squeezed by           : ") << 100.0 - 100.0 * tsize / (rsize << 3) << _(" percents\n");
+	  os << _("Dictionnary size           : ") << (dsize << 3) << _(" bits (= ") << dsize << _(" bytes)\n");
+	  os << _("Total bitstream length     : ") << tsize + (dsize << 3) << _(" bits (= ") << ((tsize >> 3) + (tsize & 7 ? 1 : 0) + dsize) << _(" bytes)\n");
+	  os << _("Real gain (4 bytes header) : ") << 100.0 - 100.0 * ((tsize >> 3) + (tsize & 7 ? 1 : 0) + dsize + 4) / rsize << _(" percents\n");
+	}
 	return os;
 }
+
+int HTree::ReadFreq(void)
+{
+	return freq;
+}
+
+char *HTree::ReadObj(void)
+{
+	return objet;
+}
diff --git a/lib/Huffman.cc b/lib/Huffman.cc
new file mode 100644
index 0000000..aadf927
--- /dev/null
+++ b/lib/Huffman.cc
@@ -0,0 +1,31 @@
+#include <stdio.h>
+#include <iostream.h>
+#include "config.h"
+#include "Huffman.h"
+
+HTree *Coder(PriorityList * P)
+{
+	int n = P->n(), i, f1, f2;
+	HTree *x, *y, *z;
+	Datas_t tx, ty;
+
+	x = y = z = NULL;
+	
+	for (i = 0; i < n - 1; i++) {
+		f1 = P->Extract_Min(tx);
+		f2 = P->Extract_Min(ty);
+		x = (HTree *) tx;
+		y = (HTree *) ty;
+		z = new HTree(x, y);
+		P->Insert(z->ReadFreq(), z);
+	}
+
+	P->Extract_Min(((Datas_t) z));
+	return z;
+}
+
+void HInsert(PriorityList * P, int freq, char *object)
+{
+	HTree * leaf = new HTree(freq, object);
+	P->Insert(freq, (Datas_t) leaf);
+}
diff --git a/lib/Makefile.am b/lib/Makefile.am
index 71b12e7..10ae1fd 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -1,10 +1,11 @@
 localedir = $(datadir)/locale
 DEFS = -DLOCALEDIR=\"$(localedir)\" @DEFS@
 AM_CFLAGS = -O3 -Wall -Wstrict-prototypes $(CFLAGS)
+AM_CXXFLAGS = -O3 -Wall -Wstrict-prototypes $(CXXFLAGS)
 INCLUDES = -I. -I.. -I$(includedir) -I../include
 lib_LTLIBRARIES = libPriorityLists.la
 
-libPriorityLists_la_SOURCES = PCommon.cc BHeap.cc FHeap.cc BinHeap.cc PLList.cc CList.cc SList.cc HTree.cc
+libPriorityLists_la_SOURCES = PCommon.cc BHeap.cc FHeap.cc BinHeap.cc PLList.cc CList.cc SList.cc HTree.cc Huffman.cc
 
 libPriorityLists_la_LDFLAGS = -version-info $(PriorityLists_VERSION_INFO)
 
diff --git a/lib/PCommon.cc b/lib/PCommon.cc
index b833a10..1dc3127 100644
--- a/lib/PCommon.cc
+++ b/lib/PCommon.cc
@@ -50,6 +50,7 @@ PriorityList *PriorityList::GenericUnion(PriorityList * P)
 		IKey = P->Extract_Min(IDatas);
 		Insert(IKey, IDatas);
 	}
+	return this;
 }
 
 
diff --git a/lib/SList.cc b/lib/SList.cc
index c65d299..ae2f54f 100644
--- a/lib/SList.cc
+++ b/lib/SList.cc
@@ -1,4 +1,5 @@
 #include <stdio.h>
+#include "config.h"
 #include "SList.h"
 
 /**********************\
-- 
cgit v1.2.3