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..ec97734d72e7304eef9cea3b81d23e5726c5c653
--- /dev/null
+++ b/chrome/common/string_index.cc
@@ -0,0 +1,140 @@
+// 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 "base/logging.h"
+
+// Constants
+static const std::string kInvalidStringIndex = "";

[akalin, 2011/10/14 10:16:29]

static non-POD types are a no-no.  use 'static const char[] kInvalidStringIndex
= '''.  Although honestly you don't really need a string for this

+static const char kZeroDigit = 'A';

[akalin, 2011/10/14 10:16:29]

prefer 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;
+
+
+StringIndex::StringIndex(const std::string& str) : string_index_(str) {
+
+}
+
+StringIndex::StringIndex() : string_index_(kInvalidStringIndex) {
+}
+
+bool StringIndex::IsValid() const {
+  if (string_index_ == kInvalidStringIndex) {

[akalin, 2011/10/14 10:16:29]

simply check for empty

+    return false;
+  }
+
+  for (size_t i = 0; i < string_index_.length(); ++i) {

[akalin, 2011/10/14 10:16:29]

better to do this computation in the constructor and store an is_valid_ flag,
since we're going to be checking this all over the place.

+    if (string_index_[i] < kZeroDigit || string_index_[i] > kMaxDigit) {
+      return false;
+    }
+  }
+
+  return (string_index_[string_index_.length() - 1] > kZeroDigit);

[akalin, 2011/10/14 10:16:29]

and it must also be <= maxdigit

[csharp1, 2011/10/14 16:52:36]

This is already checked in the above for loop. We just check the zero digit here
because it is a special case for just the last digit.

On 2011/10/14 10:16:29, akalin wrote:

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

[akalin, 2011/10/14 10:16:29]

CHECK that both strings are valid (this goes for all public functions)

+}
+
+StringIndex StringIndex::CreateBetween(const StringIndex& other) const {
+  DCHECK(LessThan(other));
+
+  return CreateStringIndexBetween(*this, other);
+}
+
+StringIndex StringIndex::CreateBefore() const {
+  StringIndex start = StringIndex(std::string(string_index_.length(),
+                                              kZeroDigit));
+
+  return CreateStringIndexBetween(start, *this);
+}
+
+StringIndex StringIndex::CreateAfter() const {
+  std::string end = std::string(string_index_.length(), kMaxDigit);
+  if (end == string_index_) {
+    end += kMaxDigit;
+  }
+  StringIndex end_index = StringIndex(end);
+
+  return CreateStringIndexBetween(*this, end_index);
+}
+
+std::string StringIndex::ToString() const {
+  return string_index_;
+}
+
+int StringIndex::GetPositionValue(size_t i) const {
+  return i < string_index_.length() ? string_index_[i] - kZeroDigit : 0;

[akalin, 2011/10/14 10:16:29]

use parenthesis to the clauses of the ternary operator

+}
+
+StringIndex StringIndex::CreateStringIndexBetween(const StringIndex& start,
+                                                  const StringIndex& end) {
+  DCHECK(start.LessThan(end));
+
+  std::string middle_string = ComputeMidpoint(start, end);
+  middle_string = RemoveTrailingZeros(middle_string);
+  DCHECK_GT(middle_string, start.ToString());
+  DCHECK_LT(middle_string, end.ToString());
+
+  return StringIndex(middle_string);
+}
+
+std::string StringIndex::ComputeMidpoint(const StringIndex& start,

[akalin, 2011/10/14 10:16:29]

so when i asked you to decomp this function out, I meant that the operation
"take two strings representing base-26 numbers and return their midpoint" should
be abstracted out.  This function doesn't take strings, and doesn't return the
midpoint (since it has that extra logic for the extra digit)

+                                         const StringIndex& end) {
+  size_t max_size = std::max(start.ToString().length(),

[akalin, 2011/10/14 10:16:29]

#include <algorithm> for max

[akalin, 2011/10/14 10:16:29]

CHECK that both start and end are valid

[akalin, 2011/10/14 10:16:29]

rather than calling ToString() multiple times, set it to a const string ref

+                             end.ToString().length());
+  std::string middle_string(max_size, kZeroDigit);
+
+  bool add_half = false;
+  for (size_t i = 0; i < max_size; ++i) {
+    int char_value = start.GetPositionValue(i);
+    char_value += end.GetPositionValue(i);
+
+    middle_string[i] += (char_value / 2);
+    if (add_half) {
+      AddHalf(i, middle_string);
+    }
+    add_half = (char_value % 2 == 1);
+  }
+
+  // We only add an extra digit if it is required for uniqueness, otherwise
+  // we accept a close to middle placement
+  if (add_half && EqualValueIndexs(middle_string,start.ToString())) {

[csharp1, 2011/10/13 16:07:08]

Note that if middle_string.length() > max_size it means that without the extra
digit our invariant would fail, which means if we have middle_string.length() >
max_size we sadly can't reduce its size.

[akalin, 2011/10/14 10:16:29]

if start is valid (which it should be if you check above) then you don't need to
trim the string.

+    middle_string += kMidDigit;
+  }
+
+  return middle_string;
+}
+
+bool StringIndex::EqualValueIndexs(const std::string& rhs,
+                                   const std::string& lhs) {
+  return RemoveTrailingZeros(rhs) == RemoveTrailingZeros(lhs);
+}
+
+void StringIndex::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) {
+    DCHECK(i > 0);

[akalin, 2011/10/14 10:16:29]

DCHECK_GT

[akalin, 2011/10/14 10:16:29]

better to CHECK -- if this fails, you'll do an out-of-bounds write, which is
bad.

+    value[i] -= kFullDigitValue;
+    ++value[i - 1];
+  }
+}
+
+std::string StringIndex::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);
+}