Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /* Soot - a J*va Optimization Framework
   * Copyright (C) 2004 Ondrej Lhotak
   *
   * This library is free software; you can redistribute it and/or
   * modify it under the terms of the GNU Lesser General Public
   * License as published by the Free Software Foundation; either
   * version 2.1 of the License, or (at your option) any later version.
   *
   * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  * Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public
  * License along with this library; if not, write to the
  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  * Boston, MA 02111-1307, USA.
  */
 
 package soot.util;
 import java.util.*;

A heap (priority queue) implementation.

Author(s):
Ondrej Lhotak
 
 public class Heap 
 { 
     public interface Keys {
         public int key(Object o);
     }
     final Keys keys;
     final ArrayList<Objectlist = new ArrayList<Object>();
     final HashSet<Objectcontents = new HashSet<Object>();
     private int size;
     public int size() { return ; }
     public boolean isEmpty() { return  <= 0; }
     public Heap(Keys keys) {
         this. = keys;
         .add(null);
         .add(null);
     }
     public boolean contains(Object o) {
         return .contains(o);
     }
     public boolean add(Object o) {
         if(!.add(o)) return false;
     	insert(o);
     	return true;   
     }
     private void insert(Object o) {
         ++;
         int i = ;
         while(.size() <= .add(null);
         whilei > 1 && key(parent(i)) > key(o) ) {
             .set(i.get(parent(i)));
             i = parent(i);
         }
         .set(io);
     }
     private int left(int i) { return 2*i; }
     private int right(int i) { return 2*i+1; }
     private int parent(int i) { return i/2; }
     private void heapify(int i) {
         int l = left(i);
         int r = right(i);
         int largest;
         ifl <=  && key(l) < key(i) ) {
             largest = l;
         } else {
             largest = i;
         }
         ifr <=  && key(r) < key(largest) ) {
             largest = r;
         }
         iflargest != i ) {
             Object iEdge = .get(i);
             Object largestEdge = .get(largest);
             .set(ilargestEdge);
             .set(largestiEdge);
             heapify(largest);
         }
     }
     public Object min() {
         return .get(1);
     }
     public Object removeMin() {
         if( == 0) throw new NoSuchElementException();
         Object ret = .get(1);
         .remove(ret);
         .set(1, .get());
         .set(null);
         --;
         heapify(1);
         return ret;
     }
     public void heapify() {
         forint i = i > 0; i-- ) heapify(i);
     }
     private int key(Object o) { return .key(o); }
    private int key(int i) { return .key(.get(i)); }
New to GrepCode? Check out our FAQ X