Introduce ItemPosition class for enhanced bookmarks.

components/enhanced_bookmarks/stars_position.cc

Index: components/enhanced_bookmarks/stars_position.cc
diff --git a/components/enhanced_bookmarks/stars_position.cc b/components/enhanced_bookmarks/stars_position.cc
new file mode 100644
index 0000000000000000000000000000000000000000..bc7f3298ed83cb9a5c8c1ab3f7a227ee2fe0acf2
--- /dev/null
+++ b/components/enhanced_bookmarks/stars_position.cc
@@ -0,0 +1,178 @@
+// 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 "base/logging.h"
+
+namespace {
+const int kPositionBase = 64;
+const char kPositionAlphabet[] =
+    ".0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz";
+}  // namespace
+
+namespace enhanced_bookmarks {
+
+StarsPosition::StarsPosition() {
+}
+
+StarsPosition::StarsPosition(const PositionVector& position)
+    : position_(position) {
+}
+
+StarsPosition::~StarsPosition() {
+}
+
+// static
+StarsPosition StarsPosition::CreateInitialPosition() {
+  PositionVector position(1, kPositionBase / 2);
+  return StarsPosition(position);
+}
+
+bool StarsPosition::IsValid() const {

[Yaron, 2014/09/05 03:52:02]

nit: ordering should match header file

[Rune Fevang, 2014/09/05 19:02:30]

Done.

+  return !position_.empty() && position_[position_.size() - 1] != 0;
+}
+
+// static
+StarsPosition StarsPosition::CreateBefore(const StarsPosition& other) {
+  DCHECK(other.IsValid());
+  return StarsPosition(CreateBeforeImpl(other.position_, 0));
+}
+
+// static
+StarsPosition::PositionVector StarsPosition::CreateBeforeImpl(
+    const PositionVector& other,
+    size_t from_index) {
+  DCHECK(from_index < other.size());

[Yaron, 2014/09/05 03:52:02]

DCHECK_LT (and similar changes throughout)

[Rune Fevang, 2014/09/05 19:02:30]

Done.

+  PositionVector before(other.begin() + from_index, other.end());
+
+  // Decrement the last character instead of going half-way to 0 in order to
+  // make sure chaining CreateBefore calls result in logarithmic rather than
+  // linear length growth.
+  before[before.size() - 1] /= 2;
+  if (before[before.size() - 1] != 0) {
+    // If the last digit didn't change to 0, we're done!
+    return before;
+  }
+
+  // Reset trailing zeros, then decrement the last non-zero digit.
+  int index = before.size() - 1;
+  while (index >= 0 && before[index] == 0) {
+    before[index--] = kPositionBase / 2;
+  }
+
+  // Negative index means all digits were zeros. Put that many zeros to the
+  // front of the string to get one that is comes before the input given.
+  // This will cause the returned string will be twice as long as the input one,

[Yaron, 2014/09/05 03:52:02]

Needs slight reversing. "returned string to be twice"

[Yaron, 2014/09/05 03:52:22]

err. "revising"

[Rune Fevang, 2014/09/05 19:02:30]

Done.

+  // (and about twice as long as needed for a valid return value), however that
+  // means this function can be called many times more before we need to
+  // increase the string size again. Increasing it with the minimum length
+  // would result in a linear string size growth.
+  if (index < 0) {
+    before.insert(before.begin(), before.size(), 0);
+  } else {
+    before[index] /= 2;
+  }
+  return before;
+}
+
+// static
+StarsPosition StarsPosition::CreateAfter(const StarsPosition& other) {
+  DCHECK(other.IsValid());
+  return StarsPosition(CreateAfterImpl(other.position_, 0));
+}
+
+// static
+StarsPosition::PositionVector StarsPosition::CreateAfterImpl(
+    const PositionVector& other,
+    size_t from_index) {
+  DCHECK(from_index <= other.size());
+  if (from_index == other.size()) {
+    return PositionVector(1, kPositionBase / 2);
+  }
+
+  PositionVector after(other.begin() + from_index, other.end());
+
+  // Instead of splitting the position with infinity, increment the last digit
+  // possible, and reset all digits after. This makes sure chaining createAfter
+  // will result in a logarithmic rather than linear length growth.
+  size_t index = after.size() - 1;
+  do {
+    after[index] += (kPositionBase - after[index] + 1) / 2;
+    if (after[index] != kPositionBase)
+      return after;
+    after[index] = kPositionBase / 2;
+  } while (index-- > 0);
+
+  // All digits must have been at the maximal value already, so the string
+  // length has to increase. Double it's size to ensure CreateAfter can be
+  // called exponentially more times every time this needs to happen.
+  after.insert(after.begin(), after.size(), kPositionBase - 1);
+
+  return after;
+}
+
+// static
+StarsPosition StarsPosition::CreateBetween(const StarsPosition& before,
+                                           const StarsPosition& after) {
+  DCHECK(before.IsValid() && after.IsValid());
+  return StarsPosition(CreateBetweenImpl(before.position_, after.position_));
+}
+
+// static
+StarsPosition::PositionVector StarsPosition::CreateBetweenImpl(
+    const PositionVector& before,
+    const PositionVector& after) {
+  DCHECK(before < after);
+
+  PositionVector between;
+  for (size_t i = 0; i < before.size(); i++) {
+    if (before[i] == after[i]) {
+      // Add the common prefix to the return value.
+      between.push_back(before[i]);
+      continue;
+    }
+    if (before[i] < after[i] - 1) {
+      // Split the difference between the two characters.
+      between.push_back((before[i] + after[i]) / 2);
+      return between;
+    }
+    // The difference between before[i] and after[i] is one character. A valid
+    // return is that character, plus something that comes after the remaining
+    // characters of before.
+    between.push_back(before[i]);
+    PositionVector suffix = CreateAfterImpl(before, i + 1);
+    between.insert(between.end(), suffix.begin(), suffix.end());
+    return between;
+  }
+
+  // |before| must be a prefix of |after|, so return that prefix followed by
+  // something that comes before the remaining digits of |after|.
+  PositionVector suffix = CreateBeforeImpl(after, before.size());
+  between.insert(between.end(), suffix.begin(), suffix.end());
+  return between;
+}
+
+std::string StarsPosition::ToString() const {
+  DCHECK(arraysize(kPositionAlphabet) > kPositionBase);
+
+  std::string str;
+  str.reserve(position_.size());
+  for (size_t i = 0; i < position_.size(); i++) {
+    int val = position_[i];
+    CHECK(val >= 0 && val < kPositionBase);
+    str.push_back(kPositionAlphabet[position_[i]]);
+  }
+  return str;
+}
+
+bool StarsPosition::Equals(const StarsPosition& other) {
+  return position_ == other.position_;
+}
+
+bool StarsPosition::LessThan(const StarsPosition& other) {
+  return position_ < other.position_;
+}
+
+}  // namespace enhanced_bookmarks