[Sync] Generalize StringOrdinal to handle ordinal_in_parent field

sync/internal_api/public/base/node_ordinal_unittest.cc

+// 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).ToString().size());
+
+  for (size_t i = 0; i < kNumTestValues; ++i) {
+    if (kTestValues[i] == kint64min) {
+      continue;
+    }
+    const NodeOrdinal ordinal = Int64ToNodeOrdinal(kTestValues[i]);
+    EXPECT_EQ(8U, ordinal.ToString().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.  The two orderings should be the same.
+TEST(NodeOrdinalTest, ConsistentOrdering) {

[rlarocque, 2012/09/05 21:43:46]

Good test.  

I have one suggestion, though.  As I understand it, both of these arrays start
off sorted.  Could you mix up the order a bit so the sort function has some work
to do?  Otherwise, the LessThan function could be hard-coded to 'return false'
and this test would not catch it, for some implementations of sort().

One option would be to add a 'reversed_ordinal_ordering' and sort it, too, then
check that all three orderings end up being equal.

[akalin, 2012/09/06 19:25:14]

The sorting does do work.  Remember that these arrays represent indices into the
ordinals array, so they start off sorted, and then get jumbled up to represent
the sorted order of their respective arrays.

Added check to make sure that the original ordering != the sorted ordering,
though.

[rlarocque, 2012/09/06 21:25:55]

Sounds good.  I misread the kTestValues.

+  NodeOrdinal ordinals[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]);
+    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_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).ToString());
+}
+
+}  // namespace
+
+}  // namespace syncer