Introduce ItemPosition class for enhanced bookmarks.

components/enhanced_bookmarks/stars_position_unittest.cc

Index: components/enhanced_bookmarks/stars_position_unittest.cc
diff --git a/components/enhanced_bookmarks/stars_position_unittest.cc b/components/enhanced_bookmarks/stars_position_unittest.cc
new file mode 100644
index 0000000000000000000000000000000000000000..c99cc605b2f512ada1abc069bd7f270296e5a31f
--- /dev/null
+++ b/components/enhanced_bookmarks/stars_position_unittest.cc
@@ -0,0 +1,81 @@
+// Copyright 2014 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 "components/enhanced_bookmarks/stars_position.h"
+
+#include "testing/gtest/include/gtest/gtest.h"
+
+using enhanced_bookmarks::StarsPosition;
+
+namespace {
+
+class StarsPositionTest : public testing::Test {};
+
+TEST_F(StarsPositionTest, TestCreateBefore) {
+  StarsPosition current = StarsPosition::CreateInitialPosition();
+  for (int i = 0; i < 10000; i++) {
+    StarsPosition next = StarsPosition::CreateBefore(current);
+    EXPECT_LT(next.ToString(), current.ToString());
+    current = next;
+  }
+  // Make sure string lengths stay reasonable.
+  EXPECT_LT(current.ToString().size(), 20u);
+}
+
+TEST_F(StarsPositionTest, TestCreateAfter) {
+  StarsPosition current = StarsPosition::CreateInitialPosition();
+  for (int i = 0; i < 10000; i++) {
+    StarsPosition next = StarsPosition::CreateAfter(current);
+    EXPECT_GT(next.ToString(), current.ToString());
+    current = next;
+  }
+  // Make sure string lengths stay reasonable.
+  EXPECT_LT(current.ToString().size(), 20u);
+}
+
+TEST_F(StarsPositionTest, TestCreateBetweenLeftBias) {
+  StarsPosition before = StarsPosition::CreateInitialPosition();
+  StarsPosition after = StarsPosition::CreateAfter(before);
+  for (int i = 0; i < 10000; i++) {
+    StarsPosition next = StarsPosition::CreateBetween(before, after);
+    EXPECT_GT(next.ToString(), before.ToString());
+    EXPECT_LT(next.ToString(), after.ToString());
+    after = next;
+  }
+  // Make sure string lengths stay reasonable.
+  EXPECT_LT(after.ToString().size(), 20u);
+}
+
+TEST_F(StarsPositionTest, TestCreateBetweenRightBias) {
+  StarsPosition before = StarsPosition::CreateInitialPosition();
+  StarsPosition after = StarsPosition::CreateAfter(before);
+  for (int i = 0; i < 10000; i++) {
+    StarsPosition next = StarsPosition::CreateBetween(before, after);
+    EXPECT_GT(next.ToString(), before.ToString());
+    EXPECT_LT(next.ToString(), after.ToString());
+    before = next;
+  }
+  // Make sure string lengths stay reasonable.
+  EXPECT_LT(before.ToString().size(), 20u);
+}
+
+TEST_F(StarsPositionTest, TestCreateBetweenAlternating) {
+  StarsPosition before = StarsPosition::CreateInitialPosition();
+  StarsPosition after = StarsPosition::CreateAfter(before);
+  for (int i = 0; i < 1000; i++) {
+    StarsPosition next = StarsPosition::CreateBetween(before, after);
+    EXPECT_GT(next.ToString(), before.ToString());
+    EXPECT_LT(next.ToString(), after.ToString());
+    if ((i & 1) == 1)
+      before = next;
+    else
+      after = next;
+  }
+  // There's no way to keep the string length down for all possible insertion
+  // scenarios, and this one should be fairly rare in practice. Still verify
+  // that at least the growth is restricted to about n*log_2(kPositionBase).
+  EXPECT_LT(before.ToString().size(), 200u);
+}
+
+}  // namespace