// Copyright (c) 2012 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "base/basictypes.h"
#include "sync/internal_api/public/base/node_ordinal.h"
#include "testing/gtest/include/gtest/gtest.h"

#include <algorithm>
#include <cstddef>

namespace syncer {

namespace {

const int64 kTestValues[] = {
  0LL,
  1LL, -1LL,
  2LL, -2LL,
  3LL, -3LL,
  0x79LL, -0x79LL,
  0x80LL, -0x80LL,
  0x81LL, -0x81LL,
  0xFELL, -0xFELL,
  0xFFLL, -0xFFLL,
  0x100LL, -0x100LL,
  0x101LL, -0x101LL,
  0xFA1AFELL, -0xFA1AFELL,
  0xFFFFFFFELL, -0xFFFFFFFELL,
  0xFFFFFFFFLL, -0xFFFFFFFFLL,
  0x100000000LL, -0x100000000LL,
  0x100000001LL, -0x100000001LL,
  0xFFFFFFFFFFLL, -0xFFFFFFFFFFLL,
  0x112358132134LL, -0x112358132134LL,
  0xFEFFBEEFABC1234LL, -0xFEFFBEEFABC1234LL,
  kint64max,
  kint64min,
  kint64min + 1,
  kint64max - 1
};

const size_t kNumTestValues = arraysize(kTestValues);

// Convert each test value to an ordinal.  All ordinals should be
// valid.
TEST(NodeOrdinalTest, IsValid) {
  for (size_t i = 0; i < kNumTestValues; ++i) {
    const NodeOrdinal ordinal = Int64ToNodeOrdinal(kTestValues[i]);
    EXPECT_TRUE(ordinal.IsValid()) << "i = " << i;
  }
}

// Convert each test value to an ordinal.  All ordinals should have
// 8-byte strings, except for kint64min, which should have a 9-byte
// string.
TEST(NodeOrdinalTest, Size) {
  EXPECT_EQ(9U, Int64ToNodeOrdinal(kint64min).ToInternalValue().size());

  for (size_t i = 0; i < kNumTestValues; ++i) {
    if (kTestValues[i] == kint64min) {
      continue;
    }
    const NodeOrdinal ordinal = Int64ToNodeOrdinal(kTestValues[i]);
    EXPECT_EQ(8U, ordinal.ToInternalValue().size()) << "i = " << i;
  }
}

// Convert each test value to an ordinal and back.  That resulting
// value should be equal to the original value.
TEST(NodeOrdinalTest, PositionToOrdinalToPosition) {
  for (size_t i = 0; i < kNumTestValues; ++i) {
    const int64 expected_value = kTestValues[i];
    const NodeOrdinal ordinal = Int64ToNodeOrdinal(expected_value);
    const int64 value = NodeOrdinalToInt64(ordinal);
    EXPECT_EQ(expected_value, value) << "i = " << i;
  }
}

template <typename T, typename LessThan = std::less<T> >
class IndexedLessThan {
 public:
  IndexedLessThan(const T* values) : values_(values) {}

  bool operator()(int i1, int i2) {
    return less_than_(values_[i1], values_[i2]);
  }

 private:
  const T* values_;
  LessThan less_than_;
};

// Sort kTestValues by int64 value and then sort it by NodeOrdinal
// value.  kTestValues should not already be sorted (by either
// comparator) and the two orderings should be the same.
TEST(NodeOrdinalTest, ConsistentOrdering) {
  NodeOrdinal ordinals[kNumTestValues];
  std::vector<int> original_ordering(kNumTestValues);
  std::vector<int> int64_ordering(kNumTestValues);
  std::vector<int> ordinal_ordering(kNumTestValues);
  for (size_t i = 0; i < kNumTestValues; ++i) {
    ordinals[i] = Int64ToNodeOrdinal(kTestValues[i]);
    original_ordering[i] = int64_ordering[i] = ordinal_ordering[i] = i;
  }

  std::sort(int64_ordering.begin(), int64_ordering.end(),
            IndexedLessThan<int64>(kTestValues));
  std::sort(ordinal_ordering.begin(), ordinal_ordering.end(),
            IndexedLessThan<NodeOrdinal, NodeOrdinal::LessThanFn>(ordinals));
  EXPECT_NE(original_ordering, int64_ordering);
  EXPECT_EQ(int64_ordering, ordinal_ordering);
}

// Create two NodeOrdinals and create another one between them.  It
// should lie halfway between them.
TEST(NodeOrdinalTest, CreateBetween) {
  const NodeOrdinal ordinal1("\1\1\1\1\1\1\1\1");
  const NodeOrdinal ordinal2("\1\1\1\1\1\1\1\3");
  EXPECT_EQ("\1\1\1\1\1\1\1\2",
            ordinal1.CreateBetween(ordinal2).ToInternalValue());
}

}  // namespace

}  // namespace syncer