104115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com/* 204115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com * Copyright 2012 Google Inc. 304115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com * 404115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com * Use of this source code is governed by a BSD-style license that can be 504115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com * found in the LICENSE file. 604115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com */ 7e4fafb146e85cdfcf9d5418597b6818aa0754adatfarina@chromium.org 804115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com#include "SkTSet.h" 98f6884aab8aecd7657cf3f9cdbc682f0deca29c5tfarina@chromium.org#include "Test.h" 1004115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 1104115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com// Tests the SkTSet<T> class template. 1204115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com// Functions that just call SkTDArray are not tested. 1304115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 1404115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.comstatic void TestTSet_basic(skiatest::Reporter* reporter) { 1504115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com SkTSet<int> set0; 1604115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set0.isEmpty()); 1704115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, !set0.contains(-1)); 1804115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, !set0.contains(0)); 1904115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, !set0.contains(1)); 2004115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set0.count() == 0); 2104115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 2204115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set0.add(0)); 2304115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, !set0.isEmpty()); 2404115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, !set0.contains(-1)); 2504115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set0.contains(0)); 2604115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, !set0.contains(1)); 2704115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set0.count() == 1); 2804115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, !set0.add(0)); 2904115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set0.count() == 1); 3004115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 3104115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com#ifdef SK_DEBUG 3204115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com set0.validate(); 3304115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com#endif 3404115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com} 3504115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 3604115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com#define COUNT 1732 3704115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com#define PRIME1 10007 3804115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com#define PRIME2 1733 3904115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 4004115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com// Generates a series of positive unique pseudo-random numbers. 4104115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.comstatic int f(int i) { 4204115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com return (long(i) * PRIME1) % PRIME2; 4304115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com} 4404115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 45a7aa810894ae85306541ed949848a4dd7f907a0bcommit-bot@chromium.org// Will expose contains() too. 4604115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.comstatic void TestTSet_advanced(skiatest::Reporter* reporter) { 4704115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com SkTSet<int> set0; 4804115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 4904115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com for (int i = 0; i < COUNT; i++) { 5004115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, !set0.contains(f(i))); 5104115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com if (i > 0) { 5204115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set0.contains(f(0))); 5304115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set0.contains(f(i / 2))); 5404115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set0.contains(f(i - 1))); 5504115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com } 5604115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, !set0.contains(f(i))); 5704115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set0.count() == i); 5804115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set0.add(f(i))); 5904115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set0.contains(f(i))); 6004115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set0.count() == i + 1); 6104115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, !set0.add(f(i))); 6204115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com } 6304115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 64a7aa810894ae85306541ed949848a4dd7f907a0bcommit-bot@chromium.org // Test deterministic output 65a7aa810894ae85306541ed949848a4dd7f907a0bcommit-bot@chromium.org for (int i = 0; i < COUNT; i++) { 66a7aa810894ae85306541ed949848a4dd7f907a0bcommit-bot@chromium.org REPORTER_ASSERT(reporter, set0[i] == f(i)); 67a7aa810894ae85306541ed949848a4dd7f907a0bcommit-bot@chromium.org } 68a7aa810894ae85306541ed949848a4dd7f907a0bcommit-bot@chromium.org 6904115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com // Test copy constructor too. 7004115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com SkTSet<int> set1 = set0; 715ca3bd0cbb34cb4e61c0ea3591a4967ee1d6140askia.committer@gmail.com 7204115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set0.count() == set1.count()); 7304115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, !set1.contains(-1000)); 7404115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 7504115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com for (int i = 0; i < COUNT; i++) { 7604115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set1.contains(f(i))); 77a7aa810894ae85306541ed949848a4dd7f907a0bcommit-bot@chromium.org REPORTER_ASSERT(reporter, set1[i] == f(i)); 7804115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com } 795ca3bd0cbb34cb4e61c0ea3591a4967ee1d6140askia.committer@gmail.com 8004115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com // Test operator= too. 8104115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com SkTSet<int> set2; 8204115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com set2 = set0; 8304115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 8404115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set0.count() == set2.count()); 8504115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, !set2.contains(-1000)); 8604115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 8704115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com for (int i = 0; i < COUNT; i++) { 8804115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set2.contains(f(i))); 89a7aa810894ae85306541ed949848a4dd7f907a0bcommit-bot@chromium.org REPORTER_ASSERT(reporter, set2[i] == f(i)); 9004115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com } 9104115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 9204115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com#ifdef SK_DEBUG 9304115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com set0.validate(); 9404115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com set1.validate(); 9504115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com set2.validate(); 9604115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com#endif 9704115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com} 9804115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 9904115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.comstatic void TestTSet_merge(skiatest::Reporter* reporter) { 10004115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com SkTSet<int> set; 10104115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com SkTSet<int> setOdd; 1025ca3bd0cbb34cb4e61c0ea3591a4967ee1d6140askia.committer@gmail.com 10304115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com for (int i = 0; i < COUNT; i++) { 10404115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set.add(2 * i)); 1055ca3bd0cbb34cb4e61c0ea3591a4967ee1d6140askia.committer@gmail.com REPORTER_ASSERT(reporter, setOdd.add(2 * i + 1)); 10604115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com } 10704115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com // mergeInto returns the number of duplicates. Expected 0. 10804115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set.mergeInto(setOdd) == 0); 10904115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set.count() == 2 * COUNT); 11004115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 11104115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com // mergeInto should now find all new numbers duplicate. 11204115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set.mergeInto(setOdd) == setOdd.count()); 11304115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set.count() == 2 * COUNT); 1145ca3bd0cbb34cb4e61c0ea3591a4967ee1d6140askia.committer@gmail.com 11504115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com for (int i = 0; i < 2 * COUNT; i++) { 11604115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com REPORTER_ASSERT(reporter, set.contains(i)); 11704115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com } 11804115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 119a7aa810894ae85306541ed949848a4dd7f907a0bcommit-bot@chromium.org // check deterministic output 120a7aa810894ae85306541ed949848a4dd7f907a0bcommit-bot@chromium.org for (int i = 0; i < COUNT; i++) { 121a7aa810894ae85306541ed949848a4dd7f907a0bcommit-bot@chromium.org REPORTER_ASSERT(reporter, set[i] == 2 * i); 122a7aa810894ae85306541ed949848a4dd7f907a0bcommit-bot@chromium.org REPORTER_ASSERT(reporter, set[COUNT + i] == 2 * i + 1); 123a7aa810894ae85306541ed949848a4dd7f907a0bcommit-bot@chromium.org } 124a7aa810894ae85306541ed949848a4dd7f907a0bcommit-bot@chromium.org 12504115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com#ifdef SK_DEBUG 12604115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com set.validate(); 12704115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com setOdd.validate(); 12804115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com#endif 12904115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com} 13004115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com 131e4fafb146e85cdfcf9d5418597b6818aa0754adatfarina@chromium.orgDEF_TEST(TSet, reporter) { 13204115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com TestTSet_basic(reporter); 13304115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com TestTSet_advanced(reporter); 13404115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com TestTSet_merge(reporter); 13504115a102c8c46b9a6fdcaaa9626f8f92cead49bedisonn@google.com} 136