Create StringOrdinal to allow placement of strings in sorted lists

chrome/common/string_index.cc

+// 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"
+
+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);
+}
+
+void StringIndex::AddHalf(size_t position, std::string& value) {
+  DCHECK(position > 0);
+  value[position] += kMidDigitValue;
+
+  if (value[position] > kMaxDigit) {
+    value[position] -= kFullDigitValue;
+    ++value[position - 1];
+    DCHECK(value[position - 1] <= kMaxDigit);

[akalin, 2011/10/12 18:50:14]

as I mentioned previously, this won't work.  you'll have to propagate the carry
backwards.

+  }
+}
+
+void StringIndex::ValidateString(const std::string& value) {
+  if (value.empty()) {
+    return;
+  }
+
+  DCHECK(value[0] >= kZeroDigit);

[akalin, 2011/10/12 18:50:14]

use DCHECK_GE, DCHECK_LE, etc.

+  DCHECK(value[0] <= kMaxDigit);
+
+  for (size_t i = 1; i < value.length(); ++i) {
+    DCHECK(value[i] >= kMinDigit);
+    DCHECK(value[i] <= kMaxDigit);
+  }
+}
+
+std::string StringIndex::CreateStringBetween(const std::string& start,
+                                             const std::string& end) {
+  ValidateString(start);
+  ValidateString(end);
+  std::string start_expanded = start;
+  std::string end_expanded = end;
+
+  // If we have no end value, we create one that has the maximum value
+  // to use as our end point.
+  if (end_expanded.empty()) {
+    int length = start_expanded.length();
+    if (start_expanded.find_first_not_of(kMaxDigit) == std::string::npos) {
+      //Ensure we are bigger than start if it is Z*
+      ++length;
+    }
+
+    end_expanded = std::string(length, kMaxDigit);
+  }
+
+  // Pad the shorter string with zeros so they are the same length
+  size_t max_size = std::max(start_expanded.length(), end_expanded.length());
+  start_expanded.resize(max_size, kZeroDigit);
+  end_expanded.resize(max_size, kZeroDigit);
+  CHECK(start_expanded < end_expanded);

[akalin, 2011/10/12 18:50:14]

CHECK_LT

+
+  std::string middle_string(max_size, kZeroDigit);
+  bool add_half = false;
+  for (size_t i = 0; i < max_size; ++i) {
+    int char_value = start_expanded[i] - kZeroDigit;
+    char_value += end_expanded[i] - kZeroDigit;
+
+    middle_string[i] += (char_value / 2);
+    if (add_half) {
+      AddHalf(i, middle_string);
+    }
+    add_half = (char_value % 2 == 1);
+  }

[akalin, 2011/10/12 18:50:14]

this should be decomped out into a helper function like ComputeMidpoint().  Then
this function could be something like:

std::string middle_string = ComputeMidpoint(start, end);
RemoveTrailingZeros(&middle_string);

if (middle_string.size() > max_size) {
  // Try truncating if it doesn't break the invariants.
}

return middle_string;

+
+  // We only add an extra digit if it is required for uniqueness, otherwise
+  // we accept a close to middle placement
+  if (add_half && middle_string == start_expanded) {
+    middle_string += kMidDigit;
+  }
+
+  DCHECK(middle_string > start_expanded);
+  DCHECK(middle_string < end_expanded);
+  return RemoveTrailingZeros(middle_string);
+}