| // Copyright (c) 2012 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 "chrome/common/string_ordinal.h" |
| |
| #include <algorithm> |
| #include <cstddef> |
| |
| #include "base/basictypes.h" |
| #include "base/logging.h" |
| |
| namespace { |
| |
| // Constants for StringOrdinal digits. |
| const char kZeroDigit = 'a'; |
| const char kMinDigit = 'b'; |
| const char kMidDigit = 'n'; |
| const char kMaxDigit = 'z'; |
| const int kMidDigitValue = kMidDigit - kZeroDigit; |
| const int kMaxDigitValue = kMaxDigit - kZeroDigit; |
| const int kRadix = kMaxDigitValue + 1; |
| COMPILE_ASSERT(kMidDigitValue == 13, kMidDigitValue_incorrect); |
| COMPILE_ASSERT(kMaxDigitValue == 25, kMaxDigitValue_incorrect); |
| COMPILE_ASSERT(kRadix == 26, kRadix_incorrect); |
| |
| // Helper Functions |
| |
| // Returns the length that string value.substr(0, length) would be with |
| // trailing zeros removed. |
| size_t GetLengthWithoutTrailingZeros(const std::string& value, size_t length) { |
| DCHECK(!value.empty()); |
| |
| size_t end_position = value.find_last_not_of(kZeroDigit, length - 1); |
| |
| // If no non kZeroDigit is found then the string is a string of all zeros |
| // digits so we return 0 as the correct length. |
| if (end_position == std::string::npos) |
| return 0; |
| |
| return end_position + 1; |
| } |
| |
| // Return the digit value at position i, padding with kZeroDigit if required. |
| int GetPositionValue(const std::string& str, size_t i) { |
| return (i < str.length()) ? (str[i] - kZeroDigit) : 0; |
| } |
| |
| // Add kMidDigitValue to the value at position index. This returns false if |
| // adding the half results in an overflow past the first digit, otherwise it |
| // returns true. This is used by ComputeMidpoint. |
| bool AddHalf(size_t position, std::string& value) { |
| DCHECK_GT(position, 0U); |
| DCHECK_LT(position, value.length()); |
| |
| // We can't perform this operation directly on the string because |
| // overflow can occur and mess up the values. |
| int new_position_value = value[position] + kMidDigitValue; |
| |
| if (new_position_value <= kMaxDigit) { |
| value[position] = new_position_value; |
| } else { |
| value[position] = new_position_value - kRadix; |
| ++value[position - 1]; |
| |
| for (size_t i = position - 1; value[i] > kMaxDigit; --i) { |
| if (i == 0U) { |
| // If the first digit is too large we have no previous digit |
| // to increase, so we fail. |
| return false; |
| } |
| value[i] -= kRadix; |
| ++value[i - 1]; |
| } |
| } |
| |
| return true; |
| } |
| |
| // Drops off the last digit of value and then all trailing zeros iff that |
| // doesn't change its ordering as greater than |start|. |
| void DropUnneededDigits(const std::string& start, std::string* value) { |
| CHECK_GT(*value, start); |
| |
| size_t drop_length = GetLengthWithoutTrailingZeros(*value, value->length()); |
| // See if the value can have its last digit removed without affecting |
| // the ordering. |
| if (drop_length > 1) { |
| // We must drop the trailing zeros before comparing |shorter_value| to |
| // |start| because if we don't we may have |shorter_value|=|start|+|a|* |
| // where |shorter_value| > |start| but not when it drops the trailing |a|s |
| // to become a valid StringOrdinal value. |
| int truncated_length = GetLengthWithoutTrailingZeros(*value, |
| drop_length - 1); |
| |
| if (truncated_length != 0 && value->compare(0, truncated_length, start) > 0) |
| drop_length = truncated_length; |
| } |
| |
| value->resize(drop_length); |
| } |
| |
| // Compute the midpoint string that is between |start| and |end|. |
| std::string ComputeMidpoint(const std::string& start, |
| const std::string& end) { |
| size_t max_size = std::max(start.length(), end.length()) + 1; |
| std::string midpoint(max_size, kZeroDigit); |
| |
| bool add_half = false; |
| for (size_t i = 0; i < max_size; ++i) { |
| int char_value = GetPositionValue(start, i); |
| char_value += GetPositionValue(end, i); |
| |
| midpoint[i] += (char_value / 2); |
| if (add_half) { |
| // AddHalf only returns false if (midpoint[0] > kMaxDigit), which |
| // implies the midpoint of two strings in (0, 1) is >= 1, which is a |
| // contradiction. |
| CHECK(AddHalf(i, midpoint)); |
| } |
| |
| add_half = (char_value % 2 == 1); |
| } |
| DCHECK(!add_half); |
| |
| return midpoint; |
| } |
| |
| // Create a StringOrdinal that is lexigraphically greater than |start| and |
| // lexigraphically less than |end|. The returned StringOrdinal will be roughly |
| // between |start| and |end|. |
| StringOrdinal CreateStringOrdinalBetween(const StringOrdinal& start, |
| const StringOrdinal& end) { |
| CHECK(start.IsValid()); |
| CHECK(end.IsValid()); |
| CHECK(start.LessThan(end)); |
| const std::string& start_string = start.ToString(); |
| const std::string& end_string = end.ToString(); |
| DCHECK_LT(start_string, end_string); |
| |
| std::string midpoint = ComputeMidpoint(start_string, end_string); |
| |
| DropUnneededDigits(start_string, &midpoint); |
| |
| DCHECK_GT(midpoint, start_string); |
| DCHECK_LT(midpoint, end_string); |
| |
| StringOrdinal midpoint_ordinal(midpoint); |
| DCHECK(midpoint_ordinal.IsValid()); |
| return midpoint_ordinal; |
| } |
| |
| // Returns true iff the input string matches the format [a-z]*[b-z]. |
| bool IsValidStringOrdinal(const std::string& value) { |
| if (value.empty()) |
| return false; |
| |
| for (size_t i = 0; i < value.length(); ++i) { |
| if (value[i] < kZeroDigit || value[i] > kMaxDigit) |
| return false; |
| } |
| |
| return value[value.length() - 1] != kZeroDigit; |
| } |
| |
| } // namespace |
| |
| StringOrdinal::StringOrdinal(const std::string& string_ordinal) |
| : string_ordinal_(string_ordinal), |
| is_valid_(IsValidStringOrdinal(string_ordinal_)) { |
| } |
| |
| StringOrdinal::StringOrdinal() : string_ordinal_(""), |
| is_valid_(false) { |
| } |
| |
| StringOrdinal StringOrdinal::CreateInitialOrdinal() { |
| return StringOrdinal(std::string(1, kMidDigit)); |
| } |
| |
| bool StringOrdinal::IsValid() const { |
| return is_valid_; |
| } |
| |
| bool StringOrdinal::LessThan(const StringOrdinal& other) const { |
| CHECK(IsValid()); |
| CHECK(other.IsValid()); |
| return string_ordinal_ < other.string_ordinal_; |
| } |
| |
| bool StringOrdinal::GreaterThan(const StringOrdinal& other) const { |
| CHECK(IsValid()); |
| CHECK(other.IsValid()); |
| return string_ordinal_ > other.string_ordinal_; |
| } |
| |
| bool StringOrdinal::Equal(const StringOrdinal& other) const { |
| CHECK(IsValid()); |
| CHECK(other.IsValid()); |
| return string_ordinal_ == other.string_ordinal_; |
| } |
| |
| StringOrdinal StringOrdinal::CreateBetween(const StringOrdinal& other) const { |
| CHECK(IsValid()); |
| CHECK(other.IsValid()); |
| CHECK(!Equal(other)); |
| |
| if (LessThan(other)) { |
| return CreateStringOrdinalBetween(*this, other); |
| } else { |
| return CreateStringOrdinalBetween(other, *this); |
| } |
| } |
| |
| StringOrdinal StringOrdinal::CreateBefore() const { |
| CHECK(IsValid()); |
| // Create the smallest valid StringOrdinal of the appropriate length |
| // to be the minimum boundary. |
| const size_t length = string_ordinal_.length(); |
| std::string start(length, kZeroDigit); |
| start[length - 1] = kMinDigit; |
| if (start == string_ordinal_) { |
| start[length - 1] = kZeroDigit; |
| start += kMinDigit; |
| } |
| |
| // Even though |start| is already a valid StringOrdinal that is less |
| // than |*this|, we don't return it because we wouldn't have much space in |
| // front of it to insert potential future values. |
| return CreateBetween(StringOrdinal(start)); |
| } |
| |
| StringOrdinal StringOrdinal::CreateAfter() const { |
| CHECK(IsValid()); |
| // Create the largest valid StringOrdinal of the appropriate length to be |
| // the maximum boundary. |
| std::string end(string_ordinal_.length(), kMaxDigit); |
| if (end == string_ordinal_) |
| end += kMaxDigit; |
| |
| // Even though |end| is already a valid StringOrdinal that is greater than |
| // |*this|, we don't return it because we wouldn't have much space after |
| // it to insert potential future values. |
| return CreateBetween(StringOrdinal(end)); |
| } |
| |
| std::string StringOrdinal::ToString() const { |
| CHECK(IsValid()); |
| return string_ordinal_; |
| } |
| |
| bool StringOrdinalLessThan::operator() (const StringOrdinal& lhs, |
| const StringOrdinal& rhs) const { |
| return lhs.LessThan(rhs); |
| } |
| |
| bool StringOrdinal::operator==(const StringOrdinal& rhs) const { |
| return Equal(rhs); |
| } |