Create StringOrdinal to allow placement of strings in sorted lists

chrome/common/string_ordinal.cc

+// Copyright (c) 2011 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());
+
+  int end_position = length - 1;
+  while (value[end_position] == kZeroDigit) {

[MAD, 2011/10/25 15:13:29]

Check for end_position > 0

[akalin, 2011/10/25 17:22:19]

Ah, right.  The implicit cast to int is gross, too.  This should probably look
like:

while ((length > 0) && (value[length - 1] == kZeroDigit) {
  --length;
}

return length;

+    --end_position;
+  }
+
+  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 is used by
+// ComputeMidpoint.
+void AddHalf(size_t position, std::string& value) {
+  DCHECK_GT(position, 0U);

[MAD, 2011/10/25 15:13:29]

Also check that position is LT size...

+
+  // 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) {
+      CHECK_GT(i, 0U);

[MAD, 2011/10/25 15:13:29]

So we crash when all previous values have reached max???

[akalin, 2011/10/25 17:22:19]

Yeah, you're right.  This should probably return a carry bit and the caller can
check that instead (I don't think it's possible to actually hit this case with
the caller)

[csharp1, 2011/10/25 18:50:48]

We would, but this case can't occur.

For this to occur the digit infront would need to be kMaxDigit, but it also
needed to require an extra digit to represent the difference between the two
digits it used as input, so it's input can't be (kMaxDigit, kMaxDigit). This
means the inorder for it to still have the value of kMaxDigit, add half needed
to be called on it as well. The same argument applies and all digits would
require addhalf to be called on them, however the first digit can never have
addhalf called on it (because there is no digit before), so it can't make
addhalf added to the next value and also have the value kMaxDigit, so we never
have this case.

Hopefully I did ok job of explaining it, took me a few rewrite to get it
sounding better.

+      value[i] -= kRadix;
+      ++value[i - 1];
+    }
+  }
+}
+
+// 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 (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(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) {
+}
+
+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::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_;
+}