type KV interface {

	// Put puts a key-value pair into etcd.

	// Note that key,value can be plain bytes array and string is

	// an immutable representation of that bytes array.

	// To get a string of bytes, do string([]byte{0x10, 0x20}).

	Put(ctx context.Context, key, val string, opts ...OpOption) (*PutResponse, error)

	// Get retrieves keys.

	// By default, Get will return the value for "key", if any.

	// When passed WithRange(end), Get will return the keys in the range [key, end).

	// When passed WithFromKey(), Get returns keys greater than or equal to key.

	// When passed WithRev(rev) with rev > 0, Get retrieves keys at the given revision;

	// if the required revision is compacted, the request will fail with ErrCompacted .

	// When passed WithLimit(limit), the number of returned keys is bounded by limit.

	// When passed WithSort(), the keys will be sorted.

	Get(ctx context.Context, key string, opts ...OpOption) (*GetResponse, error)

	// Delete deletes a key, or optionally using WithRange(end), [key, end).

	Delete(ctx context.Context, key string, opts ...OpOption) (*DeleteResponse, error)

	// Compact compacts etcd KV history before the given rev.

	Compact(ctx context.Context, rev int64, opts ...CompactOption) (*CompactResponse, error)

	// Txn creates a transaction.

	Txn(ctx context.Context) Txn

}

type Lease interface {

	// Grant creates a new lease.

	Grant(ctx context.Context, ttl int64) (*LeaseGrantResponse, error)

	// Revoke revokes the given lease.

	Revoke(ctx context.Context, id LeaseID) (*LeaseRevokeResponse, error)

	// TimeToLive retrieves the lease information of the given lease ID.

	TimeToLive(ctx context.Context, id LeaseID, opts ...LeaseOption) (*LeaseTimeToLiveResponse, error)

	// Leases retrieves all leases.

	Leases(ctx context.Context) (*LeaseLeasesResponse, error)

	// KeepAlive keeps the given lease alive forever. If the keepalive response

	// posted to the channel is not consumed immediately, the lease client will

	// continue sending keep alive requests to the etcd server at least every

	// second until latest response is consumed.

	//

	// The returned "LeaseKeepAliveResponse" channel closes if underlying keep

	// alive stream is interrupted in some way the client cannot handle itself;

	// given context "ctx" is canceled or timed out. "LeaseKeepAliveResponse"

	// from this closed channel is nil.

	//

	// If client keep alive loop halts with an unexpected error (e.g. "etcdserver:

	// no leader") or canceled by the caller (e.g. context.Canceled), the error

	// is returned. Otherwise, it retries.

	//

	// TODO(v4.0): post errors to last keep alive message before closing

	// (see https://github.com/coreos/etcd/pull/7866)

	KeepAlive(ctx context.Context, id LeaseID) (<-chan *LeaseKeepAliveResponse, error)

	// KeepAliveOnce renews the lease once. The response corresponds to the

	// first message from calling KeepAlive. If the response has a recoverable

	// error, KeepAliveOnce will retry the RPC with a new keep alive message.

	//

	// In most of the cases, Keepalive should be used instead of KeepAliveOnce.

	KeepAliveOnce(ctx context.Context, id LeaseID) (*LeaseKeepAliveResponse, error)

	// Close releases all resources Lease keeps for efficient communication

	// with the etcd server.

	Close() error

}

type Watcher interface {

	// Watch watches on a key or prefix. The watched events will be returned

	// through the returned channel. If revisions waiting to be sent over the

	// watch are compacted, then the watch will be canceled by the server, the

	// client will post a compacted error watch response, and the channel will close.

	// If the context "ctx" is canceled or timed out, returned "WatchChan" is closed,

	// and "WatchResponse" from this closed channel has zero events and nil "Err()".

	// The context "ctx" MUST be canceled, as soon as watcher is no longer being used,

	// to release the associated resources.

	//

	// If the context is "context.Background/TODO", returned "WatchChan" will

	// not be closed and block until event is triggered, except when server

	// returns a non-recoverable error (e.g. ErrCompacted).

	// For example, when context passed with "WithRequireLeader" and the

	// connected server has no leader (e.g. due to network partition),

	// error "etcdserver: no leader" (ErrNoLeader) will be returned,

	// and then "WatchChan" is closed with non-nil "Err()".

	// In order to prevent a watch stream being stuck in a partitioned node,

	// make sure to wrap context with "WithRequireLeader".

	//

	// Otherwise, as long as the context has not been canceled or timed out,

	// watch will retry on other recoverable errors forever until reconnected.

	//

	// TODO: explicitly set context error in the last "WatchResponse" message and close channel?

	// Currently, client contexts are overwritten with "valCtx" that never closes.

	// TODO(v3.4): configure watch retry policy, limit maximum retry number

	// (see https://github.com/etcd-io/etcd/issues/8980)

	Watch(ctx context.Context, key string, opts ...OpOption) WatchChan

	// RequestProgress requests a progress notify response be sent in all watch channels.

	RequestProgress(ctx context.Context) error

	// Close closes the watcher and cancels all watch requests.

	Close() error

}

type revision struct {

	// main is the main revision of a set of changes that happen atomically.

	main int64

	// sub is the the sub revision of a change in a set of changes that happen

	// atomically. Each change has different increasing sub revision in that

	// set.

	sub int64

}

func (a revision) GreaterThan(b revision) bool {

	if a.main > b.main {

		return true

	}

	if a.main < b.main {

		return false

	}

	return a.sub > b.sub

}

type treeIndex struct {

	sync.RWMutex

	tree *btree.BTree

}

func newTreeIndex() index {

	return &treeIndex{

		tree: btree.New(32),

	}

}

func (ti *treeIndex) Put(key []byte, rev revision) {

	keyi := &keyIndex{key: key}

	ti.Lock()

	defer ti.Unlock()

	item := ti.tree.Get(keyi)

	if item == nil {

		keyi.put(rev.main, rev.sub)

		ti.tree.ReplaceOrInsert(keyi)

		return

	}

	okeyi := item.(*keyIndex)

	okeyi.put(rev.main, rev.sub)

}