1 /*--------------------------------------------------------------------------
2 Copyright (c) 2010-2011, 2013, The Linux Foundation. All rights reserved.
3
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions are met:
6 * Redistributions of source code must retain the above copyright
7 notice, this list of conditions and the following disclaimer.
8 * Redistributions in binary form must reproduce the above copyright
9 notice, this list of conditions and the following disclaimer in the
10 documentation and/or other materials provided with the distribution.
11 * Neither the name of The Linux Foundation nor
12 the names of its contributors may be used to endorse or promote
13 products derived from this software without specific prior written
14 permission.
15
16 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 NON-INFRINGEMENT ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
20 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
21 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
22 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
23 OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
24 WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
25 OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
26 ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 --------------------------------------------------------------------------*/
28 #ifndef _MAP_H_
29 #define _MAP_H_
30
31 #include <stdio.h>
32 using namespace std;
33
34 template <typename T,typename T2>
35 class Map
36 {
37 struct node {
38 T data;
39 T2 data2;
40 node* prev;
41 node* next;
nodenode42 node(T t, T2 t2,node* p, node* n) :
43 data(t), data2(t2), prev(p), next(n) {}
44 };
45 node* head;
46 node* tail;
47 node* tmp;
48 unsigned size_of_list;
49 static Map<T,T2> *m_self;
50 public:
Map()51 Map() : head( NULL ), tail ( NULL ),tmp(head),size_of_list(0) {}
empty()52 bool empty() const {
53 return ( !head || !tail );
54 }
55 operator bool() const {
56 return !empty();
57 }
58 void insert(T,T2);
59 void show();
60 int size();
61 T2 find(T); // Return VALUE
62 T find_ele(T);// Check if the KEY is present or not
63 T2 begin(); //give the first ele
64 bool erase(T);
65 bool eraseall();
66 bool isempty();
~Map()67 ~Map() {
68 while (head) {
69 node* temp(head);
70 head=head->next;
71 size_of_list--;
72 delete temp;
73 }
74 }
75 };
76
77 template <typename T,typename T2>
find(T d1)78 T2 Map<T,T2>::find(T d1)
79 {
80 tmp = head;
81
82 while (tmp) {
83 if (tmp->data == d1) {
84 return tmp->data2;
85 }
86
87 tmp = tmp->next;
88 }
89
90 return 0;
91 }
92
93 template <typename T,typename T2>
find_ele(T d1)94 T Map<T,T2>::find_ele(T d1)
95 {
96 tmp = head;
97
98 while (tmp) {
99 if (tmp->data == d1) {
100 return tmp->data;
101 }
102
103 tmp = tmp->next;
104 }
105
106 return 0;
107 }
108
109 template <typename T,typename T2>
begin()110 T2 Map<T,T2>::begin()
111 {
112 tmp = head;
113
114 if (tmp) {
115 return (tmp->data2);
116 }
117
118 return 0;
119 }
120
121 template <typename T,typename T2>
show()122 void Map<T,T2>::show()
123 {
124 tmp = head;
125
126 while (tmp) {
127 printf("%d-->%d\n",tmp->data,tmp->data2);
128 tmp = tmp->next;
129 }
130 }
131
132 template <typename T,typename T2>
size()133 int Map<T,T2>::size()
134 {
135 int count =0;
136 tmp = head;
137
138 while (tmp) {
139 tmp = tmp->next;
140 count++;
141 }
142
143 return count;
144 }
145
146 template <typename T,typename T2>
insert(T data,T2 data2)147 void Map<T,T2>::insert(T data, T2 data2)
148 {
149 tail = new node(data, data2,tail, NULL);
150
151 if ( tail->prev )
152 tail->prev->next = tail;
153
154 if ( empty() ) {
155 head = tail;
156 tmp=head;
157 }
158
159 tmp = head;
160 size_of_list++;
161 }
162
163 template <typename T,typename T2>
erase(T d)164 bool Map<T,T2>::erase(T d)
165 {
166 bool found = false;
167 tmp = head;
168 node* prevnode = tmp;
169 node *tempnode;
170
171 while (tmp) {
172 if ((head == tail) && (head->data == d)) {
173 found = true;
174 tempnode = head;
175 head = tail = NULL;
176 delete tempnode;
177 break;
178 }
179
180 if ((tmp ==head) && (tmp->data ==d)) {
181 found = true;
182 tempnode = tmp;
183 tmp = tmp->next;
184 tmp->prev = NULL;
185 head = tmp;
186 tempnode->next = NULL;
187 delete tempnode;
188 break;
189 }
190
191 if ((tmp == tail) && (tmp->data ==d)) {
192 found = true;
193 tempnode = tmp;
194 prevnode->next = NULL;
195 tmp->prev = NULL;
196 tail = prevnode;
197 delete tempnode;
198 break;
199 }
200
201 if (tmp->data == d) {
202 found = true;
203 prevnode->next = tmp->next;
204 tmp->next->prev = prevnode->next;
205 tempnode = tmp;
206 //tmp = tmp->next;
207 delete tempnode;
208 break;
209 }
210
211 prevnode = tmp;
212 tmp = tmp->next;
213 }
214
215 if (found)size_of_list--;
216
217 return found;
218 }
219
220 template <typename T,typename T2>
eraseall()221 bool Map<T,T2>::eraseall()
222 {
223 node *tempnode;
224 tmp = head;
225
226 while (head) {
227 tempnode = head;
228 tempnode->next = NULL;
229 head = head->next;
230 delete tempnode;
231 }
232
233 tail = head = NULL;
234 return true;
235 }
236
237
238 template <typename T,typename T2>
isempty()239 bool Map<T,T2>::isempty()
240 {
241 if (!size_of_list) return true;
242 else return false;
243 }
244
245 #endif // _MAP_H_
246