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>
40 #include <madness/world/vector.h>
43 #include <stdint.h>
44 
45 namespace 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
104  static Key<NDIM> invalid() {
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  }
278 MADNESS_PRAGMA_GCC(diagnostic push)
279 MADNESS_PRAGMA_GCC(diagnostic ignored "-Waggressive-loop-optimizations")
280  for (size_t i=LDIM; i<NDIM; ++i) {
281  l2[i-LDIM]=l[i];
282  }
283 MADNESS_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>
313  Key<NDIM+LDIM> merge_with(const Key<LDIM>& rhs) const {
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
337  rehash() {
338  //hashval = sdbm(sizeof(n)+sizeof(l), (unsigned char*)(&n));
339  // default hash is still best
340 
341  hashval = hash_value(l);
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>
378  bool finished;
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.
const Key & key()
Definition: test_tree.cc:106
ulong i
Definition: test_tree.cc:82
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
KeyChildIterator()
Definition: key.h:381
Key< NDIM > child
Definition: key.h:376
KeyChildIterator & operator++()
Pre-increment of an iterator (i.e., ++it)
Definition: key.h:392
Key< NDIM > parent
Definition: key.h:375
const Key< NDIM > & key() const
Returns the key of the child.
Definition: key.h:425
void serialize(Archive &ar)
Definition: key.h:419
Key is the index for a node of the 2^NDIM-tree.
Definition: key.h:66
static Key< NDIM > invalid()
Returns an invalid key.
Definition: key.h:104
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
const Vector< Translation, NDIM > & translation() const
Definition: key.h:164
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
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
static const std::size_t static_size
Definition: key.h:69
bool operator!=(const Key &other) const
Definition: key.h:127
hashT hashval
Definition: key.h:75
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
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
bool operator<(const Key &other) const
Comparison operator less than to enable storage in STL map.
Definition: key.h:132
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
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
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
static double pow(const double *a, const double *b)
Definition: lda.h:74
#define max(a, b)
Definition: lda.h:51
#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
File holds all helper structures necessary for the CC_Operator and CC2 class.
Definition: DFParameters.h:10
void hash_combine(hashT &seed, const T &v)
Combine hash values.
Definition: worldhash.h:260
int64_t Translation
Definition: key.h:54
std::ostream & operator<<(std::ostream &os, const particle< PDIM > &p)
Definition: lowrankfunction.h:397
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
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
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
ulong n
Definition: test_tree.cc:41
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
void d()
Definition: test_sig.cc:79
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