[mareframe] Annotation of /trunk/paramin-beta/datastructure.cc
Annotation of /trunk/paramin-beta/datastructure.cc
Parent Directory
| Revision Log
Revision 1 -
(view)
(download)
1 : |
agomez |
1 |
#include "datastructure.h" |
2 : |
|
|
|
3 : |
|
|
Queue::Queue() {
|
4 : |
|
|
first = NULL;
|
5 : |
|
|
last = NULL;
|
6 : |
|
|
numberInQueue = 0;
|
7 : |
|
|
}
|
8 : |
|
|
|
9 : |
|
|
Queue::~Queue() {
|
10 : |
|
|
int temp;
|
11 : |
|
|
while (!isEmpty())
|
12 : |
|
|
temp = get();
|
13 : |
|
|
}
|
14 : |
|
|
|
15 : |
|
|
int Queue::isEmpty() {
|
16 : |
|
|
return (first == NULL);
|
17 : |
|
|
}
|
18 : |
|
|
|
19 : |
|
|
int Queue::getNumItems() {
|
20 : |
|
|
return numberInQueue;
|
21 : |
|
|
}
|
22 : |
|
|
|
23 : |
|
|
void Queue::put(int tid) {
|
24 : |
|
|
if (first) {
|
25 : |
|
|
Link* temp = new Link;
|
26 : |
|
|
last->l = temp;
|
27 : |
|
|
last = temp;
|
28 : |
|
|
last->tid = tid;
|
29 : |
|
|
last->l = NULL;
|
30 : |
|
|
} else {
|
31 : |
|
|
first = new Link;
|
32 : |
|
|
last = first;
|
33 : |
|
|
first->tid = tid;
|
34 : |
|
|
last->l = NULL;
|
35 : |
|
|
}
|
36 : |
|
|
|
37 : |
|
|
numberInQueue++;
|
38 : |
|
|
}
|
39 : |
|
|
|
40 : |
|
|
int Queue::get() {
|
41 : |
|
|
assert(first);
|
42 : |
|
|
int tid = first->tid;
|
43 : |
|
|
if (first == last) {
|
44 : |
|
|
delete last;
|
45 : |
|
|
last = NULL;
|
46 : |
|
|
first = NULL;
|
47 : |
|
|
} else {
|
48 : |
|
|
Link* temp = first->l;
|
49 : |
|
|
delete first;
|
50 : |
|
|
first = temp;
|
51 : |
|
|
}
|
52 : |
|
|
numberInQueue--;
|
53 : |
|
|
return tid;
|
54 : |
|
|
}
|
55 : |
|
|
|
56 : |
|
|
int Queue::getLast() {
|
57 : |
|
|
assert(last);
|
58 : |
|
|
int tid = last->tid;
|
59 : |
|
|
if (first == last) {
|
60 : |
|
|
delete last;
|
61 : |
|
|
last = NULL;
|
62 : |
|
|
first = NULL;
|
63 : |
|
|
} else {
|
64 : |
|
|
Link* temp = last->l;
|
65 : |
|
|
delete last;
|
66 : |
|
|
last = temp;
|
67 : |
|
|
}
|
68 : |
|
|
numberInQueue--;
|
69 : |
|
|
return tid;
|
70 : |
|
|
}
|
71 : |
|
|
|
72 : |
|
|
void Queue::putFirst(int dataID) {
|
73 : |
|
|
if (first) {
|
74 : |
|
|
// the queue is not empty
|
75 : |
|
|
Link* temp = new Link;
|
76 : |
|
|
temp->l = first;
|
77 : |
|
|
first = temp;
|
78 : |
|
|
first->tid = dataID;
|
79 : |
|
|
} else {
|
80 : |
|
|
// making first link in queue
|
81 : |
|
|
first = new Link;
|
82 : |
|
|
last = first;
|
83 : |
|
|
first->tid = dataID;
|
84 : |
|
|
last->l = NULL;
|
85 : |
|
|
}
|
86 : |
|
|
numberInQueue++;
|
87 : |
|
|
}
|
88 : |
|
|
|
89 : |
|
|
int Queue::contains(int id) {
|
90 : |
|
|
int i = 0;
|
91 : |
|
|
int inQueue = 0;
|
92 : |
|
|
Link* temp;
|
93 : |
|
|
if (isEmpty()) {
|
94 : |
|
|
return 0;
|
95 : |
|
|
};
|
96 : |
|
|
|
97 : |
|
|
temp = first;
|
98 : |
|
|
while (inQueue == 0 && i < numberInQueue) {
|
99 : |
|
|
assert(temp != NULL);
|
100 : |
|
|
inQueue = (temp->tid == id);
|
101 : |
|
|
temp = temp->l;
|
102 : |
|
|
i++;
|
103 : |
|
|
}
|
104 : |
|
|
return inQueue;
|
105 : |
|
|
}
|
|