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 (25 years, 5 months ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Log Message:	* empty log message *
#	Content
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