CluE  1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
fixedsizesubsetiterator.h
Go to the documentation of this file.
1 #ifndef FIXEDSIZESUBSETITERATOR_H
2 #define FIXEDSIZESUBSETITERATOR_H
3 
4 #include <cmath>
5 #include <stdexcept>
6 
7 #include "../exception/invalidargumentexception.h"
8 #include "../misc/setiterator.h"
9 
10 namespace CluE
11 {
20 template<class T> class FixedSizeSubsetIterator : public SetIterator<T>
21 {
22 public:
27  FixedSizeSubsetIterator(std::set<T*> superset, size_t size);
28 
33  FixedSizeSubsetIterator(std::vector<T*> superset, size_t size);
34 
39  virtual size_t size() const;
40 
45  virtual void next();
46 
50  virtual bool hasMore() const;
51 
55  virtual std::set<T*> set() const;
56 
61  virtual std::vector<T*> vector() const;
62 
63 private:
64  void buildSubsetIndices(std::vector<size_t> &buildVector);
65 
66  std::vector<T*> supersetVector;
67  std::vector<std::vector<size_t> > subsetIndices;
68  size_t fixedSize;
70 };
71 
72 template<class T> FixedSizeSubsetIterator<T>::FixedSizeSubsetIterator(std::set<T*> superset, size_t size) :
73  fixedSize(size),
74  currentPosition(0),
75  supersetVector(superset.begin(), superset.end())
76 {
77  if(size == 0 || size >= superset.size())
78  throw InvalidArgumentException(0, "Value of size is invalid!", "size");
79 
80  std::vector<size_t> empty;
81  buildSubsetIndices(empty);
82 }
83 
84 template<class T> FixedSizeSubsetIterator<T>::FixedSizeSubsetIterator(std::vector<T*> superset, size_t size) :
85  supersetVector(superset),
86  fixedSize(size),
87  currentPosition(0)
88 {
89  if(size == 0 || size > superset.size())
90  throw InvalidArgumentException(0, "Value of size is invalid!", "size");
91 
92  std::vector<size_t> empty;
93  buildSubsetIndices(empty);
94 }
95 
96 template<class T> void FixedSizeSubsetIterator<T>::buildSubsetIndices(std::vector<size_t> &buildVector)
97 {
98  size_t start = 0;
99  if(buildVector.size() > 0)
100  start = buildVector[buildVector.size()-1]+1;
101 
102  for(; start < supersetVector.size(); start++)
103  {
104  buildVector.push_back(start);
105  if(buildVector.size() < fixedSize)
106  buildSubsetIndices(buildVector);
107  else
108  subsetIndices.push_back(buildVector);
109  buildVector.erase(buildVector.end()-1);
110  }
111 }
112 
113 template<class T> size_t FixedSizeSubsetIterator<T>::size() const
114 {
115  return subsetIndices[currentPosition].size();
116 }
117 
118 template<class T> void FixedSizeSubsetIterator<T>::next()
119 {
120  if(currentPosition < subsetIndices.size()-1)
121  currentPosition++;
122  else
123  throw std::out_of_range("No more subsets.");
124 }
125 
126 template<class T> bool FixedSizeSubsetIterator<T>::hasMore() const
127 {
128  return currentPosition < subsetIndices.size()-1;
129 }
130 
131 template<class T> std::set<T*> FixedSizeSubsetIterator<T>::set() const
132 {
133  std::set<T*> result;
134  size_t n = subsetIndices[currentPosition].size();
135  for(size_t i = 0; i < n; i++)
136  result.insert(supersetVector[subsetIndices[currentPosition][i]]);
137 
138  return result;
139 }
140 
141 template<class T> std::vector<T*> FixedSizeSubsetIterator<T>::vector() const
142 {
143  std::vector<T*> result;
144  size_t n = subsetIndices[currentPosition].size();
145  for(size_t i = 0; i < n; i++)
146  result.push_back(supersetVector[subsetIndices[currentPosition][i]]);
147 
148  return result;
149 }
150 
151 }
152 
153 #endif
virtual bool hasMore() const
Returns if the Graycode sequence is incomplete yet or not.
Iterates over all fixed-size subsets of a given superset.
virtual size_t size() const
Size of the current subset.
std::vector< std::vector< size_t > > subsetIndices
Base class used to provide iterating over sets.
Definition: setiterator.h:15
void buildSubsetIndices(std::vector< size_t > &buildVector)
FixedSizeSubsetIterator(std::set< T * > superset, size_t size)
Provide the superset as a set.
virtual std::vector< T * > vector() const
Returns the current subset as a vector.
virtual std::set< T * > set() const
Returns the current subset as a set.
Indicates invalid values of arguments.
virtual void next()
Generates the next subset.