1 /*--------------------------------------------------------------------------
2 Copyright (c) 2010-2011, Code Aurora Forum. 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 Code Aurora 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 {
39 T data;
40 T2 data2;
41 node* prev;
42 node* next;
nodenode43 node(T t, T2 t2,node* p, node* n) :
44 data(t), data2(t2), prev(p), next(n) {}
45 };
46 node* head;
47 node* tail;
48 node* tmp;
49 unsigned size_of_list;
50 static Map<T,T2> *m_self;
51 public:
Map()52 Map() : head( NULL ), tail ( NULL ),tmp(head),size_of_list(0) {}
empty()53 bool empty() const { return ( !head || !tail ); }
54 operator bool() const { return !empty(); }
55 void insert(T,T2);
56 void show();
57 int size();
58 T2 find(T); // Return VALUE
59 T find_ele(T);// Check if the KEY is present or not
60 T2 begin(); //give the first ele
61 bool erase(T);
62 bool eraseall();
63 bool isempty();
~Map()64 ~Map()
65 {
66 while(head)
67 {
68 node* temp(head);
69 head=head->next;
70 size_of_list--;
71 delete temp;
72 }
73 }
74 };
75
76 template <typename T,typename T2>
find(T d1)77 T2 Map<T,T2>::find(T d1)
78 {
79 tmp = head;
80 while(tmp)
81 {
82 if(tmp->data == d1)
83 {
84 return tmp->data2;
85 }
86 tmp = tmp->next;
87 }
88 return 0;
89 }
90
91 template <typename T,typename T2>
find_ele(T d1)92 T Map<T,T2>::find_ele(T d1)
93 {
94 tmp = head;
95 while(tmp)
96 {
97 if(tmp->data == d1)
98 {
99 return tmp->data;
100 }
101 tmp = tmp->next;
102 }
103 return 0;
104 }
105
106 template <typename T,typename T2>
begin()107 T2 Map<T,T2>::begin()
108 {
109 tmp = head;
110 if(tmp)
111 {
112 return (tmp->data2);
113 }
114 return 0;
115 }
116
117 template <typename T,typename T2>
show()118 void Map<T,T2>::show()
119 {
120 tmp = head;
121 while(tmp)
122 {
123 printf("%d-->%d\n",tmp->data,tmp->data2);
124 tmp = tmp->next;
125 }
126 }
127
128 template <typename T,typename T2>
size()129 int Map<T,T2>::size()
130 {
131 int count =0;
132 tmp = head;
133 while(tmp)
134 {
135 tmp = tmp->next;
136 count++;
137 }
138 return count;
139 }
140
141 template <typename T,typename T2>
insert(T data,T2 data2)142 void Map<T,T2>::insert(T data, T2 data2)
143 {
144 tail = new node(data, data2,tail, NULL);
145 if( tail->prev )
146 tail->prev->next = tail;
147
148 if( empty() )
149 {
150 head = tail;
151 tmp=head;
152 }
153 tmp = head;
154 size_of_list++;
155 }
156
157 template <typename T,typename T2>
erase(T d)158 bool Map<T,T2>::erase(T d)
159 {
160 bool found = false;
161 tmp = head;
162 node* prevnode = tmp;
163 node *tempnode;
164
165 while(tmp)
166 {
167 if((head == tail) && (head->data == d))
168 {
169 found = true;
170 tempnode = head;
171 head = tail = NULL;
172 delete tempnode;
173 break;
174 }
175 if((tmp ==head) && (tmp->data ==d))
176 {
177 found = true;
178 tempnode = tmp;
179 tmp = tmp->next;
180 tmp->prev = NULL;
181 head = tmp;
182 tempnode->next = NULL;
183 delete tempnode;
184 break;
185 }
186 if((tmp == tail) && (tmp->data ==d))
187 {
188 found = true;
189 tempnode = tmp;
190 prevnode->next = NULL;
191 tmp->prev = NULL;
192 tail = prevnode;
193 delete tempnode;
194 break;
195 }
196 if(tmp->data == d)
197 {
198 found = true;
199 prevnode->next = tmp->next;
200 tmp->next->prev = prevnode->next;
201 tempnode = tmp;
202 //tmp = tmp->next;
203 delete tempnode;
204 break;
205 }
206 prevnode = tmp;
207 tmp = tmp->next;
208 }
209 if(found)size_of_list--;
210 return found;
211 }
212
213 template <typename T,typename T2>
eraseall()214 bool Map<T,T2>::eraseall()
215 {
216 node *tempnode;
217 tmp = head;
218 while(head)
219 {
220 tempnode = head;
221 tempnode->next = NULL;
222 head = head->next;
223 delete tempnode;
224 }
225 tail = head = NULL;
226 return true;
227 }
228
229
230 template <typename T,typename T2>
isempty()231 bool Map<T,T2>::isempty()
232 {
233 if(!size_of_list) return true;
234 else return false;
235 }
236
237 #endif // _MAP_H_
238