// Auto-generated variant of sort.go:heapSort
770256
func heapSort_func(data lessSwap, a, b int) {
	first := a
	lo := 0
	hi := b - a
	for i := (hi - 1) / 2; i >= 0; i-- {
		siftDown_func(data, i, hi, first)
	}
	for i := hi - 1; i >= 0; i-- {
		data.Swap(first, first+i)
		siftDown_func(data, lo, i, first)
	}
}
992090
func (api *ServerAPI) SortByMemory(reverse bool) *ServerAPI {
	api.sortBy("ServerPlan.MemoryMB", reverse)
	return api
}
1140807
func (fs *FileSorter) externalSort() (*comparableRow, error) {
	if !fs.fetched {
		// flush all remaining content to file (if any)
		for _, w := range fs.workers {
			if atomic.LoadInt32(&(w.busy)) == 0 && len(w.buf) > 0 {
				fs.wg.Add(1)
				go w.flushToFile()
			}
		}

		// wait for all workers to finish
		fs.wg.Wait()

		// check errors from workers
		for _, w := range fs.workers {
			if w.err != nil {
				return nil, errors.Trace(w.err)
			}
			if w.rowSize > fs.maxRowSize {
				fs.maxRowSize = w.rowSize
			}
		}

		heap.Init(fs.rowHeap)
		if fs.rowHeap.err != nil {
			return nil, errors.Trace(fs.rowHeap.err)
		}

		fs.rowBytes = make([]byte, fs.maxRowSize)

		err := fs.openAllFiles()
		if err != nil {
			return nil, errors.Trace(err)
		}

		for id := range fs.fds {
			row, err := fs.fetchNextRow(id)
			if err != nil {
				return nil, errors.Trace(err)
			}
			if row == nil {
				return nil, errors.New("file is empty")
			}

			im := &item{
				index: id,
				value: row,
			}

			heap.Push(fs.rowHeap, im)
			if fs.rowHeap.err != nil {
				return nil, errors.Trace(fs.rowHeap.err)
			}
		}

		fs.fetched = true
	}

	if fs.rowHeap.Len() > 0 {
		im := heap.Pop(fs.rowHeap).(*item)
		if fs.rowHeap.err != nil {
			return nil, errors.Trace(fs.rowHeap.err)
		}

		row, err := fs.fetchNextRow(im.index)
		if err != nil {
			return nil, errors.Trace(err)
		}
		if row != nil {
			nextIm := &item{
				index: im.index,
				value: row,
			}

			heap.Push(fs.rowHeap, nextIm)
			if fs.rowHeap.err != nil {
				return nil, errors.Trace(fs.rowHeap.err)
			}
		}

		return im.value, nil
	}

	return nil, nil
}
1137056
func SortBy(rows [][]string, lesses ...LessFunc) *MultiSorter {
	return &MultiSorter{
		data: rows,
		less: lesses,
	}
}
28398
func (b *Sortable) Comparator(k string, less StringComparator) SortComparator {
	return func(i, j int) bool {
		return less(b.Data[i].Get(k), b.Data[j].Get(k))
	}
}
1093640
func (heap *FloatingFibonacciHeap) DequeueMin() (*Entry, error) {
	if heap.IsEmpty() {
		return nil, EmptyHeapError("Cannot dequeue minimum of empty heap")
	}

	heap.size--

	// Copy pointer. Will need it later.
	min := heap.min

	if min.next == min { // This is the only root node
		heap.min = nil
	} else { // There are more root nodes
		heap.min.prev.next = heap.min.next
		heap.min.next.prev = heap.min.prev
		heap.min = heap.min.next // Arbitrary element of the root list
	}

	if min.child != nil {
		// Keep track of the first visited node
		curr := min.child
		for ok := true; ok; ok = (curr != min.child) {
			curr.parent = nil
			curr = curr.next
		}
	}

	heap.min = mergeLists(heap.min, min.child)

	if heap.min == nil {
		// If there are no entries left, we're done.
		return min, nil
	}

	treeSlice := make([]*Entry, 0, heap.size)
	toVisit := make([]*Entry, 0, heap.size)

	for curr := heap.min; len(toVisit) == 0 || toVisit[0] != curr; curr = curr.next {
		toVisit = append(toVisit, curr)
	}

	for _, curr := range toVisit {
		for {
			for curr.degree >= len(treeSlice) {
				treeSlice = append(treeSlice, nil)
			}

			if treeSlice[curr.degree] == nil {
				treeSlice[curr.degree] = curr
				break
			}

			other := treeSlice[curr.degree]
			treeSlice[curr.degree] = nil

			// Determine which of two trees has the smaller root
			var minT, maxT *Entry
			if other.Priority < curr.Priority {
				minT = other
				maxT = curr
			} else {
				minT = curr
				maxT = other
			}

			// Break max out of the root list,
			// then merge it into min's child list
			maxT.next.prev = maxT.prev
			maxT.prev.next = maxT.next

			// Make it a singleton so that we can merge it
			maxT.prev = maxT
			maxT.next = maxT
			minT.child = mergeLists(minT.child, maxT)

			// Reparent max appropriately
			maxT.parent = minT

			// Clear max's mark, since it can now lose another child
			maxT.marked = false

			// Increase min's degree. It has another child.
			minT.degree++

			// Continue merging this tree
			curr = minT
		}

		/* Update the global min based on this node.  Note that we compare
		 * for <= instead of < here.  That's because if we just did a
		 * reparent operation that merged two different trees of equal
		 * priority, we need to make sure that the min pointer points to
		 * the root-level one.
		 */
		if curr.Priority <= heap.min.Priority {
			heap.min = curr
		}
	}

	return min, nil
}
813966
func getTopK(queue []interface{}, id *bitmap, k int) []interface{} {
	topkHeap := make(topKHeap, 0, k+1)

	for _, value := range queue {
		node := value.(*node)
		distance := id.Xor(node.id)
		if topkHeap.Len() == k {
			var last = topkHeap[topkHeap.Len() - 1]
			if last.distance.Compare(distance, maxPrefixLength) == 1 {
				item := &heapItem{
					distance,
					value,
				}
				heap.Push(&topkHeap, item)
				heap.Pop(&topkHeap)
			}
		} else {
			item := &heapItem{
				distance,
				value,
			}
			heap.Push(&topkHeap, item)
		}
	}

	tops := make([]interface{}, topkHeap.Len())
	for i := len(tops) - 1; i >= 0; i-- {
		tops[i] = heap.Pop(&topkHeap).(*heapItem).value
	}

	return tops
}
865308
func (pq *BlockPriorityQueue) Swap(i, j int) {
	pq.bh[i], pq.bh[j] = pq.bh[j], pq.bh[i]
	pq.bh[i].heapIdx = i
	pq.bh[j].heapIdx = j
}
641803
func MergeSort(me []int, from, to int, tch chan<- int) {
	if from < to-1 {
		lch, rch := make(chan int), make(chan int)
		go MergeSort(me, from, (from+to)/2, lch)
		go MergeSort(me, (from+to)/2, to, rch)
		mergeCombine(lch, rch, tch)
	} else {
		for i := from; i < to; i++ {
			tch <- me[i]
		}
		close(tch)
	}
}
170062
func IndexSort(data sort.Interface) []int {
	indexes := make([]int, data.Len())
	for i := range indexes {
		indexes[i] = i
	}
	sort.Sort(InterfaceStruct{
		LenF: data.Len,
		LessF: func(i, j int) bool {
			return data.Less(indexes[i], indexes[j])
		},
		SwapF: func(i, j int) {
			indexes[i], indexes[j] = indexes[j], indexes[i]
		},
	})
	return indexes
}
819364
func (s *GeoDistanceSort) NestedSort(nestedSort *NestedSort) *GeoDistanceSort {
	s.nestedSort = nestedSort
	return s
}
1203549
func (l Listing) applySort() {
	// Check '.Order' to know how to sort
	if l.Order == "desc" {
		switch l.Sort {
		case sortByName:
			sort.Sort(sort.Reverse(byName(l)))
		case sortBySize:
			sort.Sort(sort.Reverse(bySize(l)))
		case sortByTime:
			sort.Sort(sort.Reverse(byTime(l)))
		default:
			// If not one of the above, do nothing
			return
		}
	} else { // If we had more Orderings we could add them here
		switch l.Sort {
		case sortByName:
			sort.Sort(byName(l))
		case sortBySize:
			sort.Sort(bySize(l))
		case sortByTime:
			sort.Sort(byTime(l))
		default:
			// If not one of the above, do nothing
			return
		}
	}
}
502151
func (s *Sorter) Sort() {
	if s.Slice.Len() < 2 {
		// Nothing to sort
		return
	}
	if s.Getter == nil {
		s.Getter = SimpleGetter()
	}
	s.itemType = s.Slice.Index(0).Type()
	s.vals = s.Getter(s.Slice)
	one := s.vals[0]
	s.valType = one.Type()
	s.valKind = one.Kind()
	switch s.valKind {
	// If the value isn't a standard kind, find a known type to sort by
	default:
		switch s.valType {
		default:
			panic(fmt.Sprintf("Cannot sort by type %v", s.valType))
		case t_time:
			switch s.Ordering {
			default:
				panic(fmt.Sprintf("Invalid ordering %v for time.Time", s.Ordering))
			case Ascending:
				sort.Sort(timeAscending{s})
			case Descending:
				sort.Sort(timeDescending{s})
			}
		}
	// Strings
	case reflect.String:
		switch s.Ordering {
		default:
			panic(fmt.Sprintf("Invalid ordering %v for strings", s.Ordering))
		case Ascending:
			sort.Sort(stringAscending{s})
		case Descending:
			sort.Sort(stringDescending{s})
		case CaseInsensitiveAscending:
			sort.Sort(stringInsensitiveAscending{s})
		case CaseInsensitiveDescending:
			sort.Sort(stringInsensitiveDescending{s})
		}
	// Booleans
	case reflect.Bool:
		switch s.Ordering {
		default:
			panic(fmt.Sprintf("Invalid ordering %v for booleans", s.Ordering))
		case Ascending:
			sort.Sort(boolAscending{s})
		case Descending:
			sort.Sort(boolDescending{s})
		}
	// Ints
	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
		switch s.Ordering {
		default:
			panic(fmt.Sprintf("Invalid ordering %v for ints", s.Ordering))
		case Ascending:
			sort.Sort(intAscending{s})
		case Descending:
			sort.Sort(intDescending{s})
		}
	// Uints
	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64:
		switch s.Ordering {
		default:
			panic(fmt.Sprintf("Invalid ordering %v for uints", s.Ordering))
		case Ascending:
			sort.Sort(uintAscending{s})
		case Descending:
			sort.Sort(uintDescending{s})
		}
	// Floats
	case reflect.Float32, reflect.Float64:
		switch s.Ordering {
		default:
			panic(fmt.Sprintf("Invalid ordering %v for floats", s.Ordering))
		case Ascending:
			sort.Sort(floatAscending{s})
		case Descending:
			sort.Sort(floatDescending{s})
		}
	}
}
612367
func HeapOr(bitmaps ...*Bitmap) *Bitmap {
	if len(bitmaps) == 0 {
		return NewBitmap()
	}
	// TODO:  for better speed, we could do the operation lazily, see Java implementation
	pq := make(priorityQueue, len(bitmaps))
	for i, bm := range bitmaps {
		pq[i] = &item{bm, i}
	}
	heap.Init(&pq)

	for pq.Len() > 1 {
		x1 := heap.Pop(&pq).(*item)
		x2 := heap.Pop(&pq).(*item)
		heap.Push(&pq, &item{Or(x1.value, x2.value), 0})
	}
	return heap.Pop(&pq).(*item).value
}
110196
func (p *PriorityQueue) UpdatePriority(x interface{}, newPriority float64) {
	item, ok := p.lookup[x]
	if !ok {
		return
	}

	item.priority = newPriority
	heap.Fix(p.itemHeap, item.index)
}
1356250
func (h *heapData) Pop() interface{} {
	key := h.queue[len(h.queue)-1]
	h.queue = h.queue[0 : len(h.queue)-1]
	item, ok := h.items[key]
	if !ok {
		// This is an error
		return nil
	}
	delete(h.items, key)
	return item.obj
}
809290
func (a *segment) readyDeferredSort() {
	a.needSorterCh = make(chan bool, 1)
	a.needSorterCh <- true // A ticket for the future sorter.
	close(a.needSorterCh)

	a.waitSortedCh = make(chan struct{})
}