sorting.go

package kbucket

import (
	"container/list"
	"sort"

	peer "github.com/libp2p/go-libp2p-peer"
)

// A helper struct to sort peers by their distance to the local node
type peerDistance struct {
	p        peer.ID
	distance ID
}

// peerDistanceSorter implements sort.Interface to sort peers by xor distance
type peerDistanceSorter struct {
	peers  []peerDistance
	target ID
}

func (pds peerDistanceSorter) Len() int      { return len(pds.peers) }
func (pds peerDistanceSorter) Swap(a, b int) { pds.peers[a], pds.peers[b] = pds.peers[b], pds.peers[a] }
func (pds peerDistanceSorter) Less(a, b int) bool {
	return pds.peers[a].distance.less(pds.peers[b].distance)
}

// Append the peer.ID to the sorter's slice. It may no longer be sorted.
func (pds peerDistanceSorter) appendPeer(p peer.ID) peerDistanceSorter {
	pds.peers = append(pds.peers, peerDistance{
		p:        p,
		distance: xor(pds.target, ConvertPeerID(p)),
	})
	return pds
}

// Append the peer.ID values in the list to the sorter's slice. It may no longer be sorted.
func (pds peerDistanceSorter) appendPeersFromList(l *list.List) peerDistanceSorter {
	startLen := pds.Len()
	for e := l.Front(); e != nil; e = e.Next() {
		pds = pds.appendPeer(e.Value.(peer.ID))
	}
	if pds.Len() != startLen+l.Len() {
		panic("len did not increase")
	}
	return pds
}

func (pds peerDistanceSorter) sort() {
	sort.Sort(pds)
}

// Sort the given peers by their ascending distance from the target. A new slice is returned.
func SortClosestPeers(peers []peer.ID, target ID) []peer.ID {
	sorter := peerDistanceSorter{
		peers:  make([]peerDistance, 0, len(peers)),
		target: target,
	}
	for _, p := range peers {
		sorter = sorter.appendPeer(p)
	}
	sorter.sort()
	out := make([]peer.ID, 0, sorter.Len())
	for _, p := range sorter.peers {
		out = append(out, p.p)
	}
	return out
}