// Graph Int -> ()
// computes the shortest path to all elements in Graph g from node n
func (g Graph) dijkstra(n int) []int {
	maxIndex := len(g)
	if maxIndex < 1 {
		return make([]int, 0)
	} //set all Node distance to maxInt
	for i := 0; i < len(g); i++ {
		g[i].distance = 0x3f3f3f3f
		g[i].index = i
	}
	//initialize heap
	heap.Init(&g)
	//set starting Node distance to 0
	g.update(g[n-1], 0)
	heap.Init(&g)
	for len(g) > 1 {
		node := heap.Pop(&g).(*Node)
		node.explored = true
		for _, edge := range node.edges {
			if !edge.node.explored {
				g.update(edge.node, (edge.length + node.distance))
			}
		}
	}
	g = g[:maxIndex]
	values := make([]int, len(g))
	for _, v := range g {
		values[v.name-1] = v.distance
	}
	return values
}

// Dijkstra returns the shortest path using Dijkstra algorithm with a min-priority queue.
// This algorithm does not work with negative weight edges.
// (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)
//
//	1  function Dijkstra(Graph, source):
//	2      dist[source] ← 0                      // Initialization
//	3      for each vertex v in Graph:
//	4          if v ≠ source
//	5              dist[v] ← infinity            // Unknown distance from source to v
//	6              prev[v] ← undefined           // Predecessor of v
//	7          end if
//	8          Q.add_with_priority(v, dist[v])
//	9      end for
//	10
//	11     while Q is not empty:               // The main loop
//	12         u ← Q.extract_min()            // Remove and return best vertex
//	13         for each neighbor v of u:
//	14             alt = dist[u] + length(u, v)
//	15             if alt < dist[v]
//	16                 dist[v] ← alt
//	17                 prev[v] ← u
//	18                 Q.decrease_priority(v, alt)
//	19             end if
//	20         end for
//	21     end while
//	22     return prev[]
//
func (d *Data) Dijkstra(src, dst *Node) ([]*Node, map[*Node]float32) {

	mapToDistance := make(map[*Node]float32)
	mapToDistance[src] = 0.0

	minHeap := &nodeDistanceHeap{}

	// initialize mapToDistance
	for nd := range d.NodeMap {
		if nd != src {
			mapToDistance[nd] = 2147483646.0
		}
		ndd := nodeDistance{}
		ndd.node = nd
		ndd.distance = mapToDistance[nd]
		heap.Push(minHeap, ndd)
	}

	mapToPrevID := make(map[string]string)
	heap.Init(minHeap)

	for minHeap.Len() != 0 {
		elem := heap.Pop(minHeap)
		for ov, weight := range elem.(nodeDistance).node.WeightTo {
			if mapToDistance[ov] > mapToDistance[elem.(nodeDistance).node]+weight {
				mapToDistance[ov] = mapToDistance[elem.(nodeDistance).node] + weight
				minHeap.updateDistance(ov, mapToDistance[elem.(nodeDistance).node]+weight)
				heap.Init(minHeap)

				mapToPrevID[ov.ID] = elem.(nodeDistance).node.ID
			}
		}
		for iv, weight := range elem.(nodeDistance).node.WeightTo {
			if mapToDistance[iv] > mapToDistance[elem.(nodeDistance).node]+weight {
				mapToDistance[iv] = mapToDistance[elem.(nodeDistance).node] + weight
				minHeap.updateDistance(iv, mapToDistance[elem.(nodeDistance).node]+weight)
				heap.Init(minHeap)

				mapToPrevID[iv.ID] = elem.(nodeDistance).node.ID
			}
		}
	}

	pathSlice := []*Node{dst}
	id := dst.ID
	for mapToPrevID[id] != src.ID {
		prevID := mapToPrevID[id]
		id = prevID
		copied := make([]*Node, len(pathSlice)+1) // push front
		copied[0] = d.GetNodeByID(prevID)
		copy(copied[1:], pathSlice)
		pathSlice = copied
	}
	copied := make([]*Node, len(pathSlice)+1) // push front
	copied[0] = d.GetNodeByID(src.ID)
	copy(copied[1:], pathSlice)
	pathSlice = copied

	return pathSlice, mapToDistance
}

func main() {

	//创建一个heap
	h := &Heap{}

	heap.Init(h)
	//向heap中插入元素
	h.Push(5)
	h.Push(2)
	h.Push(1)
	h.Push(8)
	h.Push(4)
	h.Push(6)
	h.Push(2)

	//输出heap中的元素，相当于一个数组，原始数组
	fmt.Println(h)

	//这里必须要reheapify，建立好堆了
	heap.Init(h)

	//小顶堆对应的元素在数组中的位置
	fmt.Println(h)

	//移除下标为5的元素，下标从0开始
	h.Remove(5)

	//按照堆的形式输出
	for h.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(h))
	}
	fmt.Println()
}

func docAtATime(q []*Term, k int) []*Result {
	results := &ResultHeap{}
	terms := &TermHeap{}
	heap.Init(results)
	heap.Init(terms)
	for i := 0; i < k; i++ {
		heap.Push(results, &Result{0, 0})
	}
	for i := 0; i < len(q); i++ {
		nextDoc := nextDoc(q[i], 0)
		if nextDoc != nil {
			heap.Push(terms, &TermNextDoc{term: q[i], nextDoc: nextDoc})
		}
	}

	var term *TermNextDoc
	var d int
	var score float64
	var nDoc *Document
	var res *Result
	popped := false
	for len(*terms) > 0 {
		popped = false
		term = heap.Pop(terms).(*TermNextDoc)
		d = term.nextDoc.docId
		score = 0.0

		for d == term.nextDoc.docId {
			score += BM25(term.term, term.nextDoc)
			nDoc = nextDoc(term.term, d)
			if nDoc != nil {
				heap.Push(terms, &TermNextDoc{term: term.term, nextDoc: nDoc})
			}

			if len(*terms) > 0 {
				term = heap.Pop(terms).(*TermNextDoc)
				popped = true
			} else {
				break
			}
		}
		if popped {
			heap.Push(terms, term)
		}
		if score > 0.0 {
			res = &Result{doc: d, score: score}
			results.PushGreater(res)
		}
	}

	sortedResults := make([]*Result, (*results).Len())
	for i := len(sortedResults) - 1; i >= 0; i-- {
		sortedResults[i] = heap.Pop(results).(*Result)
	}
	return sortedResults
}

func (s *serverHeap) Handler() {
	var rec *heapCommand

	ticker := time.Tick(30 * 1000000000)
	for {
		select {
		case rec = <-s.serverChan:
			if rec.command == 0 {
				s.vec.Push(rec.server)
				rec.retChan <- &heapCommand{}
			}
			if rec.command == 1 {
				rec.retChan <- &heapCommand{1, s.vec.Pop(), nil}
			}
			if rec.command == 2 {
				deadServer := rec.server.(*server)
				//find the server to remove
				for cnt := 0; cnt < s.vec.Len(); cnt++ {

					testserv := s.vec.At(cnt).(*server)
					if testserv.id == deadServer.id {
						log.Printf("master: heap Handler: found server %d to delete\n", deadServer.id)

						//find each chunk to modify
						for cnt1 := 0; cnt1 < testserv.chunks.Len(); cnt1++ {

							tempchunk := testserv.chunks.At(cnt1).(*chunk)

							//find the server to remove from EACH CHUNK LIST
							for cnt2 := 0; cnt2 < tempchunk.servers.Len(); cnt2++ {

								tempserv := tempchunk.servers.At(cnt2).(*server)
								if tempserv.id == deadServer.id {
									tempchunk.servers.Delete(cnt2)
								}
							}
						}
						prevCnt := s.vec.Len()
						s.vec.Delete(cnt)
						log.Printf("master: heap Handler: prev vec count %d, now %d\n", prevCnt, s.vec.Len())
						break
					}
				}
				heap.Init(s)
				rec.retChan <- &heapCommand{}
			}
		case <-ticker:
			log.Printf("master: scheduled reheap\n")
			log.Printf("BEFORE \n %s \n", s.printPresent())
			heap.Init(s)
			log.Printf("AFTER  \n %s \n", s.printPresent())
		}
	}
}

func solve(r *os.File, w *os.File) {
	reader := bufio.NewReader(r)

	count := int(nextNumber(reader))
	minHeap := &MinHeap{}
	maxHeap := &MaxHeap{}

	heap.Init(minHeap)
	heap.Init(maxHeap)

	var median float64

	for i := 0; i < count; i++ {
		num := int64(nextNumber(reader))

		// Push on correct heap
		if 2 == i && maxHeap.Root() > minHeap.Root() {
			min := heap.Pop(minHeap)
			max := heap.Pop(maxHeap)
			heap.Push(minHeap, max)
			heap.Push(maxHeap, min)
		}
		if minHeap.Len() == 0 {
			heap.Push(minHeap, num)
		} else if (maxHeap.Len() == 0) || (num < maxHeap.Root()) {
			heap.Push(maxHeap, num)
		} else {
			heap.Push(minHeap, num)
		}

		// Rebalance
		if minHeap.Len()-maxHeap.Len() > 1 {
			heap.Push(maxHeap, heap.Pop(minHeap))
		} else if maxHeap.Len()-maxHeap.Len() > 1 {
			heap.Push(minHeap, heap.Pop(maxHeap))
		}

		if maxHeap.Len() == minHeap.Len() {
			median = (float64(maxHeap.Root()) + float64(minHeap.Root())) / 2
		} else if maxHeap.Len() > minHeap.Len() {
			median = float64(maxHeap.Root())
		} else {
			median = float64(minHeap.Root())
		}

		w.WriteString(strconv.FormatFloat(median, 'f', 1, 32))

		if (i + 1) < count {
			w.WriteString("\n")
		}
	}
}

// NewStorePool creates a StorePool and registers the store updating callback
// with gossip.
func NewStorePool(
	ambient log.AmbientContext,
	g *gossip.Gossip,
	clock *hlc.Clock,
	rpcContext *rpc.Context,
	timeUntilStoreDead time.Duration,
	stopper *stop.Stopper,
	deterministic bool,
) *StorePool {
	sp := &StorePool{
		AmbientContext:     ambient,
		clock:              clock,
		timeUntilStoreDead: timeUntilStoreDead,
		rpcContext:         rpcContext,
		failedReservationsTimeout: envutil.EnvOrDefaultDuration("COCKROACH_FAILED_RESERVATION_TIMEOUT",
			defaultFailedReservationsTimeout),
		declinedReservationsTimeout: envutil.EnvOrDefaultDuration("COCKROACH_DECLINED_RESERVATION_TIMEOUT",
			defaultDeclinedReservationsTimeout),
		resolver:      GossipAddressResolver(g),
		deterministic: deterministic,
	}
	sp.mu.storeDetails = make(map[roachpb.StoreID]*storeDetail)
	heap.Init(&sp.mu.queue)
	sp.mu.nodeLocalities = make(map[roachpb.NodeID]roachpb.Locality)
	storeRegex := gossip.MakePrefixPattern(gossip.KeyStorePrefix)
	g.RegisterCallback(storeRegex, sp.storeGossipUpdate)
	deadReplicasRegex := gossip.MakePrefixPattern(gossip.KeyDeadReplicasPrefix)
	g.RegisterCallback(deadReplicasRegex, sp.deadReplicasGossipUpdate)
	sp.start(stopper)

	return sp
}

func (s *S) TestEvictAndReplaceWithMedian(c *C) {
	q := make(utility.PriorityQueue, 0, 10)
	heap.Init(&q)
	var e EvictionPolicy = EvictAndReplaceWith(5, maths.Median)

	for i := 0; i < 10; i++ {
		var item utility.Item = utility.Item{
			Value:    float64(i),
			Priority: int64(i),
		}

		heap.Push(&q, &item)
	}

	c.Check(q, HasLen, 10)

	e(&q)

	c.Check(q, HasLen, 6)

	c.Check(heap.Pop(&q), utility.ValueEquals, 4.0)
	c.Check(heap.Pop(&q), utility.ValueEquals, 3.0)
	c.Check(heap.Pop(&q), utility.ValueEquals, 2.0)
	c.Check(heap.Pop(&q), utility.ValueEquals, 1.0)
	c.Check(heap.Pop(&q), utility.ValueEquals, 0.0)
	c.Check(heap.Pop(&q), utility.ValueEquals, 7.0)
}

func (s *S) TestEvictAndReplaceWithFirstMode(c *C) {
	q := make(utility.PriorityQueue, 0, 10)
	heap.Init(&q)
	e := EvictAndReplaceWith(5, maths.FirstMode)

	for i := 0; i < 10; i++ {
		heap.Push(&q, &utility.Item{
			Value:    float64(i),
			Priority: int64(i),
		})
	}

	c.Check(q, HasLen, 10)

	e(&q)

	c.Check(q, HasLen, 6)

	c.Check(heap.Pop(&q), utility.ValueEquals, 4.0)
	c.Check(heap.Pop(&q), utility.ValueEquals, 3.0)
	c.Check(heap.Pop(&q), utility.ValueEquals, 2.0)
	c.Check(heap.Pop(&q), utility.ValueEquals, 1.0)
	c.Check(heap.Pop(&q), utility.ValueEquals, 0.0)
	c.Check(heap.Pop(&q), utility.ValueEquals, 9.0)
}

// Clear removes all the entries in the cache
func (c *Cache) Clear() {
	c.lock.Lock()
	defer c.lock.Unlock()

	c.entries = make(entries, c.capacity)
	heap.Init(&c.entriesH)
}

func (c *controller) sandboxAdd(key string, create bool, ep *endpoint) (sandbox.Sandbox, error) {
	c.Lock()
	sData, ok := c.sandboxes[key]
	c.Unlock()

	if !ok {
		sb, err := sandbox.NewSandbox(key, create)
		if err != nil {
			return nil, fmt.Errorf("failed to create new sandbox: %v", err)
		}

		sData = &sandboxData{
			sbox:      sb,
			endpoints: epHeap{},
		}

		heap.Init(&sData.endpoints)
		c.Lock()
		c.sandboxes[key] = sData
		c.Unlock()
	}

	if err := sData.addEndpoint(ep); err != nil {
		return nil, err
	}

	return sData.sandbox(), nil
}

// goroutine safe
func DialWithTimeout(url string, sessionNum int, dialTimeout time.Duration, timeout time.Duration) (*DialContext, error) {
	if sessionNum <= 0 {
		sessionNum = 100
		log.Release("invalid sessionNum, reset to %v", sessionNum)
	}

	s, err := mgo.DialWithTimeout(url, dialTimeout)
	if err != nil {
		return nil, err
	}
	s.SetSyncTimeout(timeout)
	s.SetSocketTimeout(timeout)

	c := new(DialContext)

	// sessions
	c.sessions = make(SessionHeap, sessionNum)
	c.sessions[0] = &Session{s, 0, 0}
	for i := 1; i < sessionNum; i++ {
		c.sessions[i] = &Session{s.New(), 0, i}
	}
	heap.Init(&c.sessions)

	return c, nil
}

func addMinPathLeft(graph *m.Graph) {
	dp := &m.DijkstraPrio{}
	heap.Init(dp)
	visited := make(map[*m.Node]bool)
	endNode := graph.EndNode()
	endNode.SetMinPathLeft(0)
	visited[endNode] = true
	for _, edge := range endNode.ToEdges() {
		node := edge.From()
		node.SetMinPathLeft(edge.FastestTime())
		heap.Push(dp, node)
	}
	if dp.Len() > 0 {
		for node := heap.Pop(dp).(*m.Node); dp.Len() > 0; node = heap.Pop(dp).(*m.Node) {
			visited[node] = true
			for _, edge := range node.ToEdges() {
				innerNode := edge.From()
				if !visited[innerNode] {
					innerNode.SetMinPathLeft(edge.FastestTime() + node.MinPathLeft())
					heap.Push(dp, innerNode)
				}
			}
		}
	}
}

// Run is the block's main loop. Here we listen on the different channels we set up.
func (b *Queue) Run() {
	pq := &PriorityQueue{}
	heap.Init(pq)
	for {
		select {
		case <-b.quit:
			// quit the block
			return
		case msg := <-b.inPush:
			queueMessage := &PQMessage{
				val: msg,
				t:   time.Now(),
			}
			heap.Push(pq, queueMessage)
		case <-b.inPop:
			if len(*pq) == 0 {
				continue
			}
			msg := heap.Pop(pq).(*PQMessage).val
			b.out <- msg
		case MsgChan := <-b.queryPop:
			var msg interface{}
			if len(*pq) > 0 {
				msg = heap.Pop(pq).(*PQMessage).val
			}
			MsgChan <- msg
		case MsgChan := <-b.queryPeek:
			var msg interface{}
			if len(*pq) > 0 {
				msg = pq.Peek().(*PQMessage).val
			}
			MsgChan <- msg
		}
	}
}

func heapSort(a sort.Interface) {
	helper := HeapHelper{a, a.Len()}
	heap.Init(&helper)
	for helper.length > 0 {
		heap.Pop(&helper)
	}
}

func main() {
	// Some items and their priorities.
	items := map[string]int{
		"banana": 3, "apple": 2, "pear": 4,
	}

	// Create a priority queue, put the items in it, and
	// establish the priority queue (heap) invariants.
	pq := make(PriorityQueue, len(items))
	i := 0
	for value, priority := range items {
		pq[i] = &Worker{
			Identity: value,
			priority: priority,
			index:    i,
		}
		i++
	}
	heap.Init(&pq)

	// Insert a new item and then modify its priority.
	item := NewWorker("orange", 1, 0)
	heap.Push(&pq, item)
	pq.UpdateItem(item, 5)

	// Take the items out; they arrive in decreasing priority order.
	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Worker)
		fmt.Printf("%.2d:%s\n", item.priority, item.Identity)
	}
}

func (g TGraph) dijkstra(x int) (dist map[*Node]int64) {
	q := &Q{}
	heap.Init(q)

	ini := g.nod(x)

	dist = make(map[*Node]int64)
	dist[ini] = 0
	for k, v := range g {
		if k != x {
			dist[v] = math.MaxInt64
		}
		item := QItem{
			n:    v,
			dist: dist[v],
		}
		heap.Push(q, item)
	}

	for q.Len() != 0 {
		u := heap.Pop(q).(QItem).n
		if dist[u] == math.MaxInt64 {
			continue
		}
		for v, w := range u.w {
			if alt := dist[u] + w; alt < dist[v] {
				dist[v] = alt
				q.update(v, alt)
			}
		}
	}
	return
}

// Ingests an alert into the memoryAlertManager and creates a new
// AggregationInstance for it, if necessary.
func (s *memoryAlertManager) ingest(a *Alert) {
	fp := a.Fingerprint()
	agg, ok := s.aggregates[fp]
	if !ok {
		agg = &AlertAggregate{
			Created: time.Now(),
		}
		agg.Ingest(a)

		for _, r := range s.rules {
			if r.Handles(agg.Alert) {
				agg.Rule = r
				break
			}
		}

		s.aggregates[fp] = agg
		heap.Push(&s.aggregatesByLastRefreshed, agg)
		heap.Push(&s.aggregatesByNextNotification, agg)

		s.needsNotificationRefresh = true
	} else {
		agg.Ingest(a)
		heap.Init(&s.aggregatesByLastRefreshed)
	}
}

// advance advances each iterator in the set to the next value for which *any*
// interpolatingIterator has a real value.
func (is unionIterator) advance() {
	if !is.isValid() {
		return
	}

	// All iterators in the set currently point to the same offset. Advancement
	// begins by pre-advancing any iterators that have a real value for the
	// current offset.
	current := is[0].offset
	for is[0].offset == current {
		is[0].advanceTo(current + 1)
		heap.Fix(&is, 0)
	}

	// It is possible that all iterators are now invalid.
	if !is.isValid() {
		return
	}

	// The iterator in position zero now has the lowest value for
	// nextReal.offset - advance all iterators to that offset.
	min := is[0].nextReal.offset
	for i := range is {
		is[i].advanceTo(min)
	}
	heap.Init(&is)
}

// Recomputes all currently uninhibited/unsilenced alerts and queues
// notifications for them according to their RepeatRate.
func (s *memoryAlertManager) refreshNotifications() {
	s.mu.Lock()
	defer s.mu.Unlock()

	s.needsNotificationRefresh = false

	l := s.filteredLabelSets(false)

	numSent := 0
	for _, lb := range l {
		agg := s.aggregates[lb.Fingerprint()]
		if agg.NextNotification.After(time.Now()) {
			continue
		}
		if agg.Rule != nil {
			s.notifier.QueueNotification(agg.Alert, notificationOpTrigger, agg.Rule.NotificationConfigName)
			agg.LastNotification = time.Now()
			agg.NextNotification = agg.LastNotification.Add(agg.Rule.RepeatRate)
			numSent++
		}
	}
	if numSent > 0 {
		log.Infof("Sent %d notifications", numSent)
		heap.Init(&s.aggregatesByNextNotification)
	}
}