1
2 //
3 // This source file is part of appleseed.
4 // Visit https://appleseedhq.net/ for additional information and resources.
5 //
6 // This software is released under the MIT license.
7 //
8 // Copyright (c) 2010-2013 Francois Beaune, Jupiter Jazz Limited
9 // Copyright (c) 2014-2018 Francois Beaune, The appleseedhq Organization
10 //
11 // Permission is hereby granted, free of charge, to any person obtaining a copy
12 // of this software and associated documentation files (the "Software"), to deal
13 // in the Software without restriction, including without limitation the rights
14 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
15 // copies of the Software, and to permit persons to whom the Software is
16 // furnished to do so, subject to the following conditions:
17 //
18 // The above copyright notice and this permission notice shall be included in
19 // all copies or substantial portions of the Software.
20 //
21 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
24 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
26 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
27 // THE SOFTWARE.
28 //
29
30 // appleseed.foundation headers.
31 #include "foundation/math/cdf.h"
32 #include "foundation/math/fp.h"
33 #include "foundation/utility/test.h"
34
35 using namespace foundation;
36 using namespace std;
37
TEST_SUITE(Foundation_Math_CDF)38 TEST_SUITE(Foundation_Math_CDF)
39 {
40 typedef foundation::CDF<int, double> CDF;
41
42 TEST_CASE(Empty_GivenCDFInInitialState_ReturnsTrue)
43 {
44 CDF cdf;
45
46 EXPECT_TRUE(cdf.empty());
47 }
48
49 TEST_CASE(Valid_GivenCDFInInitialState_ReturnsFalse)
50 {
51 CDF cdf;
52
53 EXPECT_FALSE(cdf.valid());
54 }
55
56 TEST_CASE(Empty_GivenCDFWithOneItem_ReturnsFalse)
57 {
58 CDF cdf;
59 cdf.insert(1, 0.5);
60
61 EXPECT_FALSE(cdf.empty());
62 }
63
64 TEST_CASE(Valid_GivenCDFWithOneItemWithPositiveWeight_ReturnsTrue)
65 {
66 CDF cdf;
67 cdf.insert(1, 0.5);
68
69 EXPECT_TRUE(cdf.valid());
70 }
71
72 TEST_CASE(Valid_GivenCDFWithOneItemWithZeroWeight_ReturnsFalse)
73 {
74 CDF cdf;
75 cdf.insert(1, 0.0);
76
77 EXPECT_FALSE(cdf.valid());
78 }
79
80 TEST_CASE(Clear_GivenCDFWithOneItem_RemovesItem)
81 {
82 CDF cdf;
83 cdf.insert(1, 0.5);
84 cdf.clear();
85
86 EXPECT_TRUE(cdf.empty());
87 }
88
89 TEST_CASE(Clear_GivenCDFWithOneItem_MakesCDFInvalid)
90 {
91 CDF cdf;
92 cdf.insert(1, 0.5);
93 cdf.clear();
94
95 EXPECT_FALSE(cdf.valid());
96 }
97
98 TEST_CASE(Sample_GivenCDFWithOneItemWithPositiveWeight_ReturnsItem)
99 {
100 CDF cdf;
101 cdf.insert(1, 0.5);
102 cdf.prepare();
103
104 const CDF::ItemWeightPair result = cdf.sample(0.5);
105
106 EXPECT_EQ(1, result.first);
107 EXPECT_FEQ(1.0, result.second);
108 }
109
110 struct Fixture
111 {
112 CDF m_cdf;
113
114 Fixture()
115 {
116 m_cdf.insert(1, 0.4);
117 m_cdf.insert(2, 1.6);
118 m_cdf.prepare();
119 }
120 };
121
122 TEST_CASE_F(Sample_GivenInputEqualToZero_ReturnsItems1, Fixture)
123 {
124 const CDF::ItemWeightPair result = m_cdf.sample(0.0);
125
126 EXPECT_EQ(1, result.first);
127 EXPECT_FEQ(0.2, result.second);
128 }
129
130 TEST_CASE_F(Sample_GivenInputEqualTo0_2_ReturnsItems2, Fixture)
131 {
132 const CDF::ItemWeightPair result = m_cdf.sample(0.2);
133
134 EXPECT_EQ(2, result.first);
135 EXPECT_FEQ(0.8, result.second);
136 }
137
138 TEST_CASE_F(Sample_GivenInputNearOne_ReturnsItem2, Fixture)
139 {
140 const CDF::ItemWeightPair result = m_cdf.sample(0.99);
141
142 EXPECT_EQ(2, result.first);
143 EXPECT_FEQ(0.8, result.second);
144 }
145
146 TEST_CASE_F(Sample_GivenInputOneUlpBeforeOne_ReturnsItem2, Fixture)
147 {
148 const double almost_one = shift(1.0, -1);
149 const CDF::ItemWeightPair result = m_cdf.sample(almost_one);
150
151 EXPECT_EQ(2, result.first);
152 EXPECT_FEQ(0.8, result.second);
153 }
154
155 TEST_CASE(TwoDimensional_CDF_Exploration)
156 {
157 CDF child[2];
158
159 child[0].insert(1, 0.3);
160 child[0].insert(2, 0.7);
161 child[0].prepare();
162
163 child[1].insert(3, 0.1);
164 child[1].insert(4, 0.4);
165 child[1].prepare();
166
167 CDF parent;
168 parent.insert(0, child[0].weight());
169 parent.insert(1, child[1].weight());
170 parent.prepare();
171
172 const double x = 0.3; // will choose child[0]
173 const double y = 0.6; // will choose value 2
174
175 const CDF::ItemWeightPair u = parent.sample(x);
176 const CDF::ItemWeightPair v = child[u.first].sample(y);
177
178 const int value = v.first;
179 const double prob = u.second * v.second;
180
181 EXPECT_EQ(2, value);
182 EXPECT_FEQ(0.7 * (2.0 / 3), prob);
183 }
184
185 TEST_CASE(SampleCDF)
186 {
187 static const double Cdf[] =
188 {
189 0.03, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0
190 };
191
192 static const double Weights[] =
193 {
194 0.0, 0.07, 0.15, 0.23, 0.41, 0.77, 0.98
195 };
196
197 static const size_t Result[] =
198 {
199 0, 1, 2, 3, 5, 8, 10
200 };
201
202 const double* begin = Cdf;
203 const double* end = Cdf + countof(Cdf);
204
205 for (size_t i = 0, e = countof(Result); i < e; ++i)
206 EXPECT_EQ(Result[i], sample_cdf(begin, end, Weights[i]));
207 }
208
209 TEST_CASE(SampleCDFLinearSearch)
210 {
211 static const double Cdf[] =
212 {
213 0.03, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0
214 };
215
216 static const double Weights[] =
217 {
218 0.0, 0.07, 0.15, 0.23, 0.41, 0.77, 0.98
219 };
220
221 static const size_t Result[] =
222 {
223 0, 1, 2, 3, 5, 8, 10
224 };
225
226 for (size_t i = 0, e = countof(Result); i < e; ++i)
227 EXPECT_EQ(Result[i], sample_cdf_linear_search(Cdf, Weights[i]));
228 }
229 }
230