KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sun > enterprise > util > collection > SortedArrayListBucket


1 /*
2  * The contents of this file are subject to the terms
3  * of the Common Development and Distribution License
4  * (the License). You may not use this file except in
5  * compliance with the License.
6  *
7  * You can obtain a copy of the license at
8  * https://glassfish.dev.java.net/public/CDDLv1.0.html or
9  * glassfish/bootstrap/legal/CDDLv1.0.txt.
10  * See the License for the specific language governing
11  * permissions and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL
14  * Header Notice in each file and include the License file
15  * at glassfish/bootstrap/legal/CDDLv1.0.txt.
16  * If applicable, add the following below the CDDL Header,
17  * with the fields enclosed by brackets [] replaced by
18  * you own identifying information:
19  * "Portions Copyrighted [year] [name of copyright owner]"
20  *
21  * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
22  */
23
24 //NOTE: Tabs are used instead of spaces for indentation.
25 // Make sure that your editor does not replace tabs with spaces.
26 // Set the tab length using your favourite editor to your
27 // visual preference.
28
29 /*
30  * Filename: TooManyTasksException.java
31  *
32  * Copyright 2000-2001 by iPlanet/Sun Microsystems, Inc.,
33  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
34  * All rights reserved.
35  *
36  * This software is the confidential and proprietary information
37  * of iPlanet/Sun Microsystems, Inc. ("Confidential Information").
38  * You shall not disclose such Confidential Information and shall
39  * use it only in accordance with the terms of the license
40  * agreement you entered into with iPlanet/Sun Microsystems.
41  */
42  
43 /**
44  * <BR> <I>$Source: /cvs/glassfish/appserv-commons/src/java/com/sun/enterprise/util/collection/SortedArrayListBucket.java,v $</I>
45  * @author $Author: tcfujii $
46  * @version $Revision: 1.3 $ $Date: 2005/12/25 04:12:13 $
47  */
48  
49 package com.sun.enterprise.util.collection;
50
51 import java.util.HashMap JavaDoc;
52 import java.util.ArrayList JavaDoc;
53 import java.util.Iterator JavaDoc;
54     
55
56 /**
57  *
58  */
59      
60 /*
61  * A simple test program populated an ArrayListBucket with 20 entries. Then it performed
62  * 50,000,000 get(int key) took 32.968 seconds!! 60% of the time the key that was searched
63  * was not in the bucket and hence had to search the maximum.
64  */
65 public class SortedArrayListBucket
66     implements Bucket
67 {
68
69     protected ArrayList JavaDoc entries;
70     
71     SortedArrayListBucket() {
72         entries = new ArrayList JavaDoc();
73     }
74     
75     public Object JavaDoc put(long searchKey, Object JavaDoc object) {
76         return put((int) searchKey, object);
77     }
78     
79     public Object JavaDoc put(int searchKey, Object JavaDoc object) {
80         int low = 0, high = entries.size()-1, mid;
81         int entryKey = 0;
82         IntEntry entry = null;
83         while (low <= high) {
84             mid = (low + high) / 2;
85             entry = (IntEntry) entries.get(mid);
86             entryKey = entry.key;
87             if (entryKey == searchKey) {
88                 Object JavaDoc oldObject = entry.object;
89                 entry.object = object;
90                 return oldObject;
91             } else if (searchKey < entryKey) {
92                 high = mid - 1;
93             } else {
94                 low = mid + 1;
95             }
96         }
97             
98         //totalEntries++;
99 //System.out.println("**Inserting key: " + searchKey + " at Lo: " + low);
100 entries.add(low, new IntEntry(searchKey, object));
101         return null;
102     }
103         
104     public Object JavaDoc get(long searchKey) {
105         return get((int) searchKey);
106     }
107     
108     public Object JavaDoc get(int searchKey) {
109         int low = 0, high = entries.size()-1, mid;
110         int entryKey = 0;
111         IntEntry entry = null;
112         while (low <= high) {
113             mid = (low + high) / 2;
114             entry = (IntEntry) entries.get(mid);
115             entryKey = entry.key;
116             if (entryKey == searchKey) {
117                 return entry.object;
118             } else if (searchKey < entryKey) {
119                 high = mid - 1;
120             } else {
121                 low = mid + 1;
122             }
123         }
124         return null;
125     }
126         
127     public Object JavaDoc remove(long searchKey) {
128         return remove((int) searchKey);
129     }
130         
131     public Object JavaDoc remove(int searchKey) {
132         int low = 0, high = entries.size()-1, mid;
133         int entryKey = 0;
134         IntEntry entry = null;
135
136         while (low <= high) {
137             mid = (low + high) / 2;
138             entry = (IntEntry) entries.get(mid);
139             entryKey = entry.key;
140             if (entryKey == searchKey) {
141                 entries.remove(mid);
142                 //totalEntries--;
143 return entry.object;
144             } else if (searchKey < entryKey) {
145                 high = mid - 1;
146             } else {
147                 low = mid + 1;
148             }
149         }
150         return null;
151     }
152     
153     public int size() {
154         return entries.size();
155     }
156
157     public boolean containsKey(int searchKey) {
158         return (get((long) searchKey) != null);
159     }
160
161     public boolean containsKey(long searchKey) {
162         return (get(searchKey) != null);
163     }
164
165     public Iterator JavaDoc iterator() {
166         return new BucketIterator(entries, false);
167     }
168
169     public Iterator JavaDoc entryIterator() {
170         return new BucketIterator(entries, true);
171     }
172
173     private class BucketIterator
174         implements java.util.Iterator JavaDoc
175     {
176         ArrayList JavaDoc entries;
177         int index = 0;
178         boolean iterateEntry;
179         
180         BucketIterator(ArrayList JavaDoc entries, boolean iterateEntry) {
181             this.entries = entries;
182             this.index = 0;
183             this.iterateEntry = iterateEntry;
184         }
185         
186         public boolean hasNext() {
187             return (index < entries.size());
188         }
189         
190         public Object JavaDoc next() {
191             return (iterateEntry ? entries.get(index++) : ((IntEntry) entries.get(index++)).object);
192         }
193         
194         public void remove() {
195             
196         }
197         
198     }
199         
200     
201         
202 }
203
204
Popular Tags