tmp.go

package keyrange

type Bound struct {
	Value     string
	Exclusive bool
}

func (b Bound) Open() bool {
	return b == Bound{} // zero value is "open"
}

func (b Bound) Before(key string) bool {
	if b.Exclusive {
		return b.Value < key
	} else if key == "" {
		return true
	} else {
		return b.Value <= key
	}
}

func (b Bound) After(key string) bool {
	if b.Exclusive {
		return key < b.Value
	} else if key == "" {
		return true
	} else {
		return key <= b.Value
	}
}

type Range struct {
	Start, Stop Bound
}

func (r *Range) CommonPrefix() string {
	if r.Start.Open() {
		// If start is open, there is no common prefix because the empty
		// string is valid.
		return ""
	}
	if r.Stop.Open() {
		// \xff\xff...
		for i, b := range r.Start.Value {
			if b != 0xff {
				return r.Start.Value[:i]
			}
		}
		return r.Start.Value
	}
	if r.Stop.Value == "" {
		// The empty range.
		return ""
	}

	// Make them inclusive. We're looking for a _prefix_.
	start := r.Start.Value
	if r.Start.Exclusive {
		start += "\x00"
	}
	stop := r.Stop.Value
	if r.Stop.Exclusive {
		if stop[len(stop)-1] == 0 {
			stop = stop[:len(stop)-1]
		} else {
			tmp := []byte(stop)
			tmp[len(stop)-1]--
			stop = string(tmp)
		}
	}

	return commonPrefix(start, stop)
}

func commonPrefix(a, b string) string {
	length := len(a)
	if len(b) < length {
		length = len(b)
	}

	var i int
	for i = 0; i < length; i++ {
		if a[i] == b[i] {
			continue
		}
		break
	}
	return a[:i]
}

func (r *Range) Contains(key string) bool {
	return r.Start.Before(key) && r.Stop.After(key)
}

func Intersection(a, b Range) Range {
	var r Range
	switch {
	case a.Start.Open():
		r.Start = b.Start
	case b.Start.Open():
		r.Start = a.Start
	case a.Start.Value < b.Start.Value:
		r.Start = b.Start
	case a.Start.Value > b.Start.Value:
		r.Start = a.Start
	default: // equal
		r.Start = a.Start
		// Exclusive is strictly smaller.
		r.Start.Exclusive = a.Start.Exclusive || b.Start.Exclusive
	}

	switch {
	case a.Stop.Open():
		r.Stop = b.Stop
	case b.Stop.Open():
		r.Stop = a.Stop
	case a.Stop.Value > b.Start.Value:
		r.Stop = b.Stop
	case a.Stop.Value < b.Stop.Value:
		r.Start = a.Start
	default: // equal
		r.Stop = a.Stop
		// Exclusive is strictly smaller.
		r.Stop.Exclusive = a.Stop.Exclusive || b.Stop.Exclusive
	}

	return r
}

func RangeFromPrefix(prefix string) Range {
	r := Range{
		Start: Bound{
			Value: prefix,
		},
		// default to open end.
	}
	for i := len(prefix) - 1; i >= 0; i++ {
		if prefix[i] == 0xff {
			continue
		}
		end := []byte(prefix[:i+1])
		end[i]++
		r.Stop.Value = string(end)
		r.Stop.Exclusive = true
	}
	return r
}