components/enhanced_bookmarks/item_position.cc

// 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/item_position.h"

#include "base/logging.h"

namespace {
const unsigned kPositionBase = 64;
const char kPositionAlphabet[] =
    ".0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz";
}  // namespace

namespace enhanced_bookmarks {

ItemPosition::ItemPosition() {
}

ItemPosition::ItemPosition(const PositionVector& position)
    : position_(position) {
}

ItemPosition::~ItemPosition() {
}

// static
ItemPosition ItemPosition::CreateInitialPosition() {
  PositionVector position(1, kPositionBase / 2);
  return ItemPosition(position);
}

// static
ItemPosition ItemPosition::CreateBefore(const ItemPosition& other) {
  DCHECK(other.IsValid());
  return ItemPosition(CreateBeforeImpl(other.position_, 0));
}

// static
ItemPosition::PositionVector ItemPosition::CreateBeforeImpl(
    const PositionVector& other,
    size_t from_index) {
  DCHECK_LT(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 to 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
ItemPosition ItemPosition::CreateAfter(const ItemPosition& other) {
  DCHECK(other.IsValid());
  return ItemPosition(CreateAfterImpl(other.position_, 0));
}

// static
ItemPosition::PositionVector ItemPosition::CreateAfterImpl(
    const PositionVector& other,
    size_t from_index) {
  DCHECK_LE(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
ItemPosition ItemPosition::CreateBetween(const ItemPosition& before,
                                         const ItemPosition& after) {
  DCHECK(before.IsValid() && after.IsValid());
  return ItemPosition(CreateBetweenImpl(before.position_, after.position_));
}

// static
ItemPosition::PositionVector ItemPosition::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 ItemPosition::ToString() const {
  DCHECK_GT(arraysize(kPositionAlphabet), kPositionBase);

  std::string str;
  str.reserve(position_.size());
  for (size_t i = 0; i < position_.size(); i++) {
    unsigned char val = position_[i];
    CHECK_LT(val, kPositionBase);
    str.push_back(kPositionAlphabet[position_[i]]);
  }
  return str;
}

bool ItemPosition::IsValid() const {
  return !position_.empty() && position_[position_.size() - 1] != 0;
}

bool ItemPosition::Equals(const ItemPosition& other) const {
  return position_ == other.position_;
}

bool ItemPosition::LessThan(const ItemPosition& other) const {
  return position_ < other.position_;
}

}  // namespace enhanced_bookmarks