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(uint32_t numItems, uint32_t combinationSize);
~CombinationsIterator(void)42 virtual ~CombinationsIterator(void)
43 {
44 }
45 bool hasNext(void) const;
46 T next(void);
47 void reset(void);
48
49 protected:
50 virtual T getCombinationValue(const std::vector<uint32_t> &combination) = 0;
51
52 private:
53 static uint32_t factorial(uint32_t x);
54 uint32_t m_numItems;
55
56 uint32_t m_combinationIndex;
57 uint32_t m_combinationSize;
58 uint32_t m_combinationCount;
59
60 std::vector<uint32_t> m_combination;
61 };
62
seriesProduct(uint32_t first,uint32_t last)63 static uint32_t seriesProduct(uint32_t first, uint32_t last)
64 {
65 uint32_t result = 1;
66
67 for (uint32_t i = first; i <= last; i++)
68 result *= i;
69
70 return result;
71 }
72
73 template <typename T>
CombinationsIterator(uint32_t numItems,uint32_t combinationSize)74 CombinationsIterator<T>::CombinationsIterator(uint32_t numItems, uint32_t combinationSize)
75 : m_numItems(numItems)
76 , m_combinationSize(combinationSize)
77 {
78 DE_ASSERT(m_combinationSize > 0);
79 DE_ASSERT(m_combinationSize <= m_numItems);
80
81 m_combinationCount = seriesProduct(numItems - combinationSize + 1, numItems) / seriesProduct(1, combinationSize);
82
83 m_combination.resize(m_combinationSize);
84 reset();
85 }
86
87 template <typename T>
hasNext(void) const88 bool CombinationsIterator<T>::hasNext(void) const
89 {
90 return m_combinationIndex < m_combinationCount;
91 }
92
93 template <typename T>
next(void)94 T CombinationsIterator<T>::next(void)
95 {
96 DE_ASSERT(m_combinationIndex < m_combinationCount);
97
98 if (m_combinationIndex > 0)
99 {
100 for (int combinationItemNdx = (int)m_combinationSize - 1; combinationItemNdx >= 0; combinationItemNdx--)
101 {
102 if ((m_combination[combinationItemNdx] + 1 < m_numItems) &&
103 ((combinationItemNdx == (int)m_combinationSize - 1) ||
104 (m_combination[combinationItemNdx + 1] > m_combination[combinationItemNdx] + 1)))
105 {
106 m_combination[combinationItemNdx]++;
107
108 for (uint32_t resetNdx = combinationItemNdx + 1; resetNdx < m_combinationSize; resetNdx++)
109 m_combination[resetNdx] = m_combination[resetNdx - 1] + 1;
110
111 break;
112 }
113 }
114 }
115
116 m_combinationIndex++;
117
118 return getCombinationValue(m_combination);
119 }
120
121 template <typename T>
reset(void)122 void CombinationsIterator<T>::reset(void)
123 {
124 // Set up first combination
125 for (uint32_t itemNdx = 0; itemNdx < m_combinationSize; itemNdx++)
126 m_combination[itemNdx] = itemNdx;
127
128 m_combinationIndex = 0;
129 }
130
131 template <typename T>
factorial(uint32_t x)132 uint32_t CombinationsIterator<T>::factorial(uint32_t x)
133 {
134 uint32_t result = 1;
135
136 for (uint32_t value = x; value > 1; value--)
137 result *= value;
138
139 return result;
140 }
141
142 } // namespace pipeline
143 } // namespace vkt
144
145 #endif // _VKTPIPELINECOMBINATIONSITERATOR_HPP
146