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  * Permission is hereby granted, free of charge, to any person obtaining a
  11  * copy of this software and/or associated documentation files (the
  12  * "Materials"), to deal in the Materials without restriction, including
  13  * without limitation the rights to use, copy, modify, merge, publish,
  14  * distribute, sublicense, and/or sell copies of the Materials, and to
  15  * permit persons to whom the Materials are furnished to do so, subject to
  16  * the following conditions:
  17  *
  18  * The above copyright notice(s) and this permission notice shall be included
  19  * in all copies or substantial portions of the Materials.
  20  *
  21  * The Materials are Confidential Information as defined by the
  22  * Khronos Membership Agreement until designated non-confidential by Khronos,
  23  * at which point this condition clause shall be removed.
  24  *
  25  * THE MATERIALS ARE PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  26  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  27  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  28  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  29  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  30  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  31  * MATERIALS OR THE USE OR OTHER DEALINGS IN THE MATERIALS.
  32  *
  33  *//*!
  34  * \file
  35  * \brief Iterator over combinations of items without repetition
  36  *//*--------------------------------------------------------------------*/
  37
  38 #include "tcuDefs.hpp"
  39 #include "deRandom.hpp"
  40 #include <set>
  41 #include <vector>
  42
  43 namespace vkt
  44 {
  45 namespace pipeline
  46 {
  47
  48 template <typename T>
  49 class CombinationsIterator
  50 {
  51 public:
  52                                                         CombinationsIterator    (deUint32 numItems, deUint32 combinationSize);
  53         virtual                                 ~CombinationsIterator   (void) {}
  54         bool                                    hasNext                                 (void) const;
  55         T                                               next                                    (void);
  56         void                                    reset                                   (void);
  57
  58 protected:
  59         virtual T                               getCombinationValue             (const std::vector<deUint32>& combination) = 0;
  60
  61 private:
  62         static deUint32                 factorial                               (deUint32 x);
  63         deUint32                                m_numItems;
  64
  65         deUint32                                m_combinationIndex;
  66         deUint32                                m_combinationSize;
  67         deUint32                                m_combinationCount;
  68
  69         std::vector<deUint32>   m_combination;
  70 };
  71
  72 static deUint32 seriesProduct (deUint32 first, deUint32 last)
  73 {
  74         deUint32 result = 1;
  75
  76         for (deUint32 i = first; i <= last; i++)
  77                 result *= i;
  78
  79         return result;
  80 }
  81
  82 template <typename T>
  83 CombinationsIterator<T>::CombinationsIterator (deUint32 numItems, deUint32 combinationSize)
  84         : m_numItems            (numItems)
  85         , m_combinationSize     (combinationSize)
  86 {
  87         DE_ASSERT(m_combinationSize > 0);
  88         DE_ASSERT(m_combinationSize <= m_numItems);
  89
  90         m_combinationCount      = seriesProduct(numItems - combinationSize + 1, numItems) / seriesProduct(1, combinationSize);
  91
  92         m_combination.resize(m_combinationSize);
  93         reset();
  94 }
  95
  96 template <typename T>
  97 bool CombinationsIterator<T>::hasNext (void) const
  98 {
  99         return m_combinationIndex < m_combinationCount;
 100 }
 101
 102 template <typename T>
 103 T CombinationsIterator<T>::next (void)
 104 {
 105         DE_ASSERT(m_combinationIndex < m_combinationCount);
 106
 107         if (m_combinationIndex > 0)
 108         {
 109                 for (int combinationItemNdx = (int)m_combinationSize - 1; combinationItemNdx >= 0; combinationItemNdx--)
 110                 {
 111                         if ((m_combination[combinationItemNdx] + 1 < m_numItems) && ((combinationItemNdx == (int)m_combinationSize - 1) || (m_combination[combinationItemNdx + 1] > m_combination[combinationItemNdx] + 1)))
 112                         {
 113                                 m_combination[combinationItemNdx]++;
 114
 115                                 for (deUint32 resetNdx = combinationItemNdx + 1; resetNdx < m_combinationSize; resetNdx++)
 116                                         m_combination[resetNdx] = m_combination[resetNdx - 1] + 1;
 117
 118                                 break;
 119                         }
 120                 }
 121         }
 122
 123         m_combinationIndex++;
 124
 125         return getCombinationValue(m_combination);
 126 }
 127
 128 template <typename T>
 129 void CombinationsIterator<T>::reset (void)
 130 {
 131         // Set up first combination
 132         for (deUint32 itemNdx = 0; itemNdx < m_combinationSize; itemNdx++)
 133                 m_combination[itemNdx] = itemNdx;
 134
 135         m_combinationIndex = 0;
 136 }
 137
 138 template <typename T>
 139 deUint32 CombinationsIterator<T>::factorial (deUint32 x)
 140 {
 141         deUint32 result = 1;
 142
 143         for (deUint32 value = x; value > 1; value--)
 144                 result *= value;
 145
 146         return result;
 147 }
 148
 149 } // pipeline
 150 } // vkt
 151
 152 #endif // _VKTPIPELINECOMBINATIONSITERATOR_HPP