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     }