KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > openejb > util > LinkedListStack


1 /**
2  * Redistribution and use of this software and associated documentation
3  * ("Software"), with or without modification, are permitted provided
4  * that the following conditions are met:
5  *
6  * 1. Redistributions of source code must retain copyright
7  * statements and notices. Redistributions must also contain a
8  * copy of this document.
9  *
10  * 2. Redistributions in binary form must reproduce the
11  * above copyright notice, this list of conditions and the
12  * following disclaimer in the documentation and/or other
13  * materials provided with the distribution.
14  *
15  * 3. The name "Exolab" must not be used to endorse or promote
16  * products derived from this Software without prior written
17  * permission of Exoffice Technologies. For written permission,
18  * please contact info@exolab.org.
19  *
20  * 4. Products derived from this Software may not be called "Exolab"
21  * nor may "Exolab" appear in their names without prior written
22  * permission of Exoffice Technologies. Exolab is a registered
23  * trademark of Exoffice Technologies.
24  *
25  * 5. Due credit should be given to the Exolab Project
26  * (http://www.exolab.org/).
27  *
28  * THIS SOFTWARE IS PROVIDED BY EXOFFICE TECHNOLOGIES AND CONTRIBUTORS
29  * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
30  * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
31  * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
32  * EXOFFICE TECHNOLOGIES OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
33  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
34  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
35  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
36  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
37  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
38  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
39  * OF THE POSSIBILITY OF SUCH DAMAGE.
40  *
41  * Copyright 1999 (C) Exoffice Technologies Inc. All Rights Reserved.
42  *
43  * $Id: LinkedListStack.java 1096 2004-03-26 21:41:16Z dblevins $
44  */
45 package org.openejb.util;
46
47
48 /**
49  * A First In First Out (FIFO) queue, also known as a Stack.
50  *
51  * Note: This is an implementation of org.openejb.util.Stack
52  * not to be confused with java.util.Stack
53  */
54 public class LinkedListStack implements Stack {
55     
56     /**
57      * Entries that contain data as the result of the <code>push</code> method.
58      * The data in these entries is removed and returned when the <code>pop</code> method is called.
59      */
60     private LinkedEntry occupiedEntries;
61
62     /**
63      * Entries that contain null values as the result of the <code>pop</code> method.
64      * These entries will be populated with data when the <code>push</code> method is called.
65      */
66     private LinkedEntry vacantEntries;
67
68     /**
69      * the number of elements on the stack
70      */
71     private int size;
72     
73     /**
74      * Constructs this LinkedListStack with the specified number of LinkedEntry
75      * objects all sequentially linked together.
76      *
77      * @param initialSize
78      */
79     public LinkedListStack(int initialSize) {
80         for ( int i = 0; i < initialSize; i++ )
81             vacantEntries = new LinkedEntry( null, vacantEntries );
82     }
83
84     public synchronized Object JavaDoc push( Object JavaDoc object ) {
85         /* Take an entry from the vacant list and move it to the occupied list. */
86
87         if ( vacantEntries == null )
88             occupiedEntries = new LinkedEntry( object, occupiedEntries );
89         else {
90             // Take the top vacant entry
91 LinkedEntry entry = vacantEntries;
92
93             // Shrink the vacant entries list by one
94 vacantEntries = vacantEntries.next;
95
96             // Assign the entry a value and put it at the top of the
97 // occupied entries list
98 occupiedEntries = entry.set(object, occupiedEntries);
99         }
100         ++size;
101         return object;
102     }
103
104
105     public synchronized Object JavaDoc pop() throws java.util.EmptyStackException JavaDoc {
106         /* Take an entry from the occupied list and move it to the vacant list. */
107
108         // Take the top occupied entry
109 LinkedEntry entry = occupiedEntries;
110         if ( entry == null ) return null;
111         
112         // Shrink the occupied entries list by one
113 occupiedEntries = occupiedEntries.next;
114         
115         // Assign the entry a null value and put it at the top of the
116 // vacant entries list
117 Object JavaDoc value = entry.value;
118         vacantEntries = entry.set(null ,vacantEntries);
119         --size;
120         return value;
121     }
122
123     public synchronized int size() {
124         return size;
125     }
126     //======================================================
127 // Inner class to represent entries in the linked list
128 //
129
130     static class LinkedEntry {
131
132         LinkedEntry next;
133         Object JavaDoc value;
134
135         LinkedEntry( Object JavaDoc value, LinkedEntry next ) {
136             set(value,next);
137         }
138
139         LinkedEntry set( Object JavaDoc value, LinkedEntry next ) {
140             this.next = next;
141             this.value = value;
142             return this;
143         }
144     }
145     
146     //
147 // Inner class to represent entries in the linked list
148 //======================================================
149 }
Popular Tags