I’m using a binary heap for getting intersections with distances in ascending order… at least it does most of the time, I get spurious numbers out of order. Here’s the code distilled down to demonstrate it:-
class HeapProblem
{
/** Max number of intersections */
static final int MAX_INTERSECTIONS = 300;
/** Minimal version of the actual Intersection class */
class Intersection
{
double distance;
}
/** Intersections stored in a binary heap so we can quickly get them in distance order */
protected Intersection[] inSectHeap = new Intersection[MAX_INTERSECTIONS];
/** Index of the end of the heap */
protected int heapEnd = -1;
/**
* Test it
*/
public static void main(String[] args)
{
HeapProblem hp = new HeapProblem();
}
/**
* Testing...
*/
protected HeapProblem()
{
// Shove a load of random numbers on
java.util.Random rand = new java.util.Random();
for (int i = 0; i < 100; i++)
{
Intersection inSect = new Intersection();
inSect.distance = rand.nextDouble() * 1000;
addIntersection(inSect);
}
// Pull 'em off, shout if out of order
double prevDist = 0;
while (heapEnd >= 0)
{
Intersection inSect = getNextIntersection();
System.out.println(inSect.distance + ((inSect.distance < prevDist)? " *WRONG!*" : ""));
prevDist = inSect.distance;
}
}
/**
* Add intersection to heap
* @param inSect The intersection to add
*/
private void addIntersection(Intersection inSect)
{
inSectHeap[++heapEnd] = inSect;
int index = heapEnd;
int parent = index >> 1;
// Bubble intersection with shortest distance to the top
while (inSectHeap[index].distance < inSectHeap[parent].distance)
{
Intersection temp = inSectHeap[parent];
inSectHeap[parent] = inSectHeap[index];
inSectHeap[index] = temp;
index = parent;
parent >>= 1;
}
}
/**
* Get next nearest intersection from the heap
* @return intersection
*/
Intersection getNextIntersection()
{
Intersection next = inSectHeap[0]; // Next nearest is on top
inSectHeap[0] = inSectHeap[heapEnd--]; // Move the end of the heap to the top
// Bubble next nearest to top
for (int index = 0; (index << 1) < heapEnd; )
{
int left = (index << 1) + 1;
int right = left + 1;
// Choose the lower of the two children
int child = (inSectHeap[left].distance < inSectHeap[right].distance)? left : right;
if (inSectHeap[index].distance >= inSectHeap[child].distance)
{
Intersection temp = inSectHeap[child];
inSectHeap[child] = inSectHeap[index]; // Swap it with current one
inSectHeap[index] = temp;
}
index = child;
}
return next;
}
}
Any thoughts on what might be wrong? Thanks.
(Moderators feel free to shunt this into another forum if more appropriate)