Stack


1   /*****************************************
2    *                                       *
3    *  JBoss Portal: The OpenSource Portal  *
4    *                                       *
5    *   Distributable under LGPL license.   *
6    *   See terms of license at gnu.org.    *
7    *                                       *
8    *****************************************/
9   
10  /*****************************************
11   *                                       *
12   *  JBoss Portal: The OpenSource Portal  *
13   *                                       *
14   *   Distributable under LGPL license.   *
15   *   See terms of license at gnu.org.    *
16   *                                       *
17   *****************************************/
18  
19  package org.jboss.portal.format.util;
20  
21  import java.util.Collections  ;
22  import java.util.Iterator  ;
23  
24  /**
25   * The goal of this class is to ensure that any event with open/close
26   * well formdness semantics are respected.
27   *
28   * This class maintain a stack of keys.
29   *
30   * To be operational this class must be subclassed to provide semantics
31   * that the user wants to give to the key identities.
32   *
33   * @author <a HREF="mailto:julien@jboss.org">Julien Viet</a>
34   * @version $Revision: 1.2 $
35   */
36  public abstract class Stack
37  {
38  
39     /** The stack pointer which always points the first available element. */
40     protected int ptr = 0;
41  
42     /** The stack holder. */
43     protected Key[] stack;
44  
45     /** The reusable iterator. */
46     private KeyIterator iterator = new KeyIterator();
47  
48     /**
49      * Create a new stack with a specified depth.
50      */
51     public Stack(int initalCapacity)
52     {
53        this.stack = new Key[initalCapacity];
54        for (int i = 0; i < stack.length; i++)
55        {
56          this.stack[i] = createKey();
57        }
58     }
59  
60     /**
61      * Reset the stack state.
62      */
63     public final void reset()
64     {
65        ptr = 0;
66     }
67  
68     /**
69      * Push a key on the stack.
70      */
71     public final Key push()
72     {
73        if (ptr == stack.length)
74        {
75           enlarge();
76        }
77        return stack[ptr++];
78     }
79  
80     /**
81      * Peek a key on the stack.
82      */
83     public Key peek(int level)
84     {
85        level = ptr - level;
86        return level >= 0 ? stack[level] : null;
87     }
88  
89     /**
90      * Pop keys until it finds the good one.
91      */
92     public final Iterator   pop(Key candidate)
93     {
94        if (ptr > 0)
95        {
96           iterator.from = ptr - 1;
97           for (Key key = stack[--ptr];!equals(candidate, key) && ptr >= 1;key = stack[--ptr])
98           {
99              ;
100          }
101          iterator.to = ptr - 1;
102          return iterator;
103       }
104       else
105       {
106          // This is a warn because it is not possible to pop with empty stack
107          return Collections.EMPTY_LIST.iterator();
108       }
109    }
110 
111    /**
112     * The implementation must provide a reusable key.
113     */
114    protected abstract Key createKey();
115 
116    /**
117     * The implementation must test keys equality.
118     */
119    protected abstract boolean equals(Key key1, Key key2);
120 
121    /**
122     * Enlarge the key stack. For now it simply add 3 keys to the actual length
123     */
124    protected void enlarge()
125    {
126       Key[] tmp = new Key[stack.length + 3];
127       System.arraycopy(stack, 0, tmp, 0, stack.length);
128       for (int i = stack.length;i < tmp.length;i++)
129       {
130          tmp[i] = createKey();
131       }
132       stack = tmp;
133    }
134 
135    /**
136     * Iterates over the poped keys.
137     */
138    public class KeyIterator implements Iterator  
139    {
140       private int from;
141       private int to;
142       public boolean hasNext()
143       {
144          return from > to;
145       }
146       public Object   next()
147       {
148          return stack[from--];
149       }
150       public void remove()
151       {
152          throw new UnsupportedOperationException  ();
153       }
154    }
155 
156    /**
157     * A key for the stack.
158     */
159    public interface Key
160    {
161    }
162 }
163
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags