KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > experimental > equivalence > EquivalenceSetCreator


1 /* ==========================================
2  * JGraphT : a free Java graph-theory library
3  * ==========================================
4  *
5  * Project Info: http://jgrapht.sourceforge.net/
6  * Project Creator: Barak Naveh (http://sourceforge.net/users/barak_naveh)
7  *
8  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9  *
10  * This library is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation; either version 2.1 of the License, or
13  * (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful, but
16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this library; if not, write to the Free Software Foundation,
22  * Inc.,
23  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24  */
25 /* -----------------
26  * EquivalenceSetCreator.java
27  * -----------------
28  * (C) Copyright 2005-2006, by Assaf Lehr and Contributors.
29  *
30  * Original Author: Assaf Lehr
31  * Contributor(s): -
32  *
33  * $Id: EquivalenceSetCreator.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  */
38 package org.jgrapht.experimental.equivalence;
39
40 import java.util.*;
41
42
43 /**
44  * FIXME Document me.
45  *
46  * @param <E> the type of the elements in the set
47  * @param <C> the type of the context the element is compared against, e.g. a
48  * Graph TODO hb 060208: REVIEW: Using an array for aElementsArray causes
49  * problems with generics elsewhere - changed to List?
50  *
51  * @author Assaf
52  * @since Jul 21, 2005
53  */
54 public class EquivalenceSetCreator<E, C>
55 {
56
57     //~ Static fields/initializers --------------------------------------------
58
59     private static final EqGroupSizeComparator groupSizeComparator =
60         new EqGroupSizeComparator();
61
62     //~ Methods ---------------------------------------------------------------
63
64     /**
65      * Checks for equivalance groups in the aElementsArray. Returns an ordered
66      * array of them, where the smallest one is the first in the array.
67      *
68      * @param aElementsArray
69      * @param aEqComparator
70      *
71      * @deprecated To improve type-safety when using generics, use {@link
72      * #createEqualityGroupOrderedArray(Collection,
73      * EquivalenceComparator, Object)}
74      */
75     @Deprecated JavaDoc public static <EE, CC> EquivalenceSet []
76     createEqualityGroupOrderedArray(
77         EE [] aElementsArray,
78         EquivalenceComparator<? super EE, ? super CC> aEqComparator,
79         CC aContext)
80     {
81         return
82             (createEqualityGroupOrderedArray(
83                     Arrays.asList(aElementsArray),
84                     aEqComparator,
85                     aContext));
86             // ArrayList<EquivalenceSet<? super EE,? super CC>> arrayList =
87 // new ArrayList<EquivalenceSet<? super EE,? super CC>>();
88 //
89 // HashMap<Integer,List<EquivalenceSet<? super EE,? super CC>>> map =
90 // createEqualityGroupMap(aElementsArray, aEqComparator, aContext);
91 // // each of the map values is a list with one or more groups in it.
92 // // Object[] array = map.values().toArray();
93 // // for (int i = 0; i < array.length; i++)
94 // // {
95 // // List list = (List)array[i];
96 //
97 // for (List<EquivalenceSet<? super EE,? super CC>> list :
98 // map.values() ) {
99 // for (EquivalenceSet<? super EE,? super CC> eSet : list ) {
100 // arrayList.add( eSet );
101 // }
102 // }
103 //
104 //
105 // // now we got all the eq. groups in an array list. we need to
106 // sort
107 // // them
108 // EquivalenceSet [] resultArray = new EquivalenceSet
109 // [arrayList.size()];
110 // arrayList.toArray(resultArray);
111 // Arrays.sort(resultArray, groupSizeComparator);
112 // return resultArray;
113 }
114
115     /**
116      * Checks for equivalance groups in the aElementsArray. Returns an ordered
117      * array of them, where the smallest one is the first in the array.
118      *
119      * @param elements
120      * @param aEqComparator TODO hb 060208: Using an array for aElementsArray
121      * causes problems with generics elsewhere - change to List?
122      */
123     public static <EE, CC> EquivalenceSet [] createEqualityGroupOrderedArray(
124         Collection<EE> elements,
125         EquivalenceComparator<? super EE, ? super CC> aEqComparator,
126         CC aContext)
127     {
128         ArrayList<EquivalenceSet<? super EE, ? super CC>> arrayList =
129             new ArrayList<EquivalenceSet<? super EE, ? super CC>>();
130
131         HashMap<Integer JavaDoc, List<EquivalenceSet<? super EE, ? super CC>>> map =
132             createEqualityGroupMap(elements, aEqComparator, aContext);
133         // each of the map values is a list with one or more groups in it.
134 // Object[] array = map.values().toArray();
135 // for (int i = 0; i < array.length; i++)
136 // {
137 // List list = (List)array[i];
138
139         for (List<EquivalenceSet<? super EE, ? super CC>> list : map.values()) {
140             for (EquivalenceSet<? super EE, ? super CC> eSet : list) {
141                 arrayList.add(eSet);
142             }
143         }
144
145         // now we got all the eq. groups in an array list. we need to sort
146 // them
147 EquivalenceSet [] resultArray = new EquivalenceSet [arrayList.size()];
148         arrayList.toArray(resultArray);
149         Arrays.sort(resultArray, groupSizeComparator);
150         return resultArray;
151     }
152
153     /**
154      * The data structure we use to store groups is a map, where the key is
155      * eqGroupHashCode, and the value is list, containing one or more eqGroup
156      * which match this hash.
157      *
158      * @param elements
159      * @param aEqComparator
160      *
161      * @return a hashmap with key=group hashcode , value = list of eq.groups
162      * which match that hash. TODO hb 060208: Using an array for
163      * aElementsArray causes problems with generics elsewhere - change
164      * to List?
165      */
166     private static <EE, CC> HashMap<Integer JavaDoc, List<EquivalenceSet<? super EE, ? super CC>>>
167     createEqualityGroupMap(
168         Collection<EE> elements,
169         EquivalenceComparator<? super EE, ? super CC> aEqComparator,
170         CC aComparatorContext)
171     {
172         HashMap<Integer JavaDoc, List<EquivalenceSet<? super EE, ? super CC>>> equalityGroupMap =
173             new HashMap<Integer JavaDoc, List<EquivalenceSet<? super EE, ? super CC>>>(
174                 elements.size());
175
176         for (EE curentElement : elements) {
177             int hashcode =
178                 aEqComparator.equivalenceHashcode(
179                     curentElement,
180                     aComparatorContext);
181             List<EquivalenceSet<? super EE, ? super CC>> list =
182                 equalityGroupMap.get(Integer.valueOf(hashcode));
183
184             // determine the type of value. It can be null(no value yet) ,
185 // or a list of EquivalenceSet
186
187             if (list == null) {
188                 // create list with one element in it
189 list = new LinkedList<EquivalenceSet<? super EE, ? super CC>>();
190                 list.add(
191                     new EquivalenceSet<EE, CC>(
192                         curentElement,
193                         aEqComparator,
194                         aComparatorContext));
195
196                 // This is the first one .add it to the map , in an eqGroup
197 equalityGroupMap.put(Integer.valueOf(hashcode), list);
198             } else {
199                 boolean eqWasFound = false;
200
201                 // we need to check the groups in the list. If none are good,
202 // create a new one
203 for (EquivalenceSet<? super EE, ? super CC> eqGroup : list) {
204                     if (
205                         eqGroup.equivalentTo(
206                             curentElement,
207                             aComparatorContext)) {
208                         // add it to the list and break
209 eqGroup.add(curentElement);
210                         eqWasFound = true;
211                         break;
212                     }
213                 }
214
215                 // if no match was found add it to the list as a new group
216 if (!eqWasFound) {
217                     list.add(
218                         new EquivalenceSet<EE, CC>(
219                             curentElement,
220                             aEqComparator,
221                             aComparatorContext));
222                 }
223             }
224         }
225
226         return equalityGroupMap;
227     }
228
229     //~ Inner Classes ---------------------------------------------------------
230
231     /**
232      * Functor used to order groups by size (number of elements in the group)
233      * from the smallest to the biggest. If they have the same size, uses the
234      * hashcode of the group to compare from the smallest to the biggest. Note
235      * that it is inconsistent with equals(). See Object.equals() javadoc.
236      *
237      * @author Assaf
238      * @since Jul 22, 2005
239      */
240     private static class EqGroupSizeComparator
241         implements Comparator<EquivalenceSet>
242     {
243         /**
244          * compare by size , then (if size equal) by hashcode
245          *
246          * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
247          */
248         @SuppressWarnings JavaDoc("unchecked")
249         public int compare(EquivalenceSet arg1, EquivalenceSet arg2)
250         {
251             int eqGroupSize1 = arg1.size();
252             int eqGroupSize2 = arg2.size();
253             if (eqGroupSize1 > eqGroupSize2) {
254                 return 1;
255             } else if (eqGroupSize1 < eqGroupSize2) {
256                 return -1;
257             } else { // size equal , compare hashcodes
258 int eqGroupHash1 = arg1.hashCode();
259                 int eqGroupHash2 = arg2.hashCode();
260                 if (eqGroupHash1 > eqGroupHash2) {
261                     return 1;
262                 } else if (eqGroupHash1 < eqGroupHash2) {
263                     return -1;
264                 } else {
265                     return 0;
266                 }
267             }
268         }
269     }
270 }
271
Popular Tags