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..5cd90076601974eb3953bd62cee51a0c7fa1761a
--- /dev/null
+++ b/chrome/common/string_index.cc
@@ -0,0 +1,71 @@
+// 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"
+
+StringIndex::StringIndex(): kMaxDigitValue(kMaxDigit - kZeroDigit),

[akalin, 2011/10/11 19:34:39]

surely you don't need these to be initialized for every StringIndex object?

+                            kMidDigitValue(kMidDigit - kZeroDigit) {
+}
+
+std::string StringIndex::RemoveTrailingZeros(const std::string& value) {
+  int end_position = value.length() - 1;

[akalin, 2011/10/11 19:34:39]

assert that value is non-empty

+  while (value[end_position] == kZeroDigit) {
+    --end_position;
+  }
+
+  return value.substr(0, end_position + 1);
+}
+
+void StringIndex::AddHalf(int position, std::string& value) {
+  value[position] += kMidDigitValue;
+
+  if (value[position] > kMaxDigit) {
+    value[position] -= kMaxDigitValue;
+    ++value[position - 1];

[akalin, 2011/10/11 19:34:39]

what if this also overflows?  consider (.99999 + .00001) / 2.

[csharp1, 2011/10/11 21:46:03]

I'm fairly certain it can't overflow.

It could only overflow if the value is kMaxDigit and this function is only
called if their was a unused half when adding, so the value would have to be
2*kMaxDigit +1, which we can never get.

I've added an assert here though to ensure this condition is true.

On 2011/10/11 19:34:39, akalin wrote:

[csharp1, 2011/10/11 21:46:03]

I'm fairly certain it can't overflow.

It could only overflow if the value is kMaxDigit and this function is only
called if their was a unused half when adding, so the value would have to be
2*kMaxDigit +1, which we can never get.

I've added an assert here though to ensure this condition is true.

On 2011/10/11 19:34:39, akalin wrote:

[akalin, 2011/10/11 22:00:24]

Ah, it can't overflow because mid digit value is set to 12 (M) when it should be
13 (N) (if you're simulating base-26 arithmetic).  When you fix that bug, then
overflow can definitely happen, e.g. 'zzz', 'aab'.

[csharp1, 2011/10/12 15:31:12]

I fixed the middle digit bug, but I still don't see how the overflow could
occur. For the overflow to occur the last index would need to have a value
kMaxDigit,and also set the add_half variable to true. To get a value of
kMaxDigit the start and end string must both be kMaxDigit, but then add_half
will be false, (2*kMaxDigit) % 2 == 0, so we enter AddHalf for the next
position.

Maybe I'm missing something, could you provide an example where the overflow
will occur in value[position -1]?

On 2011/10/11 22:00:24, akalin wrote:

[akalin, 2011/10/12 18:13:07]

I did, in my previous two comments about it. :P To repeat it, in base 10,
consider .999 + .001.  In base 26, consider 'zzz' and 'aab'.

[csharp1, 2011/10/12 18:52:46]

Ok, I made a unit test with the example you gave and had it fail on me :) When I
was looking at the code I was forgetting the index value before could have had
AddHalf applied to it, which made it possible to have the overflow issue.

It should be fixed now.

On 2011/10/12 18:13:07, akalin wrote:

+  }
+}
+
+int StringIndex::GetPositionValue(const std::string& value, size_t index) {

[akalin, 2011/10/11 19:34:39]

this can be a static function, or a free function in an anon namespace

+  return index < value.length() ? value[index] - kZeroDigit : 0;
+}
+
+std::string StringIndex::CreateStringBetween(const std::string& start,
+                                             const std::string& end) {
+  // If we have no end value, we create one that has the maximum value
+  // to use as our end point.
+  if (end.length() == 0) {

[akalin, 2011/10/11 19:34:39]

end.empty()

+    return CreateStringBetween(start,

[akalin, 2011/10/11 19:34:39]

this fails the precondition below

[csharp1, 2011/10/11 21:46:03]

I'm not sure what you mean here. This does fail start < end, but this was the
best way I could see to signify that the end is the max value.

On 2011/10/11 19:34:39, akalin wrote:

[akalin, 2011/10/11 22:00:24]

Seems better to go the extra step to make the precondition hold (i.e., if end is
empty and start is all 'z's, make an end value that is greater than that.

+                               std::string(start.length(), kMaxDigit));
+  }

[akalin, 2011/10/11 19:34:39]

assert that start < end || start.empty()

assert that the strings match [a-z]*[b-z] if non-empty.

+
+  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);
+  }
+
+  std::string no_trailing_zeros = RemoveTrailingZeros(middle_string);
+  if (no_trailing_zeros.length() == 0) {
+    middle_string += kMidDigit;

[akalin, 2011/10/11 19:34:39]

pretty sure this is only needed because you don't perform the last half
operation.  I'd prefer removing this hack, implementing 'real' averaging above,
and doing the truncation as a final step below.

+  } else {
+    middle_string = no_trailing_zeros;
+  }
+
+  // We only add an extra digit if it is required for uniqueness, otherwise
+  // we accept a close to middle placement
+  if (start == middle_string) {
+    middle_string += kMidDigit;
+  }
+
+  return middle_string;

[akalin, 2011/10/11 19:34:39]

assert that start < middle < end

+}