Initial UniquePositions implementation

sync/internal_api/public/base/unique_position.h

Index: sync/internal_api/public/base/unique_position.h
diff --git a/sync/internal_api/public/base/unique_position.h b/sync/internal_api/public/base/unique_position.h
new file mode 100644
index 0000000000000000000000000000000000000000..1d472936b49de75e3f27b783bb604e9c98b4f369
--- /dev/null
+++ b/sync/internal_api/public/base/unique_position.h
@@ -0,0 +1,107 @@
+// Copyright (c) 2012 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 SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_
+#define SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_
+
+#include <string>
+
+#include "base/basictypes.h"
+
+namespace syncer {
+
+// A class to represent positions.
+//
+// By relying on the existence of unique suffixes, this class can ensure that it

[akalin, 2012/12/29 10:17:13]

would like to have a blurb about the algebraic properties of UniquePosition,
similar to the class comment for Ordinal.  You can say mention transitivity,
trichotomy, density, and unboundedness, but probably would have to modify them
to take the suffixes into account.

[rlarocque, 2013/01/07 23:22:12]

Done.

+// is always possible to create a new position between any two existing
+// positions.  It can also create new positions before or after any other
+// position, which makes it easier to support insertion at the head or tail of a
+// list.
+//
+// Note that these unique suffixes must be exactly |kSuffixLength| bytes long.
+//
+// The cost for all these features is potentially unbounded space usage.  In
+// practice, however, most ordinals should be not much longer than the suffix.
+//
+// This class currently has several bookmarks-related assumptions built in,
+// though it could be adapted to be more generally useful.
+class UniquePosition {
+ public:
+  static const size_t kSuffixLength;
+
+  static bool IsValidSuffix(const std::string& suffix);
+  static bool IsValidBytes(const std::string& bytes);
+
+  // Returns an invalid position.
+  static UniquePosition CreateInvalid();
+
+  // Converts bytes from 'ToInternalValue()' back into a UniquePosition.
+  static UniquePosition FromBytes(const std::string& bytes);
+
+  // Creates a position with the given suffix.  Ordering among positions created
+  // from this function is the same as that of the integer parameters that were
+  // passed in.
+  static UniquePosition FromInt64(int64 i, const std::string& suffix);
+
+  // Returns a valid position.  Its ordering is not defined.
+  static UniquePosition InitialPosition(const std::string& suffix);
+
+  // Returns positions compare smaller than, greater than, or between the input
+  // positions.
+  static UniquePosition Before(const UniquePosition& x,
+                               const std::string& suffix);
+  static UniquePosition After(const UniquePosition& x,
+                              const std::string& suffix);
+  static UniquePosition Between(const UniquePosition& before,
+                                const UniquePosition& after,
+                                const std::string& suffix);
+
+  UniquePosition();

[akalin, 2012/12/29 10:17:13]

comment that this creates an invalid value

[rlarocque, 2013/01/07 23:22:12]

Done.

+
+  bool LessThan(const UniquePosition& other) const;
+  bool Equals(const UniquePosition& other) const;
+
+  // Serializes the position's internal state.  To be used with FromBytes().
+  const std::string& ToInternalValue() const;
+
+  // Returns a human-readable representation of this item's internal state.
+  std::string ToDebugString() const;
+
+  // Performs a lossy conversion to an int64 position.  Positions converted to
+  // and from int64s using this and the FromInt64 function should maintain their
+  // relative orderings unless the int64 values conflict.
+  int64 ToInt64() const;
+
+  bool IsValid() const;
+
+ private:
+  friend class UniquePositionTest;
+
+  // Returns a string X such that (X ++ |suffix|) < |str|.
+  // |str| must be a trailing substring of a valid ordinal.
+  // |suffix| must be a valid unique suffix.
+  static std::string FindSmallerWithSuffix(const std::string& str,
+                                           const std::string& suffix);
+  // Returns a string X such that (X ++ |suffix|) > |str|.
+  // |str| must be a trailing substring of a valid ordinal.
+  // |suffix| must be a valid unique suffix.
+  static std::string FindGreaterWithSuffix(const std::string& str,
+                                           const std::string& suffix);
+  // Returns a string X such that |before| < (X ++ |suffix|) < |after|.
+  // |before| and after must be a trailing substrings of valid ordinals.
+  // |suffix| must be a valid unique suffix.
+  static std::string FindBetweenWithSuffix(const std::string& before,
+                                           const std::string& after,
+                                           const std::string& suffix);
+
+  explicit UniquePosition(const std::string& internal_rep);
+  UniquePosition(const std::string& prefix, const std::string& suffix);
+
+  std::string bytes_;
+  bool is_valid_;
+};
+
+}  // namespace syncer;
+
+#endif  // SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_