KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > util > Heap


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2004 Ondrej Lhotak
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */
19
20 package soot.util;
21 import java.util.*;
22
23 /** A heap (priority queue) implementation.
24  * @author Ondrej Lhotak
25  */
26 public class Heap
27 {
28     public interface Keys {
29         public int key(Object JavaDoc o);
30     }
31     final Keys keys;
32     final ArrayList list = new ArrayList();
33     final HashSet contents = new HashSet();
34     private int size;
35     public int size() { return size; }
36     public boolean isEmpty() { return size <= 0; }
37     public Heap(Keys keys) {
38         this.keys = keys;
39         list.add(null);
40         list.add(null);
41     }
42     public boolean contains(Object JavaDoc o) {
43         return contents.contains(o);
44     }
45     public boolean add(Object JavaDoc o) {
46         if(!contents.add(o)) return false;
47         insert(o);
48         return true;
49     }
50     private void insert(Object JavaDoc o) {
51         size++;
52         int i = size;
53         while(list.size() <= size) list.add(null);
54         while( i > 1 && key(parent(i)) > key(o) ) {
55             list.set(i, list.get(parent(i)));
56             i = parent(i);
57         }
58         list.set(i, o);
59     }
60     private int left(int i) { return 2*i; }
61     private int right(int i) { return 2*i+1; }
62     private int parent(int i) { return i/2; }
63     private void heapify(int i) {
64         int l = left(i);
65         int r = right(i);
66         int largest;
67         if( l <= size && key(l) < key(i) ) {
68             largest = l;
69         } else {
70             largest = i;
71         }
72         if( r <= size && key(r) < key(largest) ) {
73             largest = r;
74         }
75         if( largest != i ) {
76             Object JavaDoc iEdge = list.get(i);
77             Object JavaDoc largestEdge = list.get(largest);
78             list.set(i, largestEdge);
79             list.set(largest, iEdge);
80             heapify(largest);
81         }
82     }
83     public Object JavaDoc min() {
84         return list.get(1);
85     }
86     public Object JavaDoc removeMin() {
87         if(size == 0) throw new NoSuchElementException();
88         Object JavaDoc ret = list.get(1);
89         contents.remove(ret);
90         list.set(1, list.get(size));
91         list.set(size, null);
92         size--;
93         heapify(1);
94         return ret;
95     }
96     public void heapify() {
97         for( int i = size; i > 0; i-- ) heapify(i);
98     }
99     private int key(Object JavaDoc o) { return keys.key(o); }
100     private int key(int i) { return keys.key(list.get(i)); }
101 }
102
103
Popular Tags