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 |