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 PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  22  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  23  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  24  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  25  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  26  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  27  * MATERIALS OR THE USE OR OTHER DEALINGS IN THE MATERIALS.
  28  *
  29  *//*!
  30  * \file
  31  * \brief Iterator over combinations of items without repetition
  32  *//*--------------------------------------------------------------------*/
  33
  34 #include "tcuDefs.hpp"
  35 #include "deRandom.hpp"
  36 #include <set>
  37 #include <vector>
  38
  39 namespace vkt
  40 {
  41 namespace pipeline
  42 {
  43
  44 template <typename T>
  45 class CombinationsIterator
  46 {
  47 public:
  48                                                         CombinationsIterator    (deUint32 numItems, deUint32 combinationSize);
  49         virtual                                 ~CombinationsIterator   (void) {}
  50         bool                                    hasNext                                 (void) const;
  51         T                                               next                                    (void);
  52         void                                    reset                                   (void);
  53
  54 protected:
  55         virtual T                               getCombinationValue             (const std::vector<deUint32>& combination) = 0;
  56
  57 private:
  58         static deUint32                 factorial                               (deUint32 x);
  59         deUint32                                m_numItems;
  60
  61         deUint32                                m_combinationIndex;
  62         deUint32                                m_combinationSize;
  63         deUint32                                m_combinationCount;
  64
  65         std::vector<deUint32>   m_combination;
  66 };
  67
  68 static deUint32 seriesProduct (deUint32 first, deUint32 last)
  69 {
  70         deUint32 result = 1;
  71
  72         for (deUint32 i = first; i <= last; i++)
  73                 result *= i;
  74
  75         return result;
  76 }
  77
  78 template <typename T>
  79 CombinationsIterator<T>::CombinationsIterator (deUint32 numItems, deUint32 combinationSize)
  80         : m_numItems            (numItems)
  81         , m_combinationSize     (combinationSize)
  82 {
  83         DE_ASSERT(m_combinationSize > 0);
  84         DE_ASSERT(m_combinationSize <= m_numItems);
  85
  86         m_combinationCount      = seriesProduct(numItems - combinationSize + 1, numItems) / seriesProduct(1, combinationSize);
  87
  88         m_combination.resize(m_combinationSize);
  89         reset();
  90 }
  91
  92 template <typename T>
  93 bool CombinationsIterator<T>::hasNext (void) const
  94 {
  95         return m_combinationIndex < m_combinationCount;
  96 }
  97
  98 template <typename T>
  99 T CombinationsIterator<T>::next (void)
 100 {
 101         DE_ASSERT(m_combinationIndex < m_combinationCount);
 102
 103         if (m_combinationIndex > 0)
 104         {
 105                 for (int combinationItemNdx = (int)m_combinationSize - 1; combinationItemNdx >= 0; combinationItemNdx--)
 106                 {
 107                         if ((m_combination[combinationItemNdx] + 1 < m_numItems) && ((combinationItemNdx == (int)m_combinationSize - 1) || (m_combination[combinationItemNdx + 1] > m_combination[combinationItemNdx] + 1)))
 108                         {
 109                                 m_combination[combinationItemNdx]++;
 110
 111                                 for (deUint32 resetNdx = combinationItemNdx + 1; resetNdx < m_combinationSize; resetNdx++)
 112                                         m_combination[resetNdx] = m_combination[resetNdx - 1] + 1;
 113
 114                                 break;
 115                         }
 116                 }
 117         }
 118
 119         m_combinationIndex++;
 120
 121         return getCombinationValue(m_combination);
 122 }
 123
 124 template <typename T>
 125 void CombinationsIterator<T>::reset (void)
 126 {
 127         // Set up first combination
 128         for (deUint32 itemNdx = 0; itemNdx < m_combinationSize; itemNdx++)
 129                 m_combination[itemNdx] = itemNdx;
 130
 131         m_combinationIndex = 0;
 132 }
 133
 134 template <typename T>
 135 deUint32 CombinationsIterator<T>::factorial (deUint32 x)
 136 {
 137         deUint32 result = 1;
 138
 139         for (deUint32 value = x; value > 1; value--)
 140                 result *= value;
 141
 142         return result;
 143 }
 144
 145 } // pipeline
 146 } // vkt
 147
 148 #endif // _VKTPIPELINECOMBINATIONSITERATOR_HPP