abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Data Structures | Public Member Functions | Private Member Functions | Private Attributes
Minisat::Map< K, D, H, E > Class Template Reference

#include <Map.h>

Data Structures

struct  Pair
 

Public Member Functions

 Map ()
 
 Map (const H &h, const E &e)
 
 ~Map ()
 
const D & operator[] (const K &k) const
 
D & operator[] (const K &k)
 
void insert (const K &k, const D &d)
 
bool peek (const K &k, D &d) const
 
bool has (const K &k) const
 
void remove (const K &k)
 
void clear ()
 
int elems () const
 
int bucket_count () const
 
void moveTo (Map &other)
 
const vec< Pair > & bucket (int i) const
 

Private Member Functions

Map< K, D, H, E > & operator= (Map< K, D, H, E > &other)
 
 Map (Map< K, D, H, E > &other)
 
bool checkCap (int new_size) const
 
int32_t index (const K &k) const
 
void _insert (const K &k, const D &d)
 
void rehash ()
 

Private Attributes

H hash
 
E equals
 
vec< Pair > * table
 
int cap
 
int size
 

Detailed Description

template<class K, class D, class H = Hash<K>, class E = Equal<K>>
class Minisat::Map< K, D, H, E >

Definition at line 56 of file Map.h.

Constructor & Destructor Documentation

template<class K, class D, class H = Hash<K>, class E = Equal<K>>
Minisat::Map< K, D, H, E >::Map ( Map< K, D, H, E > &  other)
inlineprivate

Definition at line 70 of file Map.h.

70 { assert(0); }
assert
#define assert(ex)
Definition: util_old.h:213
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
Minisat::Map< K, D, H, E >::Map ( )
inline

Definition at line 102 of file Map.h.

102 : table(NULL), cap(0), size(0) {}
Minisat::Map::cap
int cap
Definition: Map.h:65
Minisat::Map::size
int size
Definition: Map.h:66
Minisat::Map::table
vec< Pair > * table
Definition: Map.h:64
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
Minisat::Map< K, D, H, E >::Map ( const H &  h,
const E &  e 
)
inline

Definition at line 103 of file Map.h.

103 : hash(h), equals(e), table(NULL), cap(0), size(0){}
Minisat::Map::cap
int cap
Definition: Map.h:65
Minisat::Map::hash
H hash
Definition: Map.h:61
Minisat::Map::equals
E equals
Definition: Map.h:62
Minisat::Map::size
int size
Definition: Map.h:66
Minisat::Map::table
vec< Pair > * table
Definition: Map.h:64
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
Minisat::Map< K, D, H, E >::~Map ( )
inline

Definition at line 104 of file Map.h.

104 { delete [] table; }
Minisat::Map::table
vec< Pair > * table
Definition: Map.h:64

Member Function Documentation

template<class K, class D, class H = Hash<K>, class E = Equal<K>>
void Minisat::Map< K, D, H, E >::_insert ( const K &  k,
const D &  d 
)
inlineprivate

Definition at line 75 of file Map.h.

75  {
76  vec<Pair>& ps = table[index(k)];
77  ps.push(); ps.last().key = k; ps.last().data = d; }
Minisat::Map::table
vec< Pair > * table
Definition: Map.h:64
Minisat::Map::index
int32_t index(const K &k) const
Definition: Map.h:74
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
const vec<Pair>& Minisat::Map< K, D, H, E >::bucket ( int  i) const
inline

Definition at line 187 of file Map.h.

187 { return table[i]; }
Minisat::Map::table
vec< Pair > * table
Definition: Map.h:64
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
int Minisat::Map< K, D, H, E >::bucket_count ( ) const
inline

Definition at line 172 of file Map.h.

172 { return cap; }
Minisat::Map::cap
int cap
Definition: Map.h:65
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
bool Minisat::Map< K, D, H, E >::checkCap ( int  new_size) const
inlineprivate

Definition at line 72 of file Map.h.

72 { return new_size > cap; }
Minisat::Map::cap
int cap
Definition: Map.h:65
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
void Minisat::Map< K, D, H, E >::clear ( )
inline

Definition at line 165 of file Map.h.

165  {
166  cap = size = 0;
167  delete [] table;
168  table = NULL;
169  }
Minisat::Map::cap
int cap
Definition: Map.h:65
Minisat::Map::size
int size
Definition: Map.h:66
Minisat::Map::table
vec< Pair > * table
Definition: Map.h:64
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
int Minisat::Map< K, D, H, E >::elems ( ) const
inline

Definition at line 171 of file Map.h.

171 { return size; }
Minisat::Map::size
int size
Definition: Map.h:66
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
bool Minisat::Map< K, D, H, E >::has ( const K &  k) const
inline

Definition at line 144 of file Map.h.

144  {
145  if (size == 0) return false;
146  const vec<Pair>& ps = table[index(k)];
147  for (int i = 0; i < ps.size(); i++)
148  if (equals(ps[i].key, k))
149  return true;
150  return false;
151  }
Minisat::Map::equals
E equals
Definition: Map.h:62
Minisat::Map::size
int size
Definition: Map.h:66
Minisat::Map::table
vec< Pair > * table
Definition: Map.h:64
Minisat::Map::index
int32_t index(const K &k) const
Definition: Map.h:74
key
enum keys key
Definition: misc/espresso/main.h:25
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
int32_t Minisat::Map< K, D, H, E >::index ( const K &  k) const
inlineprivate

Definition at line 74 of file Map.h.

74 { return hash(k) % cap; }
Minisat::Map::cap
int cap
Definition: Map.h:65
Minisat::Map::hash
H hash
Definition: Map.h:61
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
void Minisat::Map< K, D, H, E >::insert ( const K &  k,
const D &  d 
)
inline

Definition at line 133 of file Map.h.

133 { if (checkCap(size+1)) rehash(); _insert(k, d); size++; }
Minisat::Map::size
int size
Definition: Map.h:66
Minisat::Map::checkCap
bool checkCap(int new_size) const
Definition: Map.h:72
Minisat::Map::rehash
void rehash()
Definition: Map.h:79
Minisat::Map::_insert
void _insert(const K &k, const D &d)
Definition: Map.h:75
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
void Minisat::Map< K, D, H, E >::moveTo ( Map< K, D, H, E > &  other)
inline

Definition at line 175 of file Map.h.

175  {
176  delete [] other.table;
177 
178  other.table = table;
179  other.cap = cap;
180  other.size = size;
181 
182  table = NULL;
183  size = cap = 0;
184  }
Minisat::Map::cap
int cap
Definition: Map.h:65
Minisat::Map::size
int size
Definition: Map.h:66
Minisat::Map::table
vec< Pair > * table
Definition: Map.h:64
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
Map<K,D,H,E>& Minisat::Map< K, D, H, E >::operator= ( Map< K, D, H, E > &  other)
inlineprivate

Definition at line 69 of file Map.h.

69 { assert(0); }
assert
#define assert(ex)
Definition: util_old.h:213
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
const D& Minisat::Map< K, D, H, E >::operator[] ( const K &  k) const
inline

Definition at line 107 of file Map.h.

108  {
109  assert(size != 0);
110  const D* res = NULL;
111  const vec<Pair>& ps = table[index(k)];
112  for (int i = 0; i < ps.size(); i++)
113  if (equals(ps[i].key, k))
114  res = &ps[i].data;
115  assert(res != NULL);
116  return *res;
117  }
Minisat::Map::equals
E equals
Definition: Map.h:62
Minisat::Map::size
int size
Definition: Map.h:66
Minisat::Map::table
vec< Pair > * table
Definition: Map.h:64
Minisat::Map::index
int32_t index(const K &k) const
Definition: Map.h:74
key
enum keys key
Definition: misc/espresso/main.h:25
assert
#define assert(ex)
Definition: util_old.h:213
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
D& Minisat::Map< K, D, H, E >::operator[] ( const K &  k)
inline

Definition at line 120 of file Map.h.

121  {
122  assert(size != 0);
123  D* res = NULL;
124  vec<Pair>& ps = table[index(k)];
125  for (int i = 0; i < ps.size(); i++)
126  if (equals(ps[i].key, k))
127  res = &ps[i].data;
128  assert(res != NULL);
129  return *res;
130  }
Minisat::Map::equals
E equals
Definition: Map.h:62
Minisat::Map::size
int size
Definition: Map.h:66
Minisat::Map::table
vec< Pair > * table
Definition: Map.h:64
Minisat::Map::index
int32_t index(const K &k) const
Definition: Map.h:74
key
enum keys key
Definition: misc/espresso/main.h:25
assert
#define assert(ex)
Definition: util_old.h:213
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
bool Minisat::Map< K, D, H, E >::peek ( const K &  k,
D &  d 
) const
inline

Definition at line 134 of file Map.h.

134  {
135  if (size == 0) return false;
136  const vec<Pair>& ps = table[index(k)];
137  for (int i = 0; i < ps.size(); i++)
138  if (equals(ps[i].key, k)){
139  d = ps[i].data;
140  return true; }
141  return false;
142  }
Minisat::Map::equals
E equals
Definition: Map.h:62
Minisat::Map::size
int size
Definition: Map.h:66
Minisat::Map::table
vec< Pair > * table
Definition: Map.h:64
Minisat::Map::index
int32_t index(const K &k) const
Definition: Map.h:74
key
enum keys key
Definition: misc/espresso/main.h:25
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
void Minisat::Map< K, D, H, E >::rehash ( )
inlineprivate

Definition at line 79 of file Map.h.

79  {
80  const vec<Pair>* old = table;
81 
82  int old_cap = cap;
83  int newsize = primes[0];
84  for (int i = 1; newsize <= cap && i < nprimes; i++)
85  newsize = primes[i];
86 
87  table = new vec<Pair>[newsize];
88  cap = newsize;
89 
90  for (int i = 0; i < old_cap; i++){
91  for (int j = 0; j < old[i].size(); j++){
92  _insert(old[i][j].key, old[i][j].data); }}
93 
94  delete [] old;
95 
96  // printf(" --- rehashing, old-cap=%d, new-cap=%d\n", cap, newsize);
97  }
Minisat::Map::cap
int cap
Definition: Map.h:65
Minisat::Map::table
vec< Pair > * table
Definition: Map.h:64
Minisat::Map::_insert
void _insert(const K &k, const D &d)
Definition: Map.h:75
key
enum keys key
Definition: misc/espresso/main.h:25
Minisat::nprimes
static const int nprimes
Definition: Map.h:48
Minisat::primes
static const int primes[nprimes]
Definition: Map.h:49
template<class K, class D, class H = Hash<K>, class E = Equal<K>>
void Minisat::Map< K, D, H, E >::remove ( const K &  k)
inline

Definition at line 154 of file Map.h.

154  {
155  assert(table != NULL);
156  vec<Pair>& ps = table[index(k)];
157  int j = 0;
158  for (; j < ps.size() && !equals(ps[j].key, k); j++);
159  assert(j < ps.size());
160  ps[j] = ps.last();
161  ps.pop();
162  size--;
163  }
Minisat::Map::equals
E equals
Definition: Map.h:62
Minisat::Map::size
int size
Definition: Map.h:66
Minisat::Map::table
vec< Pair > * table
Definition: Map.h:64
Minisat::Map::index
int32_t index(const K &k) const
Definition: Map.h:74
key
enum keys key
Definition: misc/espresso/main.h:25
assert
#define assert(ex)
Definition: util_old.h:213

Field Documentation

template<class K, class D, class H = Hash<K>, class E = Equal<K>>
int Minisat::Map< K, D, H, E >::cap
private

Definition at line 65 of file Map.h.

template<class K, class D, class H = Hash<K>, class E = Equal<K>>
E Minisat::Map< K, D, H, E >::equals
private

Definition at line 62 of file Map.h.

template<class K, class D, class H = Hash<K>, class E = Equal<K>>
H Minisat::Map< K, D, H, E >::hash
private

Definition at line 61 of file Map.h.

template<class K, class D, class H = Hash<K>, class E = Equal<K>>
int Minisat::Map< K, D, H, E >::size
private

Definition at line 66 of file Map.h.

template<class K, class D, class H = Hash<K>, class E = Equal<K>>
vec<Pair>* Minisat::Map< K, D, H, E >::table
private

Definition at line 64 of file Map.h.

The documentation for this class was generated from the following file: