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 
14  For license information see the LICENSE file
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!
118  // use newClass instead
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
Definition of dummy argument tags used for constructor overloading.
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