MADNESS 0.10.1
key.h
Go to the documentation of this file.
1/*
2 This file is part of MADNESS.
3
4 Copyright (C) 2007,2010 Oak Ridge National Laboratory
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19
20 For more information please contact:
21
22 Robert J. Harrison
23 Oak Ridge National Laboratory
24 One Bethel Valley Road
25 P.O. Box 2008, MS-6367
26
27 email: harrisonrj@ornl.gov
28 tel: 865-241-3937
29 fax: 865-572-0680
30*/
31
32#ifndef MADNESS_MRA_KEY_H__INCLUDED
33#define MADNESS_MRA_KEY_H__INCLUDED
34
35/// \file key.h
36/// \brief Multidimension Key for MRA tree and associated iterators
37
38#include <vector>
39#include <madness/mra/power.h>
43#include <stdint.h>
44
45namespace madness {
46
47 // // this has problems when nproc is a large-ish power of 2 such as 256
48 // // and leads to bad data distribution.
49 // static inline unsigned int sdbm(int n, const unsigned char* c, unsigned int sum=0) {
50 // for (int i=0; i<n; ++i) sum = c[i] + (sum << 6) + (sum << 16) - sum;
51 // return sum;
52 // }
53
54 typedef int64_t Translation;
55 typedef int Level;
56
57 template<std::size_t NDIM>
58 class KeyChildIterator;
59
60 /// Key is the index for a node of the 2^NDIM-tree
61
62 /// See KeyChildIterator for facile generation of children,
63 /// and foreach_child(parent,op) for facile applicaiton of operators
64 /// to child keys.
65 template<std::size_t NDIM>
66 class Key {
67 public:
68// static const typename Vector<Translation,NDIM>::size_type static_size = Vector<Translation,NDIM>::static_size;
69 static const std::size_t static_size = NDIM;
70
71 private:
72 friend class KeyChildIterator<NDIM> ;
76
77
78 public:
79
80 /// Default constructor makes an \em uninitialized key
81 Key() {}
82
83 /// Constructor with given n, l
85 {
86 rehash();
87 }
88
89 /// Constructor with given n and l=0
90 Key(int n) : n(n), l(0)
91 {
92 rehash();
93 }
94
95 // /// easy constructor ... UGH !!!!!!!!!!!!!!!!!!!!!!
96 // Key(const int n, const int l0, const int l1, const int l2) : n(n) {
97 // MADNESS_ASSERT(NDIM==3);
98 // l=Vector<Translation, NDIM>(0);
99 // l[0]=l0; l[1]=l1; l[2]=l2;
100 // rehash();
101 // }
102
103 /// Returns an invalid key
105 return Key<NDIM> (-1);
106 }
107
108 /// Checks if a key is invalid
109 bool is_invalid() const {
110 return n == -1;
111 }
112
113 /// Checks if a key is valid
114 bool is_valid() const {
115 return n != -1;
116 }
117
118 /// Equality test
119 bool operator==(const Key& other) const {
120 if (hashval != other.hashval) return false;
121 if (n != other.n) return false;
122 for (unsigned int i=0; i<NDIM; i++)
123 if (l[i] != other.l[i]) return false;
124 return true; // everything is equal
125 }
126
127 bool operator!=(const Key& other) const {
128 return !(*this == other);
129 }
130
131 /// Comparison operator less than to enable storage in STL map
132 bool operator<(const Key& other) const {
133 if (hashval < other.hashval) return true;
134 if (hashval > other.hashval) return false;
135
136 if (n < other.n) return true;
137 if (n > other.n) return false;
138
139 for (unsigned int i=0; i<NDIM; i++) {
140 if (l[i] < other.l[i]) return true;
141 if (l[i] > other.l[i]) return false;
142 }
143
144 return false; // everything is equal
145 }
146
147 inline hashT
148 hash() const {
149 return hashval;
150 }
151
152 // template<typename Archive>
153 // inline void
154 // serialize(Archive& ar) {
155 // ar & archive::wrap((unsigned char*) this, sizeof(*this));
156 // }
157
158 Level
159 level() const {
160 return n;
161 }
162
164 translation() const {
165 return l;
166 }
167
168 uint64_t
169 distsq() const {
170 uint64_t dist = 0;
171 for (std::size_t d = 0; d < NDIM; ++d) {
172 dist += l[d] * l[d];
173 }
174 return dist;
175 }
176
177 /// Returns the key of the parent
178
179 /// Default is the immediate parent (generation=1). To get
180 /// the grandparent use generation=2, and similarly for
181 /// great-grandparents.
182 ///
183 /// !! If there is no such parent it quietly returns the
184 /// closest match (which may be self if this is the top of the
185 /// tree).
186 Key
187 parent(int generation = 1) const {
189 if (generation > n)
190 generation = n;
191 for (std::size_t i = 0; i < NDIM; ++i)
192 pl[i] = l[i] >> generation;
193 return Key(n - generation, pl);
194 }
195
196
197 bool
198 is_child_of(const Key& key) const {
199 if (this->n < key.n) {
200 return false; // I can't be child of something lower on the tree
201 }
202 else if (this->n == key.n) {
203 return (*this == key); // I am child of myself
204 }
205 else {
206 Level dn = this->n - key.n;
207 Key mama = this->parent(dn);
208 return (mama == key);
209 }
210 }
211
212
213 bool
214 is_parent_of(const Key& key) const {
215 return (key.is_child_of(*this));
216 }
217
218 /// Assuming keys are at the same level, returns true if displaced by no more than 1 in any direction
219
220 /// Assumes key and this are at the same level
221 bool
222 is_neighbor_of(const Key& key, const std::vector<bool>& bperiodic) const {
223 Translation dist = 0;
224 Translation TWON1 = (Translation(1)<<n) - 1;
225 for (std::size_t i=0; i<NDIM; ++i)
226 {
227 Translation ll = std::abs(l[i] - key.l[i]);
228 if (bperiodic[i] && ll==TWON1) ll=1;
229 dist = std::max(dist, ll);
230 }
231 return (dist <= 1);
232 }
233
234 /// given a displacement, generate a neighbor key; ignore boundary conditions and disp's level
235
236 /// @param[in] disp the displacement
237 /// @return a new key
238 Key neighbor(const Key<NDIM>& disp) const {
240 return Key(this->level(),l);
241 }
242
243
244 /// check if this MultiIndex contains point x, disregarding these two dimensions
245 bool thisKeyContains(const Vector<double,NDIM>& x, const unsigned int& dim0,
246 const unsigned int& dim1) const {
247
248 // it's sufficient if one single dimension is out
249 bool contains=true;
250 const double twotoN = std::pow(2.0,double(n));
251 MADNESS_ASSERT(dim0<NDIM and dim1<NDIM);
252
253 for (unsigned int i=0; i<NDIM; i++ ) {
254
255 // check bounds
256 MADNESS_ASSERT((x[i]>=0.0) and (x[i]<=1.0));
257
258 // leave these two dimensions out
259 if ((i==dim0) or (i==dim1)) continue;
260
261 const int ll=int (x[i]*twotoN);
262 if (not (l[i]==ll)) contains=false;
263 }
264 return contains;
265 }
266
267 /// break key into two low-dimensional keys
268 template<std::size_t LDIM, std::size_t KDIM>
269 void break_apart(Key<LDIM>& key1, Key<KDIM>& key2) const {
270
271 // if LDIM==NDIM the 2nd key will be constructed empty
272 MADNESS_ASSERT((LDIM+KDIM==NDIM) or (LDIM==NDIM));
275 for (int i=0; i<static_cast<int>(LDIM); ++i) {
276 l1[i]=l[i];
277 }
278MADNESS_PRAGMA_GCC(diagnostic push)
279MADNESS_PRAGMA_GCC(diagnostic ignored "-Waggressive-loop-optimizations")
280 for (size_t i=LDIM; i<NDIM; ++i) {
281 l2[i-LDIM]=l[i];
282 }
283MADNESS_PRAGMA_GCC(diagnostic pop)
284
285 key1=Key<LDIM>(n,l1);
286 key2=Key<KDIM>(n,l2);
287 }
288
289 /// extract a new key with the Translations indicated in the v array
290 template<std::size_t VDIM>
291 Key<VDIM> extract_key(const std::array<int,VDIM>& v) const {
293 for (int i = 0; i < VDIM; ++i) t[i] = this->translation()[v[i]];
294 return Key<VDIM>(this->level(),t);
295 };
296
297 /// extract a new key with the Translations complementary to the ones indicated in the v array
298 template<std::size_t VDIM>
299 Key<NDIM-VDIM> extract_complement_key(const std::array<int,VDIM>& v) const {
300
301 // return the complement of v, e.g. v={0,1}, v_complement={2,3,4} if NDIM==5
302 // v must be contiguous and ascending (i.e. 1,2,3 or 2,3,4)
303 auto v_complement = [](const std::array<int, VDIM>& v) {
304 std::array<int, NDIM - VDIM> result;
305 for (std::size_t i = 0; i < NDIM - VDIM; i++) result[i] = (v.back() + i + 1) % NDIM;
306 return result;
307 };
308 return extract_key(v_complement(v));
309 };
310
311 /// merge with other key (ie concatenate), use level of rhs, not of this
312 template<std::size_t LDIM>
315 for (int i=0; i<static_cast<int>(NDIM); ++i) t[i] =this->l[i];
316 for (int i=0; i<static_cast<int>(LDIM); ++i) t[NDIM+i]=rhs.translation()[i];
317 return Key<NDIM+LDIM>(rhs.level(),t);
318 }
319
320 /// return if the other key is pointing in the same direction and is farther out
321
322 /// unlike in distsq() the direction is taken into account, and other must be
323 /// longer than this in each dimension
324 /// @param[in] other a key
325 /// @return if other is farther out
326 bool is_farther_out_than(const Key<NDIM>& other) const {
327 for (size_t i=0; i<NDIM; ++i) {
328 if ((other.translation()[i]>0) and (other.translation()[i]>l[i])) return false;
329 if ((other.translation()[i]<0) and (other.translation()[i]<l[i])) return false;
330 }
331 return true;
332 }
333
334
335 /// Recomputes hashval ... presently only done when reading from external storage
336 void
338 //hashval = sdbm(sizeof(n)+sizeof(l), (unsigned char*)(&n));
339 // default hash is still best
340
343 }
344 };
345
346 template<std::size_t NDIM>
347 std::ostream&
348 operator<<(std::ostream& s, const Key<NDIM>& key) {
349 s << "(" << key.level() << "," << key.translation() << ")";
350 return s;
351 }
352
353 /// given a source and a target, return the displacement in translation
354
355 /// @param[in] source the source key
356 /// @param[in] target the target key
357 /// @return disp such that target = source + disp
358 template<size_t NDIM>
360 MADNESS_ASSERT(source.level()==target.level());
361 const Vector<Translation,NDIM> l = target.translation()-source.translation();
362 return Key<NDIM>(source.level(),l);
363 }
364
365
366
367 /// Iterates in lexical order thru all children of a key
368
369 /// Example usage:
370 /// \code
371 /// for (KeyChildIterator<NDIM> it(key); it; ++it) print(it.key());
372 /// \endcode
373 template<std::size_t NDIM>
379
380 public:
382 p(0), finished(true) {
383 }
384
386 parent(parent), child(parent.n + 1, parent.l * 2), p(0),
387 finished(false) {
388 }
389
390 /// Pre-increment of an iterator (i.e., ++it)
393 if (finished)
394 return *this;
395 std::size_t i;
396 for (i = 0; i < NDIM; ++i) {
397 if (p[i] == 0) {
398 ++(p[i]);
399 ++(child.l[i]);
400 for (std::size_t j = 0; j < i; ++j) {
401 --(p[j]);
402 --(child.l[j]);
403 }
404 break;
405 }
406 }
407 finished = (i == NDIM);
408 child.rehash();
409 return *this;
410 }
411
412 /// True if iterator is not at end
413 operator bool() const {
414 return !finished;
415 }
416
417 template<typename Archive>
418 inline void
419 serialize(Archive& ar) {
420 ar & archive::wrap((unsigned char*) this, sizeof(*this));
421 }
422
423 /// Returns the key of the child
424 inline const Key<NDIM>&
425 key() const {
426 return child;
427 }
428 };
429
430 /// Applies op(key) to each child key of parent
431 template<std::size_t NDIM, typename opT>
432 inline void
433 foreach_child(const Key<NDIM>& parent, opT& op) {
435 it(parent); it; ++it)
436 op(it.key());
437 }
438
439 /// Applies member function of obj to each child key of parent
440 template<std::size_t NDIM, typename objT>
441 inline void
442 foreach_child(const Key<NDIM>& parent, objT* obj, void
443 (objT::*memfun)(const Key<NDIM>&)) {
445 it(parent); it; ++it)
446 (obj ->* memfun)(it.key());
447 }
448
449 namespace archive {
450
451 // For efficiency serialize opaque so is just one memcpy, but
452 // when reading from external storage rehash() so that we
453 // can read data even if hash algorithm/function has changed.
454
455 template <class Archive, std::size_t NDIM>
456 struct ArchiveLoadImpl< Archive, Key<NDIM> > {
457 static void load(const Archive& ar, Key<NDIM>& t) {
458 ar & archive::wrap((unsigned char*) &t, sizeof(t));
459 }
460 };
461
462 template <std::size_t NDIM>
464 static void load(const BinaryFstreamInputArchive& ar, Key<NDIM>& t) {
465 ar & archive::wrap((unsigned char*) &t, sizeof(t));
466 t.rehash(); // <<<<<<<<<< This is the point
467 }
468 };
469
470 template <class Archive, std::size_t NDIM>
471 struct ArchiveStoreImpl< Archive, Key<NDIM> > {
472 static void store(const Archive& ar, const Key<NDIM>& t) {
473 ar & archive::wrap((unsigned char*) &t, sizeof(t));
474 }
475 };
476 }
477
478}
479
480#endif // MADNESS_MRA_KEY_H__INCLUDED
481
Implements an archive wrapping a binary filestream.
Iterates in lexical order thru all children of a key.
Definition key.h:374
Vector< Translation, NDIM > p
Definition key.h:377
KeyChildIterator(const Key< NDIM > &parent)
Definition key.h:385
bool finished
Definition key.h:378
const Key< NDIM > & key() const
Returns the key of the child.
Definition key.h:425
KeyChildIterator()
Definition key.h:381
Key< NDIM > child
Definition key.h:376
Key< NDIM > parent
Definition key.h:375
void serialize(Archive &ar)
Definition key.h:419
KeyChildIterator & operator++()
Pre-increment of an iterator (i.e., ++it)
Definition key.h:392
Key is the index for a node of the 2^NDIM-tree.
Definition key.h:66
Key< NDIM+LDIM > merge_with(const Key< LDIM > &rhs) const
merge with other key (ie concatenate), use level of rhs, not of this
Definition key.h:313
Level level() const
Definition key.h:159
bool is_farther_out_than(const Key< NDIM > &other) const
return if the other key is pointing in the same direction and is farther out
Definition key.h:326
Vector< Translation, NDIM > l
Definition key.h:74
Key(int n)
Constructor with given n and l=0.
Definition key.h:90
Key(Level n, const Vector< Translation, NDIM > &l)
Constructor with given n, l.
Definition key.h:84
bool is_parent_of(const Key &key) const
Definition key.h:214
Key()
Default constructor makes an uninitialized key.
Definition key.h:81
bool is_valid() const
Checks if a key is valid.
Definition key.h:114
hashT hash() const
Definition key.h:148
bool thisKeyContains(const Vector< double, NDIM > &x, const unsigned int &dim0, const unsigned int &dim1) const
check if this MultiIndex contains point x, disregarding these two dimensions
Definition key.h:245
bool is_invalid() const
Checks if a key is invalid.
Definition key.h:109
bool operator==(const Key &other) const
Equality test.
Definition key.h:119
Level n
Definition key.h:73
static const std::size_t static_size
Definition key.h:69
bool operator!=(const Key &other) const
Definition key.h:127
Key< NDIM-VDIM > extract_complement_key(const std::array< int, VDIM > &v) const
extract a new key with the Translations complementary to the ones indicated in the v array
Definition key.h:299
Key< VDIM > extract_key(const std::array< int, VDIM > &v) const
extract a new key with the Translations indicated in the v array
Definition key.h:291
hashT hashval
Definition key.h:75
Key parent(int generation=1) const
Returns the key of the parent.
Definition key.h:187
void rehash()
Recomputes hashval ... presently only done when reading from external storage.
Definition key.h:337
const Vector< Translation, NDIM > & translation() const
Definition key.h:164
bool operator<(const Key &other) const
Comparison operator less than to enable storage in STL map.
Definition key.h:132
static Key< NDIM > invalid()
Returns an invalid key.
Definition key.h:104
uint64_t distsq() const
Definition key.h:169
Key neighbor(const Key< NDIM > &disp) const
given a displacement, generate a neighbor key; ignore boundary conditions and disp's level
Definition key.h:238
bool is_child_of(const Key &key) const
Definition key.h:198
void break_apart(Key< LDIM > &key1, Key< KDIM > &key2) const
break key into two low-dimensional keys
Definition key.h:269
bool is_neighbor_of(const Key &key, const std::vector< bool > &bperiodic) const
Assuming keys are at the same level, returns true if displaced by no more than 1 in any direction.
Definition key.h:222
A simple, fixed dimension vector.
Definition vector.h:64
Wraps an archive around a binary filestream for input.
Definition binary_fstream_archive.h:104
archive_array< T > wrap(const T *, unsigned int)
Factory function to wrap a dynamically allocated pointer as a typed archive_array.
Definition archive.h:913
static const double v
Definition hatom_sf_dirac.cc:20
Tensor< double > op(const Tensor< double > &x)
Definition kain.cc:508
#define MADNESS_PRAGMA_GCC(x)
Definition madness_config.h:205
#define MADNESS_ASSERT(condition)
Assert a condition that should be free of side-effects since in release builds this might be a no-op.
Definition madness_exception.h:134
Namespace for all elements and tools of MADNESS.
Definition DFParameters.h:10
std::ostream & operator<<(std::ostream &os, const particle< PDIM > &p)
Definition lowrankfunction.h:397
void hash_combine(hashT &seed, const T &v)
Combine hash values.
Definition worldhash.h:260
int64_t Translation
Definition key.h:54
Key< NDIM > displacement(const Key< NDIM > &source, const Key< NDIM > &target)
given a source and a target, return the displacement in translation
Definition key.h:359
int Level
Definition key.h:55
static double pop(std::vector< double > &v)
Definition SCF.cc:113
std::size_t hashT
The hash value type.
Definition worldhash.h:145
void foreach_child(const Key< NDIM > &parent, opT &op)
Applies op(key) to each child key of parent.
Definition key.h:433
madness::hashT hash_value(const std::array< T, N > &a)
Hash std::array with madness hash.
Definition array_addons.h:78
static long abs(long a)
Definition tensor.h:218
static const double d
Definition nonlinschro.cc:121
static void load(const Archive &ar, Key< NDIM > &t)
Definition key.h:457
static void load(const BinaryFstreamInputArchive &ar, Key< NDIM > &t)
Definition key.h:464
Default load of an object via serialize(ar, t).
Definition archive.h:666
static void store(const Archive &ar, const Key< NDIM > &t)
Definition key.h:472
Default store of an object via serialize(ar, t).
Definition archive.h:611
double dist(const Vector< double, 3 > v1, const Vector< double, 3 > v2)
distance between v1 and v2
Definition test_localizer.cc:38
static const std::size_t NDIM
Definition testpdiff.cc:42
double source(const coordT &r)
Definition testperiodic.cc:48
Implement the madness:Vector class, an extension of std::array that supports some mathematical operat...
Defines hash functions for use in distributed containers.
FLOAT target(const FLOAT &x)
Definition y.cc:295