Tree-M/MT/list.h

#ifndef LIST_H
#define LIST_H

#include <ostream.h>
#include <assert.h>

// A template ordered list package, which is handy.
template <class T>
struct listnode {
        T entry;
        listnode<T> *prev, *next;
};

template <class T>
class list {
public:
        list(int func(T, T)): compare(func) { front=rear=NULL; }
        int IsEmpty() const { return front==NULL; }

        T First() const {
                assert(front!=NULL);
                return front->entry;
        }

        T Last() const {
                assert(rear!=NULL);
                return rear->entry;
        }

        T RemoveFirst() {
                assert(front!=NULL);
                listnode<T> *temp=front;
                T e=front->entry;

                front=front->next;
                if(front) front->prev=NULL;
                else rear=NULL;
                delete temp;
                return e;
        }

        T RemoveLast() {
                assert(rear!=NULL);
                listnode<T> *temp=rear;

                T e=rear->entry;
                rear=rear->prev;
                if(rear) rear->next=NULL;
                else front=NULL;
                delete temp;
                return e;
        }

        void Insert(T entry) {
                listnode<T> *temp=front;

                while((temp)&&(compare(temp->entry, entry)<0))
                        temp=temp->next;
                if(temp) InsertBefore(temp, entry);
                else Append(entry);
        }

#ifdef PRINTING_OBJECTS
        void Print(ostream& os) const {
                listnode<T> *temp=front;

                os << "List entries:\n";
                while(temp) {
                        os << "\t" << temp->entry;
                        temp=temp->next;
                }
                os << endl;
        }
#endif
private:
        void Append(T entry) {
                listnode<T> *temp=new listnode<T>;

                temp->entry=entry;
                temp->prev=rear;
                temp->next=NULL;
                if(front==NULL) front=temp;
                else rear->next=temp;
                rear=temp;
        }

        void InsertAfter(listnode<T> *node, T entry) {
                listnode<T> *temp=new listnode<T>;

                temp->entry=entry;
                temp->prev=node;
                temp->next=node->next;
                node->next=temp;
                if(rear==node) rear=temp;
                else temp->next->prev=temp;
        }
        
        void InsertBefore(listnode<T> *node, T entry) {
                listnode<T> *temp=new listnode<T>;

                temp->entry=entry;
                temp->prev=node->prev;
                temp->next=node;
                node->prev=temp;
                if(front==node) front=temp;
                else temp->prev->next=temp;
        }
        
        listnode<T> *front, *rear;
        int (*compare)(T, T);   // should return <0 if T1<T2
};

#endif
Revision:	1.1
Committed:	Sun May 6 00:45:53 2001 UTC (23 years, 1 month ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	#ifndef LIST_H
2			#define LIST_H
3
4			#include <ostream.h>
5			#include <assert.h>
6
7			// A template ordered list package, which is handy.
8			template <class T>
9			struct listnode {
10			T entry;
11			listnode<T> prev, next;
12			};
13
14			template <class T>
15			class list {
16			public:
17			list(int func(T, T)): compare(func) { front=rear=NULL; }
18			int IsEmpty() const { return front==NULL; }
19
20			T First() const {
21			assert(front!=NULL);
22			return front->entry;
23			}
24
25			T Last() const {
26			assert(rear!=NULL);
27			return rear->entry;
28			}
29
30			T RemoveFirst() {
31			assert(front!=NULL);
32			listnode<T> *temp=front;
33			T e=front->entry;
34
35			front=front->next;
36			if(front) front->prev=NULL;
37			else rear=NULL;
38			delete temp;
39			return e;
40			}
41
42			T RemoveLast() {
43			assert(rear!=NULL);
44			listnode<T> *temp=rear;
45
46			T e=rear->entry;
47			rear=rear->prev;
48			if(rear) rear->next=NULL;
49			else front=NULL;
50			delete temp;
51			return e;
52			}
53
54			void Insert(T entry) {
55			listnode<T> *temp=front;
56
57			while((temp)&&(compare(temp->entry, entry)<0))
58			temp=temp->next;
59			if(temp) InsertBefore(temp, entry);
60			else Append(entry);
61			}
62
63			#ifdef PRINTING_OBJECTS
64			void Print(ostream& os) const {
65			listnode<T> *temp=front;
66
67			os << "List entries:\n";
68			while(temp) {
69			os << "\t" << temp->entry;
70			temp=temp->next;
71			}
72			os << endl;
73			}
74			#endif
75			private:
76			void Append(T entry) {
77			listnode<T> *temp=new listnode<T>;
78
79			temp->entry=entry;
80			temp->prev=rear;
81			temp->next=NULL;
82			if(front==NULL) front=temp;
83			else rear->next=temp;
84			rear=temp;
85			}
86
87			void InsertAfter(listnode<T> *node, T entry) {
88			listnode<T> *temp=new listnode<T>;
89
90			temp->entry=entry;
91			temp->prev=node;
92			temp->next=node->next;
93			node->next=temp;
94			if(rear==node) rear=temp;
95			else temp->next->prev=temp;
96			}
97
98			void InsertBefore(listnode<T> *node, T entry) {
99			listnode<T> *temp=new listnode<T>;
100
101			temp->entry=entry;
102			temp->prev=node->prev;
103			temp->next=node;
104			node->prev=temp;
105			if(front==node) front=temp;
106			else temp->prev->next=temp;
107			}
108
109			listnode<T> front, rear;
110			int (*compare)(T, T); // should return <0 if T1<T2
111			};
112
113			#endif