1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
/*
* rtmap.templ.cpp
*
* Copyright (c) 2000-2004 by Florian Fischer (florianfischer@gmx.de)
* and Martin Trautmann (martintrautmann@gmx.de)
*
* This file may be distributed and/or modified under the terms of the
* GNU General Public License version 2 as published by the Free Software
* Foundation.
*
* This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
* WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
*
*/
///////////// Map template functions implementation ///////////
#ifndef __LRT_MAP_TEMPL__
#define __LRT_MAP_TEMPL__
#include "rtmap.h"
#include "rtlist.h"
#include "rtiterator.h"
namespace lrt {
template<class K, class V> Pair<K,V> Map<K,V>::noValue;
template<class K, class V> Map<K,V>::Map() : data(), compareFun(stdCompare)
{
}
template<class K, class V> Map<K,V>::Map(int(*compareFun)(const K&, const K&)) :
data(), compareFun(compareFun)
{
}
template<class K, class V> Map<K,V>::Map(const Map& m) : data(m.data), compareFun(m.compareFun)
{
}
template<class K, class V> const Map<K,V>& Map<K,V>::operator=(const Map<K,V>& m)
{
data = m.data;
compareFun = m.compareFun;
return *this;
}
template<class K, class V> bool Map<K,V>::isSet(const K& key) const
{
for(Iterator iter = begin(); iter.hasElement(); ++iter)
{
int cmp = compareFun(iter.get().getKey(), key);
if(cmp > 0) return false; // element cannot be contained in the map
if(cmp == 0) return true;
}
return false;
}
template<class K, class V> const V& Map<K,V>::get(const K& key) const
{
for(Iterator iter = begin(); iter.hasElement(); ++iter)
{
int cmp = compareFun(iter.get().getKey(), key);
if(cmp > 0) break; // element cannot be contained in the map
if(cmp == 0) return iter.get().getValue();
}
return noValue.getValue();
}
template<class K, class V> V& Map<K,V>::get(const K& key)
{
for(Iterator iter = begin(); iter.hasElement(); ++iter)
{
int cmp = compareFun(iter.get().getKey(), key);
if(cmp > 0) return data.insertBefore(iter, Pair<K,V>(key, V())).getValue();
if(cmp == 0) return iter.get().getValue();
}
return data.append(Pair<K,V>(key, V())).getValue();
}
// sorts the element into the map
template<class K, class V> Pair<K,V>& Map<K,V>::put(const K& key, const V& value)
{
for(Iterator iter = begin(); iter.hasElement(); ++iter)
{
int cmp = compareFun(iter.get().getKey(), key);
if(cmp > 0) return data.insertBefore(iter, Pair<K,V>(key, value));
if(cmp == 0) {
iter.get().value = value;
return iter.get();
}
}
return data.append(Pair<K,V>(key, value));
}
template<class K, class V> void Map<K,V>::putAll(const Map<K,V>& map)
{
for(Iterator iter = map.begin(); iter.hasElement(); ++iter)
put(iter.get().getKey(), iter.get().getValue());
}
template<class K, class V> bool Map<K,V>::remove(const K& key)
{
for(Iterator iter = begin(); iter.hasElement(); ++iter)
{
int cmp = compareFun(iter.get().getKey(), key);
if(cmp > 0) return false;
if(cmp == 0) { data.remove(iter); return true; }
}
return false;
}
template<class K, class V> void Map<K,V>::remove(Iterator& iter)
{
data.remove(iter);
}
template<class K, class V> void Map<K,V>::clear()
{
data.clear();
}
template<class K, class V> inline const V& Map<K,V>::operator[](const K& key) const
{
return get(key);
}
template<class K, class V> inline V& Map<K,V>::operator[](const K& key)
{
return get(key);
}
template<class K, class V> int Map<K,V>::length() const
{
return data.length();
}
// "constant" iterators (unmodifyable)
template<class K, class V> typename Map<K,V>::Iterator Map<K,V>::begin() const
{
return data.begin();
}
template<class K, class V> typename Map<K,V>::Iterator Map<K,V>::end() const
{
return data.end();
}
// modifyable iterators
template<class K, class V> typename Map<K,V>::Iterator Map<K,V>::begin()
{
return data.begin();
}
template<class K, class V> typename Map<K,V>::Iterator Map<K,V>::end()
{
return data.end();
}
} // namespace
#endif
|
