KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > go > trove > util > SortedArrayList


1 /* ====================================================================
2  * Trove - Copyright (c) 1997-2000 Walt Disney Internet Group
3  * ====================================================================
4  * The Tea Software License, Version 1.1
5  *
6  * Copyright (c) 2000 Walt Disney Internet Group. All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * 1. Redistributions of source code must retain the above copyright
13  * notice, this list of conditions and the following disclaimer.
14  *
15  * 2. Redistributions in binary form must reproduce the above copyright
16  * notice, this list of conditions and the following disclaimer in
17  * the documentation and/or other materials provided with the
18  * distribution.
19  *
20  * 3. The end-user documentation included with the redistribution,
21  * if any, must include the following acknowledgment:
22  * "This product includes software developed by the
23  * Walt Disney Internet Group (http://opensource.go.com/)."
24  * Alternately, this acknowledgment may appear in the software itself,
25  * if and wherever such third-party acknowledgments normally appear.
26  *
27  * 4. The names "Tea", "TeaServlet", "Kettle", "Trove" and "BeanDoc" must
28  * not be used to endorse or promote products derived from this
29  * software without prior written permission. For written
30  * permission, please contact opensource@dig.com.
31  *
32  * 5. Products derived from this software may not be called "Tea",
33  * "TeaServlet", "Kettle" or "Trove", nor may "Tea", "TeaServlet",
34  * "Kettle", "Trove" or "BeanDoc" appear in their name, without prior
35  * written permission of the Walt Disney Internet Group.
36  *
37  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
38  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
39  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
40  * DISCLAIMED. IN NO EVENT SHALL THE WALT DISNEY INTERNET GROUP OR ITS
41  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
42  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
43  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
44  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
45  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
46  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
47  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
48  * ====================================================================
49  *
50  * For more information about Tea, please see http://opensource.go.com/.
51  */
52
53 package com.go.trove.util;
54
55 import java.util.*;
56
57 /******************************************************************************
58  * An extension of ArrayList that insures that all of the items added are
59  * sorted. A binary search method has been added to provide a quick way to
60  * auto sort this Collection. The method call for this search has been made
61  * public so that this Collection can be searched.
62  * Note: Not all methods for adding and removing elements are supported.
63  *
64  * @author Sean T. Treat
65  * @version
66  * @see java.util.Collection
67  * @see java.util.List
68  * @see java.util.ArrayList
69  * <!--$$Revision:--> 5 <!-- $-->, <!--$$JustDate:--> 5/04/01 <!-- $-->
70  */
71 public class SortedArrayList extends ArrayList {
72
73     //
74 // Data Members
75 //
76
77     private Comparator mComparator = null;
78
79     /**
80      * Constructs a new SortedArrayList. To guarantee that this Collection
81      * is properly sorted, this constructor should be called.
82      * @param c The comparator to use when sorting this Collection.
83      */
84     public SortedArrayList(Comparator c) {
85         mComparator = c;
86     }
87
88     public SortedArrayList() {
89     }
90     
91     public SortedArrayList(Collection c) {
92         addAll(c);
93     }
94
95     /**
96      * @return the Comparator that has been assigned to this Collection.
97      */
98     public Comparator comparator() {
99         return mComparator;
100     }
101
102     /**
103      * Adds an Object to this Collection.
104      * @param o The Object to be added.
105      * @return true if this Collection is modified as a result of this call.
106      */
107     public boolean add(Object JavaDoc o) {
108         // find the index where this item should go
109 // add the item @ the specified index
110 int idx = 0;
111         if(!isEmpty()) {
112             idx = findInsertionPoint(o);
113         }
114
115         try {
116             super.add(idx, o);
117         }
118         catch(IndexOutOfBoundsException JavaDoc e) {
119             return false;
120         }
121         return true;
122     }
123
124     /**
125      * Add all of the elements in the c to this List.
126      * @param c The Collection that is to be added.
127      * @return true if this Collection is altered. Otherwise, false.
128      */
129     public boolean addAll(Collection c) {
130         Iterator i = c.iterator();
131         boolean changed = false;
132         boolean ret;
133         while(i.hasNext()) {
134             ret = add(i.next());
135             if(!changed) {
136                 changed = ret;
137             }
138         }
139         return changed;
140     }
141
142     /**
143      * Retrieves the last element in this List.
144      * @exception Thrown if this List is empty.
145      */
146     public Object JavaDoc lastElement() throws NoSuchElementException {
147         if(isEmpty()) {
148             throw new NoSuchElementException();
149         }
150         
151         return get(size()-1);
152     }
153
154     /**
155      * Finds the index at which o should be inserted.
156      * @param o The Object that is to be inserted.
157      * @return The index where Object o should be inserted.
158      */
159     public int findInsertionPoint(Object JavaDoc o) {
160         return findInsertionPoint(o, 0, size()-1);
161     }
162
163     //
164 // Unsupported Methods
165 //
166
167     /**
168      * @exception This method not supported.
169      */
170     public void add(int index, Object JavaDoc element) {
171         System.out.println("add");
172         throw new UnsupportedOperationException JavaDoc("add(int index, Object element is not Supported");
173     }
174
175     /**
176      * @exception This method not supported.
177      */
178     public Object JavaDoc set(int index, Object JavaDoc element) {
179         throw new UnsupportedOperationException JavaDoc("set(int index, Object element) is not Supported");
180     }
181     
182     /**
183      * @exception This method not supported.
184      */
185     public boolean addAll(int index, Collection c) {
186         throw new UnsupportedOperationException JavaDoc("addAll(int index, Collection c) is not Supported");
187     }
188
189     //
190 // Private Methods
191 //
192
193     /**
194      * Compares two keys using the correct comparison method for this
195      * Collection.
196      * @param k1 The first item to be compared.
197      * @param k2 The second item to be compared.
198      * @return a positive or negative integer if they differ, and zero if
199      * equal.
200      */
201     private int compare(Object JavaDoc k1, Object JavaDoc k2) {
202         return (mComparator==null ? ((Comparable JavaDoc)k1).compareTo(k2)
203                 : mComparator.compare(k1, k2));
204     }
205
206     /**
207      * Conducts a binary search to find the index where Object o should
208      * be inserted.
209      * @param o The Object that is to be inserted.
210      * @param startIndex The starting point for the search.
211      * @param endIndex The end boundary for this search.
212      * @return The index where Object o should be inserted.
213      */
214     private int findInsertionPoint(Object JavaDoc o, int startIndex, int endIndex) {
215
216         int halfPt = ((endIndex - startIndex)/2) + startIndex;
217         int delta = compare(get(halfPt), o);
218
219         if(delta < 0) {
220             endIndex = halfPt;
221         }
222         else if(delta > 0) {
223             startIndex = halfPt;
224         }
225         else {
226             // System.out.println("halfPt: " + halfPt);
227 return halfPt;
228         }
229
230         // the object in question falls between two elements
231 if((endIndex - startIndex) <= 1) {
232             // System.out.println("endIndex: " + endIndex);
233 return endIndex+1;
234         }
235
236         return findInsertionPoint(o, startIndex, endIndex);
237     }
238 }
239
Popular Tags