MPQC  3.0.0-alpha
string.h
1 //
2 // string.h
3 //
4 // Copyright (C) 2012 Edward Valeev
5 //
6 // Author: Edward Valeev <evaleev@vt.edu>
7 // Maintainer: EV
8 //
9 // This file is part of the SC Toolkit.
10 //
11 // The SC Toolkit is free software; you can redistribute it and/or modify
12 // it under the terms of the GNU Library General Public License as published by
13 // the Free Software Foundation; either version 2, or (at your option)
14 // any later version.
15 //
16 // The SC Toolkit is distributed in the hope that it will be useful,
17 // but WITHOUT ANY WARRANTY; without even the implied warranty of
18 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 // GNU Library General Public License for more details.
20 //
21 // You should have received a copy of the GNU Library General Public License
22 // along with the SC Toolkit; see the file COPYING.LIB. If not, write to_
23 // the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
24 //
25 // The U.S. Government is granted a limited license as per AL 91-7.
26 //
27 
28 #ifdef __GNUG__
29 #pragma implementation
30 #endif
31 
32 #ifndef _mpqc_src_lib_chemistry_qc_nbody_string_h
33 #define _mpqc_src_lib_chemistry_qc_nbody_string_h
34 
35 #include <bitset>
36 #include <vector>
37 #include <array>
38 #include <set>
39 #include <ostream>
40 #include <iostream>
41 #include <array>
42 #include <functional>
43 #include <unordered_set>
44 
45 #define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS // need this to expose dynamic_bitset's naughty bits
46 #include <boost/dynamic_bitset.hpp>
47 #include <boost/functional/hash.hpp>
48 
49 namespace sc {
50 
55  template <size_t Ns=64ul>
56  class FermionOccupationNBitString : public std::bitset<Ns> {
57  public:
58  typedef std::bitset<Ns> parent_type;
59  typedef size_t state_index_type;
60 
64  FermionOccupationNBitString(size_t nstates = Ns) : nstates_(nstates) {
65  }
66 
71  explicit FermionOccupationNBitString(size_t nstates, const std::vector<state_index_type>& occupied_states) :
72  nstates_(nstates) {
73  for(auto v : occupied_states) {
74  (*this)[v].flip();
75  }
76  }
78 
83  bool empty() const {
84  return this->none();
85  }
86 
90  void reset() {
91  std::bitset<Ns>::reset();
92  }
93 
98  size_t size() const {
99  return nstates_;
100  }
101 
106  size_t count() const {
107  return std::bitset<Ns>::count();
108  }
109 
116  (*this)[from] = false;
117  return *this;
118  }
119 
126  (*this)[to] = true;
127  return *this;
128  }
129 
136  size_t count(size_t pos1, size_t pos2) const {
137  // to_ determine the number of particles crossed count the number of particles between to_ and from_
138  FermionOccupationNBitString tmp(*this);
139  tmp >>= (pos1+1);
140  tmp <<= (Ns - (pos2 - pos1 - 1));
141  return tmp.count();
142  }
143 
144  size_t hash_value() const {
145  std::hash<std::bitset<Ns> > h;
146  return h(*this);
147  }
148 
149  template <size_t M> bool operator==(const FermionOccupationNBitString<M>& other) const {
150  return nstates_ == other.nstates_ &&
151  static_cast<parent_type>(*this) == static_cast<parent_type>(other);
152  }
153 
155  MPQC_ASSERT(nstates_+other.nstates_ <= Ns);
156  FermionOccupationNBitString result(nstates_+other.nstates_);
157  size_t pos=0;
158  for(size_t pos1=0; pos1<nstates_; ++pos1, ++pos)
159  result[pos] = (*this)[pos1];
160  for(size_t pos2=0; pos2<other.nstates_; ++pos2, ++pos)
161  result[pos] = other[pos2];
162  return result;
163  }
164 
165  private:
166  size_t nstates_;
167  };
168 
169  template <size_t N1, size_t N2>
170  FermionOccupationNBitString<N1+N2> operator+(const FermionOccupationNBitString<N1>& s1,
171  const FermionOccupationNBitString<N2>& s2) {
172  FermionOccupationNBitString<N1+N2> result;
173  size_t pos=0;
174  for(size_t pos1=0; pos1<N1; ++pos1, ++pos)
175  result[pos] = s1[pos1];
176  for(size_t pos2=0; pos2<N2; ++pos2, ++pos)
177  result[pos] = s2[pos2];
178  return result;
179  }
180 
181  template <class CharT, class Traits, size_t Ns>
182  std::basic_ostream<CharT, Traits>&
183  operator<<(std::basic_ostream<CharT, Traits>& os,
184  const FermionOccupationNBitString<Ns>& x)
185  {
186  os << std::bitset<Ns>(x);
187  return os;
188  }
189 
194  class FermionOccupationDBitString : public boost::dynamic_bitset<> {
195  public:
196  typedef boost::dynamic_bitset<> parent_type;
197  typedef size_t state_index_type;
198 
202  FermionOccupationDBitString(size_t N) : boost::dynamic_bitset<>(N, 0ul) {
203  }
204 
205  FermionOccupationDBitString(boost::dynamic_bitset<>&& bs) : boost::dynamic_bitset<>(bs) {
206  }
207 
212  explicit FermionOccupationDBitString(size_t N, const std::vector<state_index_type>& occupied_states) :
213  boost::dynamic_bitset<>(N, 0ul)
214  {
215  for(auto v : occupied_states) {
216  (*this)[v].flip();
217  }
218  }
220 
225  bool empty() const {
226  return this->none();
227  }
228 
232  void reset() {
233  boost::dynamic_bitset<>::reset();
234  }
235 
240  size_t count() const {
241  return boost::dynamic_bitset<>::count();
242  }
243 
250  (*this)[from] = false;
251  return *this;
252  }
253 
260  (*this)[to] = true;
261  return *this;
262  }
263 
270  size_t count(size_t pos1, size_t pos2) const {
271  // to_ determine the number of particles crossed count the number of particles between to_ and from_
272  FermionOccupationDBitString tmp(*this);
273  tmp >>= (pos1+1);
274  tmp <<= (size() - (pos2 - pos1 - 1));
275  return tmp.count();
276  }
277 
278  size_t hash_value() const {
279  typedef std::vector<parent_type::block_type, parent_type::allocator_type> m_bits_type;
280  boost::hash<m_bits_type> h;
281  return h(m_bits);
282  }
283 
284  bool operator==(const FermionOccupationDBitString& other) const {
285  return size() == other.size() &&
286  static_cast<parent_type>(*this) == static_cast<parent_type>(other);
287  }
288 
289  private:
290  };
291 
292  FermionOccupationDBitString operator+(const FermionOccupationDBitString& s1,
293  const FermionOccupationDBitString& s2) {
294  const size_t s1_size = s1.size();
295  const size_t s2_size = s2.size();
296  FermionOccupationDBitString result1(s1);
297  FermionOccupationDBitString result2(s2);
298  result1.resize(s1_size + s2_size);
299  result2.resize(s1_size + s2_size);
300  result2 <<= s1_size;
301  return result1 | result2;
302 // std::cout << "in FermionOccupationDBitString+FermionOccupationDBitString:" << std::endl
303 // << "arg1 =" << result1 << std::endl
304 // << "arg2 =" << result2 << std::endl
305 // << "result=" << result << std::endl;
306  }
307 
308  template <class CharT, class Traits>
309  std::basic_ostream<CharT, Traits>&
310  operator<<(std::basic_ostream<CharT, Traits>& os,
311  const FermionOccupationDBitString& x)
312  {
313  os << boost::dynamic_bitset<>(x);
314  return os;
315  }
316 
321  public:
322  typedef size_t state_index_type;
323 
325  struct Block {
326  Block(size_t o, bool n = true) : offset(o), length(1ul), occ(n) {}
327  Block(size_t o, size_t l, bool n = true) : offset(o), length(l), occ(n) {}
328  int offset;
329  mutable int length;
330  bool occ;
331  bool operator<(const Block& other) const { return offset < other.offset; }
332 
333  operator long int() const {
334  long int result = offset;
335  result << 31;
336  result += length;
337  return occ ? -result : result;
338  }
339  };
340  typedef std::set<Block> Blocks; //< stores blocks
341 
346  explicit FermionOccupationBlockString(size_t Ns) : nstates_(Ns), blocks_() {
347  blocks_.insert(Block(0,Ns,false));
348  }
349 
354  explicit FermionOccupationBlockString(size_t Ns, const std::vector<state_index_type>& occupied_states) : nstates_(Ns), blocks_() {
355  blocks_.insert(Block(0,Ns,false));
356  // not efficient -- should find blocks
357  for(auto v : occupied_states) {
358  this->add(v);
359  }
360  }
361 
366  explicit FermionOccupationBlockString(size_t Ns, Blocks& blocks) : nstates_(Ns), blocks_() {
367  std::swap(blocks_,blocks);
368  }
369 
371 
376  bool empty() const {
377  return this->count() == 0;
378  }
379 
383  void reset() {
384  blocks_.clear();
385  blocks_.insert(Block(0,nstates_,false));
386  }
387 
392  size_t size() const {
393  return nstates_;
394  }
395 
400  size_t count() const {
401  size_t c = 0;
402  for(auto v : blocks_) {
403  if (v.occ) c += v.length;
404  }
405  return c;
406  }
407 
413  bool operator[](size_t i) const {
414  auto ub_iter = blocks_.upper_bound(Block(i));
415  auto result_iter = --ub_iter;
416  return result_iter->occ;
417  }
418 
425 
426  // 4 possibilities:
427  // 1) state is at the beginning/end of a block -- shrink the occupied block and extend an unoccupied block
428  // 2) state is in the middle of a block -- split the occupied block, create an unoccupied block
429  // 3) state is the only one in the block -- delete the occupied block, merge the unoccupied blocks
430  auto ub_iter = blocks_.upper_bound(Block(from));
431  auto result_iter = --ub_iter;
432  MPQC_ASSERT(result_iter->occ == true);
433 
434  if (result_iter->length == 1) { // only
435  auto uocc_block = this->block_erase(result_iter);
436  }
437  else if (from == result_iter->offset) { // front
438  auto occ_block = this->block_pop_front(result_iter);
439  if (occ_block != blocks_.begin()) {
440  auto uocc_block = this->block_push_back(--occ_block);
441  }
442  else
443  auto uocc_block = blocks_.insert(occ_block, Block(0, 1, false));
444  }
445  else if (from == result_iter->offset + result_iter->length - 1) { // back
446  auto occ_block = this->block_pop_back(result_iter);
447  if (++occ_block != blocks_.end()) {
448  auto uocc_block = this->block_push_front(occ_block);
449  }
450  else
451  auto uocc_block = blocks_.insert(occ_block, Block(0, 1, false));
452  }
453  else { // in the middle
454  this->block_split(result_iter, from);
455  }
456 
457  return *this;
458  }
459 
466 
467  // 4 possibilities:
468  // 1) state is at the beginning/end of a block -- shrink the occupied block and extend an unoccupied block
469  // 2) state is in the middle of a block -- split the occupied block, create an unoccupied block
470  // 3) state is the only one in the block -- delete the occupied block, merge the unoccupied blocks
471  auto ub_iter = blocks_.upper_bound(Block(to));
472  auto result_iter = --ub_iter;
473  MPQC_ASSERT(result_iter->occ == false);
474 
475  if (result_iter->length == 1) { // only
476  auto occ_block = this->block_replace(result_iter, Block(to,1,true));
477  }
478  else if (to == result_iter->offset) { // front
479  auto uocc_block = this->block_pop_front(result_iter);
480  if (uocc_block != blocks_.begin()) {
481  auto occ_block = this->block_push_back(--uocc_block);
482  }
483  else
484  auto occ_block = blocks_.insert(uocc_block, Block(0, 1, true));
485  }
486  else if (to == result_iter->offset + result_iter->length - 1) { // back
487  auto uocc_block = this->block_pop_back(result_iter);
488  if (++uocc_block != blocks_.end()) {
489  auto occ_block = this->block_push_front(uocc_block);
490  }
491  else
492  auto occ_block = blocks_.insert(uocc_block, Block(nstates_-1, 1, true));
493  }
494  else { // in the middle
495  this->block_split(result_iter, to);
496  }
497 
498  return *this;
499  }
500 
507  size_t count(size_t pos1, size_t pos2) const {
508  // to_ determine the number of particles crossed count the number of particles between to_ and from_
509  MPQC_ASSERT(pos1 <= pos2);
510  auto ub1_iter = blocks_.upper_bound(Block(pos1));
511  auto blk1_iter = --ub1_iter;
512  auto ub2_iter = blocks_.upper_bound(Block(pos2));
513  auto blk2_iter = --ub2_iter;
514  size_t c = (blk1_iter->occ ? (blk1_iter->offset + blk1_iter->length - pos1 - 1) : 0);
515  c += (blk2_iter->occ ? (pos2 - blk2_iter->offset) : 0);
516  ++blk1_iter; --blk2_iter;
517  for(auto i=blk1_iter; i!=blk2_iter; ++i)
518  if (i->occ)
519  c += i->length;
520 // std::cout << "count = " << c << std::endl;
521  return c;
522  }
523 
524  boost::dynamic_bitset<> to_bitset() const {
525  boost::dynamic_bitset<> result(nstates_);
526  for(auto v : blocks_) {
527  if (v.occ)
528  for(size_t l=0, pos=v.offset;
529  l<v.length; ++l, ++pos) {
530  result.flip(pos);
531  }
532  }
533  return result;
534  }
535 
538  MPQC_ASSERT(size() == other.size());
539  Blocks result_blocks;
540  auto w = result_blocks.begin();
541  auto u = other.blocks().begin();
542  auto v = blocks().begin();
543  auto red = v;
544  auto black = u;
545  size_t red_end = red->offset+red->length;
546  size_t black_end = black->offset+black->length;
547  const size_t size2 = size() * 2;
548  while (red_end + black_end != size2) {
549  if (red_end <= black_end) {
550  w = result_blocks.insert(w, Block(red->offset, red->length, red->occ ^ black->occ));
551  ++red;
552  red_end = red->offset+red->length;
553  if (red->offset == black_end) {
554  ++black;
555  black_end = black->offset+black->length;
556  }
557  }
558  else {
559  w = result_blocks.insert(w, Block(red->offset, black_end - red->offset, red->occ ^ black->occ));
560  ++black;
561  black_end = black->offset+black->length;
562  std::swap(red,black);
563  std::swap(red_end,black_end);
564  }
565  }
566  w = result_blocks.insert(w, Block(red->offset, red->length, red->occ ^ black->occ));
567  FermionOccupationBlockString result(size(), result_blocks);
568  return result;
569  }
570 
571  size_t hash_value() const {
572  boost::hash<Blocks> h;
573  return h(blocks_);
574  }
575 
576  bool operator==(const FermionOccupationBlockString& other) const {
577  MPQC_ASSERT(nstates_ == other.nstates_);
578  return blocks_ == other.blocks_;
579  }
580 
587  const size_t other_offset = nstates_;
588  nstates_ += other.nstates_;
589  MPQC_ASSERT(not other.blocks_.empty());
590  MPQC_ASSERT(not blocks_.empty());
591  auto back_iter = (--blocks_.end());
592  if (back_iter->occ == other.blocks_.begin()->occ) {
593  Block merged_block(back_iter->offset, back_iter->length+other.blocks_.begin()->length, back_iter->occ);
594  blocks_.erase(back_iter);
595  auto current_iter = blocks_.insert(merged_block).first;
596  for(auto i = ++other.blocks_.begin();
597  i!=other.blocks_.end();
598  ++i) {
599  Block offset_block(i->offset + other_offset, i->length, i->occ);
600  current_iter = blocks_.insert(current_iter, offset_block);
601  }
602  }
603  else {
604  auto current_iter = back_iter;
605  for(auto i = other.blocks_.begin();
606  i!=other.blocks_.end();
607  ++i) {
608  Block offset_block(i->offset + other_offset, i->length, i->occ);
609  current_iter = blocks_.insert(current_iter, offset_block);
610  }
611  }
612  return *this;
613  }
614 
615  private:
616  size_t nstates_;
617  Blocks blocks_;
618  Blocks& blocks() { return blocks_; }
619  const Blocks& blocks() const { return blocks_; }
620 
621  Blocks::const_iterator block_pop_front(Blocks::const_iterator block) {
622  Block popped_block(*block);
623  --popped_block.length;
624  ++popped_block.offset;
625  blocks_.erase(block);
626  const auto result_iter = blocks_.insert(popped_block).first;
627  return result_iter;
628  }
629  Blocks::const_iterator block_pop_back(Blocks::const_iterator block) {
630  --(block->length);
631  return block;
632  }
633  Blocks::const_iterator block_push_front(Blocks::const_iterator block) {
634  Block popped_block(*block);
635  ++popped_block.length;
636  --popped_block.offset;
637  blocks_.erase(block);
638  const auto result_iter = blocks_.insert(popped_block).first;
639  return result_iter;
640  }
641  Blocks::const_iterator block_push_back(Blocks::const_iterator block) {
642  ++(block->length);
643  return block;
644  }
645 
646  Blocks::const_iterator block_replace(Blocks::const_iterator block,
647  const Block& new_block) {
648  blocks_.erase(block);
649  auto result = blocks_.insert(new_block);
650  MPQC_ASSERT(result.second == true);
651  return result.first;
652  }
653 
654  Blocks::const_iterator block_erase(Blocks::const_iterator block) {
655  const bool have_prev = (block != blocks_.begin());
656  Blocks::const_iterator next_block(block); ++next_block;
657  const bool have_next = (next_block != blocks_.end());
658 
659  if (have_prev) {
660  Blocks::const_iterator prev_block(block); --prev_block;
661  prev_block->length += block->length;
662  blocks_.erase(block);
663  if (have_next) {
664  prev_block->length += next_block->length;
665  blocks_.erase(next_block);
666  }
667  return prev_block;
668  }
669  else if (have_next) { // not have_prev
670  Block new_block(*next_block);
671  const size_t length = block->length;
672  new_block.offset -= length;
673  new_block.length += length;
674  blocks_.erase(block);
675  blocks_.erase(next_block);
676  auto result = blocks_.insert(new_block).first;
677  return result;
678  }
679  else { // erasing the only block
680  blocks_.clear();
681  blocks_.insert(Block(0,nstates_,false));
682  return blocks_.begin();
683  }
684  MPQC_ASSERT(false); // unreachable
685  return blocks_.begin();
686  }
687 
688  Blocks::const_iterator block_split(Blocks::const_iterator block,
689  size_t pos) {
690  const size_t orig_length = block->length;
691  const size_t offset = block->offset;
692  block->length = (pos - block->offset);
693 
694  Block split_block(pos, 1, !block->occ);
695  auto iter = blocks_.insert(block, split_block);
696 
697  Block remainder_block(pos+1, offset+orig_length-pos-1, block->occ);
698  blocks_.insert(iter, remainder_block);
699 
700  return iter;
701  }
702 
703  };
704 
705  template <class CharT, class Traits>
706  std::basic_ostream<CharT, Traits>&
707  operator<<(std::basic_ostream<CharT, Traits>& os,
708  const FermionOccupationBlockString& x)
709  {
710  os << x.to_bitset();
711  return os;
712  }
713 
714  FermionOccupationBlockString operator+(const FermionOccupationBlockString& s1,
715  const FermionOccupationBlockString& s2) {
716  FermionOccupationBlockString result(s1);
717  result.append(s2);
718  return result;
719  }
720 
722  // specialized string containers
724 
725  template <typename FString>
727  public:
728  typedef std::vector<FString> container_type;
729  typedef typename container_type::iterator iterator;
730  typedef typename container_type::const_iterator const_iterator;
731  typedef FString value_type;
732 
735 
736  const_iterator insert(const FString& s) {
737  strings_.push_back(s);
738  return --strings_.end();
739  }
740  const_iterator insert(FString&& s) {
741  strings_.push_back(s);
742  return --strings_.end();
743  }
744 
745  const_iterator begin() const {
746  return strings_.cbegin();
747  }
748  const_iterator end() const {
749  return strings_.cend();
750  }
751 
752  size_t size() const {
753  return strings_.size();
754  }
755 
756  private:
757  container_type strings_;
758  };
759 
760  template <typename FString>
762  public:
763  typedef std::unordered_set<FString> container_type;
764  typedef typename container_type::iterator iterator;
765  typedef typename container_type::const_iterator const_iterator;
766  typedef FString value_type;
767 
770 
771  const_iterator insert(const FString& s) {
772  auto result = strings_.insert(s);
773  MPQC_ASSERT(result.second == true);
774  return result.first;
775  }
776  const_iterator insert(FString&& s) {
777  auto result = strings_.insert(s);
778  MPQC_ASSERT(result.second == true);
779  return result.first;
780  }
781 
782  const_iterator begin() const {
783  return strings_.cbegin();
784  }
785  const_iterator end() const {
786  return strings_.cend();
787  }
788 
789  size_t size() const {
790  return strings_.size();
791  }
792 
793  private:
794  container_type strings_;
795  };
796 
798  // string algorithms
800 
805  template <size_t Nb, typename FString>
807  template <typename FString>
808  class FermionBasicNCOper<1,FString> {
809  public:
810  static const size_t Rank = 1;
811  typedef typename FString::state_index_type state_index_type;
812 
813  template <typename Int> FermionBasicNCOper(Int t, Int f) : to_(t) , from_(f) {
814  }
815 
820  size_t to() const { return to_[0]; }
821 
826  const std::array<state_index_type,1>& cre() const { return to_; }
827 
832  size_t from() const { return from_[0]; }
833 
838  const std::array<state_index_type,1>& ann() const { return from_; }
839 
840 
846  void apply(FString& os) const {
847  if (os[from_[0]] == true && (os[to_[0]] == false || from_ == to_)) {
848  os.remove(from_[0]).add(to_[0]);
849  }
850  else
851  os.reset();
852  }
853 
860  bool apply_sign(FString& os) const {
861  if (os[from_[0]] == true && (os[to_[0]] == false || from_ == to_)) {
862  os.remove(from_[0]).add(to_[0]);
863  // to_ determine the number of particles crossed, count the number of particles between to_ and from_
864  if (to_[0] > from_[0]) {
865  const bool sign_changes = os.count(from_[0],to_[0]) & size_t(1);
866  return sign_changes;
867  } else { // to_ <= from_
868  const bool sign_changes = os.count(to_[0],from_[0]) & size_t(1);
869  return sign_changes;
870  }
871  }
872  else {
873  os.reset();
874  return false;
875  }
876  }
877 
883  std::pair<bool,FString > operator()(const FString& os) const {
884  FString result(os);
885  const bool sign_changes = this->apply_sign(result);
886  return std::make_pair(sign_changes,result);
887  }
888 
889  private:
890  std::array<state_index_type, Rank> from_;
891  std::array<state_index_type, Rank> to_;
892  };
893 
894  template <size_t Nb, typename FString>
895  class FermionBasicNCOper {
896  public:
897  static const size_t Rank = Nb;
898  typedef typename FString::state_index_type state_index_type;
899 
900  template <typename Int> FermionBasicNCOper(const std::array<Int,Rank>& t, const std::array<Int,Rank>& f) : to_(t) , from_(f) {
901  }
902 
907  const std::array<state_index_type,Rank>& cre() const { return to_; }
908 
913  const std::array<state_index_type,Rank>& ann() const { return from_; }
914 
915 
921  void apply(FString& os) const {
922  for(size_t r=0; r<Rank; ++r)
923  os.remove(from_[r]).add(to_[r]);
924  }
925 
932  bool apply_sign(FString& os) const {
933  bool sign_changes = false;
934  for (size_t r=0; r<Rank; ++r) {
935  os.remove(from_[r]).add(to_[r]);
936  // to_ determine the number of particles crossed, count the number of particles between to_ and from_
937  if (to_[r] > from_[r]) {
938  sign_changes ^= os.count(from_[r],to_[r]) & size_t(1);
939  } else { // to_ <= from_
940  sign_changes ^= os.count(to_[r],from_[r]) & size_t(1);
941  }
942  }
943  return sign_changes;
944  }
945 
951  std::pair<bool,FString > operator()(const FString& os) const {
952  FString result(os);
953  const bool sign_changes = this->apply_sign(result);
954  return std::make_pair(sign_changes,result);
955  }
956 
957  private:
958  std::array<state_index_type, Rank> from_;
959  std::array<state_index_type, Rank> to_;
960  };
961 
962  template <class CharT, class Traits, size_t Nb, typename FString>
963  std::basic_ostream<CharT, Traits>&
964  operator<<(std::basic_ostream<CharT, Traits>& os,
965  const FermionBasicNCOper<Nb, FString>& o)
966  {
967  os << o.to() << "<-" << o.from();
968  return os;
969  }
970 
977  template <typename FString, unsigned int R, bool GenerateStrings>
979  public:
980  typedef typename FString::state_index_type state_index_type;
981  static const unsigned int Rank = R;
982 
983  StringReplacementListIterator(const FString& ref_string) :
984  rstr_(ref_string), str_(ref_string)
985  {
986  init();
987  }
988 
989  StringReplacementListIterator& operator++() {
990  MPQC_ASSERT(false); // not implemented yet
991  return *this;
992  }
993 
994  const FString& operator*() const {
995  MPQC_ASSERT(false);
996  return str_;
997  }
998 
999  const FermionBasicNCOper<Rank, FString>& oper() const {
1000  return oper_;
1001  }
1002 
1007  operator bool() const {
1008  return more_;
1009  }
1010 
1011  bool operator==(const StringReplacementListIterator& other) {
1012  if (rstr_ == other.rstr_) {
1013  if (more_ != other.more_)
1014  return false;
1015  else {
1016  return str_ == other.str_;
1017  }
1018  }
1019  else // rstr_ != other.rstr_
1020  return false;
1021  }
1022 
1023  static StringReplacementListIterator begin(const FString& ref_string) {
1024  return StringReplacementListIterator(ref_string);
1025  }
1026 
1027  static StringReplacementListIterator end(const FString& ref_string) {
1028  return StringReplacementListIterator(ref_string, false);
1029  }
1030 
1031  private:
1032  FString rstr_; //< reference string
1033  FString str_; //< current string
1034  size_t nparticles_;
1035  FermionBasicNCOper<Rank,FString> oper_;
1036  bool more_; //< are there more strings left?
1037 
1038  void init() {
1039  nparticles_ = rstr_.count();
1040  if (nparticles_ == rstr_.size()
1041  ||
1042  R > rstr_.count()
1043  )
1044  more_ = false;
1045  else
1046  more_ = true;
1047  }
1048 
1050  StringReplacementListIterator(const FString& ref_string,
1051  bool more) : rstr_(ref_string), str_(ref_string), more_(more) {
1052  init();
1053  }
1054  };
1055 
1060  template <typename FermionStringSet>
1062  public:
1063  typedef typename FermionStringSet::value_type string_type;
1064 
1070  FullFermionStringSetBuild(size_t m, size_t n) : nparticles_(n), nstates_(m) {
1071  MPQC_ASSERT(nparticles_ <= nstates_); // these are 1-particle states
1072  }
1073 
1074  void operator()(FermionStringSet& sset) {
1075  // make recursively by appending a string with 1 particle at the bottom of k states 0....01
1076  // to a full set of n-1 particles in m-k states, where 1 <= k <= m-n+1
1077  // iterate starting with most significant states empty
1078  for(size_t k=nstates_-nparticles_+1; k>=1; --k) {
1079 
1080  string_type s0(k);
1081  s0.add(0);
1082 // std::cout << "in FullFermionStringSetBuild::operator() -- s0=" << s0 << " m=" << nstates_ << " n=" << nparticles_ << std::endl;
1083 
1084  do_iter(s0, sset, nstates_-k, nparticles_-1);
1085  }
1086  }
1087 
1088  private:
1089  size_t nparticles_;
1090  size_t nstates_;
1091 
1092  static void do_iter(const string_type& s0,
1093  FermionStringSet& sset,
1094  size_t nstates, size_t nparticles) {
1095 // std::cout << "in FullFermionStringSetBuild::do_iter -- s0=" << s0 << " m=" << nstates << " n=" << nparticles << std::endl;
1096  if (nparticles == 1ul) {
1097  string_type s1(nstates);
1098  s1.add(0ul);
1099  string_type s2(s1 + s0);
1100  sset.insert(s2);
1101 // std::cout << "inserted " << s2 << std::endl;
1102  for (size_t pos = 1; pos < nstates; ++pos) {
1103  s2.remove(pos-1).add(pos);
1104  sset.insert(s2);
1105 // std::cout << "inserted " << s2 << std::endl;
1106  }
1107  }
1108  else {
1109  for (size_t k = nstates - nparticles + 1; k >= 1; --k) {
1110  string_type s1(k);
1111  s1.add(0ul);
1112  string_type s2(s1 + s0);
1113  do_iter(s2, sset, nstates - k, nparticles - 1);
1114  }
1115  }
1116  }
1117  };
1118 
1119 } // end of namespace sc
1120 
1121 // specialize std::hash for the string classes
1122 namespace std {
1123 
1127  template <size_t Ns>
1128  class hash<sc::FermionOccupationNBitString<Ns> > {
1129  public:
1130  size_t operator()(const sc::FermionOccupationNBitString<Ns> &s) const
1131  {
1132  return s.hash_value();
1133  }
1134  };
1135 
1139  template <>
1140  class hash<sc::FermionOccupationDBitString > {
1141  public:
1142  size_t operator()(const sc::FermionOccupationDBitString &s) const
1143  {
1144  return s.hash_value();
1145  }
1146  };
1147 
1151  template <>
1152  class hash<sc::FermionOccupationBlockString> {
1153  public:
1154  size_t operator()(const sc::FermionOccupationBlockString &s) const
1155  {
1156  return s.hash_value();
1157  }
1158  };
1159 
1160 }
1161 
1162 #endif // end of header guard
1163 
1164 
1165 // Local Variables:
1166 // mode: c++
1167 // c-file-style: "CLJ-CONDENSED"
1168 // End:
sc::FermionOccupationBlockString::count
size_t count() const
Reports the number of occupied states.
Definition: string.h:400
sc::FermionOccupationBlockString::operator^
FermionOccupationBlockString operator^(const FermionOccupationBlockString &other) const
XORs two strings.
Definition: string.h:537
sc::FermionOccupationNBitString
a "dense" string represents occupancies of a set of Ns states by a fixed-width bitstring
Definition: string.h:56
sc::FermionOccupationDBitString::FermionOccupationDBitString
FermionOccupationDBitString(size_t N, const std::vector< state_index_type > &occupied_states)
Constructs FermionOccupationDBitString using a (possibly-empty) set of indices of occupied states.
Definition: string.h:212
sc::FermionOccupationBlockString
a block-"sparse" string represents occupancies of an arbitrarily-large set of states as a set of alte...
Definition: string.h:320
sc::FermionOccupationBlockString::remove
FermionOccupationBlockString & remove(size_t from)
Removes a particle from_ state from_.
Definition: string.h:424
sc::FermionOccupationNBitString::count
size_t count(size_t pos1, size_t pos2) const
counts the number of bits in (pos1,pos2) (assumes pos2 >= pos1)
Definition: string.h:136
sc::FermionOccupationNBitString::FermionOccupationNBitString
FermionOccupationNBitString(size_t nstates, const std::vector< state_index_type > &occupied_states)
Constructs FermionOccupationNBitString using a (possibly-empty) set of indices of occupied states.
Definition: string.h:71
sc::operator+
Ref< GaussianBasisSet > operator+(const Ref< GaussianBasisSet > &A, const Ref< GaussianBasisSet > &B)
Nonmember operator+ is more convenient to use than the member operator+.
sc::FermionBasicNCOper
basic Nb-body number-conserving (nc) operator in sp representation
Definition: string.h:806
sc::FermionBasicNCOper< 1, FString >::apply_sign
bool apply_sign(FString &os) const
same as apply(), but returns whether application operator changes the sign of the state; the sign cha...
Definition: string.h:860
sc::FullFermionStringSetBuild
Build all possible strings by distributing n particles in m states.
Definition: string.h:1061
sc::FermionOccupationDBitString::empty
bool empty() const
are all states empty?
Definition: string.h:225
sc::StringReplacementListIterator
Iterates over strings obtained by rank R replecement from a given string.
Definition: string.h:978
sc::FermionOccupationNBitString::add
FermionOccupationNBitString & add(size_t to)
Adds a particle to_ state to_.
Definition: string.h:125
sc::FermionOccupationBlockString::operator[]
bool operator[](size_t i) const
Returns the occupancy of state i.
Definition: string.h:413
sc::FermionOccupationNBitString::empty
bool empty() const
are all states empty?
Definition: string.h:83
sc::FermionOccupationBlockString::empty
bool empty() const
are all states empty?
Definition: string.h:376
sc::FermionOccupationBlockString::FermionOccupationBlockString
FermionOccupationBlockString(size_t Ns)
Constructs an empty set of Ns states.
Definition: string.h:346
sc::FermionBasicNCOper::ann
const std::array< state_index_type, Rank > & ann() const
reports the states in which particles are annihilated
Definition: string.h:913
sc::FermionBasicNCOper< 1, FString >::to
size_t to() const
reports the state to which this operator places a particle
Definition: string.h:820
sc::FermionOccupationNBitString::FermionOccupationNBitString
FermionOccupationNBitString(size_t nstates=Ns)
Constructs an empty set of states.
Definition: string.h:64
sc::FermionOccupationDBitString
a "dense" string represents occupancies of a set of Ns states by a bitstring
Definition: string.h:194
sc::FermionBasicNCOper< 1, FString >::ann
const std::array< state_index_type, 1 > & ann() const
reports the states in which particles are annihilated
Definition: string.h:838
sc::FermionOccupationNBitString::reset
void reset()
empties all states
Definition: string.h:90
sc::FermionOccupationDBitString::add
FermionOccupationDBitString & add(size_t to)
Adds a particle to_ state to_.
Definition: string.h:259
sc::FermionOccupationDBitString::count
size_t count() const
Reports the number of occupied states.
Definition: string.h:240
sc::FermionOccupationNBitString::remove
FermionOccupationNBitString & remove(size_t from)
Removes a particle from_ state from_.
Definition: string.h:115
sc::operator<<
std::vector< unsigned int > operator<<(const GaussianBasisSet &B, const GaussianBasisSet &A)
computes a map from basis functions in A to the equivalent basis functions in B.
sc::FermionOccupationNBitString::count
size_t count() const
Reports the number of occupied states.
Definition: string.h:106
sc::FermionOccupationDBitString::reset
void reset()
empties all states
Definition: string.h:232
sc::FermionBasicNCOper::apply
void apply(FString &os) const
applies this operator to_ FermionOccupationNBitString os.
Definition: string.h:921
sc::FermionOccupationBlockString::reset
void reset()
empties all states
Definition: string.h:383
sc::FermionBasicNCOper::cre
const std::array< state_index_type, Rank > & cre() const
reports the states in which particles are created
Definition: string.h:907
sc::Rank
Rank
Rank of the RDM.
Definition: rdm.h:39
sc::FermionBasicNCOper< 1, FString >::operator()
std::pair< bool, FString > operator()(const FString &os) const
similar to_ apply_sign(), but keeps the argument unchanged
Definition: string.h:883
sc::FermionOccupationDBitString::FermionOccupationDBitString
FermionOccupationDBitString(size_t N)
Constructs an empty set of N states.
Definition: string.h:202
sc::FermionOccupationBlockString::add
FermionOccupationBlockString & add(size_t to)
Adds a particle to_ state to_.
Definition: string.h:465
sc::other
SpinCase1 other(SpinCase1 S)
given 1-spin return the other 1-spin
sc::FermionOccupationNBitString::size
size_t size() const
Reports the total number of states.
Definition: string.h:98
sc::FermionOccupationDBitString::remove
FermionOccupationDBitString & remove(size_t from)
Removes a particle from_ state from_.
Definition: string.h:249
sc::FermionStringSparseSet
Definition: string.h:761
sc::FermionOccupationBlockString::FermionOccupationBlockString
FermionOccupationBlockString(size_t Ns, Blocks &blocks)
Constructs FermionOccupationBlockString using a (possibly-empty) set of indices of occupied states.
Definition: string.h:366
sc::FermionBasicNCOper< 1, FString >::cre
const std::array< state_index_type, 1 > & cre() const
reports the states in which particles are created
Definition: string.h:826
sc::FermionBasicNCOper::operator()
std::pair< bool, FString > operator()(const FString &os) const
similar to_ apply_sign(), but keeps the argument unchanged
Definition: string.h:951
sc::FermionOccupationBlockString::append
FermionOccupationBlockString & append(const FermionOccupationBlockString &other)
appends other to the end of this
Definition: string.h:586
sc::FullFermionStringSetBuild::FullFermionStringSetBuild
FullFermionStringSetBuild(size_t m, size_t n)
Makes a set of strings by distributing n particles in m states.
Definition: string.h:1070
sc::FermionOccupationDBitString::count
size_t count(size_t pos1, size_t pos2) const
counts the number of bits in (pos1,pos2) (assumes pos2 >= pos1)
Definition: string.h:270
sc::FermionBasicNCOper< 1, FString >::apply
void apply(FString &os) const
applies this operator to_ FermionOccupationNBitString os.
Definition: string.h:846
sc::FermionBasicNCOper< 1, FString >::from
size_t from() const
reports the state from which this operator removes a particle
Definition: string.h:832
sc::FermionOccupationBlockString::count
size_t count(size_t pos1, size_t pos2) const
counts the number of bits in (pos1,pos2) (assumes pos2 >= pos1)
Definition: string.h:507
sc::FermionBasicNCOper::apply_sign
bool apply_sign(FString &os) const
same as apply(), but returns whether application operator changes the sign of the state; the sign cha...
Definition: string.h:932
sc::FermionOccupationBlockString::FermionOccupationBlockString
FermionOccupationBlockString(size_t Ns, const std::vector< state_index_type > &occupied_states)
Constructs FermionOccupationBlockString using a (possibly-empty) set of indices of occupied states.
Definition: string.h:354
sc
Contains all MPQC code up to version 3.
Definition: mpqcin.h:14
sc::FermionOccupationBlockString::Block
represents a continuous block of states of same occupancy
Definition: string.h:325
sc::FermionStringDenseSet
Definition: string.h:726
sc::FermionOccupationBlockString::size
size_t size() const
Reports the total number of states.
Definition: string.h:392

Generated at Sun Jan 26 2020 23:23:59 for MPQC 3.0.0-alpha using the documentation package Doxygen 1.8.16.