You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
77 lines
2.1 KiB
77 lines
2.1 KiB
package routing |
|
|
|
import ( |
|
"container/heap" |
|
prand "math/rand" |
|
"reflect" |
|
"sort" |
|
"testing" |
|
|
|
"github.com/lightningnetwork/lnd/routing/route" |
|
) |
|
|
|
// TestHeapOrdering ensures that the items inserted into the heap are properly |
|
// retrieved in minimum order of distance. |
|
func TestHeapOrdering(t *testing.T) { |
|
t.Parallel() |
|
|
|
// First, create a blank heap, we'll use this to push on randomly |
|
// generated items. |
|
nodeHeap := newDistanceHeap(0) |
|
|
|
prand.Seed(1) |
|
|
|
// Create 100 random entries adding them to the heap created above, but |
|
// also a list that we'll sort with the entries. |
|
const numEntries = 100 |
|
sortedEntries := make([]*nodeWithDist, 0, numEntries) |
|
for i := 0; i < numEntries; i++ { |
|
var pubKey [33]byte |
|
prand.Read(pubKey[:]) |
|
|
|
entry := &nodeWithDist{ |
|
node: route.Vertex(pubKey), |
|
dist: prand.Int63(), |
|
} |
|
|
|
// Use the PushOrFix method for the initial push to test the scenario |
|
// where entry doesn't exist on the heap. |
|
nodeHeap.PushOrFix(entry) |
|
|
|
// Re-generate this entry's dist field |
|
entry.dist = prand.Int63() |
|
|
|
// Reorder the heap with a PushOrFix call. |
|
nodeHeap.PushOrFix(entry) |
|
|
|
sortedEntries = append(sortedEntries, entry) |
|
} |
|
|
|
// Sort the regular slice, we'll compare this against all the entries |
|
// popped from the heap. |
|
sort.Slice(sortedEntries, func(i, j int) bool { |
|
return sortedEntries[i].dist < sortedEntries[j].dist |
|
}) |
|
|
|
// One by one, pop of all the entries from the heap, they should come |
|
// out in sorted order. |
|
var poppedEntries []*nodeWithDist |
|
for nodeHeap.Len() != 0 { |
|
e := heap.Pop(&nodeHeap).(*nodeWithDist) |
|
poppedEntries = append(poppedEntries, e) |
|
} |
|
|
|
// Assert that the pubkeyIndices map is empty after popping all of the |
|
// items off of it. |
|
if len(nodeHeap.pubkeyIndices) != 0 { |
|
t.Fatalf("there are still %d pubkeys in the pubkeyIndices map", |
|
len(nodeHeap.pubkeyIndices)) |
|
} |
|
|
|
// Finally, ensure that the items popped from the heap and the items we |
|
// sorted are identical at this rate. |
|
if !reflect.DeepEqual(poppedEntries, sortedEntries) { |
|
t.Fatalf("items don't match: expected %v, got %v", sortedEntries, |
|
poppedEntries) |
|
} |
|
}
|
|
|