001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2004 Ondrej Lhotak
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019:
020: package soot.util;
021:
022: import java.util.*;
023:
024: /** A heap (priority queue) implementation.
025: * @author Ondrej Lhotak
026: */
027: public class Heap {
028: public interface Keys {
029: public int key(Object o);
030: }
031:
032: final Keys keys;
033: final ArrayList<Object> list = new ArrayList<Object>();
034: final HashSet<Object> contents = new HashSet<Object>();
035: private int size;
036:
037: public int size() {
038: return size;
039: }
040:
041: public boolean isEmpty() {
042: return size <= 0;
043: }
044:
045: public Heap(Keys keys) {
046: this .keys = keys;
047: list.add(null);
048: list.add(null);
049: }
050:
051: public boolean contains(Object o) {
052: return contents.contains(o);
053: }
054:
055: public boolean add(Object o) {
056: if (!contents.add(o))
057: return false;
058: insert(o);
059: return true;
060: }
061:
062: private void insert(Object o) {
063: size++;
064: int i = size;
065: while (list.size() <= size)
066: list.add(null);
067: while (i > 1 && key(parent(i)) > key(o)) {
068: list.set(i, list.get(parent(i)));
069: i = parent(i);
070: }
071: list.set(i, o);
072: }
073:
074: private int left(int i) {
075: return 2 * i;
076: }
077:
078: private int right(int i) {
079: return 2 * i + 1;
080: }
081:
082: private int parent(int i) {
083: return i / 2;
084: }
085:
086: private void heapify(int i) {
087: int l = left(i);
088: int r = right(i);
089: int largest;
090: if (l <= size && key(l) < key(i)) {
091: largest = l;
092: } else {
093: largest = i;
094: }
095: if (r <= size && key(r) < key(largest)) {
096: largest = r;
097: }
098: if (largest != i) {
099: Object iEdge = list.get(i);
100: Object largestEdge = list.get(largest);
101: list.set(i, largestEdge);
102: list.set(largest, iEdge);
103: heapify(largest);
104: }
105: }
106:
107: public Object min() {
108: return list.get(1);
109: }
110:
111: public Object removeMin() {
112: if (size == 0)
113: throw new NoSuchElementException();
114: Object ret = list.get(1);
115: contents.remove(ret);
116: list.set(1, list.get(size));
117: list.set(size, null);
118: size--;
119: heapify(1);
120: return ret;
121: }
122:
123: public void heapify() {
124: for (int i = size; i > 0; i--)
125: heapify(i);
126: }
127:
128: private int key(Object o) {
129: return keys.key(o);
130: }
131:
132: private int key(int i) {
133: return keys.key(list.get(i));
134: }
135: }
|