1 package net.obsearch.index.ghs;
2
3 /**
4 * This data structure simulates a priority queue of objects sorted by their
5 * distance to some other object.
6 * It assumes several things for performance reasons:
7 * 1)Distances are discrete.
8 * 2) Objects to be stored are longs
9 * 3) The maximum distance value is a value m that is very small (64 for example :)).
10 * This priority queue uses a lot of memory if queueSize is too large.
11 *
12 * @author Arnoldo Jose Muller Molina
13 *
14 */
15 public final class FastPriorityQueueLong {
16
17 private long[][] data;
18 private int[] counts;
19 private final int queueSize;
20 /**
21 * Creates the queue
22 * @param maxDistance maximum distance that will be inserted in the queue. (from 0 to maxDistance)
23 * @param queueSize size of the queue (number of closest elements to be obtained).
24 */
25 public FastPriorityQueueLong(int maxDistance, int queueSize){
26 maxDistance++;
27 data = new long[maxDistance][queueSize];
28 counts = new int[maxDistance];
29 this.queueSize = queueSize;
30 }
31
32 /**
33 * Add an object that is at a certain distance.
34 * @param object the object to add
35 * @param distance the distance of the object.
36 */
37 public void add(long object, int distance){
38 int index = counts[distance];
39 if(index < queueSize){
40 data[distance][index] = object;
41 counts[distance]++;
42 }
43 }
44
45 /**
46 * Return the closest long objects
47 * We do not include the original distances to reduce
48 * the creation of objects.
49 * @return the closest long objects
50 */
51 public long[] get(){
52 int total = 0;
53 for(int c : counts){
54 total += c;
55 }
56 total = Math.min(total, queueSize);
57 long[] result = new long[total];
58 int i1 = 0;
59
60 int resi = 0;
61 while(i1 < data.length && resi < total){
62 int i2 = 0;
63 while(i2 < counts[i1] && resi < total){
64 result[resi] = data[i1][i2];
65 resi++;
66 i2++;
67 }
68 i1++;
69 }
70 return result;
71 }
72
73 }