Create StringOrdinal to allow placement of strings in sorted lists

chrome/common/string_index.h

Index: chrome/common/string_index.h
diff --git a/chrome/common/string_index.h b/chrome/common/string_index.h
new file mode 100644
index 0000000000000000000000000000000000000000..ba61dee0d0b23e75c78e0d697379123033864190
--- /dev/null
+++ b/chrome/common/string_index.h
@@ -0,0 +1,54 @@
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.

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

Thinking about it, a better name for this class would be StringOrdinal, as
"index" has multiple meanings.  So rename these files to
string_ordinal{.h,.cc,_unittest.cc}, and rename this class to StringOrdinal.

+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CHROME_COMMON_STRING_INDEX_H_
+#define CHROME_COMMON_STRING_INDEX_H_
+#pragma once
+
+#include <string>
+
+// This class allows strings to be used as floating point numbers (in base 26)

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

This class is actually closer to fixed-point than floating-point, but it is
neither.  Say something like:

A StringOrdinal represents a specially-formatted string that can be used for
ordering.  The StringOrdinal class has an unbounded dense strict total order,
which means for any StringOrdinals a, b, and c:

- a < b and b < c imply a < c (transitivity);
- exactly one of a < b, b < a, and a = b holds (trichotomy);
- if a < b, there is a StringOrdinal x such that a < x < b (density);
- there are StringOrdinals x and y such that x < a < y (unboundedness).

+// in the range of (0..1), so that if there is a sorted array of them and a
+// single element is moved, then only that element has to change its index
+// value. There will always be a valid value between two adjacent values
+// (since infinite less significant digits can be added) and no other values
+// need to be adjust to keep the same sorted order.
+class StringIndex {
+ public:
+  // Create a valid StringIndex if the string matches [A-Z]*[B-Z],

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

how about using [a-z]*[b-z] instead?  I find lowercase strings easier to read,
and we'd be stuck with this format once we start using it. :)

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

Say something like:

Creates a (possibly invalid) StringOrdinal from the given string.

+  // otherwise create an invalid StringIndex.
+  explicit StringIndex(const std::string& str);
+
+  // Create an invalid StringIndex.
+  StringIndex();
+
+  // Returns true iff this was initialized with a string matching [A-Z]*[B-Z].

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

I think we can omit this comment (since it's just an implementation detail)

+  bool IsValid() const;
+

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

add a comment:

// Ordering functions.

+  // Returns true iff other is a lexicographically smaller StringIndex than

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

The comment is incorrect (backwards).  Something like:

// Returns true iff |*this| < |other|.

(no need to specify implementation details like lexicographic order)

+  // this.
+  bool LessThan(const StringIndex& other) const;
+
+  // Return true iff other has the same value.

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

// Returns true iff |*this| = |other| (i.e., |*this| is neither greater than nor
less than |other|).

+  bool Equal(const StringIndex& other) const;
+
+  // this.LessThan(other) must hold. Returns a StringIndex x such that LessThan(

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

Actually we should relax the precondition to just nonequality.  Change comment
to:

// Given that |*this| != |other|, returns a StringOrdinal x such that
min(|*this|, |other|) < x < max(|*this|, |other|).  It is an error to call this
function with |*this| = |other|.

+  // x) holds, and x.LessThan(other) holds.
+  StringIndex CreateBetween(const StringIndex& other) const;
+
+  // Returns a StringIndex x such that x.LessThan(*this) holds.

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

Returns a StringOrdinal x such that x < |*this|.

+  StringIndex CreateBefore() const;
+
+  // Returns a StringIndex x such that LessThan(x) holds.

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

// Returns a StringOrdinal x such that |*this| < x.

+  StringIndex CreateAfter() const;
+
+  std::string ToString() const;
+
+  // Use of copy constructor and default assignment for this class is allowed.
+
+ private:
+  std::string string_index_;
+  bool is_valid_;
+};
+#endif  // CHROME_COMMON_STRING_INDEX_H_