ListTools


1   //The contents of this file are subject to the Mozilla Public License Version 1.1
2   //(the "License"); you may not use this file except in compliance with the 
3   //License. You may obtain a copy of the License at http://www.mozilla.org/MPL/
4   //
5   //Software distributed under the License is distributed on an "AS IS" basis,
6   //WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License 
7   //for the specific language governing rights and
8   //limitations under the License.
9   //
10  //The Original Code is "The Columba Project"
11  //
12  //The Initial Developers of the Original Code are Frederik Dietz and Timo Stich.
13  //Portions created by Frederik Dietz and Timo Stich are Copyright (C) 2003. 
14  //
15  //All Rights Reserved.
16  package org.columba.core.base;
17  
18  import java.util.Collections  ;
19  import java.util.Iterator  ;
20  import java.util.List  ;
21  import java.util.ListIterator  ;
22  
23  /**
24   * @author timo
25   * 
26   * To change this generated comment edit the template variable "typecomment":
27   * Window>Preferences>Java>Templates. To enable and disable the creation of type
28   * comments go to Window>Preferences>Java>Code Generation.
29   */
30  public class ListTools {
31      /**
32           * Intersect two Lists that contain Objects that implement the
33           * Comparable Interface. The Result is in List a and sorted. Be aware
34           * that List b gets also sorted!
35           * 
36           * @param a
37           * @param b
38           */
39      public static void intersect(List   a, List   b) {
40      ListIterator   aIt;
41      ListIterator   bIt;
42  
43      if (a.size() == 0) {
44          return;
45      }
46  
47      if (b.size() == 0) {
48          a.clear();
49  
50          return;
51      }
52  
53      Collections.sort(a);
54      Collections.sort(b);
55  
56      aIt = a.listIterator();
57      bIt = b.listIterator();
58  
59      Comparable   aVal;
60      Comparable   bVal;
61  
62      aVal = (Comparable  ) aIt.next();
63      bVal = (Comparable  ) bIt.next();
64  
65      boolean loop = true;
66      int compareResult;
67  
68      while (loop) {
69          compareResult = aVal.compareTo(bVal);
70  
71          if (compareResult < 0) { // a < b
72          aIt.remove();
73  
74          if (aIt.hasNext()) {
75              aVal = (Comparable  ) aIt.next();
76          } else {
77              return;
78          }
79          } else if (compareResult == 0) { // a == b
80  
81          if (aIt.hasNext()) {
82              aVal = (Comparable  ) aIt.next();
83          } else {
84              loop = false;
85  
86              return;
87          }
88  
89          if (bIt.hasNext()) {
90              bVal = (Comparable  ) bIt.next();
91          } else {
92              loop = false;
93              aIt.remove();
94          }
95          } else { // a > b
96  
97          if (bIt.hasNext()) {
98              bVal = (Comparable  ) bIt.next();
99          } else {
100             loop = false;
101             aIt.remove();
102         }
103         }
104     }
105 
106     while (aIt.hasNext()) {
107         aIt.next();
108         aIt.remove();
109     }
110     }
111 
112     /**
113          * Subtracts two Lists in O(n * log n) that contain Objects that
114          * implement the Comparable Interface. The Result is in List a and
115          * sorted. Be aware that List b gets also sorted!
116          * 
117          * @param a
118          * @param b
119          */
120     public static void substract(List   a, List   b) {
121     ListIterator   aIt;
122     ListIterator   bIt;
123 
124     if ((a.size() == 0) || (b.size() == 0)) {
125         return;
126     }
127 
128     Collections.sort(a);
129     Collections.sort(b);
130 
131     aIt = a.listIterator();
132     bIt = b.listIterator();
133 
134     Comparable   aVal;
135     Comparable   bVal;
136 
137     aVal = (Comparable  ) aIt.next();
138     bVal = (Comparable  ) bIt.next();
139 
140     boolean loop = true;
141     int compareResult;
142 
143     while (loop) {
144         compareResult = aVal.compareTo(bVal);
145 
146         if (compareResult < 0) { // a < b
147 
148         if (aIt.hasNext()) {
149             aVal = (Comparable  ) aIt.next();
150         } else {
151             return;
152         }
153         } else if (compareResult == 0) { // a == b
154         aIt.remove();
155 
156         if (aIt.hasNext()) {
157             aVal = (Comparable  ) aIt.next();
158         } else {
159             return;
160         }
161 
162         if (bIt.hasNext()) {
163             bVal = (Comparable  ) bIt.next();
164         } else {
165             return;
166         }
167         } else { // a > b
168 
169         if (bIt.hasNext()) {
170             bVal = (Comparable  ) bIt.next();
171         } else {
172             return;
173         }
174         }
175     }
176     }
177 
178     /**
179          * Intersects to list in O(length(List a) * length(List b)). This is the
180          * a stable version (elements keep their oder). The elements in b will
181          * be removed from the list.
182          * 
183          * @param a
184          * @param b
185          */
186     public static void intersect_astable(List   a, List   b) {
187     if (a.size() == 0) {
188         return;
189     }
190 
191     if (b.size() == 0) {
192         a.clear();
193 
194         return;
195     }
196 
197     Iterator   ita = a.iterator();
198     Iterator   itb;
199     Object   acta;
200 
201     boolean found;
202 
203     while (ita.hasNext()) {
204         acta = ita.next();
205         itb = b.iterator();
206         found = false;
207 
208         while (itb.hasNext() && !found) {
209         found = acta.equals(itb.next());
210         }
211 
212         if (!found) {
213         ita.remove();
214         } else {
215         itb.remove();
216         }
217     }
218     }
219 }
220
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags