Elm  2
ELM is a library providing generic data structures, OS-independent interface, plugins and XML.
ListMap.h
1 /*
2  * ListSet class interface
3  *
4  * This file is part of OTAWA
5  * Copyright (c) 2017, IRIT UPS.
6  *
7  * ELM 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  * ELM 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 ELM; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21 #ifndef ELM_DATA_LISTMAP_H_
22 #define ELM_DATA_LISTMAP_H_
23 
24 #include "SortedList.h"
25 
26 namespace elm {
27 
28 template <class K, class T, class C = Comparator<K>, class E = Equiv<T>, class A = DefaultAlloc >
29 class ListMap: private SortedList<Pair<K, T>, AssocComparator<K, T, C>, A>, public E {
31 public:
33  typedef typename base_t::Iter PairIter;
34 
35  inline ListMap() { }
36  inline ListMap(const self_t& l): base_t(l) { }
37  inline E& equivalence() { return *this; }
38 
39  class PreIter: public elm::PreIter<PreIter, T> {
40  friend class ListMap;
41  public:
42  inline PreIter() { }
43  inline PreIter(const self_t& l): i(l) { }
44  inline bool ended(void) const { return i.ended(); }
45  inline void next(void) { i.next(); }
46  inline bool equals(const PreIter& ii) const { return i.equals(ii.i); }
47  protected:
49  };
50 
51  class Iter: public PreIter, public ConstPreIter<Iter, T> {
52  public:
54  inline const T& item() const { return (*PreIter::i).snd; }
55  };
56 
57  class MutIter: public PreIter, public MutPreIter<MutIter, T> {
58  public:
60  inline T& item() const { return const_cast<Pair<K, T>&>(*PreIter::i).snd; }
61  };
62 
63  class KeyIter: public PreIterator<KeyIter, K> {
64  public:
65  inline KeyIter(void) { }
66  inline KeyIter(const ListMap<K, T>& l): i(l) { }
67  inline bool ended(void) const { return i.ended(); }
68  inline const K& item(void) const { return (*i).fst; }
69  inline void next(void) { i.next(); }
70  inline bool equals(const KeyIter& ii) { return i.equals(ii.i); }
71  private:
72  PairIter i;
73  };
74 
75  // Collection concept
76  inline Iter begin() const { return Iter(*this); }
77  inline Iter end() const { return Iter(); }
78  inline int count(void) const { return base_t::count(); }
79  inline bool contains(const T& v) const
80  { for(const auto& i: *this) if(E::isEqual(i, v)) return true; return false; }
81  template <class CC> inline bool containsAll(const CC& c) const
82  { for(const auto i: c) if(!contains(i)) return false; return true; }
83  inline bool isEmpty(void) const { return base_t::isEmpty(); }
84  inline operator bool(void) const { return !isEmpty(); }
85  inline Iter items(void) const { return begin(); }
86  inline Iter operator*(void) const { return begin(); }
87  inline operator Iter(void) const { return begin(); }
88  inline bool equals(const self_t& m) const { return base_t::equals(m); }
89  inline bool operator==(const self_t& m) const { return equals(m); }
90  inline bool operator!=(const self_t& m) const { return !equals(m); }
91  inline bool contains(const self_t& m) const { return base_t::contains(m); }
92  inline bool operator<=(const self_t& m) const { return m.contains(*this); }
93  inline bool operator<(const self_t& m) const { return m.contains(*this) && !equals(m); }
94  inline bool operator>=(const self_t& m) const { return contains(m); }
95  inline bool operator>(const self_t& m) const { return contains(m) && !equals(m); }
96 
97  // Map concept
98  inline Option<T> get(const K &k) const
99  { PairIter i = lookup(k); if(i()) return some((*i).snd); else return none; }
100  inline const T &get(const K &k, const T &d) const
101  { PairIter i = lookup(k); if(i()) return (*i).snd; else return d; }
102  inline bool hasKey(const K &k) const { return lookup(k)(); }
103 
104  inline Iterable<KeyIter> keys() const { return subiter(KeyIter(*this), KeyIter()); }
105  inline Iterable<PairIter> pairs() const { return subiter(PairIter(*this), PairIter()); }
106 
107  // MutableMap concept
108  inline MutIter begin() { return MutIter(*this); }
109  inline MutIter end() { return MutIter(); }
110  void put(const K& k, const T& v) {
111  PairIter i = lookup(k);
112  if(i())
113  base_t::set(i, pair(k, v));
114  else
115  base_t::add(pair(k, v));
116  }
117  inline void remove(const MutIter& i) { base_t::remove(i.i); }
118  inline void remove(const K& k)
119  { PairIter i = lookup(k); if(i()) base_t::remove(*i); }
120 
121 private:
122  PairIter lookup(const K& k) const {
123  for(PairIter i = base_t::begin(); i(); i++) {
124  int cmp = base_t::comparator().compareKey(k, (*i).fst);
125  if(cmp == 0)
126  return i;
127  else if(cmp < 0)
128  break;
129  }
130  return base_t::end();
131  }
132 };
133 
134 template <class K, class T, class M>
135 inline bool operator<=(const T& v, const ListMap<K, T, M>& m) { return m.contains(v); }
136 
137 } // elm
138 
139 #endif /* ELM_DATA_LISTMAP_H_ */
Definition: compare.h:64
Definition: iter.h:84
Definition: util.h:220
Definition: ListMap.h:51
const T & item() const
Definition: ListMap.h:54
Definition: ListMap.h:63
void next(void)
Definition: ListMap.h:69
bool equals(const KeyIter &ii)
Definition: ListMap.h:70
KeyIter(void)
Definition: ListMap.h:65
KeyIter(const ListMap< K, T > &l)
Definition: ListMap.h:66
const K & item(void) const
Definition: ListMap.h:68
bool ended(void) const
Definition: ListMap.h:67
Definition: ListMap.h:57
T & item() const
Definition: ListMap.h:60
Definition: ListMap.h:39
PreIter(const self_t &l)
Definition: ListMap.h:43
bool equals(const PreIter &ii) const
Definition: ListMap.h:46
PairIter i
Definition: ListMap.h:48
void next(void)
Definition: ListMap.h:45
PreIter()
Definition: ListMap.h:42
bool ended(void) const
Definition: ListMap.h:44
Definition: ListMap.h:29
bool contains(const self_t &m) const
Definition: ListMap.h:91
void remove(const MutIter &i)
Definition: ListMap.h:117
bool equals(const self_t &m) const
Definition: ListMap.h:88
Iterable< PairIter > pairs() const
Definition: ListMap.h:105
Iterable< KeyIter > keys() const
Definition: ListMap.h:104
ListMap< K, T, C, E, A > self_t
Definition: ListMap.h:32
MutIter begin()
Definition: ListMap.h:108
void remove(const K &k)
Definition: ListMap.h:118
bool hasKey(const K &k) const
Definition: ListMap.h:102
MutIter end()
Definition: ListMap.h:109
bool operator!=(const self_t &m) const
Definition: ListMap.h:90
Iter begin() const
Definition: ListMap.h:76
E & equivalence()
Definition: ListMap.h:37
int count(void) const
Definition: ListMap.h:78
bool contains(const T &v) const
Definition: ListMap.h:79
ListMap()
Definition: ListMap.h:35
bool operator>(const self_t &m) const
Definition: ListMap.h:95
bool operator>=(const self_t &m) const
Definition: ListMap.h:94
base_t::Iter PairIter
Definition: ListMap.h:33
Option< T > get(const K &k) const
Definition: ListMap.h:98
bool operator==(const self_t &m) const
Definition: ListMap.h:89
void put(const K &k, const T &v)
Definition: ListMap.h:110
Iter operator*(void) const
Definition: ListMap.h:86
bool containsAll(const CC &c) const
Definition: ListMap.h:81
bool operator<=(const self_t &m) const
Definition: ListMap.h:92
Iter end() const
Definition: ListMap.h:77
Iter items(void) const
Definition: ListMap.h:85
bool isEmpty(void) const
Definition: ListMap.h:83
const T & get(const K &k, const T &d) const
Definition: ListMap.h:100
ListMap(const self_t &l)
Definition: ListMap.h:36
bool operator<(const self_t &m) const
Definition: ListMap.h:93
void next(void)
Definition: List.h:72
bool ended(void) const
Definition: List.h:70
bool equals(const Iter &i) const
Definition: List.h:73
Definition: iter.h:92
Definition: Option.h:35
Definition: Pair.h:33
T2 snd
Definition: Pair.h:36
Definition: iter.h:69
Definition: iter.h:28
Definition: SortedList.h:60
Definition: SortedList.h:34
bool contains(const T &item) const
Definition: SortedList.h:53
Iter end(void) const
Definition: SortedList.h:69
C & comparator()
Definition: SortedList.h:43
bool equals(const SortedList< T > &l) const
Definition: SortedList.h:71
Iter begin(void) const
Definition: SortedList.h:68
int count(void) const
Definition: SortedList.h:51
void add(const T &value)
Definition: SortedList.h:85
void remove(const T &item)
Definition: SortedList.h:96
void set(Iter i, const T &val)
Definition: SortedList.h:125
bool isEmpty(void) const
Definition: SortedList.h:57
Definition: adapter.h:26
Pair< T1, T2 > pair(const T1 &v1, const T2 &v2)
Definition: Pair.h:63
bool operator<=(const T &v, const FragTable< T, E, A > &t)
Definition: FragTable.h:158
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