Elm  2
ELM is a library providing generic data structures, OS-independent interface, plugins and XML.
Map.h
1 /*
2  * avl::Map class interface
3  *
4  * This file is part of OTAWA
5  * Copyright (c) 2011, IRIT UPS.
6  *
7  * OTAWA is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * OTAWA is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with OTAWA; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21 #ifndef ELM_AVL_MAP_CPP_
22 #define ELM_AVL_MAP_CPP_
23 
24 #include <elm/delegate.h>
25 #include <elm/util/Option.h>
26 #include <elm/avl/GenTree.h>
27 #include <elm/data/util.h>
28 
29 namespace elm { namespace avl {
30 
31 // Map class
32 template <class K, class T, class C = Comparator<K>, class E = Equiv<T>, class A = DefaultAlloc >
33 class Map: public E {
36 
37 public:
39 
40  inline const C& comparator() const { return tree.comparator(); }
41  inline C& comparator() { return tree.comparator(); }
42  inline const C& allocatr() const { return tree.allocator(); }
43  inline C& allocator() { return tree.allocator(); }
44  inline const E& equivalence() const { return *this; }
45  inline E& equivalence() { return *this; }
46 
47  // Collection concept
48  inline int count(void) const { return tree.count(); }
49  inline bool contains(const T& x) const
50  { for(const auto y: *this) if(!E::isEqual(x, y)) return false; return true; }
51  template <class CC> bool containsAll(const CC& c) const
52  { for(const auto x: c) if(!contains(x)) return false; return true; }
53  inline bool isEmpty(void) const { return tree.isEmpty(); }
54  inline operator bool() const { return !isEmpty(); }
55 
56  class Iter: public PreIterator<Iter, T> {
57  public:
58  inline Iter() { }
59  inline Iter(const self_t& t): i(t.tree) { }
60  inline bool ended() const { return i.ended(); }
61  inline const T& item() const { return i.item().snd; }
62  inline void next() { i.next(); }
63  inline bool equals(const Iter& ii) const { return i.equals(ii.i); }
64  private:
65  typename tree_t::Iter i;
66  };
67  inline Iter begin() const { return Iter(*this); }
68  inline Iter end() const { return Iter(); }
69 
70  inline bool equals(const Map<K, T, C>& map) const { return tree.equals(map.tree); }
71  inline bool operator==(const Map<K, T, C>& map) const { return equals(map); }
72  inline bool operator!=(const Map<K, T, C>& map) const { return !equals(map); }
73 
74  // Map concept
75  inline Option<T> get(const K& key) const
76  { const pair_t *p = tree.get(key); if(!p) return none; else return some(p->snd); }
77  inline const T& get(const K& key, const T& def) const
78  { const pair_t *p = tree.get(key); if(!p) return def; else return p->snd; }
79  inline bool hasKey(const K& key) const
80  { const pair_t *p = tree.get(key); return p; }
81  inline const T& operator[](const K& k) const
82  { const pair_t *r = tree.get(k); if(r == nullptr) throw KeyException(); return r->snd; }
83 
84  class KeyIter: public PreIterator<KeyIter, K> {
85  public:
86  inline KeyIter() { }
87  inline KeyIter(const self_t& map): it(map.tree) { }
88  inline bool ended(void) const { return it.ended(); }
89  inline void next(void) { it.next(); }
90  inline const K& item(void) const { return it.item().fst; }
91  inline bool equals(const KeyIter& i) const { return it.equals(i.it); }
92  private:
93  typename tree_t::Iter it;
94  };
95  inline Iterable<KeyIter> keys() const { return subiter(KeyIter(*this), KeyIter()); }
96 
97  class PairIter: public tree_t::Iter {
98  public:
99  inline PairIter() { }
100  inline PairIter(const self_t& map): tree_t::Iter(map.tree) { }
101  };
102  inline Iterable<PairIter> pairs() const { return subiter(PairIter(*this), PairIter()); }
103 
104  // MutableMap concept
105  inline void put(const K &key, const T &value) { tree.set(pair_t(key, value)); }
106  inline void remove(const K &key) { tree.removeByKey(key); }
107  inline void remove(const Iter &i) { tree.remove(i.item().fst); }
108 
110  inline void clear(void) { tree.clear(); }
111  inline void copy(const Map<K, T, C>& map) { tree.copy(map.tree); }
112  inline Map<K, T, C>& operator=(const Map<K, T, C>& map) { copy(map); return *this; }
113 
114 private:
115  tree_t tree;
116 };
117 
118 } } // elm::avl
119 
120 #endif /* ELM_AVL_AVLMAP_CPP_ */
static Equiv< T > def
Definition: equiv.h:37
Definition: util.h:220
Definition: delegate.h:87
Definition: Option.h:35
Definition: Pair.h:33
T2 snd
Definition: Pair.h:36
Definition: iter.h:28
T t
Definition: iter.h:30
Definition: GenTree.h:165
void next(void)
Definition: GenTree.h:171
const T & item(void) const
Definition: GenTree.h:179
bool ended(void) const
Definition: GenTree.h:170
bool equals(const Iter &i) const
Definition: GenTree.h:180
Definition: GenTree.h:97
const C & comparator() const
Definition: GenTree.h:136
const A & allocator() const
Definition: GenTree.h:138
int count(void) const
Definition: GenTree.h:157
void remove(const T &x)
Definition: GenTree.h:232
void set(const T &item)
Definition: GenTree.h:145
bool equals(const GenTree< T, K, C > &tree) const
Definition: GenTree.h:195
T * get(const typename K::key_t &key)
Definition: GenTree.h:141
void clear(void)
Definition: GenTree.h:206
bool isEmpty(void) const
Definition: GenTree.h:162
void copy(const GenTree< T, K, C > &tree)
Definition: GenTree.h:242
void removeByKey(const typename K::key_t &item)
Definition: GenTree.h:148
Definition: Map.h:56
void next()
Definition: Map.h:62
Iter(const self_t &t)
Definition: Map.h:59
Iter()
Definition: Map.h:58
bool ended() const
Definition: Map.h:60
bool equals(const Iter &ii) const
Definition: Map.h:63
const T & item() const
Definition: Map.h:61
Definition: Map.h:84
bool equals(const KeyIter &i) const
Definition: Map.h:91
KeyIter()
Definition: Map.h:86
void next(void)
Definition: Map.h:89
KeyIter(const self_t &map)
Definition: Map.h:87
const K & item(void) const
Definition: Map.h:90
bool ended(void) const
Definition: Map.h:88
Definition: Map.h:97
PairIter()
Definition: Map.h:99
PairIter(const self_t &map)
Definition: Map.h:100
Definition: Map.h:33
const T & get(const K &key, const T &def) const
Definition: Map.h:77
const C & comparator() const
Definition: Map.h:40
Map< K, T, C, E, A > self_t
Definition: Map.h:38
Iterable< PairIter > pairs() const
Definition: Map.h:102
Iterable< KeyIter > keys() const
Definition: Map.h:95
void remove(const K &key)
Definition: Map.h:106
Option< T > get(const K &key) const
Definition: Map.h:75
const T & operator[](const K &k) const
Definition: Map.h:81
C & comparator()
Definition: Map.h:41
const C & allocatr() const
Definition: Map.h:42
Iter begin() const
Definition: Map.h:67
E & equivalence()
Definition: Map.h:45
int count(void) const
Definition: Map.h:48
const E & equivalence() const
Definition: Map.h:44
void put(const K &key, const T &value)
Definition: Map.h:105
Map< K, T, C > & operator=(const Map< K, T, C > &map)
Definition: Map.h:112
bool operator!=(const Map< K, T, C > &map) const
Definition: Map.h:72
bool hasKey(const K &key) const
Definition: Map.h:79
bool contains(const T &x) const
Definition: Map.h:49
bool operator==(const Map< K, T, C > &map) const
Definition: Map.h:71
void copy(const Map< K, T, C > &map)
Definition: Map.h:111
bool containsAll(const CC &c) const
Definition: Map.h:51
void remove(const Iter &i)
Definition: Map.h:107
Iter end() const
Definition: Map.h:68
void clear(void)
Definition: Map.h:110
bool isEmpty(void) const
Definition: Map.h:53
bool equals(const Map< K, T, C > &map) const
Definition: Map.h:70
C & allocator()
Definition: Map.h:43
var_t embed_t
Definition: type_info.h:66
void map(const C &c, const F &f, D &d)
Definition: util.h:89
Printable< T, M > p(const T &data, const M &man)
Definition: Output.h:302
Definition: adapter.h:26
Iterable< I > subiter(const I &b, const I &e)
Definition: util.h:231
const OptionalNone none
Definition: util_Option.cpp:154
Option< T > some(const T &val)
Definition: Option.h:81