Home | History | Annotate | Download | only in inc 
      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;
     42         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:
     51     Map() : head( NULL ), tail ( NULL ),tmp(head),size_of_list(0) {}
     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();
     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>
     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>
     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>
    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>
    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>
    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>
    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>
    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>
    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>
    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