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 179