From 833d20a69fe17ab846c153e35230c66a41d8fca9 Mon Sep 17 00:00:00 2001 From: Pixel <> Date: Wed, 28 Feb 2001 11:40:25 +0000 Subject: Premier jet --- include/BHeap.h | 38 ++++++++++++++++++++++++++ include/CList.h | 35 ++++++++++++++++++++++++ include/FHeap.h | 40 ++++++++++++++++++++++++++++ include/HTree.h | 25 +++++++++++++++++ include/Hash.h | 9 +++++++ include/Makefile.am | 1 + include/PCommon.h | 77 +++++++++++++++++++++++++++++++++++++++++++++++++++++ include/PLList.h | 33 +++++++++++++++++++++++ include/PTypes.h | 21 +++++++++++++++ include/SList.h | 16 +++++++++++ 10 files changed, 295 insertions(+) create mode 100644 include/BHeap.h create mode 100644 include/CList.h create mode 100644 include/FHeap.h create mode 100644 include/HTree.h create mode 100644 include/Hash.h create mode 100644 include/Makefile.am create mode 100644 include/PCommon.h create mode 100644 include/PLList.h create mode 100644 include/PTypes.h create mode 100644 include/SList.h (limited to 'include') 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 +#include + +#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 + +#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 +#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 + +#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 +#include +#define P_INFINITY INT_MAX +#define M_INFINITY INT_MIN +void exception(int e, char *msg); + +#ifdef __cplusplus +#include + +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 +#include + +#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 +#include + +#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 -- cgit v1.2.3