1// Copyright 2014 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "components/enhanced_bookmarks/item_position.h"
6
7#include "testing/gtest/include/gtest/gtest.h"
8
9using enhanced_bookmarks::ItemPosition;
10
11namespace {
12
13class ItemPositionTest : public testing::Test {};
14
15TEST_F(ItemPositionTest, TestCreateBefore) {
16  ItemPosition current = ItemPosition::CreateInitialPosition();
17  for (int i = 0; i < 10000; i++) {
18    ItemPosition next = ItemPosition::CreateBefore(current);
19    EXPECT_LT(next.ToString(), current.ToString());
20    current = next;
21  }
22  // Make sure string lengths stay reasonable.
23  EXPECT_LT(current.ToString().size(), 20u);
24}
25
26TEST_F(ItemPositionTest, TestCreateAfter) {
27  ItemPosition current = ItemPosition::CreateInitialPosition();
28  for (int i = 0; i < 10000; i++) {
29    ItemPosition next = ItemPosition::CreateAfter(current);
30    EXPECT_GT(next.ToString(), current.ToString());
31    current = next;
32  }
33  // Make sure string lengths stay reasonable.
34  EXPECT_LT(current.ToString().size(), 20u);
35}
36
37TEST_F(ItemPositionTest, TestCreateBetweenLeftBias) {
38  ItemPosition before = ItemPosition::CreateInitialPosition();
39  ItemPosition after = ItemPosition::CreateAfter(before);
40  for (int i = 0; i < 10000; i++) {
41    ItemPosition next = ItemPosition::CreateBetween(before, after);
42    EXPECT_GT(next.ToString(), before.ToString());
43    EXPECT_LT(next.ToString(), after.ToString());
44    after = next;
45  }
46  // Make sure string lengths stay reasonable.
47  EXPECT_LT(after.ToString().size(), 20u);
48}
49
50TEST_F(ItemPositionTest, TestCreateBetweenRightBias) {
51  ItemPosition before = ItemPosition::CreateInitialPosition();
52  ItemPosition after = ItemPosition::CreateAfter(before);
53  for (int i = 0; i < 10000; i++) {
54    ItemPosition next = ItemPosition::CreateBetween(before, after);
55    EXPECT_GT(next.ToString(), before.ToString());
56    EXPECT_LT(next.ToString(), after.ToString());
57    before = next;
58  }
59  // Make sure string lengths stay reasonable.
60  EXPECT_LT(before.ToString().size(), 20u);
61}
62
63TEST_F(ItemPositionTest, TestCreateBetweenAlternating) {
64  ItemPosition before = ItemPosition::CreateInitialPosition();
65  ItemPosition after = ItemPosition::CreateAfter(before);
66  for (int i = 0; i < 1000; i++) {
67    ItemPosition next = ItemPosition::CreateBetween(before, after);
68    EXPECT_GT(next.ToString(), before.ToString());
69    EXPECT_LT(next.ToString(), after.ToString());
70    if ((i & 1) == 1)
71      before = next;
72    else
73      after = next;
74  }
75  // There's no way to keep the string length down for all possible insertion
76  // scenarios, and this one should be fairly rare in practice. Still verify
77  // that at least the growth is restricted to about n*log_2(kPositionBase).
78  EXPECT_LT(before.ToString().size(), 200u);
79}
80
81}  // namespace
82