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