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..e67c104fe224a6e8a169617a7c0a2a5230c9a371
--- /dev/null
+++ b/chrome/common/string_ordinal.cc
@@ -0,0 +1,214 @@
+// 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
+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 zeros from a value as they provide no value.

[akalin, 2011/10/20 05:25:49]

zeros -> zero digits

+std::string RemoveTrailingZeros(const std::string& value) {

[akalin, 2011/10/20 05:25:49]

Make this a destructive operation, like:

void RemoveTrailingZeros(std::string* value) {
  ...
  value->resize(end_position + 1);
}

+  DCHECK(!value.empty());
+
+  int end_position = value.length() - 1;
+  while (value[end_position] == kZeroDigit) {
+    --end_position;
+  }
+
+  return value.substr(0, 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 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));
+
+  // 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|.
+std::string DropUnneededDigits(const std::string& value,

[akalin, 2011/10/20 05:25:49]

make this a destructive operation, also, so:

void DropUnneededDigits(std::string* value, const std::string& start, const
std::string& end) {
  ...
}

[tfarina, 2011/10/20 12:58:40]

Output parameters should be at the end of parameter list.

http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Functi...

+                               const std::string& start) {
+  CHECK_GT(value, start);
+
+  std::string shorter_value = value.substr(0, value.length() - 1);

[akalin, 2011/10/20 05:25:49]

it's possible that it may be enough to remove the trailing zeros first.  Maybe
something like:

RemoveTrailingZeros(value);
if ((start.length == end.length()) && (value->length() > (start.length() + 1))
|| (value->compare(0, start.length(), start) > 0))) {
  // start and end are the same length, value adds an extra digit, but dropping
the digit will still keep start < *value < end.
  value->resize(start.length());
  RemoveTrailingZeros(value);
}

(clean up the code and comments above, it's just a rough sketch)

+  shorter_value = RemoveTrailingZeros(shorter_value);
+
+  if (shorter_value != start) {
+    return shorter_value;
+  }
+  return value;
+}
+
+// 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);
+  }
+

[akalin, 2011/10/20 05:25:49]

DCHECK(!add_half); here

+  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);
+
+  midpoint = DropUnneededDigits(midpoint, start_string);
+
+  DCHECK_GT(midpoint, start_string);
+  DCHECK_LT(midpoint, end_string);
+
+  return StringOrdinal(midpoint);

[akalin, 2011/10/20 05:25:49]

Do;

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() : 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 to be the minimum boundary.

[akalin, 2011/10/20 05:25:49]

no comma between 'smallest' and 'valid'

StringOrdinal -> StringOrdinal of the appropriate length

+  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());
+  std::string end(string_ordinal_.length(), kMaxDigit);

[akalin, 2011/10/20 05:25:49]

Add a comment similar to CreateBefore();

// Create the largest valid StringOrdinal of the appropriate length to be the
maximum boundary.

+  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_;
+}