Create StringOrdinal to allow placement of strings in sorted lists

chrome/common/string_index.cc

Index: chrome/common/string_index.cc
diff --git a/chrome/common/string_index.cc b/chrome/common/string_index.cc
new file mode 100644
index 0000000000000000000000000000000000000000..919b807e7296e3c608b4a2e9a9c1b0e055dca95e
--- /dev/null
+++ b/chrome/common/string_index.cc
@@ -0,0 +1,174 @@
+// 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_index.h"
+
+#include <algorithm>
+
+#include "base/logging.h"
+
+namespace {
+// Constants
+static const char kZeroDigit = 'A';

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

no need for static since we're in anon namespace

+static const char kMinDigit = 'B';
+static const char kMidDigit = 'N';
+static const char kMaxDigit = 'Z';
+static const int kMaxDigitValue = kMaxDigit - kZeroDigit;
+static const int kMidDigitValue = kMidDigit - kZeroDigit;
+static const int kFullDigitValue = (kMaxDigit + 1) - kZeroDigit;
+
+// 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);
+}
+
+// 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));
+  value[position] += kMidDigitValue;
+
+  for (size_t i = position; value[i] > kMaxDigit; --i) {
+    CHECK_GT(i, static_cast<size_t>(0));
+    value[i] -= kFullDigitValue;
+    ++value[i - 1];
+  }
+}
+
+// Return the digit value at position i, padding with kZeroDigit if required.
+int GetPositionValue(std::string str, size_t i) {
+  return (i < str.length()) ? (str[i] - kZeroDigit) : 0;
+}
+
+// Compute the midpoint string that is between start and end.

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

This is what I want, basically:

// Given strings a, b representing base-26 numbers in (0..1), returns a string
representing (a + b) / 2.
std::string ComputeMidpoint(const std::string& a, std::string& b) {
  const size_t midpoint_size = std::max(start.length(), end.length()) + 1;
  std::string mid(midpoint_size, kZeroDigit);
  ...
}
}

That is, add an extra digit here if necessary, and truncate the string outside
this function.

+std::string ComputeMidpoint(const std::string& start,
+                            const std::string& end) {
+  size_t max_size = std::max(start.length(),
+                             end.length());
+  std::string middle_string(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);
+
+    middle_string[i] += (char_value / 2);
+    if (add_half) {
+      AddHalf(i, middle_string);
+    }
+    add_half = (char_value % 2 == 1);
+  }
+
+  return middle_string;
+}
+
+// Create a StringIndex that is lexigraphically greater than start and
+// lexigraphically less than end, ideally the StringIndex will be a
+// middle value between the two StringIndexs.
+StringIndex CreateStringIndexBetween(const StringIndex& start,
+                                     const StringIndex& end) {
+  CHECK(start.IsValid());
+  CHECK(end.IsValid());
+  std::string start_string = start.ToString();
+  std::string end_string = end.ToString();
+  DCHECK_LT(start_string, end_string);
+
+  std::string middle_string = ComputeMidpoint(start_string, end_string);
+
+  // We only add an extra digit if it is required for uniqueness, otherwise

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

Although you can decomp this logic (which will turn into 'drop last digit if
possible') into a separate fn

+  // we accept a close to middle placement.
+  if (RemoveTrailingZeros(middle_string) == start_string) {
+    middle_string += kMidDigit;
+  }
+  middle_string = RemoveTrailingZeros(middle_string);
+
+  DCHECK_GT(middle_string, start_string);
+  DCHECK_LT(middle_string, end_string);
+
+  return StringIndex(middle_string);
+}
+} // namespace
+
+StringIndex::StringIndex(const std::string& str) : string_index_(str),
+                                                   is_valid_(true) {
+  if (string_index_.empty()) {
+    is_valid_ = false;

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

decomp this into a function.  That is, have:

bool IsValidStringIndex(const std::string& str);

and have the initialization list just be:

string_index_(str), is_valid_(IsValidStringIndex(string_index_))

+  }
+
+  for (size_t i = 0; i < string_index_.length(); ++i) {
+    if (string_index_[i] < kZeroDigit || string_index_[i] > kMaxDigit) {
+      is_valid_ = false;
+    }
+  }
+
+  if (string_index_[string_index_.length() - 1] == kZeroDigit) {
+    is_valid_ = false;
+  }
+}
+
+StringIndex::StringIndex() : string_index_(""), is_valid_(false)  {

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

omit string_index_ (it's already default-initialized to be empty)

+}
+
+bool StringIndex::IsValid() const {
+  return is_valid_;
+}
+
+bool StringIndex::LessThan(const StringIndex& other) const {
+  CHECK(other.IsValid());

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

nit: prefer CHECK(IsValid()) before CHECK(other.IsValid())

+  CHECK(IsValid());
+  return string_index_ < other.string_index_;
+}
+
+bool StringIndex::Equal(const StringIndex& other) const {
+  CHECK(other.IsValid());

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

here too

+  CHECK(IsValid());
+

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

omit extra line

+  return string_index_ == other.string_index_;
+}
+
+StringIndex StringIndex::CreateBetween(const StringIndex& other) const {
+  CHECK(other.IsValid());

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

here too

+  CHECK(IsValid());
+  CHECK(LessThan(other));
+
+  return CreateStringIndexBetween(*this, other);
+}
+
+StringIndex StringIndex::CreateBefore() const {
+  CHECK(IsValid());

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

I think the following would be clearer:

const size_t length = string_index_.length();
std::string start_string = std::string(length, kZeroDigit);
start_string[length - 1] = kMinDigit;
if (...) {
  start_string[length - 1] = kZeroDigit;
  start_string += kMinDigit;
}

#include <cstddef> for size_t

+  // Create the smallest, valid StringIndex to be the minimum boundary.
+  std::string start_string = std::string(string_index_.length(),
+                                         kZeroDigit);
+  *(start_string.rbegin()) = kMinDigit;
+  if (start_string == string_index_) {
+    *(start_string.rbegin()) = kZeroDigit;
+    start_string += kMinDigit;
+  }
+
+  return CreateStringIndexBetween(StringIndex(start_string), *this);

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

return StringIndex(start_string).CreateBetween(*this);

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

Add comment saying that, even though start_string is already < *this, we want to
leave some room.

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

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

return CreateBetween(StringIndex(end))

+  return CreateStringIndexBetween(*this, StringIndex(end));

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

Add comment similar to CreateBefore

+}
+
+std::string StringIndex::ToString() const {
+  return string_index_;
+}