1 /** 2 * Copyright 2019 Huawei Technologies Co., Ltd 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 #include "minddata/dataset/util/treap.h" 17 #include "common/common.h" 18 #include "gtest/gtest.h" 19 20 using namespace mindspore::dataset; 21 22 class MindDataTestTreap : public UT::Common { 23 public: 24 MindDataTestTreap() {} 25 }; 26 27 TEST_F(MindDataTestTreap, TestALLFunction) { 28 Treap<uint64_t, uint64_t> tree; 29 srand(time(NULL)); 30 for (uint64_t i = 0; i < 1000; i++) { 31 uint64_t sz = rand() % 500; 32 tree.Insert(i, sz); 33 } 34 35 EXPECT_EQ(tree.size(), 1000); 36 37 int n = 0; 38 uint64_t key = 0; 39 for (auto it : tree) { 40 if (n > 0) { 41 EXPECT_GT(it.key, key); 42 } 43 key = it.key; 44 n++; 45 } 46 47 EXPECT_EQ(n, 1000); 48 49 uint64_t prev = 0; 50 n = 0; 51 while (!tree.empty()) { 52 auto p = tree.Top(); 53 EXPECT_TRUE(p.second); 54 uint64_t v = p.first.priority; 55 if (n > 0) { 56 EXPECT_GE(prev, v); 57 } 58 prev = v; 59 n++; 60 tree.Pop(); 61 } 62 } 63