// Return the right-most interval stored in the tree.
14148
func (t *IntTree) Max() IntInterface {
	if t.Root == nil {
		return nil
	}
	return t.Root.max().Elem
}
296237
func (t *Tree) Nearest(q Comparable) (Comparable, float64) {
	if t.Root == nil {
		return nil, inf
	}
	n, dist := t.Root.search(q, inf)
	if n == nil {
		return nil, inf
	}
	return n.Point, dist
}
109596
func (irt *immutableRangeTree) Query(interval Interval) Entries {
	entries := NewEntries()

	irt.apply(irt.top, interval, 1, func(n *node) bool {
		entries = append(entries, n.entry)
		return true
	})

	return entries
}
1021218
func (mc MongoClient) getIntervals(q bson.M) ([]models.Interval, error) {
	s := mc.getSessionCopy()
	defer s.Close()

	var mi []models.Interval
	if err := s.DB(mc.database.Name).C(db.Interval).Find(q).All(&mi); err != nil {
		return []models.Interval{}, errorMap(err)
	}
	return mi, nil
}
856426
func (qt *quadtreeNode) getIndex(pRect AABB) int {
	horzMidpoint := qt.Bounds.Min.X + (aabbWidth(qt.Bounds) / 2)
	vertMidpoint := qt.Bounds.Min.Y + (aabbHeight(qt.Bounds) / 2)

	//pRect can completely fit within the top quadrants
	topQuadrant := (pRect.Min.Y < vertMidpoint) && (pRect.Max.Y < vertMidpoint)

	//pRect can completely fit within the bottom quadrants
	bottomQuadrant := (pRect.Min.Y > vertMidpoint)

	//pRect can completely fit within the left quadrants
	if (pRect.Min.X < horzMidpoint) && (pRect.Max.X < horzMidpoint) {
		if topQuadrant {
			return 1
		} else if bottomQuadrant {
			return 2
		}
	} else if pRect.Min.X > horzMidpoint {
		//pRect can completely fit within the right quadrants
		if topQuadrant {
			return 0
		} else if bottomQuadrant {
			return 3
		}
	}

	return -1 // index of the subnode (0-3), or -1 if pRect cannot completely fit within a subnode and is part of the parent node
}
1214209
func Interval(d time.Duration) Option {
	return func(c Cache) error {
		switch oc := c.(type) {
		case *cache:
			oc.interval = d
			return nil
		default:
			return errors.New(ErrIllegalCache, errorMessages)
		}
	}
}
183348
func (tree *tree) Add(intervals ...Interval) {
	for _, iv := range intervals {
		tree.add(iv)
	}
}
493167
func (i Interval) ContainsInterval(oi Interval) bool {
	if i.IsInverted() {
		if oi.IsInverted() {
			return oi.Lo >= i.Lo && oi.Hi <= i.Hi
		}
		return (oi.Lo >= i.Lo || oi.Hi <= i.Hi) && !i.IsEmpty()
	}
	if oi.IsInverted() {
		return i.IsFull() || oi.IsEmpty()
	}
	return oi.Lo >= i.Lo && oi.Hi <= i.Hi
}
1324001
func WithCompactionInterval(interval string) OptionFunc {
	return func(n *Node) error {
		if interval == "" {
			n.compactionInterval = defaultCompactionInterval
			return nil
		}
		ci, err := time.ParseDuration(interval)
		if err != nil {
			return err
		}
		n.compactionInterval = ci
		return nil
	}
}
1059429
func (node *IntervalExpr) Format(buf *TrackedBuffer) {
	buf.Myprintf("interval %v %s", node.Expr, node.Unit)
}
67877
func (i Interval) Intersection(oi Interval) Interval {
	if oi.IsEmpty() {
		return EmptyInterval()
	}
	if i.fastContains(oi.Lo) {
		if i.fastContains(oi.Hi) {
			// Either oi ⊂ i, or i and oi intersect twice. Neither are empty.
			// In the first case we want to return i (which is shorter than oi).
			// In the second case one of them is inverted, and the smallest interval
			// that covers the two disjoint pieces is the shorter of i and oi.
			// We thus want to pick the shorter of i and oi in both cases.
			if oi.Length() < i.Length() {
				return oi
			}
			return i
		}
		return Interval{oi.Lo, i.Hi}
	}
	if i.fastContains(oi.Hi) {
		return Interval{i.Lo, oi.Hi}
	}

	// Neither endpoint of oi is in i. Either i ⊂ oi, or i and oi are disjoint.
	if oi.fastContains(i.Lo) {
		return i
	}
	return EmptyInterval()
}
889314
func PercentileContIntervalFinal(db XODB, v0 pgtypes.Internal, v1 float64) (*time.Duration, error) {
	var err error

	// sql query
	const sqlstr = `SELECT pg_catalog.percentile_cont_interval_final($1, $2)`

	// run query
	var ret *time.Duration
	XOLog(sqlstr, v0, v1)
	err = db.QueryRow(sqlstr, v0, v1).Scan(&ret)
	if err != nil {
		return nil, err
	}

	return ret, nil
}
426297
func (t *ImmutableTree) GetRangeWithProof(startKey []byte, endKey []byte, limit int) (keys, values [][]byte, proof *RangeProof, err error) {
	proof, keys, values, err = t.getRangeProof(startKey, endKey, limit)
	return
}
107274
func (tree *tree) Delete(intervals ...Interval) {
	for _, iv := range intervals {
		tree.delete(iv)
	}
	if tree.root != nil {
		tree.root.adjustRanges()
	}
}
1322062
func CompactInterval(seconds int) FileStoreOption {
	return func(o *FileStoreOptions) error {
		if seconds <= 0 {
			return fmt.Errorf("compact interval value must at least be 1 seconds")
		}
		o.CompactInterval = seconds
		return nil
	}
}
550554
func (h *Hasher) getTree() *tree {
	if h.bmt != nil {
		return h.bmt
	}
	t := h.pool.reserve()
	h.bmt = t
	return t
}
304602
func (tree *tree) add(iv Interval) {
	if tree.root == nil {
		tree.root = newNode(
			iv, iv.LowAtDimension(1),
			iv.HighAtDimension(1),
			1,
		)
		tree.root.red = false
		tree.number++
		return
	}

	tree.resetDummy()
	var (
		dummy               = tree.dummy
		parent, grandParent *node
		node                = tree.root
		dir, last           int
		otherLast           = 1
		id                  = iv.ID()
		max                 = iv.HighAtDimension(1)
		ivLow               = iv.LowAtDimension(1)
		helper              = &dummy
	)

	// set this AFTER clearing dummy
	helper.children[1] = tree.root
	for {
		if node == nil {
			node = newNode(iv, ivLow, max, 1)
			parent.children[dir] = node
			tree.number++
		} else if isRed(node.children[0]) && isRed(node.children[1]) {
			node.red = true
			node.children[0].red = false
			node.children[1].red = false
		}
		if max > node.max {
			node.max = max
		}

		if ivLow < node.min {
			node.min = ivLow
		}

		if isRed(parent) && isRed(node) {
			localDir := intFromBool(helper.children[1] == grandParent)

			if node == parent.children[last] {
				helper.children[localDir] = rotate(grandParent, otherLast)
			} else {
				helper.children[localDir] = doubleRotate(grandParent, otherLast)
			}
		}

		if node.id == id {
			break
		}

		last = dir
		otherLast = takeOpposite(last)
		dir = compare(node.interval.LowAtDimension(1), ivLow, node.id, id)

		if grandParent != nil {
			helper = grandParent
		}
		grandParent, parent, node = parent, node, node.children[dir]
	}

	tree.root = dummy.children[1]
	tree.root.red = false
}