Mercurial > hg > blitz_stable

comparison src/com/go/trove/util/SortedArrayList.java @ 0:3dc0c5604566

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial checkin of blitz 2.0 fcs - no installer yet.
author Dan Creswell <dan.creswell@gmail.com>
date Sat, 21 Mar 2009 11:00:06 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:3dc0c5604566
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: 1.1 $-->, <!--$$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 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 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 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 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 element) {
171 System.out.println("add");
172 throw new UnsupportedOperationException("add(int index, Object element is not Supported");
173 }
174
175 /**
176 * @exception This method not supported.
177 */
178 public Object set(int index, Object element) {
179 throw new UnsupportedOperationException("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("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 k1, Object k2) {
202 return (mComparator==null ? ((Comparable)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 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 }