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..de87cf81adfb92d0d2939aae6cdb97aa7ed81075
--- /dev/null
+++ b/chrome/common/string_ordinal.cc
@@ -0,0 +1,207 @@
+// 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/logging.h"
+
+namespace {
+// Constants
+const char kZeroDigit = 'a';
+const char kMinDigit = 'b';
+const char kMidDigit = 'n';
+const char kMaxDigit = 'z';
+const int kMaxDigitValue = kMaxDigit - kZeroDigit;
+const int kMidDigitValue = kMidDigit - kZeroDigit;

[akalin, 2011/10/18 17:59:27]

put kMidDigitValue before kMaxDigitValue

+const int kFullDigitValue = (kMaxDigit + 1) - kZeroDigit;

[akalin, 2011/10/18 17:59:27]

#include base/basictypes.h and use COMPILE_ASSERT to check the values of
kMaxDigitValue, etc.

[akalin, 2011/10/18 17:59:27]

a better name would be kRadix, and you can set it to kMaxDigitValue + 1

+
+// Helper Functions
+
+// Remove all trailing zeros from a value as they provide no value.
+std::string RemoveTrailingZeros(const std::string& value) {
+  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 preform this operation directly on the string because

[akalin, 2011/10/18 17:59:27]

preform -> perform

+  // overflow can occur and mess up the values.
+  int new_position_value = value[position] + kMidDigitValue;

[akalin, 2011/10/18 17:59:27]

do static_cast<int>(value[position]) just to be clear

+
+  if (new_position_value <= kMaxDigit) {
+    value[position] = new_position_value;
+  } else {
+    value[position] = new_position_value - kFullDigitValue;
+    ++value[position - 1];
+
+    for (size_t i = position - 1; value[i] > kMaxDigit; --i) {
+      CHECK_GT(i, static_cast<size_t>(0));
+      value[i] = value[i] - kFullDigitValue;

[akalin, 2011/10/18 17:59:27]

-=

+      ++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(std::string value,

[akalin, 2011/10/18 17:59:27]

use const refs to strings instead of passing by value

+                               std::string start) {
+  CHECK(value > start);

[akalin, 2011/10/18 17:59:27]

CHECK_GT

+
+  std::string shorter_value = value.substr(0, value.length() - 1);
+  shorter_value = RemoveTrailingZeros(shorter_value);
+
+  if (shorter_value != start) {
+    return shorter_value;
+  }
+  return value;
+}
+
+// Compute the midpoint string that is between start and end.

[akalin, 2011/10/18 17:59:27]

start -> |start|
end -> |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 middle_string(max_size, kZeroDigit);

[akalin, 2011/10/18 17:59:27]

middle_string -> midpoint

+
+  bool add_half = false;
+  for (size_t i = 0; i < max_size; ++i) {
+    int char_value = GetPositionValue(start, i);
+    char_value += GetPositionValue(end, i);
+
+    middle_string[i] += (char_value / 2);
+    if (add_half) {
+      AddHalf(i, middle_string);
+    }
+    add_half = (char_value % 2 == 1);
+  }
+
+  return middle_string;
+}
+
+// Create a StringOrdinal that is lexigraphically greater than start and

[akalin, 2011/10/18 17:59:27]

start -> |start|
end -> |end|

+// lexigraphically less than end, ideally the StringOrdinal will be a

[akalin, 2011/10/18 17:59:27]

"end, ideally" -> "end.  The returned StringOrdinal will be roughly between
|start| and |end|.

+// middle value between the two StringIndexs.

[akalin, 2011/10/18 17:59:27]

StringOrdinals

+StringOrdinal CreateStringOrdinalBetween(const StringOrdinal& start,
+                                         const StringOrdinal& end) {
+  CHECK(start.IsValid());
+  CHECK(end.IsValid());

[akalin, 2011/10/18 17:59:27]

CHECK(start.LessThan(end))

+  std::string start_string = start.ToString();

[akalin, 2011/10/18 17:59:27]

use const refs

+  std::string end_string = end.ToString();

[akalin, 2011/10/18 17:59:27]

here, too

+  DCHECK_LT(start_string, end_string);
+
+  std::string middle_string = ComputeMidpoint(start_string, end_string);

[akalin, 2011/10/18 17:59:27]

middle_string -> midpoint

+
+  middle_string = DropUnneededDigits(middle_string, start_string);
+
+  DCHECK_GT(middle_string, start_string);
+  DCHECK_LT(middle_string, end_string);
+
+  return StringOrdinal(middle_string);
+}
+
+// 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& str)
+  : string_index_(str),
+    is_valid_(IsValidStringOrdinal(string_index_)) {
+
+}
+
+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_index_ < other.string_index_;
+}
+
+bool StringOrdinal::Equal(const StringOrdinal& other) const {
+  CHECK(IsValid());
+  CHECK(other.IsValid());
+  return string_index_ == other.string_index_;
+}
+
+StringOrdinal StringOrdinal::CreateBetween(const StringOrdinal& other) const {
+  CHECK(IsValid());
+  CHECK(other.IsValid());

[akalin, 2011/10/18 17:59:27]

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.
+  const size_t length = string_index_.length();
+  std::string start_string = std::string(length, kZeroDigit);

[akalin, 2011/10/18 17:59:27]

start_string -> start (to be consistent with CreateAfter()

[akalin, 2011/10/18 17:59:27]

don't do std::string foo = std::string(...), just do std::string foo(...);

+  start_string[length - 1] = kMinDigit;
+  if (start_string == string_index_) {
+    start_string[length - 1] = kZeroDigit;
+    start_string += kMinDigit;
+  }
+
+  // Even though start_string is already a valid StringOrdinal that is less

[akalin, 2011/10/18 17:59:27]

|start_string|

+  // than *this, we don't return it because we wouldn't have much space in

[akalin, 2011/10/18 17:59:27]

|*this|

+  // front of it to insert potential future values.
+  return StringOrdinal(start_string).CreateBetween(*this);

[akalin, 2011/10/18 17:59:27]

can actually just do:

return CreateBetween(StringOrdinal(start))

+}
+
+StringOrdinal StringOrdinal::CreateAfter() const {
+  CHECK(IsValid());
+  std::string end = std::string(string_index_.length(), kMaxDigit);

[akalin, 2011/10/18 17:59:27]

std::string end(...)

+  if (end == string_index_) {
+    end += kMaxDigit;
+  }
+
+  // Even though end is already a valid StringOrdinal that is greater than

[akalin, 2011/10/18 17:59:27]

|end|

+  // *this, we don't return it because we wouldn't have much space after

[akalin, 2011/10/18 17:59:27]

|*this|

+  // it to insert potential future values.
+  return CreateBetween(StringOrdinal(end));
+}
+
+std::string StringOrdinal::ToString() const {

[akalin, 2011/10/18 17:59:27]

CHECK(is_valid_)

+  return string_index_;
+}