Create StringOrdinal to allow placement of strings in sorted lists

chrome/common/string_ordinal.cc

Index: chrome/common/string_ordinal.cc
diff --git a/chrome/common/string_ordinal.cc b/chrome/common/string_ordinal.cc
new file mode 100644
index 0000000000000000000000000000000000000000..d431158b95e9184ede772a1bd56f558f64725d19
--- /dev/null
+++ b/chrome/common/string_ordinal.cc
@@ -0,0 +1,229 @@
+// 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

[tfarina, 2011/10/20 14:54:35]

I think you can remove this comment. if not, please add a blank line above.

+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
+
+// Remove all trailing zero digits from a value as they provide no value.
+void RemoveTrailingZeros(std::string* value) {
+  DCHECK(!value->empty());
+
+  int end_position = value->length() - 1;
+  while ((*value)[end_position] == kZeroDigit) {
+    --end_position;
+  }
+
+  value->resize(end_position + 1);
+}
+

[tfarina, 2011/10/20 14:54:35]

remove extra line.

+
+// 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 because
+// the previous index values had an odd difference, so their correct
+// middle value is x and a half, so the half is now inserted.
+void AddHalf(size_t position, std::string& value) {
+  DCHECK_GT(position, static_cast<size_t>(0));

[tfarina, 2011/10/20 14:54:35]

instead of static_cast<size_t>, 0U?

+
+  // 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, static_cast<size_t>(0));
+      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,

[csharp, 2011/10/20 14:35:32]

I ended up taking a different approach to how we drop digit here because the
initial idea akalin@ suggested runs into some problems when the start and end
string have different lengths. After playing around with a few different ideas I
think that the best (and clearest) solution might just be to see if we can drop
a single digit, regardless of the length of the various parts. While this won't
always give the best answers (CreateAfter("YZ") returns Z) it gives good answers
most of the time without being too complex.  

+                        std::string* value) {
+  CHECK_GT(*value, start);
+
+  RemoveTrailingZeros(value);
+  // See if the value can have its last digit removed without affecting
+  // the ordering.
+  if (value->length() > 1) {
+    std::string shorter_value = value->substr(0, value->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.
+    RemoveTrailingZeros(&shorter_value);
+
+    if (shorter_value > start) {
+      value->resize(shorter_value.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()) {

[tfarina, 2011/10/20 14:54:35]

no need of  {} in single-line statements, here and elsewhere.

+    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);

[tfarina, 2011/10/20 14:54:35]

no need of parentheses here.

+}
+} // namespace

[tfarina, 2011/10/20 14:54:35]

add a blank line above.

+
+StringOrdinal::StringOrdinal(const std::string& string_ordinal)
+  : string_ordinal_(string_ordinal),

[tfarina, 2011/10/20 14:54:35]

indent this 4 spaces.

+    is_valid_(IsValidStringOrdinal(string_ordinal_)) {
+
+}
+
+StringOrdinal StringOrdinal::Invalid()  {
+  return StringOrdinal("");
+}
+
+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_;
+}