001 /* JAPI - (Yet another (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 import net.sf.japi.util.filter.Filter;
032
033 /** This class provides some additional utility methods you might miss in {@link Collections}.
034 * It is named Collections2 so you have no problems using both, this class and <code>java.util.Collections</code> (no name conflict).
035 * @author <a href="mailto:chris@riedquat.de">Christian Hujer</a>
036 * @see Collections
037 */
038 public class Collections2 {
039
040 /** Class of java.util.Arrays.ArrayList */
041 private static final Class<? extends List<?>> AL;
042 static {
043 Class<? extends List<?>> c = null;
044 try {
045 c = (Class<? extends List<?>>) forName("java.util.Arrays.ArrayList");
046 } catch (ClassNotFoundException e) { /* ignore, null is okay then. */ }
047 AL = c;
048 }
049
050 /** Returns a collection only containing those elements accepted by the given filter.
051 * The original collection remains unmodified.
052 * This method tries its best to create a new, empty variant of the Collection passed in <var>c</var>:
053 * <ol>
054 * <li>it's tried to create a new instance from the class of <var>c</var> using Reflection</li>
055 * <li>it's tried to {@link Object#clone()} <var>c</var> using Reflection and {@link Collection#clear()} the clone</li>
056 * <li>it's tried if c is a {@link RandomAccess} {@link List}, in which case an {@link ArrayList} is returned as an alternative</li>
057 * </ol>
058 * @param c Collection to filter
059 * @param filter Filter to use for <var>c</var>
060 * @return collection containing only those elements accepted by the filter or <code>null</code> if the Collection could not be created.
061 */
062 public static final <T, C extends Collection<T>> C filter(final C c, final Filter<? super T> filter) {
063 C filtered = null;
064 try {
065 filtered = (C) c.getClass().newInstance();
066 } catch (final Exception e) { /* ignore, check is done on null. */ }
067 if (filtered == null && c instanceof Cloneable) {
068 try {
069 filtered = (C) c.getClass().getMethod("clone").invoke(c);
070 c.clear();
071 } catch (final Exception e) {
072 filtered = null;
073 }
074 }
075 if (filtered == null && (AL != null && AL.isInstance(c) || c instanceof List && c instanceof RandomAccess)) {
076 filtered = (C) new ArrayList<T>();
077 }
078 if (filtered != null) { // only fill if filtered collection could be created.
079 for (final T o : c) {
080 if (filter.accept(o)) {
081 filtered.add(o);
082 }
083 }
084 }
085 return filtered;
086 }
087
088 /** Removes all elements from a collection not accepted by the given filter.
089 * The original collection is modified.
090 * It is required that the collection is modifiable.
091 * @param collection Collection to filter
092 * @param filter Filter to use for <var>c</var>
093 * @return number of elements removed
094 */
095 public static final <T, C extends Collection<T>> int removeFilter(final C collection, final Filter<? super T> filter) {
096 int removed = 0;
097 for (final T o : collection) {
098 if (!filter.accept(o)) {
099 collection.remove(o);
100 removed++;
101 }
102 }
103 return removed;
104 }
105
106 /** Checks whether a list is sorted.
107 * @param list List to check
108 * @return <code>true</code> if <var>list</var> is sorted, otherwise <code>false</code>
109 * @see Comparable
110 * @see Collections#sort(List)
111 */
112 public static final <T extends Comparable<? super T>> boolean isSorted(final List<T> list) {
113 if (list.size() < 2) {
114 // empty lists or lists with only 1 element are always sorted, no need to check
115 return true;
116 }
117 if (list instanceof RandomAccess) {
118 final int n = list.size();
119 for (int i = 0; i < n; i++) {
120 if (list.get(i).compareTo(list.get(i + 1)) < 0) {
121 return false;
122 }
123 }
124 return true;
125 } else {
126 final Iterator<T> it = list.iterator();
127 assert list.size() >= 1; // list.size() is >= 2, but >= 1 is sufficient
128 T previous = it.next(); // save because list.size() >= 1;
129 while (it.hasNext()) {
130 final T current = it.next();
131 if (previous.compareTo(current) < 0) {
132 return false;
133 }
134 previous = current;
135 }
136 return true;
137 }
138 }
139
140 /** Checks whether a list is sorted.
141 * @param list List to check
142 * @param c Comparator to use for comparing list elements
143 * @return <code>true</code> if <var>list</var> is sorted, otherwise <code>false</code>
144 * @see Comparator
145 * @see Collections#sort(List,Comparator)
146 */
147 public static final <T> boolean isSorted(final List<T> list, final Comparator<? super T> c) {
148 if (c == null) {
149 //noinspection unchecked,RawUseOfParameterizedType
150 return isSorted((List) list);
151 }
152 if (list.size() < 2) {
153 // empty lists or lists with only 1 element are always sorted, no need to check
154 return true;
155 }
156 if (list instanceof RandomAccess) {
157 final int n = list.size();
158 for (int i = 0; i < n; i++) {
159 if (c.compare(list.get(i), list.get(i + 1)) < 0) {
160 return false;
161 }
162 }
163 return true;
164 } else {
165 final Iterator<T> it = list.iterator();
166 assert list.size() >= 1;
167 T previous = it.next();
168 while (it.hasNext()) {
169 final T current = it.next();
170 if (c.compare(previous, current) < 0) {
171 return false;
172 }
173 previous = current;
174 }
175 return true;
176 }
177 }
178
179 /** Private constructor - no instances needed. */
180 private Collections2() {}
181
182 } // class Collections2