external/vulkancts/modules/vulkan/pipeline/vktPipelineCombinationsIterator.hpp

   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);
  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
  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>
  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>
  86 bool CombinationsIterator<T>::hasNext (void) const
  87 {
  88         return m_combinationIndex < m_combinationCount;
  89 }
  90
  91 template <typename T>
  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>
 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>
 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