Create StringOrdinal to allow placement of strings in sorted lists

chrome/common/string_ordinal.h

+// 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.
+
+#ifndef CHROME_COMMON_STRING_ORDINAL_H_
+#define CHROME_COMMON_STRING_ORDINAL_H_
+#pragma once
+
+#include <string>
+
+// A StringOrdinal represents a specially-formatted string that can be used
+// for ordering. The StringOrdinal class has an unbounded dense strict total
+// order, which mean for any StringOrdinals a, b and c:
+//
+//  - a < b and b < c implies 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).
+//
+// This means that when StringOrdinal is used for sorting a list, if
+// any item changes its position in the list, only its StringOrinal value

[akalin, 2011/10/20 19:06:51]

Orinal -> Ordinal

+// has to change to represent the new order, and all the other older values
+// can stay the same.
+class StringOrdinal {
+ public:
+  // Create a StringOrdinal from the given string. It may be valid or invalid.
+  explicit StringOrdinal(const std::string& string_ordinal);
+
+  // Create an invalid StringOrdinal.

[akalin, 2011/10/20 19:06:51]

please revert this back to the default constructor

(it's worth noting that the default constructor is still around, but then it
leaves the value of is_valid_ uninitialized :( )

+  static StringOrdinal Invalid();
+
+  bool IsValid() const;
+
+  // All remaining functions can only be called if IsValid() holds.
+  // It is an error to call them if IsValid() is false.
+
+  // Ordering Functions
+
+  // Returns true iff |*this| < |other|.
+  bool LessThan(const StringOrdinal& other) const;
+
+  // Return true iff |*this| == |other| (i.e. this->LessThan(other) and

[akalin, 2011/10/20 19:06:51]

say

(i.e., |*this| < |other| and |*this| > |other| are both false)

+  // other.LessThan(*this) are both false).
+  bool Equal(const StringOrdinal& other) const;
+
+  // Given |*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|.

[akalin, 2011/10/20 19:06:51]

with -> when

+  StringOrdinal CreateBetween(const StringOrdinal& other) const;
+
+  // Returns a StringOrdinal x such that x < |*this|.

[akalin, 2011/10/20 19:06:51]

x -> |x|

+  StringOrdinal CreateBefore() const;
+
+  // Returns a StringOrdinal x such that |*this| < x.

[akalin, 2011/10/20 19:06:51]

x -> |x|

+  StringOrdinal CreateAfter() const;
+
+  // It is guaranteed that a StringOrdinal constructed from the returned
+  // string will be valid.
+  std::string ToString() const;
+
+ private:
+  // The value of the StringOrdinal.

[akalin, 2011/10/20 19:06:51]

value -> string representation

+  std::string string_ordinal_;
+
+  // The validity of the StringOrdinal (is it of the format [a-z]*[b-z]),

[akalin, 2011/10/20 19:06:51]

"is it" -> "i.e., is it"

+  // created to cache validity to prevent frequent recalculations.
+  bool is_valid_;
+
+  // Use of copy constructor and default assignment for this class is allowed.
+};
+
+#endif  // CHROME_COMMON_STRING_ORDINAL_H_