1 /*-------------------------------------------------------------------------- 2 Copyright (c) 2010, 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 { 39 T data; 40 T2 data2; 41 node* prev; 42 node* next; 43 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: 52 Map() : head( NULL ), tail ( NULL ),tmp(head),size_of_list(0) {} 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(); 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> 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> 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> 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> 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> 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> 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> 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> 214 bool Map<T,T2>::eraseall() 215 { 216 // Be careful while using this method 217 // it not only removes the node but FREES(not delete) the allocated 218 // memory. 219 node *tempnode; 220 tmp = head; 221 while(head) 222 { 223 tempnode = head; 224 head = head->next; 225 tempnode->next = NULL; 226 if(tempnode->data) 227 free(tempnode->data); 228 if(tempnode->data2) 229 free(tempnode->data2); 230 delete tempnode; 231 } 232 tail = head = NULL; 233 return true; 234 } 235 236 237 template <typename T,typename T2> 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
