// Select partitions list such that all elements less than the kth largest element are
// placed placed before k in the resulting list and all elements greater than it are placed
// after the position k.
962949
func Select(list SortSlicer, k int) int {
	var (
		start int
		end   = list.Len()
	)
	if k >= end {
		if k == 0 {
			return 0
		}
		panic("kdtree: index out of range")
	}
	if start == end-1 {
		return k
	}

	for {
		if start == end {
			panic("kdtree: internal inconsistency")
		}
		sub := list.Slice(start, end)
		pivot := Partition(sub, rand.Intn(sub.Len()))
		switch {
		case pivot == k:
			return k
		case k < pivot:
			end = pivot + start
		default:
			k -= pivot
			start += pivot
		}
	}
}
1191157
func (r *LeastConn) Select(pool HostPool) *UpstreamHost {
	var bestHost *UpstreamHost
	count := 0
	leastConn := int64(1<<63 - 1)
	for _, host := range pool {
		if host.Down() {
			continue
		}
		hostConns := host.Conns
		if hostConns < leastConn {
			bestHost = host
			leastConn = hostConns
			count = 1
		} else if hostConns == leastConn {
			// randomly select host among hosts with least connections
			count++
			if count == 1 {
				bestHost = host
			} else {
				r := rand.Int() % count
				if r == (count - 1) {
					bestHost = host
				}
			}
		}
	}
	return bestHost
}
1197829
func (c *LeveledCompactor) selectOverlappingDirs(ds []dirMeta) []string {
	if len(ds) < 2 {
		return nil
	}
	var overlappingDirs []string
	globalMaxt := ds[0].meta.MaxTime
	for i, d := range ds[1:] {
		if d.meta.MinTime < globalMaxt {
			if len(overlappingDirs) == 0 { // When it is the first overlap, need to add the last one as well.
				overlappingDirs = append(overlappingDirs, ds[i].dir)
			}
			overlappingDirs = append(overlappingDirs, d.dir)
		} else if len(overlappingDirs) > 0 {
			break
		}
		if d.meta.MaxTime > globalMaxt {
			globalMaxt = d.meta.MaxTime
		}
	}
	return overlappingDirs
}
1011431
func (rc *runContainer16) selectInt16(j uint16) int {
	n := rc.cardinality()
	if int64(j) > n {
		panic(fmt.Sprintf("Cannot select %v since Cardinality is %v", j, n))
	}

	var offset int64
	for k := range rc.iv {
		nextOffset := offset + rc.iv[k].runlen() + 1
		if nextOffset > int64(j) {
			return int(int64(rc.iv[k].start) + (int64(j) - offset))
		}
		offset = nextOffset
	}
	panic(fmt.Sprintf("Cannot select %v since Cardinality is %v", j, n))
}
808183
func (s *Stmt) Select(dest interface{}, args ...interface{}) error {
	return Select(&qStmt{s}, dest, "", args...)
}
30843
func (s *Selection) AfterSelection(sel *Selection) *Selection {
	return s.AfterNodes(sel.Nodes...)
}
907786
func (tx *Tx) Select(dest interface{}, query string, args ...interface{}) error {
	return Select(tx, dest, query, args...)
}
159827
func (rb *Bitmap) Select(x uint32) (uint32, error) {
	if rb.GetCardinality() <= uint64(x) {
		return 0, fmt.Errorf("can't find %dth integer in a bitmap with only %d items", x, rb.GetCardinality())
	}

	remaining := x
	for i := 0; i < rb.highlowcontainer.size(); i++ {
		c := rb.highlowcontainer.getContainerAtIndex(i)
		if remaining >= uint32(c.getCardinality()) {
			remaining -= uint32(c.getCardinality())
		} else {
			key := rb.highlowcontainer.getKeyAtIndex(i)
			return uint32(key)<<16 + uint32(c.selectInt(uint16(remaining))), nil
		}
	}
	return 0, fmt.Errorf("can't find %dth integer in a bitmap with only %d items", x, rb.GetCardinality())
}
809242
func Select(a Type, x interface{}) Type {
	switch a := a.(type) {
	case *Array:
		n, ok := x.(json.Number)
		if !ok {
			return nil
		}
		pos, err := n.Int64()
		if err != nil {
			return nil
		}
		return a.Select(int(pos))
	case *Object:
		return a.Select(x)
	case *Set:
		tpe := TypeOf(x)
		if Compare(a.of, tpe) == 0 {
			return a.of
		}
		if any, ok := a.of.(Any); ok {
			if any.Contains(tpe) {
				return tpe
			}
		}
		return nil
	case Any:
		if Compare(a, A) == 0 {
			return A
		}
		var tpe Type
		for i := range a {
			// TODO(tsandall): test nil/nil
			tpe = Or(Select(a[i], x), tpe)
		}
		return tpe
	default:
		return nil
	}
}
275891
func (fs *FileSorter) ReduceParts() []int {
	parts := make([]int, 0, len(fs.mapOuts))
	for part, _ := range fs.mapOuts {
		parts = append(parts, part)
	}
	// fmt.Println("FileSorter ReduceParts", parts)
	return parts
}
1017765
func partition(s sortEntries) int {
	hi := len(s) - 1
	pivot := s[hi]
	i := 0
	for j := 0; j < hi; j++ {
		r := bytes.Compare(s[j].Name, pivot.Name)
		if r <= 0 {
			s[i], s[j] = s[j], s[i]
			i++
		}
	}
	s[i], s[hi] = s[hi], s[i]
	return i
}
243823
func partition(data sort.Interface, lo, hi int) (int, int) {
	med := median(data, lo, hi)
	idx := lo
	data.Swap(med, hi)
	for i := lo; i < hi; i++ {
		if data.Less(i, hi) {
			data.Swap(i, idx)
			idx++
		}
	}
	data.Swap(idx, hi)
	return idx - 1, idx + 1
}
755314
func (n *BuilderNode) Partitions() []int {
	n.builder.ring.FillReplicaToNodeToPartitions()
	var partitions holdme.OrderedIntsNoDups
	for _, nodeToPartitions := range n.builder.ring.ReplicaToNodeToPartitions {
		for _, partition := range nodeToPartitions[n.index] {
			partitions.Add(int(partition))
		}
	}
	return partitions
}
276554
func (l VirtualDeviceList) Select(f func(device types.BaseVirtualDevice) bool) VirtualDeviceList {
	var found VirtualDeviceList

	for _, device := range l {
		if f(device) {
			found = append(found, device)
		}
	}

	return found
}
850804
func (l *Ledis) Select(index int) (*DB, error) {
	if index < 0 || index >= l.cfg.Databases {
		return nil, fmt.Errorf("invalid db index %d, must in [0, %d]", index, l.cfg.Databases-1)
	}

	l.dbLock.Lock()
	defer l.dbLock.Unlock()

	db, ok := l.dbs[index]
	if ok {
		return db, nil
	}

	db = l.newDB(index)
	l.dbs[index] = db

	go func(db *DB) {
		l.ttlCheckerCh <- db.ttlChecker
	}(db)

	return db, nil
}
160398
func choose(n, k int) int {
	if k == 0 {
		return 1
	} else if n == 0 {
		return 0
	}
	result := float64(n - (k - 1))
	for i := 2; i <= k; i++ {
		result *= float64(n-(k-i)) / float64(i)
	}

	return int(result)
}
986433
func (ps partitions) Partitions() []Partition {
	parts := make([]Partition, 0, len(ps))
	for i := 0; i < len(ps); i++ {
		parts = append(parts, ps[i].Partition())
	}

	return parts
}