atlas  0.6
partition.h
Go to the documentation of this file.
1 /*
2  Class definitions and function declarations for class Partition.
3
4 The purpose of the class Partition is to represent the partition of a
5 finite set given by a group action. A typical example is a Weyl group
6 acting on elements of order 2 in a torus.
7 */
8 /*
9  This is partition.h
10
11  Copyright (C) 2004,2005 Fokko du Cloux
12  part of the Atlas of Lie Groups and Representations
13
15 */
16
17 #ifndef PARTITION_H /* guard against multiple inclusions */
18 #define PARTITION_H
19
20 #include "partition_fwd.h"
21
22 #include <cstddef>
23 #include <functional>
24 #include <vector>
25
26 #include "tags.h"
27
28 namespace atlas {
29
30 namespace partition {
31
32 /******** function declarations **********************************************/
33
34 template<typename F> // F is the type of a binary function object
35  Partition orbits(const F&, unsigned long, unsigned long);
36
37 /******** type definitions ***************************************************/
38
39  /* Partition of some set [0,n[ into classes.
40
41  The partition is represented by a vector d_class of n unsigned longs,
42  mapping values to a number in [0,s[ characterizing the class (where s is the
43  number of classes), together with a vector d_classRep of s unsigned longs
44  that inversely gives a representative element for each class.
45
46  Main application is to the Fiber class: in that case n=2^m, with m at most
47  RANK_MAX; then elements of [0,n[ are interpreted as elements of a vector
48  space (Z/2Z)^m. Typical partitions are into the orbits of a Weyl group
49  acting on this vector space (such partitions are computed by |orbits|).
50  */
51 class Partition
52 {
53  std::vector<unsigned long> d_class; // number identifying the class of |i|
54  std::vector<unsigned long> d_classRep; // section of the |d_class|
55
56  public:
57
59
60 // constructors and destructors
61  Partition() {}
62
66  explicit Partition(unsigned long n):d_class(n),d_classRep() {}
67
68  explicit Partition(std::vector<unsigned long>&);
69
70  Partition(std::vector<unsigned long>&, tags::UnnormalizedTag);
71
73
74 // copy and assignment
75  void swap(Partition&);
76
77 // accessors
78  unsigned long class_of(unsigned long j) const { return d_class[j]; }
79
80  bool operator== (const Partition& other) const
81  { return d_class == other.d_class; }
82
83  // The number of classes in the partition
84  unsigned long classCount() const { return d_classRep.size(); }
85
86  // An element belonging to class |c| (in fact the first such element)
87  unsigned long classRep(unsigned long c) const { return d_classRep[c]; }
88
89  // The number of elements belonging to class |c|
90  unsigned long classSize(unsigned long) const;
91
92  // Number of elements of the underlying set of the partition
93  unsigned long size() const { return d_class.size(); }
94
95  // an auxiliary class to turn a partition into function object for comparison
96  class Comp : public std::unary_function<unsigned long,unsigned long>
97  {
98  const Partition& pi;
99  public:
100  Comp (const Partition& p) : pi(p) {}
101  Comp::result_type operator()(Comp::argument_type x) const
102  { return pi.class_of(x); }
103  };
104
105  Comp comparer() const { return Comp(*this); }
106
107 // manipulators
108
116  void addToClass(unsigned long c, unsigned long j) {
117  // should not be used for the first element in a class!
119  d_class[j] = c;
120  }
121
125  void clear() { d_classRep.clear(); }
126
127  unsigned long new_class(unsigned long c);
128
132  void resize(unsigned long n) {
133  d_class.resize(n);
134  }
135 }; // |class Partition|
136
177 {
178  public:
179  typedef std::vector<unsigned long>::const_iterator SubIterator;
180
181  private:
182
183  std::vector<unsigned long> d_data;
184  std::vector<SubIterator> d_stop;
185  std::pair<SubIterator,SubIterator> d_range;
186  std::vector<SubIterator>::const_iterator d_currentEnd; // points into d_stop
187
188  public:
189
190 // associated types
191  typedef std::forward_iterator_tag iterator_category;
192  typedef std::pair<SubIterator,SubIterator> value_type;
193  typedef ptrdiff_t difference_type;
194  typedef const value_type* pointer;
195  typedef const value_type& reference;
196
197 // constructors and destructors
198  explicit PartitionIterator(const Partition&);
199
200 // accessors
201  bool operator== (const PartitionIterator& i) const {
202  return d_range.first == i.d_range.first;
203  }
204
205  bool operator!= (const PartitionIterator& i) const {
206  return d_range.first != i.d_range.first;
207  }
208
209  reference operator* () const {
210  return d_range;
211  }
212
213  pointer operator-> () const {
214  return &d_range;
215  }
216
217  bool operator() () const {
218  return d_range.first != d_data.end();
219  }
220
221 // manipulators
222  PartitionIterator& operator++ ();
223
224  PartitionIterator operator++ (int) {
225  PartitionIterator tmp(*this);
226  ++(*this);
227  return tmp;
228  }
229
230  void rewind () // set itereator to point to the first class
231  { d_range.first = d_stop[0];
232  d_range.second = d_stop[1];
233  d_currentEnd = d_stop.begin()+1;
234  }
235
236 }; // |class PartitionIterator|
237
238 } // |namespace partition|
239
240 } // |namespace atlas|
241
242 /******** template definitions ***********************************************/
243
244 #include "partition_def.h"
245
246 #endif
Comp::result_type operator()(Comp::argument_type x) const
Definition: partition.h:101
void swap(Partition &)
Definition: partition.cpp:98
Definition: partition.h:51
bool operator==(const Partition &other) const
Definition: partition.h:80
bool operator!=(const type_expr &x, const type_expr &y)
Definition: axis-types.h:374
Definition: Poincare.cpp:13
Partition orbits(const F &, unsigned long, unsigned long)
uA p
Definition: lists.cpp:26
std::pair< SubIterator, SubIterator > d_range
Definition: partition.h:185
void rewind()
Definition: partition.h:230
unsigned long new_class(unsigned long c)
Definition: partition.cpp:107
const value_type * pointer
Definition: partition.h:194
void clear()
Clears all entries of d_classRep.
Definition: partition.h:125
unsigned long classRep(unsigned long c) const
Definition: partition.h:87
std::pair< SubIterator, SubIterator > value_type
Definition: partition.h:192
void addToClass(unsigned long c, unsigned long j)
Adds value j to class #c.
Definition: partition.h:116
std::vector< SubIterator > d_stop
Definition: partition.h:184
Definition: partition.h:176
RationalVector< C2 > operator*(const matrix::Matrix< C1 > &M, const RationalVector< C2 > &v)
Definition: ratvec.cpp:158
ptrdiff_t difference_type
Definition: partition.h:193
unsigned long classSize(unsigned long) const
Counts the number of elements in class #c.
Definition: partition.cpp:120
Partition(unsigned long n)
Undefined partition of [0,n[ with no classes yet (use |add_class|)
Definition: partition.h:66
std::vector< unsigned long >::const_iterator SubIterator
Definition: partition.h:179
std::vector< unsigned long > d_class
Definition: partition.h:53
Partition()
Definition: partition.h:61
PartitionIterator iterator
Definition: partition.h:58
std::vector< unsigned long > d_data
Definition: partition.h:183
std::vector< unsigned long > d_classRep
Definition: partition.h:54
Comp(const Partition &p)
Definition: partition.h:100
~Partition()
Definition: partition.h:72
Comp comparer() const
Definition: partition.h:105
void resize(unsigned long n)
Resizes the class to be a partition of [0,n[.
Definition: partition.h:132
Definition: partition.h:96
unsigned long n
Definition: axis.cpp:77
Definition: Atlas.h:38
std::forward_iterator_tag iterator_category
Definition: partition.h:191
unsigned long classCount() const
Definition: partition.h:84
Dummy argument to distinguish two constructors for Partition.
Definition: tags.h:37
std::vector< SubIterator >::const_iterator d_currentEnd
Definition: partition.h:186
Template definitions for the class Partition.
unsigned long size() const
Definition: partition.h:93
const Partition & pi
Definition: partition.h:98
const value_type & reference
Definition: partition.h:195
unsigned long class_of(unsigned long j) const
Definition: partition.h:78