summaryrefslogtreecommitdiff
path: root/include
diff options
context:
space:
mode:
Diffstat (limited to 'include')
-rw-r--r--include/BHeap.h38
-rw-r--r--include/CList.h35
-rw-r--r--include/FHeap.h40
-rw-r--r--include/HTree.h25
-rw-r--r--include/Hash.h9
-rw-r--r--include/Makefile.am1
-rw-r--r--include/PCommon.h77
-rw-r--r--include/PLList.h33
-rw-r--r--include/PTypes.h21
-rw-r--r--include/SList.h16
10 files changed, 295 insertions, 0 deletions
diff --git a/include/BHeap.h b/include/BHeap.h
new file mode 100644
index 0000000..ab63852
--- /dev/null
+++ b/include/BHeap.h
@@ -0,0 +1,38 @@
+#ifndef __BHEAP_H__
+#define __BHEAP_H__
+#include <PCommon.h>
+#include <CList.h>
+
+#ifdef __cplusplus
+class BHeap:public PriorityList {
+ private:
+ int Degree;
+ BHeap *Father, *Child, *Brother;
+ CList *FP;
+
+ void Link(BHeap * z);
+ void Merge(BHeap * H);
+ BHeap(Key_t IKey, Datas_t const &IDatas); // Insert
+ Cell Insert(BHeap * x);
+
+ public:
+ BHeap(void); // Constructor
+ ~BHeap(void); // Destructor
+ virtual int rn(void);
+ virtual Key_t ReadKey(Cell C);
+ virtual Datas_t ReadDatas(Cell C);
+
+ virtual void Dump(ostream & os);
+ virtual bool IsEmpty(void);
+
+ virtual Cell Min(void);
+ virtual Cell Insert(Key_t IKey, Datas_t const &IDatas);
+ virtual Key_t Extract_Min(Datas_t & Datas);
+ virtual PriorityList *Union(PriorityList * P);
+ virtual bool Lower_Key(Cell x, Key_t NKey);
+ virtual Key_t Delete(Datas_t & Datas, Cell x);
+};
+#else
+#error This librairy will only compile with a C++ compiler.
+#endif
+#endif
diff --git a/include/CList.h b/include/CList.h
new file mode 100644
index 0000000..147fe71
--- /dev/null
+++ b/include/CList.h
@@ -0,0 +1,35 @@
+#ifndef __CLIST_H__
+#define __CLIST_H__
+
+#include <PTypes.h>
+
+#ifdef __cplusplus
+
+class CList {
+ protected:
+ CList * Left, *Right;
+ Key_t Key;
+ Datas_t Datas;
+ CList(CList * IPoint, Datas_t IDatas, Key_t IKey);
+
+ friend class PLList;
+ friend class SList;
+ friend class BHeap;
+
+ public:
+ CList(void);
+ ~CList(void);
+
+ virtual Datas_t ReadDatas(Cell C);
+ virtual Key_t ReadKey(Cell C);
+
+ virtual Cell Insert(Key_t IKey, Datas_t const &IDatas);
+ virtual Key_t Delete(Datas_t & Datas, Cell C);
+ virtual Cell GetFirst(void);
+ virtual Key_t Pop(Datas_t & Datas);
+};
+
+#else
+#error This librairy will only compile with a C++ compiler.
+#endif
+#endif
diff --git a/include/FHeap.h b/include/FHeap.h
new file mode 100644
index 0000000..ac58a6d
--- /dev/null
+++ b/include/FHeap.h
@@ -0,0 +1,40 @@
+#ifndef __FHEAP_H__
+#define __FHEAP_H__
+#include <PCommon.h>
+#define DFMAX 128
+
+#ifdef __cplusplus
+typedef class FHeap:public PriorityList {
+ private:
+ FHeap * Father, *Child, *Left, *Right;
+ int Degree;
+ bool Mark;
+
+ void Link(FHeap * x);
+ void Rebuild(void);
+ FHeap(Key_t IKey, Datas_t const &IDatas); // Insert
+ FHeap *Insert(FHeap * x);
+ void Cut(FHeap * x, FHeap * y);
+ void CascadeCut(FHeap * y);
+
+ public:
+ FHeap(void); // Constructor
+ ~FHeap(void); // Destructor
+
+ virtual int rn(void);
+
+ virtual void Dump(ostream & os);
+ void RDump(ostream & os);
+ virtual bool IsEmpty(void);
+
+ virtual Cell Min(void);
+ virtual Cell Insert(Key_t IKey, Datas_t const &IDatas);
+ virtual Key_t Extract_Min(Datas_t & Datas);
+ virtual PriorityList *Union(PriorityList * P);
+ virtual bool Lower_Key(Cell x, Key_t NKey);
+ virtual Key_t Delete(Datas_t & Datas, Cell x);
+} FHeap;
+#else
+#error This librairy will only compile with a C++ compiler.
+#endif
+#endif
diff --git a/include/HTree.h b/include/HTree.h
new file mode 100644
index 0000000..7a8dea0
--- /dev/null
+++ b/include/HTree.h
@@ -0,0 +1,25 @@
+#ifndef __HTREE_H__
+#define __HTREE_H__
+
+#include <PTypes.h>
+
+#define MAX_HDEPTH 256
+
+#ifdef __cplusplus
+
+class HTree {
+private:
+ HTree * left, * right;
+ int freq;
+ Datas_t objet;
+public:
+ HTree(int n_freq, char * n_objet);
+ HTree(HTree * n_left, HTree * n_right);
+ ~HTree();
+ ostream & Trace(ostream & os, int d = 0);
+};
+
+#else
+#error This librairy will only compile with a C++ compiler.
+#endif
+#endif
diff --git a/include/Hash.h b/include/Hash.h
new file mode 100644
index 0000000..a8d8c1e
--- /dev/null
+++ b/include/Hash.h
@@ -0,0 +1,9 @@
+#ifndef __HASH_H__
+#define __HASH_H__
+
+class Hash {
+ private:
+ void *table;
+};
+
+#endif
diff --git a/include/Makefile.am b/include/Makefile.am
new file mode 100644
index 0000000..a2c74d9
--- /dev/null
+++ b/include/Makefile.am
@@ -0,0 +1 @@
+include_HEADERS = PCommon.h PLList.h FHeap.h BHeap.h Hash.h CList.h SList.h PTypes.h
diff --git a/include/PCommon.h b/include/PCommon.h
new file mode 100644
index 0000000..1d90a21
--- /dev/null
+++ b/include/PCommon.h
@@ -0,0 +1,77 @@
+#ifndef __PCOMMON_H__
+#define __PCOMMON_H__
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#ifndef _
+#define _(x) x
+#endif
+
+#include <PTypes.h>
+#include <limits.h>
+#define P_INFINITY INT_MAX
+#define M_INFINITY INT_MIN
+void exception(int e, char *msg);
+
+#ifdef __cplusplus
+#include <iostream.h>
+
+class PriorityList {
+ protected:
+ class GeneralException;
+ int type;
+ Key_t Key;
+ Datas_t Datas;
+ PriorityList(Key_t IKey, Datas_t const &IDatas);
+
+ public:
+ PriorityList(void);
+ ~PriorityList(void);
+
+ virtual Key_t ReadKey(Cell C);
+ virtual Datas_t ReadDatas(Cell C);
+ virtual int n(void);
+ virtual int rn(void) = 0;
+
+ virtual void Dump(ostream & os) = 0;
+ virtual bool IsEmpty(void) = 0;
+
+ virtual Cell Min(void) = 0;
+ virtual Cell Insert(Key_t IKey, Datas_t const &IDatas) = 0;
+ virtual Key_t Extract_Min(Datas_t & Datas) = 0;
+ virtual PriorityList *Union(PriorityList * P) = 0;
+ virtual bool Lower_Key(Cell x, Key_t NKey) = 0;
+ virtual Key_t Delete(Datas_t & Datas, Cell x) = 0;
+ PriorityList *GenericUnion(PriorityList * P);
+ int GetType(void);
+};
+
+#ifndef SWAP
+template < class T > inline void SWAP(T & a, T & b)
+{
+ T tmp(a);
+
+ a = b;
+ b = tmp;
+};
+#endif
+
+#else
+#warning This librairy is only designed for a C++ compiler.
+#ifndef SWAP
+#define SWAP(a,b) { \
+ char T[sizeof(a)]; \
+ memcpy(T, &a, sizeof(a)); \
+ memcpy(&a, &b, sizeof(a)); \
+ memcpy(&b, T, sizeof(a)); \
+}
+#endif
+#endif
+
+#ifdef DEBUG
+extern int nc, nd;
+#endif
+
+#endif
diff --git a/include/PLList.h b/include/PLList.h
new file mode 100644
index 0000000..6e9af25
--- /dev/null
+++ b/include/PLList.h
@@ -0,0 +1,33 @@
+#ifndef __PLLIST_H__
+#define __PLLIST_H__
+
+#include <PCommon.h>
+#include <SList.h>
+
+#ifdef __cplusplus
+class PLList:public PriorityList { private:
+ SList Head;
+
+ public:
+ PLList(void);
+ ~PLList(void);
+
+ virtual Key_t ReadKey(Cell C);
+ virtual Datas_t ReadDatas(Cell C);
+ virtual int rn(void);
+
+ virtual void Dump(ostream & os);
+ virtual bool IsEmpty(void);
+
+ virtual Cell Min(void);
+ virtual Cell Insert(Key_t IKey, Datas_t const &IDatas);
+ virtual Key_t Extract_Min(Datas_t & Datas);
+ virtual PriorityList *Union(PriorityList * P);
+ virtual bool Lower_Key(Cell x, Key_t NKey);
+ virtual Key_t Delete(Datas_t & Datas, Cell x);
+};
+
+#else
+#error This librairy is will only compile with a C++ compiler.
+#endif
+#endif
diff --git a/include/PTypes.h b/include/PTypes.h
new file mode 100644
index 0000000..6e4e7b7
--- /dev/null
+++ b/include/PTypes.h
@@ -0,0 +1,21 @@
+#ifndef __PTYPES_H__
+#define __PTYPES_H__
+
+#ifndef Key_t
+typedef int Key_t;
+#else
+#warning You have modified the base type for Key_t.
+#warning We will assume you know what you are doing.
+#endif
+
+typedef void *Datas_t;
+typedef void *Cell;
+
+enum {
+ T_PLLIST = 1,
+ T_BINHEAP,
+ T_BHEAP,
+ T_FHEAP
+};
+
+#endif
diff --git a/include/SList.h b/include/SList.h
new file mode 100644
index 0000000..845d83a
--- /dev/null
+++ b/include/SList.h
@@ -0,0 +1,16 @@
+#ifndef __SLIST_H__
+#define __SLIST_H__
+
+#include <PTypes.h>
+#include <CList.h>
+
+#ifdef __cplusplus
+
+class SList:public CList { public:
+ virtual Cell Insert(Key_t IKey, Datas_t const &IDatas);
+};
+
+#else
+#error This librairy will only compile with a C++ compiler.
+#endif
+#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-21 18:21:52 +0000