Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1096)

Unified Diff: sync/internal_api/public/base/ordinal.h

Issue 10920017: [Sync] Generalize StringOrdinal to handle ordinal_in_parent field (Closed) Base URL: svn://svn.chromium.org/chrome/trunk/src
Patch Set: Fix another compile error Created 8 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: sync/internal_api/public/base/ordinal.h
diff --git a/sync/internal_api/public/base/ordinal.h b/sync/internal_api/public/base/ordinal.h
new file mode 100644
index 0000000000000000000000000000000000000000..c65b652003a7521b536a7d578395407498d9b70a
--- /dev/null
+++ b/sync/internal_api/public/base/ordinal.h
@@ -0,0 +1,469 @@
+// 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_ORDINAL_H_
+#define SYNC_INTERNAL_API_PUBLIC_BASE_ORDINAL_H_
+
+#include <algorithm>
+#include <cstddef>
+#include <ostream>
+#include <string>
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+
+namespace syncer {
+
+// A Ordinal represents an object convertible to and from a string
+// that can be used for ordering. The Ordinal class has an unbounded
+// dense strict total order, which mean for any Ordinals 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 Ordinal x such that a < x < b (density);
+// - there are Ordinals x and y such that x < a < y (unboundedness).
+//
+// This means that when Ordinal is used for sorting a list, if any
+// item changes its position in the list, only its Ordinal value has
+// to change to represent the new order, and all the other older
+// values can stay the same.
+//
+// The Traits class should look like the following:
+//
+// // Don't forget to #include "base/basictypes.h".
+// struct MyOrdinalTraits {
+// // There must be at least two distinct values greater than kZeroDigit
+// // and less than kMaxDigit.
+// static const uint8 kZeroDigit = '0';
+// static const uint8 kMaxDigit = '9';
+// // kMinLength must be positive.
+// static const size_t kMinLength = 1;
+// };
+//
+// An Ordinal is valid iff its corresponding string has at least
+// kMinLength characters, does not contain any characters less than
+// kZeroDigit or greater than kMaxDigit, is not all zero digits, and
+// does not have any unnecessary trailing zero digits.
+//
+// Note that even if the native char type is signed, strings still
+// compare as if their they are unsigned. (This is explicitly in
+// C++11 but not in C++98, even though all implementations do so
+// anyway in practice.) Thus, it is safe to use any byte range for
+// Ordinals.
+template <typename Traits>
+class Ordinal {
+ public:
+ // Functors for use with STL algorithms and containers.
+ class LessThanFn {
+ public:
+ LessThanFn();
+
+ bool operator()(const Ordinal<Traits>& lhs,
+ const Ordinal<Traits>& rhs) const;
+ };
+
+ class EqualsFn {
+ public:
+ EqualsFn();
+
+ bool operator()(const Ordinal<Traits>& lhs,
+ const Ordinal<Traits>& rhs) const;
+ };
+
+ // Creates an Ordinal from the given string. The Ordinal may be
+ // valid or invalid.
+ explicit Ordinal(const std::string& ordinal_string);
+
+ // Creates an invalid Ordinal.
+ Ordinal();
+
+ // Creates a valid initial Ordinal. This is called to create the first
+ // element of Ordinal list (i.e. before we have any other values we can
+ // generate from).
+ static Ordinal CreateInitialOrdinal();
+
+ // Returns true iff this Ordinal is valid. This takes constant
+ // time.
+ bool IsValid() const;
+
+ // Returns true iff |*this| == |other| or |*this| and |other|
+ // are both invalid.
+ bool EqualsOrBothInvalid(const Ordinal& other) const;
+
+ // All remaining functions can only be called if IsValid() holds.
+ // It is an error to call them if IsValid() is false.
+
+ // Order-related functions.
+
+ // Returns true iff |*this| < |other|.
+ bool LessThan(const Ordinal& other) const;
+
+ // Returns true iff |*this| > |other|.
+ bool GreaterThan(const Ordinal& other) const;
+
+ // Returns true iff |*this| == |other| (i.e. |*this| < |other| and
+ // |other| < |*this| are both false).
+ bool Equals(const Ordinal& other) const;
+
+ // Given |*this| != |other|, returns a Ordinal x such that
+ // min(|*this|, |other|) < x < max(|*this|, |other|). It is an error
+ // to call this function when |*this| == |other|.
+ Ordinal CreateBetween(const Ordinal& other) const;
+
+ // Returns a Ordinal |x| such that |x| < |*this|.
+ Ordinal CreateBefore() const;
+
+ // Returns a Ordinal |x| such that |*this| < |x|.
+ Ordinal CreateAfter() const;
+
+ // It is guaranteed that a Ordinal constructed from the returned
+ // string will be valid.
+ std::string ToString() const;
+
+ // Use of copy constructor and default assignment for this class is allowed.
+
+ // Constants for Ordinal digits.
+ static const uint8 kZeroDigit = Traits::kZeroDigit;
+ static const uint8 kMaxDigit = Traits::kMaxDigit;
+ static const size_t kMinLength = Traits::kMinLength;
+ static const uint8 kOneDigit = kZeroDigit + 1;
+ static const uint8 kMidDigit = kOneDigit + (kMaxDigit - kOneDigit) / 2;
+ static const unsigned int kMidDigitValue = kMidDigit - kZeroDigit;
+ static const unsigned int kMaxDigitValue = kMaxDigit - kZeroDigit;
+ static const unsigned int kRadix = kMaxDigitValue + 1;
+
+ COMPILE_ASSERT(kOneDigit > kZeroDigit, OrdinalOneDigitGreaterThanMinDigit);
+ COMPILE_ASSERT(kMidDigit > kOneDigit, OrdinalMidDigitGreaterThanOneDigit);
+ COMPILE_ASSERT(kMaxDigit > kMidDigit, OrdinalMaxDigitGreaterThanMidDigit);
+ COMPILE_ASSERT(kMinLength > 0, OrdinalMinLengthIsPositive);
+ COMPILE_ASSERT(kMidDigitValue > 1, OrdinalMidDigitValueGreaterThanOne);
+ COMPILE_ASSERT(kMaxDigitValue > kMidDigitValue,
+ OrdinalMaxDigitValueGreaterThanMidDigitValue);
+ COMPILE_ASSERT(kRadix == kMaxDigitValue + 1,
+ OrdinalRadixIsMaxDigitValuePlusOne);
+
+ private:
+ // Returns true iff the given string satisfies the criteria for a
+ // valid Ordinal.
+ static bool IsValidOrdinalString(const std::string& str);
+
+ // Returns the length that string value.substr(0, length) would be with
+ // trailing zeros removed.
+ static size_t GetLengthWithoutTrailingZeros(
+ const std::string& str,
+ size_t length);
+
+ // Returns the digit at position i, padding with kZeroDigit if required.
+ static uint8 GetDigit(const std::string& str, size_t i);
+
+ // Returns the digit value at position i, padding with 0 if required.
+ static int GetDigitValue(const std::string& str, size_t i);
+
+ // Adds the given value to |str| at position i, carrying when
+ // necessary. Returns the left-most carry.
+ static int AddDigitValue(std::string* str, size_t i, int digit_value);
+
+ // Returns the proper length |ordinal| should be resized to,
+ // i.e. the smallest length such that |ordinal| is still greater
+ // than |lower_bound| and is still valid. |ordinal| should be
+ // greater than |lower_bound|.
+ static size_t GetProperLength(const std::string& lower_bound,
+ const std::string& ordinal);
+
+ // Compute the midpoint string that is between |start| and |end|.
+ static std::string ComputeMidpoint(const std::string& start,
+ const std::string& end);
+
+ // Create a Ordinal that is lexigraphically greater than |start| and
+ // lexigraphically less than |end|. The returned Ordinal will be roughly
+ // between |start| and |end|.
+ static Ordinal<Traits> CreateOrdinalBetween(const Ordinal<Traits>& start,
+ const Ordinal<Traits>& end);
+
+ // The string representation of the Ordinal.
+ std::string ordinal_string_;
+
+ // The validity of the Ordinal created to cache validity to prevent
+ // frequent recalculations.
+ bool is_valid_;
+};
+
+template <typename Traits> const uint8 Ordinal<Traits>::kZeroDigit;
+template <typename Traits> const uint8 Ordinal<Traits>::kMaxDigit;
+template <typename Traits> const size_t Ordinal<Traits>::kMinLength;
+template <typename Traits> const uint8 Ordinal<Traits>::kOneDigit;
+template <typename Traits> const uint8 Ordinal<Traits>::kMidDigit;
+template <typename Traits> const unsigned int Ordinal<Traits>::kMidDigitValue;
+template <typename Traits> const unsigned int Ordinal<Traits>::kMaxDigitValue;
+template <typename Traits> const unsigned int Ordinal<Traits>::kRadix;
+
+template <typename Traits>
+Ordinal<Traits>::LessThanFn::LessThanFn() {}
+
+template <typename Traits>
+bool Ordinal<Traits>::LessThanFn::operator()(const Ordinal<Traits>& lhs,
+ const Ordinal<Traits>& rhs) const {
+ return lhs.LessThan(rhs);
+}
+
+template <typename Traits>
+Ordinal<Traits>::EqualsFn::EqualsFn() {}
+
+template <typename Traits>
+bool Ordinal<Traits>::EqualsFn::operator()(const Ordinal<Traits>& lhs,
+ const Ordinal<Traits>& rhs) const {
+ return lhs.Equals(rhs);
+}
+
+template <typename Traits>
+Ordinal<Traits>::Ordinal(const std::string& ordinal_string)
+ : ordinal_string_(ordinal_string),
+ is_valid_(IsValidOrdinalString(ordinal_string_)) {}
+
+template <typename Traits>
+Ordinal<Traits>::Ordinal() : is_valid_(false) {}
+
+template <typename Traits>
+Ordinal<Traits> Ordinal<Traits>::CreateInitialOrdinal() {
+ std::string ordinal_string(Traits::kMinLength, kZeroDigit);
+ ordinal_string[0] = kMidDigit;
+ return Ordinal(ordinal_string);
+}
+
+template <typename Traits>
+bool Ordinal<Traits>::IsValid() const {
+ return is_valid_;
rlarocque 2012/09/05 21:43:46 I'd feel safer if there was a DCHECK(IsInvalidOrdi
akalin 2012/09/06 19:25:14 assuming you meant DCHECK_EQ(is_valid_, ...), done
rlarocque 2012/09/06 21:25:55 Correct. Thanks.
+}
+
+template <typename Traits>
+bool Ordinal<Traits>::EqualsOrBothInvalid(const Ordinal& other) const {
+ if (!IsValid() && !other.IsValid())
+ return true;
+
+ if (!IsValid() || !other.IsValid())
+ return false;
+
+ return Equals(other);
+}
+
+template <typename Traits>
+bool Ordinal<Traits>::LessThan(const Ordinal& other) const {
+ CHECK(IsValid());
+ CHECK(other.IsValid());
+ return ordinal_string_ < other.ordinal_string_;
+}
+
+template <typename Traits>
+bool Ordinal<Traits>::GreaterThan(const Ordinal& other) const {
+ CHECK(IsValid());
+ CHECK(other.IsValid());
+ return ordinal_string_ > other.ordinal_string_;
+}
+
+template <typename Traits>
+bool Ordinal<Traits>::Equals(const Ordinal& other) const {
+ CHECK(IsValid());
+ CHECK(other.IsValid());
+ return ordinal_string_ == other.ordinal_string_;
+}
+
+template <typename Traits>
+Ordinal<Traits> Ordinal<Traits>::CreateBetween(const Ordinal& other) const {
+ CHECK(IsValid());
+ CHECK(other.IsValid());
+ CHECK(!Equals(other));
+
+ if (LessThan(other)) {
+ return CreateOrdinalBetween(*this, other);
+ } else {
+ return CreateOrdinalBetween(other, *this);
+ }
+}
+
+template <typename Traits>
+Ordinal<Traits> Ordinal<Traits>::CreateBefore() const {
+ CHECK(IsValid());
+ // Create the smallest valid Ordinal of the appropriate length
+ // to be the minimum boundary.
+ const size_t length = ordinal_string_.length();
+ std::string start(length, kZeroDigit);
+ start[length - 1] = kOneDigit;
+ if (start == ordinal_string_) {
+ start[length - 1] = kZeroDigit;
+ start += kOneDigit;
+ }
+
+ // Even though |start| is already a valid Ordinal that is less
+ // than |*this|, we don't return it because we wouldn't have much space in
+ // front of it to insert potential future values.
+ return CreateBetween(Ordinal(start));
+}
+
+template <typename Traits>
+Ordinal<Traits> Ordinal<Traits>::CreateAfter() const {
+ CHECK(IsValid());
+ // Create the largest valid Ordinal of the appropriate length to be
+ // the maximum boundary.
+ std::string end(ordinal_string_.length(), kMaxDigit);
+ if (end == ordinal_string_)
+ end += kMaxDigit;
+
+ // Even though |end| is already a valid Ordinal that is greater than
+ // |*this|, we don't return it because we wouldn't have much space after
+ // it to insert potential future values.
+ return CreateBetween(Ordinal(end));
+}
+
+template <typename Traits>
+std::string Ordinal<Traits>::ToString() const {
+ CHECK(IsValid());
+ return ordinal_string_;
+}
+
+template <typename Traits>
+bool Ordinal<Traits>::IsValidOrdinalString(const std::string& str) {
+ const size_t length = str.length();
+ if (length < kMinLength)
+ return false;
+
+ bool found_non_zero = false;
+ for (size_t i = 0; i < length; ++i) {
+ const uint8 byte = str[i];
+ if (byte < kZeroDigit || byte > kMaxDigit)
+ return false;
+ if (byte > kZeroDigit)
+ found_non_zero = true;
+ }
+ if (!found_non_zero)
+ return false;
+
+ if (length > kMinLength) {
+ const uint8 last_byte = str[str.length() - 1];
+ if (last_byte == kZeroDigit)
+ return false;
+ }
+
+ return true;
+}
+
+template <typename Traits>
+size_t Ordinal<Traits>::GetLengthWithoutTrailingZeros(
+ const std::string& str, size_t length) {
+ DCHECK(!str.empty());
+ DCHECK_GT(length, 0U);
+
+ size_t end_position =
+ str.find_last_not_of(static_cast<char>(kZeroDigit), length - 1);
+
+ // If no non kZeroDigit is found then the string is a string of all zeros
+ // digits so we return 0 as the correct length.
+ if (end_position == std::string::npos)
+ return 0;
+
+ return end_position + 1;
+}
+
+template <typename Traits>
+uint8 Ordinal<Traits>::GetDigit(const std::string& str, size_t i) {
+ return (i < str.length()) ? str[i] : kZeroDigit;
+}
+
+template <typename Traits>
+int Ordinal<Traits>::GetDigitValue(const std::string& str, size_t i) {
+ return GetDigit(str, i) - kZeroDigit;
+}
+
+template <typename Traits>
+int Ordinal<Traits>::AddDigitValue(std::string* str,
+ size_t i, int digit_value) {
+ DCHECK_GE(i, 0U);
+ DCHECK_LT(i, str->length());
+
+ for (int j = i; j >= 0 && digit_value > 0; --j) {
+ int str_j_value = GetDigitValue(*str, j) + digit_value;
+ digit_value = str_j_value / kRadix;
+ DCHECK_LE(digit_value, 1);
+ str_j_value %= kRadix;
+ (*str)[j] = static_cast<char>(kZeroDigit + str_j_value);
+ }
+ return digit_value;
+}
+
+template <typename Traits>
+size_t Ordinal<Traits>::GetProperLength(const std::string& lower_bound,
+ const std::string& ordinal) {
+ CHECK_GT(ordinal, lower_bound);
+
+ size_t drop_length = GetLengthWithoutTrailingZeros(ordinal, ordinal.length());
+ // See if the |ordinal| can be truncated after its last non-zero
+ // digit without affecting the ordering.
+ if (drop_length > kMinLength) {
+ size_t truncated_length =
+ GetLengthWithoutTrailingZeros(ordinal, drop_length - 1);
+
+ if (truncated_length > 0 &&
+ ordinal.compare(0, truncated_length, lower_bound) > 0)
+ drop_length = truncated_length;
+ }
+ return std::max(drop_length, kMinLength);
+}
+
+template <typename Traits>
+std::string Ordinal<Traits>::ComputeMidpoint(
+ const std::string& start,
+ const std::string& end) {
+ size_t max_size = std::max(start.length(), end.length()) + 1;
+ std::string midpoint(max_size, kZeroDigit);
+
+ // Perform the operation (start + end) / 2 left-to-right by
+ // maintaining a "forward carry" which is either 0 or
+ // kMidDigitValue. AddDigitValue() is in general O(n), but this
+ // operation is still O(n) despite that; calls to AddDigitValue()
+ // will overflow at most to the last position where AddDigitValue()
+ // last overflowed.
+ int forward_carry = 0;
+ for (size_t i = 0; i < max_size; ++i) {
+ const int sum_value = GetDigitValue(start, i) + GetDigitValue(end, i);
+ const int digit_value = sum_value / 2 + forward_carry;
+ // AddDigitValue returning a non-zero carry would imply that
+ // midpoint[0] >= kMaxDigit, which one can show is impossible.
+ CHECK_EQ(AddDigitValue(&midpoint, i, digit_value), 0);
+ forward_carry = (sum_value % 2 == 1) ? kMidDigitValue : 0;
+ }
+ DCHECK_EQ(forward_carry, 0);
+
+ return midpoint;
+}
+
+template <typename Traits>
+Ordinal<Traits> Ordinal<Traits>::CreateOrdinalBetween(
+ const Ordinal<Traits>& start,
+ const Ordinal<Traits>& end) {
+ CHECK(start.IsValid());
+ CHECK(end.IsValid());
+ CHECK(start.LessThan(end));
+ const std::string& start_string = start.ToString();
+ const std::string& end_string = end.ToString();
+ DCHECK_LT(start_string, end_string);
+
+ std::string midpoint = ComputeMidpoint(start_string, end_string);
+ const size_t proper_length = GetProperLength(start_string, midpoint);
+ midpoint.resize(proper_length, kZeroDigit);
+
+ DCHECK_GT(midpoint, start_string);
+ DCHECK_LT(midpoint, end_string);
+
+ Ordinal<Traits> midpoint_ordinal(midpoint);
+ DCHECK(midpoint_ordinal.IsValid());
+ return midpoint_ordinal;
+}
+
+template <typename Traits>
+void PrintTo(const Ordinal<Traits>& ordinal, ::std::ostream* os) {
+ *os << (ordinal.IsValid() ? ordinal.ToString() : "[invalid]");
+}
+
+} // namespace syncer
+
+#endif // SYNC_INTERNAL_API_PUBLIC_BASE_ORDINAL_H_

Powered by Google App Engine
This is Rietveld 408576698