components/enhanced_bookmarks/item_position.cc

   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 "base/logging.h"
   8
   9 namespace {
  10 const unsigned kPositionBase = 64;
  11 const char kPositionAlphabet[] =
  12     ".0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz";
  13 }  // namespace
  14
  15 namespace enhanced_bookmarks {
  16
  17 ItemPosition::ItemPosition() {
  18 }
  19
  20 ItemPosition::ItemPosition(const PositionVector& position)
  21     : position_(position) {
  22 }
  23
  24 ItemPosition::~ItemPosition() {
  25 }
  26
  27 // static
  28 ItemPosition ItemPosition::CreateInitialPosition() {
  29   PositionVector position(1, kPositionBase / 2);
  30   return ItemPosition(position);
  31 }
  32
  33 // static
  34 ItemPosition ItemPosition::CreateBefore(const ItemPosition& other) {
  35   DCHECK(other.IsValid());
  36   return ItemPosition(CreateBeforeImpl(other.position_, 0));
  37 }
  38
  39 // static
  40 ItemPosition::PositionVector ItemPosition::CreateBeforeImpl(
  41     const PositionVector& other,
  42     size_t from_index) {
  43   DCHECK_LT(from_index, other.size());
  44   PositionVector before(other.begin() + from_index, other.end());
  45
  46   // Decrement the last character instead of going half-way to 0 in order to
  47   // make sure chaining CreateBefore calls result in logarithmic rather than
  48   // linear length growth.
  49   before[before.size() - 1] /= 2;
  50   if (before[before.size() - 1] != 0) {
  51     // If the last digit didn't change to 0, we're done!
  52     return before;
  53   }
  54
  55   // Reset trailing zeros, then decrement the last non-zero digit.
  56   int index = before.size() - 1;
  57   while (index >= 0 && before[index] == 0) {
  58     before[index--] = kPositionBase / 2;
  59   }
  60
  61   // Negative index means all digits were zeros. Put that many zeros to the
  62   // front of the string to get one that is comes before the input given.
  63   // This will cause the returned string to be twice as long as the input one,
  64   // (and about twice as long as needed for a valid return value), however that
  65   // means this function can be called many times more before we need to
  66   // increase the string size again. Increasing it with the minimum length
  67   // would result in a linear string size growth.
  68   if (index < 0) {
  69     before.insert(before.begin(), before.size(), 0);
  70   } else {
  71     before[index] /= 2;
  72   }
  73   return before;
  74 }
  75
  76 // static
  77 ItemPosition ItemPosition::CreateAfter(const ItemPosition& other) {
  78   DCHECK(other.IsValid());
  79   return ItemPosition(CreateAfterImpl(other.position_, 0));
  80 }
  81
  82 // static
  83 ItemPosition::PositionVector ItemPosition::CreateAfterImpl(
  84     const PositionVector& other,
  85     size_t from_index) {
  86   DCHECK_LE(from_index, other.size());
  87   if (from_index == other.size()) {
  88     return PositionVector(1, kPositionBase / 2);
  89   }
  90
  91   PositionVector after(other.begin() + from_index, other.end());
  92
  93   // Instead of splitting the position with infinity, increment the last digit
  94   // possible, and reset all digits after. This makes sure chaining createAfter
  95   // will result in a logarithmic rather than linear length growth.
  96   size_t index = after.size() - 1;
  97   do {
  98     after[index] += (kPositionBase - after[index] + 1) / 2;
  99     if (after[index] != kPositionBase)
 100       return after;
 101     after[index] = kPositionBase / 2;
 102   } while (index-- > 0);
 103
 104   // All digits must have been at the maximal value already, so the string
 105   // length has to increase. Double it's size to ensure CreateAfter can be
 106   // called exponentially more times every time this needs to happen.
 107   after.insert(after.begin(), after.size(), kPositionBase - 1);
 108
 109   return after;
 110 }
 111
 112 // static
 113 ItemPosition ItemPosition::CreateBetween(const ItemPosition& before,
 114                                          const ItemPosition& after) {
 115   DCHECK(before.IsValid() && after.IsValid());
 116   return ItemPosition(CreateBetweenImpl(before.position_, after.position_));
 117 }
 118
 119 // static
 120 ItemPosition::PositionVector ItemPosition::CreateBetweenImpl(
 121     const PositionVector& before,
 122     const PositionVector& after) {
 123   DCHECK(before < after);
 124
 125   PositionVector between;
 126   for (size_t i = 0; i < before.size(); i++) {
 127     if (before[i] == after[i]) {
 128       // Add the common prefix to the return value.
 129       between.push_back(before[i]);
 130       continue;
 131     }
 132     if (before[i] < after[i] - 1) {
 133       // Split the difference between the two characters.
 134       between.push_back((before[i] + after[i]) / 2);
 135       return between;
 136     }
 137     // The difference between before[i] and after[i] is one character. A valid
 138     // return is that character, plus something that comes after the remaining
 139     // characters of before.
 140     between.push_back(before[i]);
 141     PositionVector suffix = CreateAfterImpl(before, i + 1);
 142     between.insert(between.end(), suffix.begin(), suffix.end());
 143     return between;
 144   }
 145
 146   // |before| must be a prefix of |after|, so return that prefix followed by
 147   // something that comes before the remaining digits of |after|.
 148   PositionVector suffix = CreateBeforeImpl(after, before.size());
 149   between.insert(between.end(), suffix.begin(), suffix.end());
 150   return between;
 151 }
 152
 153 std::string ItemPosition::ToString() const {
 154   DCHECK_GT(arraysize(kPositionAlphabet), kPositionBase);
 155
 156   std::string str;
 157   str.reserve(position_.size());
 158   for (size_t i = 0; i < position_.size(); i++) {
 159     unsigned char val = position_[i];
 160     CHECK_LT(val, kPositionBase);
 161     str.push_back(kPositionAlphabet[position_[i]]);
 162   }
 163   return str;
 164 }
 165
 166 bool ItemPosition::IsValid() const {
 167   return !position_.empty() && position_[position_.size() - 1] != 0;
 168 }
 169
 170 bool ItemPosition::Equals(const ItemPosition& other) const {
 171   return position_ == other.position_;
 172 }
 173
 174 bool ItemPosition::LessThan(const ItemPosition& other) const {
 175   return position_ < other.position_;
 176 }
 177
 178 }  // namespace enhanced_bookmarks