/*
 * Copyright 2017 Facebook, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <folly/SparseByteSet.h>

#include <cstdint>
#include <limits>
#include <random>
#include <set>

#include <folly/portability/GTest.h>

using namespace std;
using namespace folly;

namespace {

class SparseByteSetTest : public testing::Test {
 protected:
  using lims = numeric_limits<uint8_t>;
  SparseByteSet s;
};

}

TEST_F(SparseByteSetTest, empty) {
  for (auto c = lims::min(); c < lims::max(); ++c) {
    EXPECT_FALSE(s.contains(c));
  }
}

TEST_F(SparseByteSetTest, each) {
  for (auto c = lims::min(); c < lims::max(); ++c) {
    EXPECT_TRUE(s.add(c));
    EXPECT_TRUE(s.contains(c));
  }
  for (auto c = lims::min(); c < lims::max(); ++c) {
    EXPECT_FALSE(s.add(c));
    EXPECT_TRUE(s.contains(c));
  }
}

TEST_F(SparseByteSetTest, each_random) {
  mt19937 rng;
  uniform_int_distribution<uint16_t> dist{lims::min(), lims::max()};
  set<uint8_t> added;
  while (added.size() <= lims::max()) {
    auto c = uint8_t(dist(rng));
    EXPECT_EQ(added.count(c), s.contains(c));
    EXPECT_EQ(!added.count(c), s.add(c));
    added.insert(c);
    EXPECT_TRUE(added.count(c)); // sanity
    EXPECT_TRUE(s.contains(c));
  }
}
