001 /* JAPI - (Yet anothr (hopefully) useful) Java API
002 *
003 * Copyright (C) 2004-2006 Christian Hujer
004 *
005 * This program is free software; you can redistribute it and/or
006 * modify it under the terms of the GNU General Public License as
007 * published by the Free Software Foundation; either version 2 of the
008 * License, or (at your option) any later version.
009 *
010 * This program is distributed in the hope that it will be useful, but
011 * WITHOUT ANY WARRANTY; without even the implied warranty of
012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013 * General Public License for more details.
014 *
015 * You should have received a copy of the GNU General Public License
016 * along with this program; if not, write to the Free Software
017 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
018 * 02111-1307, USA.
019 */
020
021 package net.sf.japi.util;
022
023 import static java.lang.Class.forName;
024 import java.util.ArrayList;
025 import java.util.Collection;
026 import java.util.Collections;
027 import java.util.List;
028 import java.util.RandomAccess;
029 import java.util.Iterator;
030 import java.util.Comparator;
031
032 /** This class provides some additional utility methods you might miss in {@link Collections}.
033 * It is named Collections2 so you have no problems using both, this class and <code>java.util.Collections</code> (no name conflict).
034 * @author <a href="mailto:Christian.Hujer@itcqis.com">Christian Hujer</a>
035 * @see Collections
036 */
037 public class Collections2 {
038
039 /** Class of java.util.Arrays.ArrayList */
040 private static final Class<? extends List<?>> AL;
041 static {
042 Class<? extends List<?>> c = null;
043 try {
044 c = (Class<? extends List<?>>) forName("java.util.Arrays.ArrayList");
045 } catch (ClassNotFoundException e) { /* ignore, null is okay then. */ }
046 AL = c;
047 }
048
049 /** Returns a collection only containing those elements accepted by the given filter.
050 * The original collection remains unmodified.
051 * This method tries its best to create a new, empty variant of the Collection passed in <var>c</var>:
052 * <ol>
053 * <li>it's tried to create a new instance from the class of <var>c</var> using Reflection</li>
054 * <li>it's tried to {@link Object#clone()} <var>c</var> using Reflection and {@link Collection#clear()} the clone</li>
055 * <li>it's tried if c is a {@link RandomAccess} {@link List}, in which case an {@link ArrayList} is returned as an alternative</li>
056 * </ol>
057 * @param c Collection to filter
058 * @param filter Filter to use for <var>c</var>
059 * @return collection containing only those elements accepted by the filter or <code>null</code> if the Collection could not be created.
060 */
061 public static final <T, C extends Collection<T>> C filter(final C c, final Filter<T> filter) {
062 C filtered = null;
063 try {
064 filtered = (C) c.getClass().newInstance();
065 } catch (final Exception e) { /* ignore, check is done on null. */ }
066 if (filtered == null && c instanceof Cloneable) {
067 try {
068 filtered = (C) c.getClass().getMethod("clone").invoke(c);
069 c.clear();
070 } catch (final Exception e) {
071 filtered = null;
072 }
073 }
074 if (filtered == null && (AL != null && AL.isInstance(c) || c instanceof List && c instanceof RandomAccess)) {
075 filtered = (C) new ArrayList<T>();
076 }
077 if (filtered != null) { // only fill if filtered collection could be created.
078 for (final T o : c) {
079 if (filter.accept(o)) {
080 filtered.add(o);
081 }
082 }
083 }
084 return filtered;
085 }
086
087 /** Removes all elements from a collection not accepted by the given filter.
088 * The original collection is modified.
089 * It is required that the collection is modifiable.
090 * @param collection Collection to filter
091 * @param filter Filter to use for <var>c</var>
092 * @return number of elements removed
093 */
094 public static final <T, C extends Collection<T>> int removeFilter(final C collection, final Filter<T> filter) {
095 int removed = 0;
096 for (T o : collection) {
097 if (!filter.accept(o)) {
098 collection.remove(o);
099 removed++;
100 }
101 }
102 return removed;
103 }
104
105 /** Checks whether a list is sorted.
106 * @param list List to check
107 * @return <code>true</code> if <var>list</var> is sorted, otherwise <code>false</code>
108 * @see Comparable
109 * @see Collections#sort(List)
110 */
111 public static final <T extends Comparable<? super T>> boolean isSorted(final List<T> list) {
112 if (list.size() < 2) {
113 // empty lists or lists with only 1 element are always sorted, no need to check
114 return true;
115 }
116 if (list instanceof RandomAccess) {
117 final int n = list.size();
118 for (int i = 0; i < n; i++) {
119 if (list.get(i).compareTo(list.get(i + 1)) < 0) {
120 return false;
121 }
122 }
123 return true;
124 } else {
125 final Iterator<T> it = list.iterator();
126 assert list.size() >= 1; // list.size() is >= 2, but >= 1 is sufficient
127 T previous = it.next(); // save because list.size() >= 1;
128 while (it.hasNext()) {
129 final T current = it.next();
130 if (previous.compareTo(current) < 0) {
131 return false;
132 }
133 previous = current;
134 }
135 return true;
136 }
137 }
138
139 /** Checks whether a list is sorted.
140 * @param list List to check
141 * @param c Comparator to use for comparing list elements
142 * @return <code>true</code> if <var>list</var> is sorted, otherwise <code>false</code>
143 * @see Comparator
144 * @see Collections#sort(List,Comparator)
145 */
146 public static final <T> boolean isSorted(final List<T> list, final Comparator<? super T> c) {
147 if (c == null) {
148 return isSorted((List) list);
149 }
150 if (list.size() < 2) {
151 // empty lists or lists with only 1 element are always sorted, no need to check
152 return true;
153 }
154 if (list instanceof RandomAccess) {
155 final int n = list.size();
156 for (int i = 0; i < n; i++) {
157 if (c.compare(list.get(i), list.get(i + 1)) < 0) {
158 return false;
159 }
160 }
161 return true;
162 } else {
163 final Iterator<T> it = list.iterator();
164 assert list.size() >= 1;
165 T previous = it.next();
166 while (it.hasNext()) {
167 final T current = it.next();
168 if (c.compare(previous, current) < 0) {
169 return false;
170 }
171 previous = current;
172 }
173 return true;
174 }
175 }
176
177 /** Private constructor - no instances needed. */
178 private Collections2() {}
179 /* TODO: Planned methods for future versions:
180 * - isSorted for lists with and without Comparators
181 */
182
183 } // class Collections2