1 #ifndef _VKTPIPELINECOMBINATIONSITERATOR_HPP
2 #define _VKTPIPELINECOMBINATIONSITERATOR_HPP
3 /*------------------------------------------------------------------------
4 * Vulkan Conformance Tests
5 * ------------------------
6 *
7 * Copyright (c) 2015 The Khronos Group Inc.
8 * Copyright (c) 2015 Imagination Technologies Ltd.
9 *
10 * Licensed under the Apache License, Version 2.0 (the "License");
11 * you may not use this file except in compliance with the License.
12 * You may obtain a copy of the License at
13 *
14 * http://www.apache.org/licenses/LICENSE-2.0
15 *
16 * Unless required by applicable law or agreed to in writing, software
17 * distributed under the License is distributed on an "AS IS" BASIS,
18 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19 * See the License for the specific language governing permissions and
20 * limitations under the License.
21 *
22 *//*!
23 * \file
24 * \brief Iterator over combinations of items without repetition
25 *//*--------------------------------------------------------------------*/
26
27 #include "tcuDefs.hpp"
28 #include "deRandom.hpp"
29 #include <set>
30 #include <vector>
31
32 namespace vkt
33 {
34 namespace pipeline
35 {
36
37 template <typename T>
38 class CombinationsIterator
39 {
40 public:
41 CombinationsIterator (deUint32 numItems, deUint32 combinationSize);
~CombinationsIterator(void)42 virtual ~CombinationsIterator (void) {}
43 bool hasNext (void) const;
44 T next (void);
45 void reset (void);
46
47 protected:
48 virtual T getCombinationValue (const std::vector<deUint32>& combination) = 0;
49
50 private:
51 static deUint32 factorial (deUint32 x);
52 deUint32 m_numItems;
53
54 deUint32 m_combinationIndex;
55 deUint32 m_combinationSize;
56 deUint32 m_combinationCount;
57
58 std::vector<deUint32> m_combination;
59 };
60
seriesProduct(deUint32 first,deUint32 last)61 static deUint32 seriesProduct (deUint32 first, deUint32 last)
62 {
63 deUint32 result = 1;
64
65 for (deUint32 i = first; i <= last; i++)
66 result *= i;
67
68 return result;
69 }
70
71 template <typename T>
CombinationsIterator(deUint32 numItems,deUint32 combinationSize)72 CombinationsIterator<T>::CombinationsIterator (deUint32 numItems, deUint32 combinationSize)
73 : m_numItems (numItems)
74 , m_combinationSize (combinationSize)
75 {
76 DE_ASSERT(m_combinationSize > 0);
77 DE_ASSERT(m_combinationSize <= m_numItems);
78
79 m_combinationCount = seriesProduct(numItems - combinationSize + 1, numItems) / seriesProduct(1, combinationSize);
80
81 m_combination.resize(m_combinationSize);
82 reset();
83 }
84
85 template <typename T>
hasNext(void) const86 bool CombinationsIterator<T>::hasNext (void) const
87 {
88 return m_combinationIndex < m_combinationCount;
89 }
90
91 template <typename T>
next(void)92 T CombinationsIterator<T>::next (void)
93 {
94 DE_ASSERT(m_combinationIndex < m_combinationCount);
95
96 if (m_combinationIndex > 0)
97 {
98 for (int combinationItemNdx = (int)m_combinationSize - 1; combinationItemNdx >= 0; combinationItemNdx--)
99 {
100 if ((m_combination[combinationItemNdx] + 1 < m_numItems) && ((combinationItemNdx == (int)m_combinationSize - 1) || (m_combination[combinationItemNdx + 1] > m_combination[combinationItemNdx] + 1)))
101 {
102 m_combination[combinationItemNdx]++;
103
104 for (deUint32 resetNdx = combinationItemNdx + 1; resetNdx < m_combinationSize; resetNdx++)
105 m_combination[resetNdx] = m_combination[resetNdx - 1] + 1;
106
107 break;
108 }
109 }
110 }
111
112 m_combinationIndex++;
113
114 return getCombinationValue(m_combination);
115 }
116
117 template <typename T>
reset(void)118 void CombinationsIterator<T>::reset (void)
119 {
120 // Set up first combination
121 for (deUint32 itemNdx = 0; itemNdx < m_combinationSize; itemNdx++)
122 m_combination[itemNdx] = itemNdx;
123
124 m_combinationIndex = 0;
125 }
126
127 template <typename T>
factorial(deUint32 x)128 deUint32 CombinationsIterator<T>::factorial (deUint32 x)
129 {
130 deUint32 result = 1;
131
132 for (deUint32 value = x; value > 1; value--)
133 result *= value;
134
135 return result;
136 }
137
138 } // pipeline
139 } // vkt
140
141 #endif // _VKTPIPELINECOMBINATIONSITERATOR_HPP
142