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..ccc84da478c8d3f3536070fc14e3ab5274ce789a
--- /dev/null
+++ b/components/enhanced_bookmarks/stars_position.cc
@@ -0,0 +1,170 @@
+// 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";

[Mark, 2014/09/04 21:51:24]

So the key question here is consistency.  What happens when a JS client sets the
FolioInfo.position field?  Will that work consistently with what is being done
here?  What happens if two items end up with the same position field?  How is
that resolved.

[Rune Fevang, 2014/09/04 22:56:47]

It should be similar, though not necessarily an exact match. The alphabet here
is the same as used on the JS side. I wrote a section on duplicate placements in
the doc, basically the only thing we can do is write a new position field using
the underlying bookmark model position to figure out which order they should be
in.

BTW, the sync string position clients append a random suffix to avoid two
clients setting the same position for different nodes, we could consider doing
something similar.

[Mark, 2014/09/05 01:02:00]

That sounds like a good idea.

+}  // 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 {
+  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());
+  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,
+  // (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;
+}
+
+}  // namespace enhanced_bookmarks