KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > objectweb > dream > queue > ListAddRemoveFirstLastFastImpl


1 /**
2  * Dream
3  * Copyright (C) 2003-2004 INRIA Rhone-Alpes
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18  *
19  * Contact: dream@objectweb.org
20  *
21  * Initial developer(s): Vivien Quema
22  * Contributor(s):
23  */
24
25 package org.objectweb.dream.queue;
26
27 import java.util.Enumeration JavaDoc;
28
29 import org.objectweb.dream.AbstractComponent;
30 import org.objectweb.dream.message.manager.MessageManager;
31 import org.objectweb.dream.pool.ObjectPool;
32 import org.objectweb.dream.pool.Recyclable;
33 import org.objectweb.fractal.api.NoSuchInterfaceException;
34 import org.objectweb.fractal.api.control.IllegalBindingException;
35 import org.objectweb.fractal.api.control.IllegalLifeCycleException;
36
37 /**
38  * The ListAddRemoveFirstLastFastImpl class is just a linked list that supports
39  * very efficient insertion and deletion, as well as an Enumeration interface.
40  * <p>
41  * <i>Note: </i>None of the methods in this linked list are synchronized.
42  * <p>
43  * This class is freely inspired from code belonging to the SEDA project (see
44  * http://sourceforge.net/projects/seda/).
45  */
46 public class ListAddRemoveFirstLastFastImpl extends AbstractComponent
47     implements
48       List,
49       ListAddFirstLast,
50       ListRemoveFirstLast
51 {
52
53   private int numInList;
54   private Element first;
55   private Element last;
56
57   /** The client interface used to access the pool of {@link Element}instances. */
58   protected ObjectPool objectPoolItf;
59
60   //---------------------------------------------------------------------------
61 // Constructor.
62 // ---------------------------------------------------------------------------
63
64   /**
65    * Allocates a brand new ListAddRemoveFirstLastFastImpl.
66    */
67   public ListAddRemoveFirstLastFastImpl()
68   {
69     numInList = 0;
70     first = null;
71     last = null;
72   }
73
74   //---------------------------------------------------------------------------
75 // Implementation of the List interface.
76 // ---------------------------------------------------------------------------
77
78   /**
79    * @see List#add(Object)
80    */
81   public void add(Object JavaDoc o)
82   {
83     addLast(o);
84
85   }
86
87   /**
88    * @see List#remove()
89    */
90   public Object JavaDoc remove()
91   {
92     return removeFirst();
93   }
94
95   /**
96    * @see List#isEmpty()
97    */
98   public boolean isEmpty()
99   {
100     return numInList == 0;
101   }
102
103   //---------------------------------------------------------------------------
104 // Implementation of the ListAddFirstLast interface.
105 // ---------------------------------------------------------------------------
106
107   /**
108    * @see ListAddFirstLast#addLast(Object)
109    */
110   public void addLast(Object JavaDoc o)
111   {
112     Element lle = (Element) objectPoolItf.newInstance();
113     lle.obj = o;
114
115     if (first == null)
116     {
117       first = lle;
118       last = lle;
119     }
120     else
121     {
122       last.next = lle;
123       lle.prev = last;
124       last = lle;
125     }
126     numInList++;
127   }
128
129   /**
130    * @see ListAddFirstLast#addFirst(Object)
131    */
132   public void addFirst(Object JavaDoc o)
133   {
134     Element lle = (Element) objectPoolItf.newInstance();
135     lle.obj = o;
136
137     if (first == null)
138     {
139       first = lle;
140       last = lle;
141     }
142     else
143     {
144       first.prev = lle;
145       lle.next = first;
146       first = lle;
147     }
148     numInList++;
149   }
150
151   //---------------------------------------------------------------------------
152 // Implementation of the ListRemoveFirstLast interface.
153 // ---------------------------------------------------------------------------
154
155   /**
156    * @see ListRemoveFirstLast#getLast()
157    */
158   public Object JavaDoc getLast()
159   {
160     if (last == null)
161     {
162       return null;
163     }
164     return last.obj;
165   }
166
167   /**
168    * @see ListRemoveFirstLast#removeLast()
169    */
170   public Object JavaDoc removeLast()
171   {
172     Element retme = null;
173     Object JavaDoc retobj = null;
174
175     if (last == null)
176     {
177       return null;
178     }
179     retme = last;
180
181     if (first == last)
182     {
183       first = null;
184       last = null;
185     }
186     else
187     {
188       last = last.prev;
189       last.next = null;
190     }
191
192     numInList--;
193     retobj = retme.obj;
194     objectPoolItf.recycleInstance(retme);
195     return retobj;
196   }
197
198   /**
199    * @see ListRemoveFirstLast#getFirst()
200    */
201   public Object JavaDoc getFirst()
202   {
203     if (first == null)
204     {
205       return null;
206     }
207     return first.obj;
208   }
209
210   /**
211    * @see ListRemoveFirstLast#removeFirst()
212    */
213   public Object JavaDoc removeFirst()
214   {
215     Element retme = null;
216     Object JavaDoc retobj = null;
217
218     if (first == null)
219       return null;
220     retme = first;
221
222     if (first == last)
223     {
224       first = null;
225       last = null;
226     }
227     else
228     {
229       first = first.next;
230       first.prev = null;
231     }
232
233     numInList--;
234     retobj = retme.obj;
235     objectPoolItf.recycleInstance(retme);
236     return retobj;
237   }
238
239   //---------------------------------------------------------------------------
240 // Other methods.
241 // ---------------------------------------------------------------------------
242
243   /**
244    * Returns the first object that is "equal" to the given object, based on the
245    * response of the Object.equals() method.
246    *
247    * @param known the object to which an element must be equal.
248    * @return the matching object, or null if there is nothing that matches.
249    */
250   public Object JavaDoc getItem(Object JavaDoc known)
251   {
252     Element tmp;
253
254     tmp = first;
255     while (tmp != null)
256     {
257       if (known.equals(tmp.obj))
258       {
259         return tmp.obj;
260       }
261       tmp = tmp.next;
262     }
263     return null;
264   }
265
266   /**
267    * Removes the first object that is "equal" to the given object, based on the
268    * response of the Object.equals() method.
269    *
270    * @param known the object to which an element must be equal.
271    * @return the match, or null if there is nothing that matches.
272    */
273   public Object JavaDoc removeItem(Object JavaDoc known)
274   {
275     Element tmp;
276
277     tmp = first;
278     while (tmp != null)
279     {
280       if (known.equals(tmp.obj))
281       {
282
283         // cut it out and return it
284 if (tmp == first)
285         {
286           return this.removeFirst();
287         }
288         else if (tmp == last)
289         {
290           return this.removeLast();
291         }
292         else
293         {
294           // somewhere in middle
295 Object JavaDoc retobj;
296
297           (tmp.prev).next = tmp.next;
298           (tmp.next).prev = tmp.prev;
299           numInList--;
300           retobj = tmp.obj;
301           objectPoolItf.recycleInstance(tmp);
302           return retobj;
303         }
304       }
305       tmp = tmp.next;
306     }
307     return null;
308   }
309
310   /**
311    * Returns a java.util.Enumeration enumeration over the elements of the linked
312    * list. If you modify the list while enumerating over it, you get what you
313    * deserve (i.e. undefined behaviour).
314    *
315    * @return the enumeration over the elements
316    * @see Enumeration
317    */
318   public Enumeration JavaDoc elements()
319   {
320     return new FastLinkedListEnumeration();
321   }
322
323   //---------------------------------------------------------------------------
324 // Overriden methods.
325 // ---------------------------------------------------------------------------
326
327   /**
328    * @see Object#toString()
329    */
330   public String JavaDoc toString()
331   {
332     return toString("");
333   }
334
335   private String JavaDoc toString(String JavaDoc prefix)
336   {
337     String JavaDoc pre = prefix;
338     if (pre == null)
339       pre = "";
340
341     String JavaDoc ret = pre + "ListAddRemoveFirstLastFastImpl: length=" + numInList
342         + "\n";
343
344     Element current = first;
345     while (current != null)
346     {
347       if (current.obj == null)
348       {
349         ret += pre + " (null)\n";
350       }
351
352       else
353       {
354         if (current.obj instanceof ListAddRemoveFirstLastFastImpl)
355         {
356           ret += pre
357               + "LINKED LIST\n"
358               + ((ListAddRemoveFirstLastFastImpl) current.obj).toString(pre
359                   + " ");
360         }
361         else
362         {
363           ret += pre + " " + current.obj.toString() + "\n";
364         }
365       }
366
367       current = current.next;
368     }
369
370     return ret;
371   }
372
373   // ---------------------------------------------------------------------------
374 // Inner classes.
375 // ---------------------------------------------------------------------------
376
377   /**
378    * This class represents elements of a linked list. Each element contains a
379    * reference to its predecessor (<code>previous</code>), its successor (
380    * <code>next</code>), a message, and a sequence number.
381    */
382   public static class Element implements Recyclable
383   {
384     Object JavaDoc obj;
385     Element prev;
386     Element next;
387
388     /**
389      * @see org.objectweb.dream.pool.Recyclable#recycle()
390      */
391     public void recycle()
392     {
393       // Do nothing because code does not require anything.
394 }
395
396   }
397
398   // ---------------------------------------------------------------------------
399 // Inner classes implementing the Enumeration interface.
400 // ---------------------------------------------------------------------------
401
402   /**
403    * A FastLinkedListEnumeration is a java.util.Enumeration over the
404    * ListAddRemoveFirstLastFastImpl elements.
405    *
406    * @see Enumeration
407    */
408   public class FastLinkedListEnumeration implements Enumeration JavaDoc
409   {
410     private Element curElement;
411
412     /**
413      * Constructor.
414      */
415     public FastLinkedListEnumeration()
416     {
417       curElement = ListAddRemoveFirstLastFastImpl.this.first;
418     }
419
420     /**
421      * @see Enumeration#hasMoreElements()
422      */
423     public boolean hasMoreElements()
424     {
425       if (curElement == null)
426         return false;
427       return true;
428     }
429
430     /**
431      * @see Enumeration#nextElement()
432      */
433     public Object JavaDoc nextElement() throws java.util.NoSuchElementException JavaDoc
434     {
435       Object JavaDoc retme;
436
437       if (curElement == null)
438         throw new java.util.NoSuchElementException JavaDoc();
439       retme = curElement.obj;
440       curElement = curElement.next;
441       return retme;
442     }
443   }
444
445   // ---------------------------------------------------------------------------
446 // Implementation of the BindingController interface.
447 // ---------------------------------------------------------------------------
448
449   /**
450    * @see org.objectweb.fractal.api.control.BindingController#bindFc(String,
451    * Object)
452    */
453   public synchronized void bindFc(String JavaDoc clientItfName, Object JavaDoc serverItf)
454       throws NoSuchInterfaceException, IllegalBindingException,
455       IllegalLifeCycleException
456   {
457     super.bindFc(clientItfName, serverItf);
458     if (clientItfName.equals(ObjectPool.ITF_NAME))
459     {
460       objectPoolItf = (ObjectPool) serverItf;
461     }
462   }
463
464   /**
465    * @see org.objectweb.fractal.api.control.BindingController#listFc()
466    */
467   public String JavaDoc[] listFc()
468   {
469     return new String JavaDoc[]{MessageManager.ITF_NAME, ObjectPool.ITF_NAME};
470   }
471
472   // test code
473 private static void printTime(long long1, long long3, int int5)
474   {
475     long long6 = long3 - long1;
476     double double8 = (double) int5 / (double) long6;
477     double double10 = double8 * 1000.0;
478
479     System.out.println(int5 + " iterations in " + long6 + " milliseconds = "
480         + double10 + " iterations per second");
481   }
482
483 }
484
485
Popular Tags