1/*--------------------------------------------------------------------------
2Copyright (c) 2010, Code Aurora Forum. All rights reserved.
3
4Redistribution and use in source and binary forms, with or without
5modification, 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
16THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19NON-INFRINGEMENT ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
20CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
21EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
22PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
23OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
24WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
25OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
26ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27--------------------------------------------------------------------------*/
28#ifndef _MAP_H_
29#define _MAP_H_
30
31#include <stdio.h>
32using namespace std;
33
34template <typename T,typename T2>
35class 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;
51public:
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
76template <typename T,typename T2>
77T2 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
91template <typename T,typename T2>
92T 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
106template <typename T,typename T2>
107T2 Map<T,T2>::begin()
108{
109    tmp = head;
110    if(tmp)
111    {
112        return (tmp->data2);
113    }
114    return 0;
115}
116
117template <typename T,typename T2>
118void 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
128template <typename T,typename T2>
129int 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
141template <typename T,typename T2>
142void 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
157template <typename T,typename T2>
158bool 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
213template <typename T,typename T2>
214bool 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
230template <typename T,typename T2>
231bool Map<T,T2>::isempty()
232{
233    if(!size_of_list) return true;
234    else return false;
235}
236
237#endif // _MAP_H_
238