| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2012 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 "chrome/common/string_ordinal.h" | |
| 6 | |
| 7 #include <algorithm> | |
| 8 #include <cstddef> | |
| 9 | |
| 10 #include "base/basictypes.h" | |
| 11 #include "base/logging.h" | |
| 12 | |
| 13 namespace { | |
| 14 | |
| 15 // Constants for StringOrdinal digits. | |
| 16 const char kZeroDigit = 'a'; | |
| 17 const char kMinDigit = 'b'; | |
| 18 const char kMidDigit = 'n'; | |
| 19 const char kMaxDigit = 'z'; | |
| 20 const int kMidDigitValue = kMidDigit - kZeroDigit; | |
| 21 const int kMaxDigitValue = kMaxDigit - kZeroDigit; | |
| 22 const int kRadix = kMaxDigitValue + 1; | |
| 23 COMPILE_ASSERT(kMidDigitValue == 13, kMidDigitValue_incorrect); | |
| 24 COMPILE_ASSERT(kMaxDigitValue == 25, kMaxDigitValue_incorrect); | |
| 25 COMPILE_ASSERT(kRadix == 26, kRadix_incorrect); | |
| 26 | |
| 27 // Helper Functions | |
| 28 | |
| 29 // Returns the length that string value.substr(0, length) would be with | |
| 30 // trailing zeros removed. | |
| 31 size_t GetLengthWithoutTrailingZeros(const std::string& value, size_t length) { | |
| 32 DCHECK(!value.empty()); | |
| 33 | |
| 34 size_t end_position = value.find_last_not_of(kZeroDigit, length - 1); | |
| 35 | |
| 36 // If no non kZeroDigit is found then the string is a string of all zeros | |
| 37 // digits so we return 0 as the correct length. | |
| 38 if (end_position == std::string::npos) | |
| 39 return 0; | |
| 40 | |
| 41 return end_position + 1; | |
| 42 } | |
| 43 | |
| 44 // Return the digit value at position i, padding with kZeroDigit if required. | |
| 45 int GetPositionValue(const std::string& str, size_t i) { | |
| 46 return (i < str.length()) ? (str[i] - kZeroDigit) : 0; | |
| 47 } | |
| 48 | |
| 49 // Add kMidDigitValue to the value at position index. This returns false if | |
| 50 // adding the half results in an overflow past the first digit, otherwise it | |
| 51 // returns true. This is used by ComputeMidpoint. | |
| 52 bool AddHalf(size_t position, std::string& value) { | |
| 53 DCHECK_GT(position, 0U); | |
| 54 DCHECK_LT(position, value.length()); | |
| 55 | |
| 56 // We can't perform this operation directly on the string because | |
| 57 // overflow can occur and mess up the values. | |
| 58 int new_position_value = value[position] + kMidDigitValue; | |
| 59 | |
| 60 if (new_position_value <= kMaxDigit) { | |
| 61 value[position] = new_position_value; | |
| 62 } else { | |
| 63 value[position] = new_position_value - kRadix; | |
| 64 ++value[position - 1]; | |
| 65 | |
| 66 for (size_t i = position - 1; value[i] > kMaxDigit; --i) { | |
| 67 if (i == 0U) { | |
| 68 // If the first digit is too large we have no previous digit | |
| 69 // to increase, so we fail. | |
| 70 return false; | |
| 71 } | |
| 72 value[i] -= kRadix; | |
| 73 ++value[i - 1]; | |
| 74 } | |
| 75 } | |
| 76 | |
| 77 return true; | |
| 78 } | |
| 79 | |
| 80 // Drops off the last digit of value and then all trailing zeros iff that | |
| 81 // doesn't change its ordering as greater than |start|. | |
| 82 void DropUnneededDigits(const std::string& start, std::string* value) { | |
| 83 CHECK_GT(*value, start); | |
| 84 | |
| 85 size_t drop_length = GetLengthWithoutTrailingZeros(*value, value->length()); | |
| 86 // See if the value can have its last digit removed without affecting | |
| 87 // the ordering. | |
| 88 if (drop_length > 1) { | |
| 89 // We must drop the trailing zeros before comparing |shorter_value| to | |
| 90 // |start| because if we don't we may have |shorter_value|=|start|+|a|* | |
| 91 // where |shorter_value| > |start| but not when it drops the trailing |a|s | |
| 92 // to become a valid StringOrdinal value. | |
| 93 int truncated_length = GetLengthWithoutTrailingZeros(*value, | |
| 94 drop_length - 1); | |
| 95 | |
| 96 if (truncated_length != 0 && value->compare(0, truncated_length, start) > 0) | |
| 97 drop_length = truncated_length; | |
| 98 } | |
| 99 | |
| 100 value->resize(drop_length); | |
| 101 } | |
| 102 | |
| 103 // Compute the midpoint string that is between |start| and |end|. | |
| 104 std::string ComputeMidpoint(const std::string& start, | |
| 105 const std::string& end) { | |
| 106 size_t max_size = std::max(start.length(), end.length()) + 1; | |
| 107 std::string midpoint(max_size, kZeroDigit); | |
| 108 | |
| 109 bool add_half = false; | |
| 110 for (size_t i = 0; i < max_size; ++i) { | |
| 111 int char_value = GetPositionValue(start, i); | |
| 112 char_value += GetPositionValue(end, i); | |
| 113 | |
| 114 midpoint[i] += (char_value / 2); | |
| 115 if (add_half) { | |
| 116 // AddHalf only returns false if (midpoint[0] > kMaxDigit), which | |
| 117 // implies the midpoint of two strings in (0, 1) is >= 1, which is a | |
| 118 // contradiction. | |
| 119 CHECK(AddHalf(i, midpoint)); | |
| 120 } | |
| 121 | |
| 122 add_half = (char_value % 2 == 1); | |
| 123 } | |
| 124 DCHECK(!add_half); | |
| 125 | |
| 126 return midpoint; | |
| 127 } | |
| 128 | |
| 129 // Create a StringOrdinal that is lexigraphically greater than |start| and | |
| 130 // lexigraphically less than |end|. The returned StringOrdinal will be roughly | |
| 131 // between |start| and |end|. | |
| 132 StringOrdinal CreateStringOrdinalBetween(const StringOrdinal& start, | |
| 133 const StringOrdinal& end) { | |
| 134 CHECK(start.IsValid()); | |
| 135 CHECK(end.IsValid()); | |
| 136 CHECK(start.LessThan(end)); | |
| 137 const std::string& start_string = start.ToString(); | |
| 138 const std::string& end_string = end.ToString(); | |
| 139 DCHECK_LT(start_string, end_string); | |
| 140 | |
| 141 std::string midpoint = ComputeMidpoint(start_string, end_string); | |
| 142 | |
| 143 DropUnneededDigits(start_string, &midpoint); | |
| 144 | |
| 145 DCHECK_GT(midpoint, start_string); | |
| 146 DCHECK_LT(midpoint, end_string); | |
| 147 | |
| 148 StringOrdinal midpoint_ordinal(midpoint); | |
| 149 DCHECK(midpoint_ordinal.IsValid()); | |
| 150 return midpoint_ordinal; | |
| 151 } | |
| 152 | |
| 153 // Returns true iff the input string matches the format [a-z]*[b-z]. | |
| 154 bool IsValidStringOrdinal(const std::string& value) { | |
| 155 if (value.empty()) | |
| 156 return false; | |
| 157 | |
| 158 for (size_t i = 0; i < value.length(); ++i) { | |
| 159 if (value[i] < kZeroDigit || value[i] > kMaxDigit) | |
| 160 return false; | |
| 161 } | |
| 162 | |
| 163 return value[value.length() - 1] != kZeroDigit; | |
| 164 } | |
| 165 | |
| 166 } // namespace | |
| 167 | |
| 168 StringOrdinal::StringOrdinal(const std::string& string_ordinal) | |
| 169 : string_ordinal_(string_ordinal), | |
| 170 is_valid_(IsValidStringOrdinal(string_ordinal_)) { | |
| 171 } | |
| 172 | |
| 173 StringOrdinal::StringOrdinal() : string_ordinal_(""), | |
| 174 is_valid_(false) { | |
| 175 } | |
| 176 | |
| 177 StringOrdinal StringOrdinal::CreateInitialOrdinal() { | |
| 178 return StringOrdinal(std::string(1, kMidDigit)); | |
| 179 } | |
| 180 | |
| 181 bool StringOrdinal::IsValid() const { | |
| 182 return is_valid_; | |
| 183 } | |
| 184 | |
| 185 bool StringOrdinal::LessThan(const StringOrdinal& other) const { | |
| 186 CHECK(IsValid()); | |
| 187 CHECK(other.IsValid()); | |
| 188 return string_ordinal_ < other.string_ordinal_; | |
| 189 } | |
| 190 | |
| 191 bool StringOrdinal::GreaterThan(const StringOrdinal& other) const { | |
| 192 CHECK(IsValid()); | |
| 193 CHECK(other.IsValid()); | |
| 194 return string_ordinal_ > other.string_ordinal_; | |
| 195 } | |
| 196 | |
| 197 bool StringOrdinal::Equal(const StringOrdinal& other) const { | |
| 198 CHECK(IsValid()); | |
| 199 CHECK(other.IsValid()); | |
| 200 return string_ordinal_ == other.string_ordinal_; | |
| 201 } | |
| 202 | |
| 203 bool StringOrdinal::EqualOrBothInvalid(const StringOrdinal& other) const { | |
| 204 if (!IsValid() && !other.IsValid()) | |
| 205 return true; | |
| 206 | |
| 207 if (!IsValid() || !other.IsValid()) | |
| 208 return false; | |
| 209 | |
| 210 return Equal(other); | |
| 211 } | |
| 212 | |
| 213 StringOrdinal StringOrdinal::CreateBetween(const StringOrdinal& other) const { | |
| 214 CHECK(IsValid()); | |
| 215 CHECK(other.IsValid()); | |
| 216 CHECK(!Equal(other)); | |
| 217 | |
| 218 if (LessThan(other)) { | |
| 219 return CreateStringOrdinalBetween(*this, other); | |
| 220 } else { | |
| 221 return CreateStringOrdinalBetween(other, *this); | |
| 222 } | |
| 223 } | |
| 224 | |
| 225 StringOrdinal StringOrdinal::CreateBefore() const { | |
| 226 CHECK(IsValid()); | |
| 227 // Create the smallest valid StringOrdinal of the appropriate length | |
| 228 // to be the minimum boundary. | |
| 229 const size_t length = string_ordinal_.length(); | |
| 230 std::string start(length, kZeroDigit); | |
| 231 start[length - 1] = kMinDigit; | |
| 232 if (start == string_ordinal_) { | |
| 233 start[length - 1] = kZeroDigit; | |
| 234 start += kMinDigit; | |
| 235 } | |
| 236 | |
| 237 // Even though |start| is already a valid StringOrdinal that is less | |
| 238 // than |*this|, we don't return it because we wouldn't have much space in | |
| 239 // front of it to insert potential future values. | |
| 240 return CreateBetween(StringOrdinal(start)); | |
| 241 } | |
| 242 | |
| 243 StringOrdinal StringOrdinal::CreateAfter() const { | |
| 244 CHECK(IsValid()); | |
| 245 // Create the largest valid StringOrdinal of the appropriate length to be | |
| 246 // the maximum boundary. | |
| 247 std::string end(string_ordinal_.length(), kMaxDigit); | |
| 248 if (end == string_ordinal_) | |
| 249 end += kMaxDigit; | |
| 250 | |
| 251 // Even though |end| is already a valid StringOrdinal that is greater than | |
| 252 // |*this|, we don't return it because we wouldn't have much space after | |
| 253 // it to insert potential future values. | |
| 254 return CreateBetween(StringOrdinal(end)); | |
| 255 } | |
| 256 | |
| 257 std::string StringOrdinal::ToString() const { | |
| 258 CHECK(IsValid()); | |
| 259 return string_ordinal_; | |
| 260 } | |
| 261 | |
| 262 bool StringOrdinalLessThan::operator() (const StringOrdinal& lhs, | |
| 263 const StringOrdinal& rhs) const { | |
| 264 return lhs.LessThan(rhs); | |
| 265 } | |
| 266 | |
| 267 bool StringOrdinal::operator==(const StringOrdinal& rhs) const { | |
| 268 return Equal(rhs); | |
| 269 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 10920017:
[Sync] Generalize StringOrdinal to handle ordinal_in_parent field (Closed)
Base URL: svn://svn.chromium.org/chrome/trunk/src