chromium/components/sync/base/unique_position.h

// Copyright 2012 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef COMPONENTS_SYNC_BASE_UNIQUE_POSITION_H_
#define COMPONENTS_SYNC_BASE_UNIQUE_POSITION_H_

#include <stddef.h>
#include <stdint.h>

#include <string>

namespace sync_pb {
class UniquePosition;
}

namespace syncer {

// A class to represent positions.
//
// Valid UniquePosition objects have the following properties:
//
//  - 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 UniquePosition such that a < x < b (density);
//  - there are UniquePositions x and y such that x < a < y (unboundedness);
//  - if a and b were constructed with different unique suffixes, then a != b.
//
// As long as all UniquePositions used to sort a list were created with unique
// suffixes, then if any item changes its position in the list, only its
// UniquePosition value has to change to represent the new order, and all other
// values can stay the same.
//
// Note that the 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 { … };

}  // namespace syncer

#endif  // COMPONENTS_SYNC_BASE_UNIQUE_POSITION_H_