1 marinov 1.1.2.1 // AuxUniqueFIFO.java, created Sun Dec 6 18:45:39 1998 by marinov 2 cananian 1.1.2.3 // Copyright (C) 1998 Darko Marinov <marinov@lcs.mit.edu> 3 cananian 1.1.2.3 // Licensed under the terms of the GNU GPL; see COPYING for details. 4 marinov 1.1.2.1 package harpoon.Analysis.TypeInference; 5 marinov 1.1.2.1 6 cananian 1.1.2.5 import java.util.HashSet; 7 cananian 1.1.2.5 import java.util.List; 8 cananian 1.1.2.5 import java.util.LinkedList; 9 cananian 1.1.2.5 import java.util.Set; 10 marinov 1.1.2.1 import java.util.EmptyStackException; 11 marinov 1.1.2.1 /** 12 marinov 1.1.2.1 * <code>AuxUniqueFIFO</code> 13 marinov 1.1.2.1 * 14 marinov 1.1.2.1 * @author Darko Marinov <marinov@lcs.mit.edu> 15 cananian 1.2 * @version $Id: AuxUniqueFIFO.java,v 1.2 2002/02/25 21:00:36 cananian Exp $ 16 marinov 1.1.2.1 */ 17 marinov 1.1.2.1 18 marinov 1.1.2.1 public class AuxUniqueFIFO { 19 marinov 1.1.2.1 int max; 20 cananian 1.1.2.5 LinkedList[] list; // elements used as FIFOs 21 marinov 1.1.2.1 int cur; 22 cananian 1.1.2.5 Set all = new HashSet(); 23 marinov 1.1.2.1 /** Creates a <code>AuxUniqueFIFO</code>. */ 24 marinov 1.1.2.1 public AuxUniqueFIFO() { this(8); } 25 marinov 1.1.2.1 public AuxUniqueFIFO(int n) { 26 marinov 1.1.2.1 max = n; 27 cananian 1.1.2.5 list = new LinkedList[n+1]; 28 cananian 1.1.2.5 for (int i=0; i<=n; i++) list[i] = new LinkedList(); 29 marinov 1.1.2.1 cur = -1; 30 marinov 1.1.2.1 } 31 marinov 1.1.2.1 //Object push(Object o) { } 32 marinov 1.1.2.1 void push(Object o, int p) { 33 cananian 1.1.2.5 if (!all.contains(o)) { 34 marinov 1.1.2.2 if (p>max) p = max; 35 marinov 1.1.2.2 if (p<0) p = 0; 36 cananian 1.1.2.5 list[p].add(o); 37 marinov 1.1.2.2 if (p>cur) cur = p; 38 cananian 1.1.2.5 all.add(o); 39 marinov 1.1.2.2 } 40 marinov 1.1.2.1 } 41 marinov 1.1.2.1 Object pull() { 42 marinov 1.1.2.1 while (cur>=0) { 43 marinov 1.1.2.1 if (!list[cur].isEmpty()) { 44 cananian 1.1.2.5 Object o = list[cur].removeFirst(); // use as FIFO 45 marinov 1.1.2.1 all.remove(o); 46 marinov 1.1.2.1 return o; 47 marinov 1.1.2.1 } 48 marinov 1.1.2.1 cur--; 49 marinov 1.1.2.1 } 50 marinov 1.1.2.1 throw new EmptyStackException(); 51 marinov 1.1.2.1 } 52 marinov 1.1.2.1 //boolean contains(Object o) { } 53 marinov 1.1.2.1 boolean isEmpty() { 54 marinov 1.1.2.1 while (cur>=0) { 55 marinov 1.1.2.1 if (!list[cur].isEmpty()) return false; 56 marinov 1.1.2.1 cur--; 57 marinov 1.1.2.1 } 58 marinov 1.1.2.1 return true; 59 marinov 1.1.2.1 } 60 cananian 1.2 }