001/* ----------------------------------------------------------------------------
002   The Kiwi Toolkit - A Java Class Library
003   Copyright (C) 1998-2004 Mark A. Lindner
004
005   This library 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 library is distributed in the hope that it will be useful,
011   but 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 library; if not, write to the Free Software
017   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
018   02111-1307, USA.
019 
020   The author may be contacted at: mark_a_lindner@yahoo.com
021   ----------------------------------------------------------------------------
022   $Log: KCollections.java,v $
023   Revision 1.2  2004/05/05 21:22:45  markl
024   Comment header updates.
025
026   Revision 1.1  2004/05/05 18:29:32  markl
027   VectorUtils replaced by KCollections
028   ----------------------------------------------------------------------------
029*/
030
031package kiwi.util;
032
033import java.util.*;
034
035/** A utility class that provides methods for performing additional common
036 * operations on sorted and unsorted collections.
037 *
038 * @author Mark Lindner
039 * @since Kiwi 2.0
040 */
041
042public final class KCollections
043  {
044  /*
045   */
046
047  private KCollections() { }
048
049  /** Print the contents of a collection. This method displays a list
050   * of all items in a collection. For each item, the class name of
051   * the object type is listed, followed by the string representation
052   * of the object.
053   *
054   * @param c The collection to print.
055   */
056  
057  public static void print(Collection c)
058    {
059    if(c == null)
060      {
061      System.out.println("(null)");
062      return;
063      }
064
065    Iterator iter = c.iterator();
066    while(iter.hasNext())
067      {
068      Object o = iter.next();
069      System.out.println("[" + StringUtils.getClassName(o.getClass()) + "] "
070                         + o.toString());
071      }
072    }
073
074  /** Search for an object in a list. If the list is sorted, a binary
075   * search is performed. Otherwise, a linear search is performed.
076   *
077   * @param l The list to search.
078   * @param o The object to search for.
079   * @param sorted A flag specifying whether the list is sorted.
080   * @param comparator The comparator to use.
081   * @return The index of the object, or <code>-1</code> if not found.
082   */
083  
084  public static int search(List l, Object o, boolean sorted,
085                           Comparator comparator)
086    {
087    return(sorted ? Collections.binarySearch(l, o, comparator)
088           : linearSearch(l, o, comparator));
089    }
090
091  /** Perform a linear search on a collection.
092   *
093   * @param c The collection to search.
094   * @param o The object to search for.
095   * @param comparator The comparator to use.
096   * @return The index of the object, or <code>-1</code> if not found.
097   */
098  
099  public static int linearSearch(Collection c, Object o, Comparator comparator)
100    {
101    Iterator iter = c.iterator();
102
103    for(int i = 0; iter.hasNext(); i++)
104      {
105      Object obj = iter.next();
106      if(comparator.compare(o, obj) == 0)
107        return(i);
108      }
109
110    return(-1);
111    }
112
113  /** Compare two lists. The lists are considered "equal" if both lists
114   * contain equivalent elements, but not necessarily in the same order.
115   *
116   * @param l1 The first list.
117   * @param l2 The second list.
118   * @param sorted A flag specifying whether the lists are sorted.
119   * @param comparator The comparator to use.
120   * @return <code>true</code> if the lists are "equal" and
121   * <code>false</code> otherwise.
122   */
123
124  public static boolean compare(List l1, List l2, boolean sorted,
125                                Comparator comparator)
126    {
127    int n = l1.size();
128    if(l2.size() != n)
129      return(false);
130
131    Iterator iter = l1.iterator();
132    while(iter.hasNext())
133      {
134      if(search(l2, iter.next(), sorted, comparator) >= 0)
135        n--;
136      }
137    
138    return(n == 0);
139    }
140
141  /** Compute the union of two lists. The union consists of all items
142   * from the two lists that are not in both lists.
143   *
144   * @param l1 The first list.
145   * @param l2 The second list.
146   * @param sorted A flag specifying whether the lists are sorted.
147   * @param comparator The comparator to use.
148   * @return A list consisting of all items in <code>l1</code> and all
149   * items in <code>l2</code> that are not also in <code>l1</code>.
150   */
151
152  public static List union(List l1, List l2, boolean sorted,
153                           Comparator comparator)
154    {
155    ArrayList list = new ArrayList();
156
157    add(list, l1);
158
159    Iterator iter = l2.iterator();
160    while(iter.hasNext())
161      {
162      Object o = iter.next();
163      if(search(list, o, sorted, comparator) >= 0)
164        list.add(o);
165      }
166
167    return(list);
168    }
169
170  /** Compute the intersection of two lists. The intersection of two lists
171   * consists of all the elements that appear in both lists.
172   *
173   * @param l1 The first vector.
174   * @param l2 The second vector.
175   * @param sorted A flag specifying whether the lists are sorted.
176   * @param comparator The comparator to use.
177   * @return A list that includes all items that are in both <code>l1</code>
178   * and <code>l2</code>.
179   */
180  
181  public static List intersection(List l1, List l2, boolean sorted,
182                                  Comparator comparator)
183    {
184    ArrayList list = new ArrayList();
185
186    Iterator iter = l1.iterator();
187    while(iter.hasNext())
188      {
189      Object o = iter.next();
190      if(search(l2, o, sorted, comparator) >= 0)
191        list.add(o);
192      }
193
194    return(list);
195    }
196
197  /** Compute the difference between two lists. The difference
198   * consists of all items in one list that are not in the other
199   * list.
200   *
201   * @param l1 The first list.
202   * @param l2 The second list.
203   * @param sorted A flag specifying whether the lists are sorted.
204   * @param comparator The comparator to use.
205   * @return A list that includes all elements from <code>l1</code> that are
206   * not in <code>l2</code>.
207   */
208
209  public static List difference(List l1, List l2, boolean sorted,
210                                Comparator comparator)
211    {
212    List list = new ArrayList();
213
214    Iterator iter = l1.iterator();
215    while(iter.hasNext())
216      {
217      Object o = iter.next();
218      if(search(l2, o, sorted, comparator) >= 0)
219        list.add(o);
220      }
221
222    return(list);
223    }
224
225  /** Add the elements from one collection to another collection.
226   *
227   * @param c1 The original collection.
228   * @param c2 The collection of items to add to <code>c1</code>.
229   * @return <code>c1</code>
230   */
231  
232  public static Collection add(Collection c1, Collection c2)
233    {
234    if(!((c2 == null) || (c2.size() == 0) || (c1 == null)))
235      {
236      Iterator iter = c2.iterator();
237      while(iter.hasNext())
238        c1.add(iter.next());
239      }
240
241    return(c1);
242    }
243
244  }
245
246/* end of source file */