dune-common  2.2.0
indexset.hh
Go to the documentation of this file.
1 // $Id$
2 #ifndef DUNE_INDEXSET_HH
3 #define DUNE_INDEXSET_HH
4 
5 #include<algorithm>
8 #include<iostream>
9 
10 #include"localindex.hh"
11 
12 #include <stdint.h> // for uint32_t
13 
14 namespace Dune
15 {
25  // forward declarations
26 
27  template<class TG, class TL>
28  class IndexPair;
29 
35  template<class TG, class TL>
36  std::ostream& operator<<(std::ostream& os, const IndexPair<TG,TL>& pair);
37 
38  template<class TG, class TL>
39  bool operator==(const IndexPair<TG,TL>&, const IndexPair<TG,TL>&);
40 
41  template<class TG, class TL>
42  bool operator!=(const IndexPair<TG,TL>&, const IndexPair<TG,TL>&);
43 
44  template<class TG, class TL>
45  bool operator<(const IndexPair<TG,TL>&, const IndexPair<TG,TL>&);
46 
47  template<class TG, class TL>
48  bool operator>(const IndexPair<TG,TL>&, const IndexPair<TG,TL>&);
49 
50  template<class TG, class TL>
51  bool operator<=(const IndexPair<TG,TL>&, const IndexPair<TG,TL>&);
52 
53  template<class TG, class TL>
54  bool operator >=(const IndexPair<TG,TL>&, const IndexPair<TG,TL>&);
55 
56  template<class TG, class TL>
57  bool operator==(const IndexPair<TG,TL>&, const TG&);
58 
59  template<class TG, class TL>
60  bool operator!=(const IndexPair<TG,TL>&, const TG&);
61 
62  template<class TG, class TL>
63  bool operator<(const IndexPair<TG,TL>&, const TG&);
64 
65  template<class TG, class TL>
66  bool operator>(const IndexPair<TG,TL>&, const TG&);
67 
68  template<class TG, class TL>
69  bool operator<=(const IndexPair<TG,TL>&, const TG&);
70 
71  template<class TG, class TL>
72  bool operator >=(const IndexPair<TG,TL>&, const TG&);
73 
74  template<typename T>
75  class MPITraits;
76 
80  template<class TG, class TL>
81  class IndexPair
82  {
83  friend std::ostream& operator<<<>(std::ostream&, const IndexPair<TG,TL>&);
84  friend bool operator==<>(const IndexPair<TG,TL>&, const IndexPair<TG,TL>&);
85  friend bool operator!=<>(const IndexPair<TG,TL>&, const IndexPair<TG,TL>&);
86  friend bool operator< <>(const IndexPair<TG,TL>&, const IndexPair<TG,TL>&);
87  friend bool operator><>(const IndexPair<TG,TL>&, const IndexPair<TG,TL>&);
88  friend bool operator<=<>(const IndexPair<TG,TL>&, const IndexPair<TG,TL>&);
89  friend bool operator>=<>(const IndexPair<TG,TL>&, const IndexPair<TG,TL>&);
90  friend bool operator==<>(const IndexPair<TG,TL>&, const TG&);
91  friend bool operator!=<>(const IndexPair<TG,TL>&, const TG&);
92  friend bool operator< <>(const IndexPair<TG,TL>&, const TG&);
93  friend bool operator> <>(const IndexPair<TG,TL>&, const TG&);
94  friend bool operator<=<>(const IndexPair<TG,TL>&, const TG&);
95  friend bool operator>=<>(const IndexPair<TG,TL>&, const TG&);
96  friend class MPITraits<IndexPair<TG,TL> >;
97 
98  public:
104  typedef TG GlobalIndex;
105 
117  typedef TL LocalIndex;
118 
125  IndexPair(const GlobalIndex& global, const LocalIndex& local);
126 
130  IndexPair();
137  IndexPair(const GlobalIndex& global);
138 
144  inline const GlobalIndex& global() const;
145 
151  inline LocalIndex& local();
152 
158  inline const LocalIndex& local()const;
159 
165  inline void setLocal(int index);
166  private:
168  GlobalIndex global_;
170  LocalIndex local_;
171  };
172 
178  {
197  };
198 
203 
204  // Forward declaration
205  template<class I> class GlobalLookupIndexSet;
206 
213  template<typename TG, typename TL, int N=100>
215  {
216  friend class GlobalLookupIndexSet<ParallelIndexSet<TG,TL,N> >;
217 
218  public:
223  typedef TG GlobalIndex;
224 
236  typedef TL LocalIndex;
237 
242 
243  enum{
250  arraySize= (N>0)?N:1
251  };
252 
254  class iterator :
255  public ArrayList<IndexPair,N>::iterator
256  {
257  typedef typename ArrayList<IndexPair,N>::iterator
258  Father;
260  public:
261  iterator(ParallelIndexSet<TG,TL,N>& indexSet, const Father& father)
262  : Father(father), indexSet_(&indexSet)
263  {}
264 
265  iterator(const iterator& other)
266  : Father(other), indexSet_(other.indexSet_)
267  {}
268 
269  iterator& operator==(const iterator& other)
270  {
271  Father::operator==(other);
272  indexSet_ = other.indexSet_;
273  }
274 
275  private:
283  inline void markAsDeleted() const throw(InvalidIndexSetState)
284  {
285 #ifndef NDEBUG
286  if(indexSet_->state_ != RESIZE)
287  DUNE_THROW(InvalidIndexSetState, "Indices can only be removed "
288  <<"while in RESIZE state!");
289 #endif
290  Father::operator*().local().setState(DELETED);
291  }
292 
294  ParallelIndexSet<TG,TL,N>* indexSet_;
295 
296  };
297 
298 
299 
301  typedef typename
304 
309 
314  inline const ParallelIndexSetState& state();
315 
321  void beginResize() throw(InvalidIndexSetState);
322 
331  inline void add(const GlobalIndex& global) throw(InvalidIndexSetState);
332 
341  inline void add(const GlobalIndex& global, const LocalIndex& local)
342  throw(InvalidIndexSetState);
343 
351  inline void markAsDeleted(const iterator& position)
352  throw(InvalidIndexSetState);
353 
366  void endResize() throw(InvalidIndexSetState);
367 
378  inline IndexPair&
379  operator[](const GlobalIndex& global);
380 
390  inline IndexPair&
391  at(const GlobalIndex& global);
392 
403  inline const IndexPair&
404  operator[](const GlobalIndex& global) const;
405 
415  inline const IndexPair&
416  at(const GlobalIndex& global) const;
417 
422  inline iterator begin();
423 
428  inline iterator end();
429 
434  inline const_iterator begin() const;
435 
440  inline const_iterator end() const;
441 
451  inline void renumberLocal();
452 
459  inline int seqNo() const;
460 
465  inline size_t size() const;
466 
467  private:
469  ArrayList<IndexPair,N> localIndices_;
471  ArrayList<IndexPair,N> newIndices_;
473  ParallelIndexSetState state_;
475  int seqNo_;
477  bool deletedEntries_;
482  inline void merge();
483  };
484 
485 
491  template<class TG, class TL, int N>
492  std::ostream& operator<<(std::ostream& os, const ParallelIndexSet<TG,TL,N>& indexSet);
493 
499  template<class I>
501  {
502  public:
506  typedef I ParallelIndexSet;
507 
512 
517 
522 
524 
531  GlobalLookupIndexSet(const ParallelIndexSet& indexset, std::size_t size);
532 
538  GlobalLookupIndexSet(const ParallelIndexSet& indexset);
539 
543  ~GlobalLookupIndexSet();
544 
554  inline const IndexPair&
555  operator[](const GlobalIndex& global) const;
556 
560  inline const IndexPair*
561  pair(const std::size_t& local) const;
562 
567  inline const_iterator begin() const;
568 
573  inline const_iterator end() const;
574 
581  inline int seqNo() const;
582 
587  inline size_t size() const;
588  private:
592  const ParallelIndexSet& indexSet_;
593 
597  std::size_t size_;
598 
602  std::vector<const IndexPair*> indices_;
603 
604  };
605 
606 
607  template<typename T>
609  {
610  static bool compare(const T& t1, const T& t2){
611  return false;
612  }
613  };
614 
615  template<class TG, class TL>
617  {
618  bool operator()(const IndexPair<TG,TL>& i1, const IndexPair<TG,TL>& i2)
619  {
620  return i1.global()<i2.global() || (i1.global()==i2.global() &&
622  i2.local()));
623  }
624  };
625 
626 
627 
628  template<class TG, class TL>
629  inline std::ostream& operator<<(std::ostream& os, const IndexPair<TG,TL>& pair)
630  {
631  os<<"{global="<<pair.global_<<", local="<<pair.local_<<"}";
632  return os;
633  }
634 
635  template<class TG, class TL, int N>
636  inline std::ostream& operator<<(std::ostream& os, const ParallelIndexSet<TG,TL,N>& indexSet)
637  {
638  typedef typename ParallelIndexSet<TG,TL,N>::const_iterator Iterator;
639  Iterator end = indexSet.end();
640  os<<"{";
641  for(Iterator index = indexSet.begin(); index != end; ++index)
642  os<<*index<<" ";
643  os<<"}";
644  return os;
645 
646  }
647 
648  template<class TG, class TL>
649  inline bool operator==(const IndexPair<TG,TL>& a, const IndexPair<TG,TL>& b)
650  {
651  return a.global_==b.global_;
652  }
653 
654  template<class TG, class TL>
655  inline bool operator!=(const IndexPair<TG,TL>& a, const IndexPair<TG,TL>& b)
656  {
657  return a.global_!=b.global_;
658  }
659 
660  template<class TG, class TL>
661  inline bool operator<(const IndexPair<TG,TL>& a, const IndexPair<TG,TL>& b)
662  {
663  return a.global_<b.global_;
664  }
665 
666  template<class TG, class TL>
667  inline bool operator>(const IndexPair<TG,TL>& a, const IndexPair<TG,TL>& b)
668  {
669  return a.global_>b.global_;
670  }
671 
672  template<class TG, class TL>
673  inline bool operator<=(const IndexPair<TG,TL>& a, const IndexPair<TG,TL>& b)
674  {
675  return a.global_<=b.global_;
676  }
677 
678  template<class TG, class TL>
679  inline bool operator >=(const IndexPair<TG,TL>& a, const IndexPair<TG,TL>& b)
680  {
681  return a.global_>=b.global_;
682  }
683 
684  template<class TG, class TL>
685  inline bool operator==(const IndexPair<TG,TL>& a, const TG& b)
686  {
687  return a.global_==b;
688  }
689 
690  template<class TG, class TL>
691  inline bool operator!=(const IndexPair<TG,TL>& a, const TG& b)
692  {
693  return a.global_!=b;
694  }
695 
696  template<class TG, class TL>
697  inline bool operator<(const IndexPair<TG,TL>& a, const TG& b)
698  {
699  return a.global_<b;
700  }
701 
702  template<class TG, class TL>
703  inline bool operator>(const IndexPair<TG,TL>& a, const TG& b)
704  {
705  return a.global_>b;
706  }
707 
708  template<class TG, class TL>
709  inline bool operator<=(const IndexPair<TG,TL>& a, const TG& b)
710  {
711  return a.global_<=b;
712  }
713 
714  template<class TG, class TL>
715  inline bool operator >=(const IndexPair<TG,TL>& a, const TG& b)
716  {
717  return a.global_>=b;
718  }
719 
720 #ifndef DOXYGEN
721 
722  template<class TG, class TL>
723  IndexPair<TG,TL>::IndexPair(const TG& global, const TL& local)
724  : global_(global), local_(local){}
725 
726  template<class TG, class TL>
727  IndexPair<TG,TL>::IndexPair(const TG& global)
728  : global_(global), local_(){}
729 
730  template<class TG, class TL>
731  IndexPair<TG,TL>::IndexPair()
732  : global_(), local_(){}
733 
734  template<class TG, class TL>
735  inline const TG& IndexPair<TG,TL>::global() const{
736  return global_;
737  }
738 
739  template<class TG, class TL>
740  inline TL& IndexPair<TG,TL>::local() {
741  return local_;
742  }
743 
744  template<class TG, class TL>
745  inline const TL& IndexPair<TG,TL>::local() const{
746  return local_;
747  }
748 
749  template<class TG, class TL>
750  inline void IndexPair<TG,TL>::setLocal(int local){
751  local_=local;
752  }
753 
754  template<class TG, class TL, int N>
755  ParallelIndexSet<TG,TL,N>::ParallelIndexSet()
756  : state_(GROUND), seqNo_(0)
757  {}
758 
759  template<class TG, class TL, int N>
760  void ParallelIndexSet<TG,TL,N>::beginResize() throw(InvalidIndexSetState)
761  {
762 
763  // Checks in unproductive code
764 #ifndef NDEBUG
765  if(state_!=GROUND)
766  DUNE_THROW(InvalidIndexSetState,
767  "IndexSet has to be in GROUND state, when "
768  << "beginResize() is called!");
769 #endif
770 
771  state_ = RESIZE;
772  deletedEntries_ = false;
773  }
774 
775  template<class TG, class TL, int N>
776  inline void ParallelIndexSet<TG,TL,N>::add(const GlobalIndex& global)
777  throw(InvalidIndexSetState)
778  {
779  // Checks in unproductive code
780 #ifndef NDEBUG
781  if(state_ != RESIZE)
782  DUNE_THROW(InvalidIndexSetState, "Indices can only be added "
783  <<"while in RESIZE state!");
784 #endif
785  newIndices_.push_back(IndexPair(global));
786  }
787 
788  template<class TG, class TL, int N>
789  inline void ParallelIndexSet<TG,TL,N>::add(const TG& global, const TL& local)
790  throw(InvalidIndexSetState)
791  {
792  // Checks in unproductive code
793 #ifndef NDEBUG
794  if(state_ != RESIZE)
795  DUNE_THROW(InvalidIndexSetState, "Indices can only be added "
796  <<"while in RESIZE state!");
797 #endif
798  newIndices_.push_back(IndexPair(global,local));
799  }
800 
801  template<class TG, class TL, int N>
802  inline void ParallelIndexSet<TG,TL,N>::markAsDeleted(const iterator& global)
803  throw(InvalidIndexSetState){
804  // Checks in unproductive code
805 #ifndef NDEBUG
806  if(state_ != RESIZE)
807  DUNE_THROW(InvalidIndexSetState, "Indices can only be removed "
808  <<"while in RESIZE state!");
809 #endif
810  deletedEntries_ = true;
811 
812  global.markAsDeleted();
813  }
814 
815  template<class TG, class TL, int N>
816  void ParallelIndexSet<TG,TL,N>::endResize() throw(InvalidIndexSetState){
817  // Checks in unproductive code
818 #ifndef NDEBUG
819  if(state_ != RESIZE)
820  DUNE_THROW(InvalidIndexSetState, "endResize called while not "
821  <<"in RESIZE state!");
822 #endif
823 
824  std::sort(newIndices_.begin(), newIndices_.end(), IndexSetSortFunctor<TG,TL>());
825  merge();
826  seqNo_++;
827  state_ = GROUND;
828  }
829 
830 
831  template<class TG, class TL, int N>
832  inline void ParallelIndexSet<TG,TL,N>::merge(){
833  if(localIndices_.size()==0)
834  {
835  localIndices_=newIndices_;
836  newIndices_.clear();
837  }
838  else if(newIndices_.size()>0 || deletedEntries_)
839  {
840  ArrayList<IndexPair,N> tempPairs;
841  typedef typename ArrayList<IndexPair,N>::iterator iterator;
842  typedef typename ArrayList<IndexPair,N>::const_iterator const_iterator;
843 
844  iterator old=localIndices_.begin();
845  iterator added=newIndices_.begin();
846  const const_iterator endold=localIndices_.end();
847  const const_iterator endadded=newIndices_.end();
848 
849  while(old != endold && added!= endadded)
850  {
851  if(old->local().state()==DELETED){
852  old.eraseToHere();
853  }
854  else
855  {
856  if(old->global() < added->global() ||
857  (old->global() == added->global()
858  && LocalIndexComparator<TL>::compare(old->local(),added->local())))
859  {
860  tempPairs.push_back(*old);
861  old.eraseToHere();
862  continue;
863  }else
864  {
865  tempPairs.push_back(*added);
866  added.eraseToHere();
867  }
868  }
869  }
870 
871  while(old != endold)
872  {
873  if(old->local().state()!=DELETED){
874  tempPairs.push_back(*old);
875  }
876  old.eraseToHere();
877  }
878 
879  while(added!= endadded)
880  {
881  tempPairs.push_back(*added);
882  added.eraseToHere();
883  }
884  localIndices_ = tempPairs;
885  }
886  }
887 
888 
889  template<class TG, class TL, int N>
890  inline const IndexPair<TG,TL>&
891  ParallelIndexSet<TG,TL,N>::at(const TG& global) const
892  {
893  // perform a binary search
894  int low=0, high=localIndices_.size()-1, probe=-1;
895 
896  while(low<high)
897  {
898  probe = (high + low) / 2;
899  if(global <= localIndices_[probe].global())
900  high = probe;
901  else
902  low = probe+1;
903  }
904 
905  if(probe==-1)
906  DUNE_THROW(RangeError, "No entries!");
907 
908  if( localIndices_[low].global() != global)
909  DUNE_THROW(RangeError, "Could not find entry of "<<global);
910  else
911  return localIndices_[low];
912  }
913 
914  template<class TG, class TL, int N>
915  inline const IndexPair<TG,TL>&
916  ParallelIndexSet<TG,TL,N>::operator[](const TG& global) const
917  {
918  // perform a binary search
919  int low=0, high=localIndices_.size()-1, probe=-1;
920 
921  while(low<high)
922  {
923  probe = (high + low) / 2;
924  if(global <= localIndices_[probe].global())
925  high = probe;
926  else
927  low = probe+1;
928  }
929 
930  return localIndices_[low];
931  }
932  template<class TG, class TL, int N>
933  inline IndexPair<TG,TL>& ParallelIndexSet<TG,TL,N>::at(const TG& global)
934  {
935  // perform a binary search
936  int low=0, high=localIndices_.size()-1, probe=-1;
937 
938  while(low<high)
939  {
940  probe = (high + low) / 2;
941  if(localIndices_[probe].global() >= global)
942  high = probe;
943  else
944  low = probe+1;
945  }
946 
947  if(probe==-1)
948  DUNE_THROW(RangeError, "No entries!");
949 
950  if( localIndices_[low].global() != global)
951  DUNE_THROW(RangeError, "Could not find entry of "<<global);
952  else
953  return localIndices_[low];
954  }
955 
956  template<class TG, class TL, int N>
957  inline IndexPair<TG,TL>& ParallelIndexSet<TG,TL,N>::operator[](const TG& global)
958  {
959  // perform a binary search
960  int low=0, high=localIndices_.size()-1, probe=-1;
961 
962  while(low<high)
963  {
964  probe = (high + low) / 2;
965  if(localIndices_[probe].global() >= global)
966  high = probe;
967  else
968  low = probe+1;
969  }
970 
971  return localIndices_[low];
972  }
973  template<class TG, class TL, int N>
974  inline typename ParallelIndexSet<TG,TL,N>::iterator
975  ParallelIndexSet<TG,TL,N>::begin()
976  {
977  return iterator(*this, localIndices_.begin());
978  }
979 
980 
981  template<class TG, class TL, int N>
982  inline typename ParallelIndexSet<TG,TL,N>::iterator
983  ParallelIndexSet<TG,TL,N>::end()
984  {
985  return iterator(*this,localIndices_.end());
986  }
987 
988  template<class TG, class TL, int N>
989  inline typename ParallelIndexSet<TG,TL,N>::const_iterator
990  ParallelIndexSet<TG,TL,N>::begin() const
991  {
992  return localIndices_.begin();
993  }
994 
995 
996  template<class TG, class TL, int N>
997  inline typename ParallelIndexSet<TG,TL,N>::const_iterator
998  ParallelIndexSet<TG,TL,N>::end() const
999  {
1000  return localIndices_.end();
1001  }
1002 
1003  template<class TG, class TL, int N>
1004  void ParallelIndexSet<TG,TL,N>::renumberLocal(){
1005 #ifndef NDEBUG
1006  if(state_==RESIZE)
1007  DUNE_THROW(InvalidIndexSetState, "IndexSet has to be in "
1008  <<"GROUND state for renumberLocal()");
1009 #endif
1010 
1011  typedef typename ArrayList<IndexPair,N>::iterator iterator;
1012  const const_iterator end_ = end();
1013  uint32_t index=0;
1014 
1015  for(iterator pair=begin(); pair!=end_; index++, ++pair)
1016  pair->local()=index;
1017  }
1018 
1019  template<class TG, class TL, int N>
1020  inline int ParallelIndexSet<TG,TL,N>::seqNo() const
1021  {
1022  return seqNo_;
1023  }
1024 
1025  template<class TG, class TL, int N>
1026  inline size_t ParallelIndexSet<TG,TL,N>::size() const
1027  {
1028  return localIndices_.size();
1029  }
1030 
1031  template<class I>
1032  GlobalLookupIndexSet<I>::GlobalLookupIndexSet(const I& indexset,
1033  std::size_t size)
1034  : indexSet_(indexset), size_(size),
1035  indices_(size_, static_cast<const IndexPair*>(0))
1036  {
1037  const_iterator end_ = indexSet_.end();
1038 
1039  for(const_iterator pair = indexSet_.begin(); pair!=end_; ++pair){
1040  assert(pair->local()<size_);
1041  indices_[pair->local()] = &(*pair);
1042  }
1043  }
1044 
1045  template<class I>
1046  GlobalLookupIndexSet<I>::GlobalLookupIndexSet(const I& indexset)
1047  : indexSet_(indexset), size_(0)
1048  {
1049  const_iterator end_ = indexSet_.end();
1050  for(const_iterator pair = indexSet_.begin(); pair!=end_; ++pair)
1051  size_=std::max(size_,static_cast<std::size_t>(pair->local()));
1052 
1053  indices_.resize(++size_, 0);
1054 
1055  for(const_iterator pair = indexSet_.begin(); pair!=end_; ++pair)
1056  indices_[pair->local()] = &(*pair);
1057  }
1058 
1059  template<class I>
1060  GlobalLookupIndexSet<I>::~GlobalLookupIndexSet()
1061  {}
1062 
1063  template<class I>
1064  inline const IndexPair<typename I::GlobalIndex, typename I::LocalIndex>*
1065  GlobalLookupIndexSet<I>::pair(const std::size_t& local) const
1066  {
1067  return indices_[local];
1068  }
1069 
1070  template<class I>
1071  inline const IndexPair<typename I::GlobalIndex, typename I::LocalIndex>&
1072  GlobalLookupIndexSet<I>::operator[](const GlobalIndex& global) const
1073  {
1074  return indexSet_[global];
1075  }
1076 
1077  template<class I>
1078  typename I::const_iterator GlobalLookupIndexSet<I>::begin() const
1079  {
1080  return indexSet_.begin();
1081  }
1082 
1083  template<class I>
1084  typename I::const_iterator GlobalLookupIndexSet<I>::end() const
1085  {
1086  return indexSet_.end();
1087  }
1088 
1089  template<class I>
1090  inline size_t GlobalLookupIndexSet<I>::size() const
1091  {
1092  return size_;
1093  }
1094 
1095  template<class I>
1096  inline int GlobalLookupIndexSet<I>::seqNo() const
1097  {
1098  return indexSet_.seqNo();
1099  }
1100 
1101  template<typename TG, typename TL, int N, typename TG1, typename TL1, int N1>
1102  bool operator==(const ParallelIndexSet<TG,TL,N>& idxset,
1103  const ParallelIndexSet<TG1,TL1,N1>& idxset1)
1104  {
1105  if(idxset.size()!=idxset1.size())
1106  return false;
1107  typedef typename ParallelIndexSet<TG,TL,N>::const_iterator Iter;
1108  typedef typename ParallelIndexSet<TG1,TL1,N1>::const_iterator Iter1;
1109  Iter iter=idxset.begin();
1110  for(Iter1 iter1=idxset1.begin(); iter1 != idxset1.end(); ++iter, ++iter1){
1111  if(iter1->global()!=iter->global())
1112  return false;
1113  typedef typename ParallelIndexSet<TG,TL,N>::LocalIndex PI;
1114  const PI& pi=iter->local(), pi1=iter1->local();
1115 
1116  if(pi!=pi1)
1117  return false;
1118  }
1119  return true;
1120  }
1121 
1122  template<typename TG, typename TL, int N, typename TG1, typename TL1, int N1>
1123  bool operator!=(const ParallelIndexSet<TG,TL,N>& idxset,
1124  const ParallelIndexSet<TG1,TL1,N1>& idxset1)
1125  {
1126  return !(idxset==idxset1);
1127  }
1128 
1129 
1130 #endif // DOXYGEN
1131 
1132 }
1133 #endif