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; 41 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: 50 Map() : head( NULL ), tail ( NULL ),tmp(head),size_of_list(0) {} 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(); 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> 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> 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> 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> 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> 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> 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> 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> 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> 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
