Lines Matching refs:Ordinal
18 // An Ordinal<T> is an object that can be used for ordering. The
19 // Ordinal<T> class has an unbounded dense strict total order, which
20 // mean for any Ordinal<T>s a, b and c:
24 // - if a < b, there is a Ordinal<T> x such that a < x < b (density);
27 // This means that when Ordinal<T> is used for sorting a list, if any
28 // item changes its position in the list, only its Ordinal<T> value
32 // An Ordinal<T> is internally represented as an array of bytes, so it
47 // An Ordinal<T> is valid iff its corresponding string has at least
56 // Ordinal<T>s.
58 class Ordinal {
65 bool operator()(const Ordinal<Traits>& lhs,
66 const Ordinal<Traits>& rhs) const;
73 bool operator()(const Ordinal<Traits>& lhs,
74 const Ordinal<Traits>& rhs) const;
77 // Creates an Ordinal from the given string of bytes. The Ordinal
79 explicit Ordinal(const std::string& bytes);
81 // Creates an invalid Ordinal.
82 Ordinal();
84 // Creates a valid initial Ordinal. This is called to create the first
85 // element of Ordinal list (i.e. before we have any other values we can
87 static Ordinal CreateInitialOrdinal();
89 // Returns true iff this Ordinal is valid. This takes constant
95 bool EqualsOrBothInvalid(const Ordinal& other) const;
97 // Returns a printable string representation of the Ordinal suitable
107 bool LessThan(const Ordinal& other) const;
110 bool GreaterThan(const Ordinal& other) const;
114 bool Equals(const Ordinal& other) const;
116 // Given |*this| != |other|, returns a Ordinal x such that
119 Ordinal CreateBetween(const Ordinal& other) const;
121 // Returns a Ordinal |x| such that |x| < |*this|.
122 Ordinal CreateBefore() const;
124 // Returns a Ordinal |x| such that |*this| < |x|.
125 Ordinal CreateAfter() const;
127 // Returns the string of bytes representing the Ordinal. It is
128 // guaranteed that an Ordinal constructed from the returned string
134 // Constants for Ordinal digits.
156 // a valid Ordinal.
183 // Compute the midpoint ordinal byte string that is between |start|
188 // Create a Ordinal that is lexigraphically greater than |start| and
189 // lexigraphically less than |end|. The returned Ordinal will be roughly
191 static Ordinal<Traits> CreateOrdinalBetween(const Ordinal<Traits>& start,
192 const Ordinal<Traits>& end);
194 // The internal byte string representation of the Ordinal. Never
202 template <typename Traits> const uint8 Ordinal<Traits>::kZeroDigit;
203 template <typename Traits> const uint8 Ordinal<Traits>::kMaxDigit;
204 template <typename Traits> const size_t Ordinal<Traits>::kMinLength;
205 template <typename Traits> const uint8 Ordinal<Traits>::kOneDigit;
206 template <typename Traits> const uint8 Ordinal<Traits>::kMidDigit;
207 template <typename Traits> const unsigned int Ordinal<Traits>::kMidDigitValue;
208 template <typename Traits> const unsigned int Ordinal<Traits>::kMaxDigitValue;
209 template <typename Traits> const unsigned int Ordinal<Traits>::kRadix;
212 Ordinal<Traits>::LessThanFn::LessThanFn() {}
215 bool Ordinal<Traits>::LessThanFn::operator()(const Ordinal<Traits>& lhs,
216 const Ordinal<Traits>& rhs) const {
221 Ordinal<Traits>::EqualsFn::EqualsFn() {}
224 bool Ordinal<Traits>::EqualsFn::operator()(const Ordinal<Traits>& lhs,
225 const Ordinal<Traits>& rhs) const {
230 Ordinal<Traits>::Ordinal(const std::string& bytes)
235 Ordinal<Traits>::Ordinal() : is_valid_(false) {}
238 Ordinal<Traits> Ordinal<Traits>::CreateInitialOrdinal() {
241 return Ordinal(bytes);
245 bool Ordinal<Traits>::IsValid() const {
251 bool Ordinal<Traits>::EqualsOrBothInvalid(const Ordinal& other) const {
262 std::string Ordinal<Traits>::ToDebugString() const {
272 bool Ordinal<Traits>::LessThan(const Ordinal& other) const {
279 bool Ordinal<Traits>::GreaterThan(const Ordinal& other) const {
286 bool Ordinal<Traits>::Equals(const Ordinal& other) const {
293 Ordinal<Traits> Ordinal<Traits>::CreateBetween(const Ordinal& other) const {
306 Ordinal<Traits> Ordinal<Traits>::CreateBefore() const {
308 // Create the smallest valid Ordinal of the appropriate length
318 // Even though |start| is already a valid Ordinal that is less
321 return CreateBetween(Ordinal(start));
325 Ordinal<Traits> Ordinal<Traits>::CreateAfter() const {
327 // Create the largest valid Ordinal of the appropriate length to be
333 // Even though |end| is already a valid Ordinal that is greater than
336 return CreateBetween(Ordinal(end));
340 std::string Ordinal<Traits>::ToInternalValue() const {
346 bool Ordinal<Traits>::IsValidOrdinalBytes(const std::string& bytes) {
372 size_t Ordinal<Traits>::GetLengthWithoutTrailingZeroDigits(
389 uint8 Ordinal<Traits>::GetDigit(const std::string& bytes, size_t i) {
394 int Ordinal<Traits>::GetDigitValue(const std::string& bytes, size_t i) {
399 int Ordinal<Traits>::AddDigitValue(std::string* bytes,
415 size_t Ordinal<Traits>::GetProperLength(const std::string& lower_bound,
421 // See if the |ordinal| can be truncated after its last non-zero
435 std::string Ordinal<Traits>::ComputeMidpoint(
462 Ordinal<Traits> Ordinal<Traits>::CreateOrdinalBetween(
463 const Ordinal<Traits>& start,
464 const Ordinal<Traits>& end) {
479 Ordinal
