KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > net > nutch > util > TestFibonacciHeap


1 /* Copyright (c) 2003 The Nutch Organization. All rights reserved. */
2 /* Use subject to the conditions in http://www.nutch.org/LICENSE.txt. */
3
4 package net.nutch.util;
5
6 import junit.framework.TestCase;
7
8 import java.util.Arrays JavaDoc;
9
10 /** Unit tests for FibonacciHeap. */
11 public class TestFibonacciHeap extends TestCase {
12   public TestFibonacciHeap(String JavaDoc name) {
13     super(name);
14   }
15
16   
17   private static class TestItem implements Comparable JavaDoc {
18     int id;
19     int priority;
20
21     public TestItem(int id, int priority) {
22       this.id= id;
23       this.priority= priority;
24     }
25
26     public String JavaDoc toString() {
27       return "<"+id+","+priority+">";
28     }
29
30     public int compareTo(Object JavaDoc other) {
31       TestItem o= (TestItem) other;
32       if (this.priority < o.priority)
33         return -1;
34       else if (this.priority == o.priority)
35         return 0;
36       else return 1;
37     }
38   }
39
40   private final static int NUM_TEST_ITEMS= 200;
41
42   private final static int NUM_TEST_OPERATIONS= 10000;
43
44   // likelihood of doing any of these operations
45 private final static double ADD_PROB= .35;
46   private final static double DECREASEKEY_PROB= .25;
47   private final static double POP_PROB= .30;
48   private final static double PEEK_PROB= .10;
49
50   public void testFibHeap() {
51     FibonacciHeap h= new FibonacciHeap();
52
53     TestItem[] vals= new TestItem[NUM_TEST_ITEMS];
54     for (int i= 0; i < NUM_TEST_ITEMS; i++)
55       vals[i]= new TestItem(i,i);
56
57     // the number of vals in the heap
58 int numInVal= 0;
59     // the number of vals that are not in the heap
60 int numOutVal= NUM_TEST_ITEMS;
61
62     // thresholds
63 double addMaxP= ADD_PROB;
64     double decreaseKeyMaxP= ADD_PROB + DECREASEKEY_PROB;
65     double popMaxP= ADD_PROB + DECREASEKEY_PROB + POP_PROB;
66
67     // number of operations we've done
68 int numOps= 0;
69
70     // test add/peek/pop/decreaseKey
71 while (numOps < NUM_TEST_OPERATIONS) {
72
73       numOps++;
74
75       assertTrue("heap reports wrong size!", numInVal == h.size());
76
77       double randVal= Math.random();
78       if (randVal < addMaxP) {
79
80         if (numOutVal == 0) // can't add...
81 continue;
82
83         // add
84 int index= ( (NUM_TEST_ITEMS - 1) -
85                      (int) (Math.random() * (double) numOutVal) );
86         TestItem tmp= vals[index];
87         vals[index]= vals[numInVal];
88         vals[numInVal]= tmp;
89         numInVal++;
90         numOutVal--;
91
92         h.add(tmp, tmp.priority);
93
94       } else if (randVal < decreaseKeyMaxP) {
95
96         // decreaseKey
97 if (numInVal == 0) {
98           // do nothing
99 } else {
100           int index= (int) (Math.random() * (double) numInVal);
101           TestItem tmp= vals[index];
102
103           tmp.priority-= Math.random() * 5.0;
104
105           h.decreaseKey(tmp, tmp.priority);
106         }
107
108       } else if (randVal < popMaxP) {
109
110         // pop
111 if (numInVal == 0) {
112           if (h.size() != 0) {
113             assertTrue("heap empty, but peekMin() did not return null!",
114                        h.peekMin() == null);
115             assertTrue("heap empty, but popMin() did not return null!",
116                        h.popMin() == null );
117           }
118         } else {
119           Arrays.sort(vals, 0, numInVal);
120           int i= 0;
121           TestItem tmp= (TestItem) h.popMin();
122           while ( (i < numInVal) && (tmp.priority == vals[i].priority) ) {
123             if (tmp.id == vals[i].id)
124               break;
125             i++;
126           }
127           assertTrue("popMin did not return lowest-priority item!",
128                      tmp.id == vals[i].id);
129           assertTrue("popMin did not return lowest-priority item!",
130                      tmp == vals[i]);
131
132           vals[i]= vals[numInVal - 1];
133           vals[numInVal - 1]= tmp;
134           numInVal--;
135           numOutVal++;
136         }
137
138       } else {
139
140         // peek
141 if (numInVal == 0) {
142           assertTrue("heap reports non-zero size when empty", h.size() == 0);
143           assertTrue("heap.peekMin() returns item when empty",
144                      h.peekMin() == null);
145           assertTrue("heap.popMin() returns item when empty",
146                      h.popMin() == null);
147         } else {
148           Arrays.sort(vals, 0, numInVal);
149           int i= 0;
150           TestItem tmp= (TestItem) h.peekMin();
151
152           while ( (i < numInVal) && (tmp.priority == vals[i].priority) ) {
153             if (tmp.id == vals[i].id)
154               break;
155             i++;
156           }
157           assertTrue("heap.peekMin() returns wrong item",
158                      tmp.id == vals[i].id);
159           assertTrue("heap.peekMin() returns wrong item",
160                      tmp == vals[i]);
161         }
162       }
163     }
164
165   }
166
167 }
168
Popular Tags