| #ifndef _VKTPIPELINECOMBINATIONSITERATOR_HPP |
| #define _VKTPIPELINECOMBINATIONSITERATOR_HPP |
| /*------------------------------------------------------------------------ |
| * Vulkan Conformance Tests |
| * ------------------------ |
| * |
| * Copyright (c) 2015 The Khronos Group Inc. |
| * Copyright (c) 2015 Imagination Technologies Ltd. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| * |
| *//*! |
| * \file |
| * \brief Iterator over combinations of items without repetition |
| *//*--------------------------------------------------------------------*/ |
| |
| #include "tcuDefs.hpp" |
| #include "deRandom.hpp" |
| #include <set> |
| #include <vector> |
| |
| namespace vkt |
| { |
| namespace pipeline |
| { |
| |
| template <typename T> |
| class CombinationsIterator |
| { |
| public: |
| CombinationsIterator (deUint32 numItems, deUint32 combinationSize); |
| virtual ~CombinationsIterator (void) {} |
| bool hasNext (void) const; |
| T next (void); |
| void reset (void); |
| |
| protected: |
| virtual T getCombinationValue (const std::vector<deUint32>& combination) = 0; |
| |
| private: |
| static deUint32 factorial (deUint32 x); |
| deUint32 m_numItems; |
| |
| deUint32 m_combinationIndex; |
| deUint32 m_combinationSize; |
| deUint32 m_combinationCount; |
| |
| std::vector<deUint32> m_combination; |
| }; |
| |
| static deUint32 seriesProduct (deUint32 first, deUint32 last) |
| { |
| deUint32 result = 1; |
| |
| for (deUint32 i = first; i <= last; i++) |
| result *= i; |
| |
| return result; |
| } |
| |
| template <typename T> |
| CombinationsIterator<T>::CombinationsIterator (deUint32 numItems, deUint32 combinationSize) |
| : m_numItems (numItems) |
| , m_combinationSize (combinationSize) |
| { |
| DE_ASSERT(m_combinationSize > 0); |
| DE_ASSERT(m_combinationSize <= m_numItems); |
| |
| m_combinationCount = seriesProduct(numItems - combinationSize + 1, numItems) / seriesProduct(1, combinationSize); |
| |
| m_combination.resize(m_combinationSize); |
| reset(); |
| } |
| |
| template <typename T> |
| bool CombinationsIterator<T>::hasNext (void) const |
| { |
| return m_combinationIndex < m_combinationCount; |
| } |
| |
| template <typename T> |
| T CombinationsIterator<T>::next (void) |
| { |
| DE_ASSERT(m_combinationIndex < m_combinationCount); |
| |
| if (m_combinationIndex > 0) |
| { |
| for (int combinationItemNdx = (int)m_combinationSize - 1; combinationItemNdx >= 0; combinationItemNdx--) |
| { |
| if ((m_combination[combinationItemNdx] + 1 < m_numItems) && ((combinationItemNdx == (int)m_combinationSize - 1) || (m_combination[combinationItemNdx + 1] > m_combination[combinationItemNdx] + 1))) |
| { |
| m_combination[combinationItemNdx]++; |
| |
| for (deUint32 resetNdx = combinationItemNdx + 1; resetNdx < m_combinationSize; resetNdx++) |
| m_combination[resetNdx] = m_combination[resetNdx - 1] + 1; |
| |
| break; |
| } |
| } |
| } |
| |
| m_combinationIndex++; |
| |
| return getCombinationValue(m_combination); |
| } |
| |
| template <typename T> |
| void CombinationsIterator<T>::reset (void) |
| { |
| // Set up first combination |
| for (deUint32 itemNdx = 0; itemNdx < m_combinationSize; itemNdx++) |
| m_combination[itemNdx] = itemNdx; |
| |
| m_combinationIndex = 0; |
| } |
| |
| template <typename T> |
| deUint32 CombinationsIterator<T>::factorial (deUint32 x) |
| { |
| deUint32 result = 1; |
| |
| for (deUint32 value = x; value > 1; value--) |
| result *= value; |
| |
| return result; |
| } |
| |
| } // pipeline |
| } // vkt |
| |
| #endif // _VKTPIPELINECOMBINATIONSITERATOR_HPP |