15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef SYNC_INTERNAL_API_PUBLIC_BASE_ORDINAL_H_ 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define SYNC_INTERNAL_API_PUBLIC_BASE_ORDINAL_H_ 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <algorithm> 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <cstddef> 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <string> 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/basictypes.h" 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/json/string_escape.h" 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h" 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace syncer { 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// An Ordinal<T> is an object that can be used for ordering. The 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Ordinal<T> class has an unbounded dense strict total order, which 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// mean for any Ordinal<T>s a, b and c: 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// - a < b and b < c implies a < c (transitivity); 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// - exactly one of a < b, b < a and a = b holds (trichotomy); 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// - if a < b, there is a Ordinal<T> x such that a < x < b (density); 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// - there are Ordinals<T> x and y such that x < a < y (unboundedness). 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This means that when Ordinal<T> is used for sorting a list, if any 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// item changes its position in the list, only its Ordinal<T> value 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// has to change to represent the new order, and all the other values 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// can stay the same. 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// An Ordinal<T> is internally represented as an array of bytes, so it 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// can be serialized to and deserialized from disk. 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The Traits class should look like the following: 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// // Don't forget to #include "base/basictypes.h". 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// struct MyOrdinalTraits { 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// // There must be at least two distinct values greater than kZeroDigit 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// // and less than kMaxDigit. 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// static const uint8 kZeroDigit = '0'; 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// static const uint8 kMaxDigit = '9'; 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// // kMinLength must be positive. 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// static const size_t kMinLength = 1; 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// }; 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// An Ordinal<T> is valid iff its corresponding string has at least 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// kMinLength characters, does not contain any characters less than 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// kZeroDigit or greater than kMaxDigit, is not all zero digits, and 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// does not have any unnecessary trailing zero digits. 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Note that even if the native char type is signed, strings still 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// compare as if their they are unsigned. (This is explicitly in 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// C++11 but not in C++98, even though all implementations do so 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// anyway in practice.) Thus, it is safe to use any byte range for 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Ordinal<T>s. 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class Ordinal { 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Functors for use with STL algorithms and containers. 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class LessThanFn { 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LessThanFn(); 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool operator()(const Ordinal<Traits>& lhs, 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Ordinal<Traits>& rhs) const; 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) class EqualsFn { 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EqualsFn(); 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool operator()(const Ordinal<Traits>& lhs, 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Ordinal<Traits>& rhs) const; 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Creates an Ordinal from the given string of bytes. The Ordinal 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // may be valid or invalid. 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit Ordinal(const std::string& bytes); 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Creates an invalid Ordinal. 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Ordinal(); 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Creates a valid initial Ordinal. This is called to create the first 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // element of Ordinal list (i.e. before we have any other values we can 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // generate from). 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static Ordinal CreateInitialOrdinal(); 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns true iff this Ordinal is valid. This takes constant 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // time. 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsValid() const; 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns true iff |*this| == |other| or |*this| and |other| 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // are both invalid. 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool EqualsOrBothInvalid(const Ordinal& other) const; 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns a printable string representation of the Ordinal suitable 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // for logging. 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string ToDebugString() const; 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // All remaining functions can only be called if IsValid() holds. 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // It is an error to call them if IsValid() is false. 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Order-related functions. 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns true iff |*this| < |other|. 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool LessThan(const Ordinal& other) const; 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns true iff |*this| > |other|. 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool GreaterThan(const Ordinal& other) const; 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns true iff |*this| == |other| (i.e. |*this| < |other| and 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // |other| < |*this| are both false). 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool Equals(const Ordinal& other) const; 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Given |*this| != |other|, returns a Ordinal x such that 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // min(|*this|, |other|) < x < max(|*this|, |other|). It is an error 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to call this function when |*this| == |other|. 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Ordinal CreateBetween(const Ordinal& other) const; 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns a Ordinal |x| such that |x| < |*this|. 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Ordinal CreateBefore() const; 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns a Ordinal |x| such that |*this| < |x|. 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Ordinal CreateAfter() const; 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns the string of bytes representing the Ordinal. It is 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // guaranteed that an Ordinal constructed from the returned string 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // will be valid. 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string ToInternalValue() const; 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Use of copy constructor and default assignment for this class is allowed. 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Constants for Ordinal digits. 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const uint8 kZeroDigit = Traits::kZeroDigit; 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const uint8 kMaxDigit = Traits::kMaxDigit; 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const size_t kMinLength = Traits::kMinLength; 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const uint8 kOneDigit = kZeroDigit + 1; 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const uint8 kMidDigit = kOneDigit + (kMaxDigit - kOneDigit) / 2; 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const unsigned int kMidDigitValue = kMidDigit - kZeroDigit; 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const unsigned int kMaxDigitValue = kMaxDigit - kZeroDigit; 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const unsigned int kRadix = kMaxDigitValue + 1; 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) COMPILE_ASSERT(kOneDigit > kZeroDigit, OrdinalOneDigitGreaterThanMinDigit); 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) COMPILE_ASSERT(kMidDigit > kOneDigit, OrdinalMidDigitGreaterThanOneDigit); 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) COMPILE_ASSERT(kMaxDigit > kMidDigit, OrdinalMaxDigitGreaterThanMidDigit); 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) COMPILE_ASSERT(kMinLength > 0, OrdinalMinLengthIsPositive); 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) COMPILE_ASSERT(kMidDigitValue > 1, OrdinalMidDigitValueGreaterThanOne); 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) COMPILE_ASSERT(kMaxDigitValue > kMidDigitValue, 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) OrdinalMaxDigitValueGreaterThanMidDigitValue); 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) COMPILE_ASSERT(kRadix == kMaxDigitValue + 1, 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) OrdinalRadixIsMaxDigitValuePlusOne); 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns true iff the given byte string satisfies the criteria for 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // a valid Ordinal. 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static bool IsValidOrdinalBytes(const std::string& bytes); 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns the length that bytes.substr(0, length) would be with 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // trailing zero digits removed. 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static size_t GetLengthWithoutTrailingZeroDigits( 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::string& bytes, 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t length); 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns the digit at position i, padding with zero digits if 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // required. 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static uint8 GetDigit(const std::string& bytes, size_t i); 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns the digit value at position i, padding with 0 if required. 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static int GetDigitValue(const std::string& bytes, size_t i); 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Adds the given value to |bytes| at position i, carrying when 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // necessary. Returns the left-most carry. 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static int AddDigitValue(std::string* bytes, size_t i, int digit_value); 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns the proper length |bytes| should be resized to, i.e. the 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // smallest length such that |bytes| is still greater than 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // |lower_bound| and is still valid. |bytes| should be greater than 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // |lower_bound|. 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static size_t GetProperLength(const std::string& lower_bound, 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::string& bytes); 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Compute the midpoint ordinal byte string that is between |start| 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and |end|. 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static std::string ComputeMidpoint(const std::string& start, 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::string& end); 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create a Ordinal that is lexigraphically greater than |start| and 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // lexigraphically less than |end|. The returned Ordinal will be roughly 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // between |start| and |end|. 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static Ordinal<Traits> CreateOrdinalBetween(const Ordinal<Traits>& start, 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Ordinal<Traits>& end); 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The internal byte string representation of the Ordinal. Never 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // changes after construction except for assignment. 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string bytes_; 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // A cache of the result of IsValidOrdinalBytes(bytes_). 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool is_valid_; 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> const uint8 Ordinal<Traits>::kZeroDigit; 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> const uint8 Ordinal<Traits>::kMaxDigit; 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> const size_t Ordinal<Traits>::kMinLength; 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> const uint8 Ordinal<Traits>::kOneDigit; 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> const uint8 Ordinal<Traits>::kMidDigit; 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> const unsigned int Ordinal<Traits>::kMidDigitValue; 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> const unsigned int Ordinal<Traits>::kMaxDigitValue; 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> const unsigned int Ordinal<Traits>::kRadix; 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Ordinal<Traits>::LessThanFn::LessThanFn() {} 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool Ordinal<Traits>::LessThanFn::operator()(const Ordinal<Traits>& lhs, 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Ordinal<Traits>& rhs) const { 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return lhs.LessThan(rhs); 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Ordinal<Traits>::EqualsFn::EqualsFn() {} 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool Ordinal<Traits>::EqualsFn::operator()(const Ordinal<Traits>& lhs, 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Ordinal<Traits>& rhs) const { 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return lhs.Equals(rhs); 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Ordinal<Traits>::Ordinal(const std::string& bytes) 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : bytes_(bytes), 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) is_valid_(IsValidOrdinalBytes(bytes_)) {} 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Ordinal<Traits>::Ordinal() : is_valid_(false) {} 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Ordinal<Traits> Ordinal<Traits>::CreateInitialOrdinal() { 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string bytes(Traits::kMinLength, kZeroDigit); 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bytes[0] = kMidDigit; 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Ordinal(bytes); 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool Ordinal<Traits>::IsValid() const { 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_EQ(IsValidOrdinalBytes(bytes_), is_valid_); 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return is_valid_; 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool Ordinal<Traits>::EqualsOrBothInvalid(const Ordinal& other) const { 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!IsValid() && !other.IsValid()) 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!IsValid() || !other.IsValid()) 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Equals(other); 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)std::string Ordinal<Traits>::ToDebugString() const { 2635d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) std::string debug_string = 2645d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) base::EscapeBytesAsInvalidJSONString(bytes_, false /* put_in_quotes */); 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!is_valid_) { 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) debug_string = "INVALID[" + debug_string + "]"; 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return debug_string; 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool Ordinal<Traits>::LessThan(const Ordinal& other) const { 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(IsValid()); 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(other.IsValid()); 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return bytes_ < other.bytes_; 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool Ordinal<Traits>::GreaterThan(const Ordinal& other) const { 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(IsValid()); 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(other.IsValid()); 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return bytes_ > other.bytes_; 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool Ordinal<Traits>::Equals(const Ordinal& other) const { 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(IsValid()); 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(other.IsValid()); 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return bytes_ == other.bytes_; 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Ordinal<Traits> Ordinal<Traits>::CreateBetween(const Ordinal& other) const { 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(IsValid()); 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(other.IsValid()); 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(!Equals(other)); 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (LessThan(other)) { 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CreateOrdinalBetween(*this, other); 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CreateOrdinalBetween(other, *this); 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Ordinal<Traits> Ordinal<Traits>::CreateBefore() const { 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(IsValid()); 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create the smallest valid Ordinal of the appropriate length 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to be the minimum boundary. 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t length = bytes_.length(); 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string start(length, kZeroDigit); 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) start[length - 1] = kOneDigit; 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (start == bytes_) { 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) start[length - 1] = kZeroDigit; 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) start += kOneDigit; 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Even though |start| is already a valid Ordinal that is less 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // than |*this|, we don't return it because we wouldn't have much space in 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // front of it to insert potential future values. 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CreateBetween(Ordinal(start)); 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Ordinal<Traits> Ordinal<Traits>::CreateAfter() const { 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(IsValid()); 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Create the largest valid Ordinal of the appropriate length to be 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the maximum boundary. 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string end(bytes_.length(), kMaxDigit); 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (end == bytes_) 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) end += kMaxDigit; 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Even though |end| is already a valid Ordinal that is greater than 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // |*this|, we don't return it because we wouldn't have much space after 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // it to insert potential future values. 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return CreateBetween(Ordinal(end)); 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)std::string Ordinal<Traits>::ToInternalValue() const { 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(IsValid()); 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return bytes_; 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool Ordinal<Traits>::IsValidOrdinalBytes(const std::string& bytes) { 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t length = bytes.length(); 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (length < kMinLength) 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool found_non_zero = false; 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < length; ++i) { 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint8 byte = bytes[i]; 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (byte < kZeroDigit || byte > kMaxDigit) 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (byte > kZeroDigit) 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) found_non_zero = true; 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!found_non_zero) 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (length > kMinLength) { 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint8 last_byte = bytes[length - 1]; 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (last_byte == kZeroDigit) 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)size_t Ordinal<Traits>::GetLengthWithoutTrailingZeroDigits( 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::string& bytes, size_t length) { 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(!bytes.empty()); 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GT(length, 0U); 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t end_position = 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bytes.find_last_not_of(static_cast<char>(kZeroDigit), length - 1); 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If no non kZeroDigit is found then the string is a string of all zeros 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // digits so we return 0 as the correct length. 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (end_position == std::string::npos) 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return end_position + 1; 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)uint8 Ordinal<Traits>::GetDigit(const std::string& bytes, size_t i) { 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (i < bytes.length()) ? bytes[i] : kZeroDigit; 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int Ordinal<Traits>::GetDigitValue(const std::string& bytes, size_t i) { 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return GetDigit(bytes, i) - kZeroDigit; 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int Ordinal<Traits>::AddDigitValue(std::string* bytes, 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t i, int digit_value) { 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GE(i, 0U); 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LT(i, bytes->length()); 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 404f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) for (int j = static_cast<int>(i); j >= 0 && digit_value > 0; --j) { 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int byte_j_value = GetDigitValue(*bytes, j) + digit_value; 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) digit_value = byte_j_value / kRadix; 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LE(digit_value, 1); 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) byte_j_value %= kRadix; 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) (*bytes)[j] = static_cast<char>(kZeroDigit + byte_j_value); 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return digit_value; 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)size_t Ordinal<Traits>::GetProperLength(const std::string& lower_bound, 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::string& bytes) { 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_GT(bytes, lower_bound); 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t drop_length = 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GetLengthWithoutTrailingZeroDigits(bytes, bytes.length()); 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // See if the |ordinal| can be truncated after its last non-zero 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // digit without affecting the ordering. 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (drop_length > kMinLength) { 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t truncated_length = 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) GetLengthWithoutTrailingZeroDigits(bytes, drop_length - 1); 4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (truncated_length > 0 && 4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bytes.compare(0, truncated_length, lower_bound) > 0) 4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) drop_length = truncated_length; 4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return std::max(drop_length, kMinLength); 4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)std::string Ordinal<Traits>::ComputeMidpoint( 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::string& start, 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::string& end) { 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t max_size = std::max(start.length(), end.length()) + 1; 4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string midpoint(max_size, kZeroDigit); 4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Perform the operation (start + end) / 2 left-to-right by 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // maintaining a "forward carry" which is either 0 or 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // kMidDigitValue. AddDigitValue() is in general O(n), but this 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // operation is still O(n) despite that; calls to AddDigitValue() 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // will overflow at most to the last position where AddDigitValue() 4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // last overflowed. 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int forward_carry = 0; 4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < max_size; ++i) { 4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int sum_value = GetDigitValue(start, i) + GetDigitValue(end, i); 4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int digit_value = sum_value / 2 + forward_carry; 4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // AddDigitValue returning a non-zero carry would imply that 4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // midpoint[0] >= kMaxDigit, which one can show is impossible. 4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_EQ(AddDigitValue(&midpoint, i, digit_value), 0); 4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) forward_carry = (sum_value % 2 == 1) ? kMidDigitValue : 0; 4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_EQ(forward_carry, 0); 4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return midpoint; 4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <typename Traits> 4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Ordinal<Traits> Ordinal<Traits>::CreateOrdinalBetween( 4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Ordinal<Traits>& start, 4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Ordinal<Traits>& end) { 4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(start.IsValid()); 4665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(end.IsValid()); 4675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(start.LessThan(end)); 4685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::string& start_bytes = start.ToInternalValue(); 4695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const std::string& end_bytes = end.ToInternalValue(); 4705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LT(start_bytes, end_bytes); 4715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) std::string midpoint = ComputeMidpoint(start_bytes, end_bytes); 4735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t proper_length = GetProperLength(start_bytes, midpoint); 4745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) midpoint.resize(proper_length, kZeroDigit); 4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_GT(midpoint, start_bytes); 4775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK_LT(midpoint, end_bytes); 4785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Ordinal<Traits> midpoint_ordinal(midpoint); 4805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(midpoint_ordinal.IsValid()); 4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return midpoint_ordinal; 4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace syncer 4855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // SYNC_INTERNAL_API_PUBLIC_BASE_ORDINAL_H_ 487