PackageSorter


1   /* ========================================================================
2    * JCommon : a free general purpose class library for the Java(tm) platform
3    * ========================================================================
4    *
5    * (C) Copyright 2000-2005, by Object Refinery Limited and Contributors.
6    * 
7    * Project Info:  http://www.jfree.org/jcommon/index.html
8    *
9    * This library is free software; you can redistribute it and/or modify it 
10   * under the terms of the GNU Lesser General Public License as published by 
11   * the Free Software Foundation; either version 2.1 of the License, or 
12   * (at your option) any later version.
13   *
14   * This library is distributed in the hope that it will be useful, but 
15   * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
16   * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 
17   * License for more details.
18   *
19   * You should have received a copy of the GNU Lesser General Public
20   * License along with this library; if not, write to the Free Software
21   * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, 
22   * USA.  
23   *
24   * [Java is a trademark or registered trademark of Sun Microsystems, Inc. 
25   * in the United States and other countries.]
26   * 
27   * ------------------
28   * PackageSorter.java
29   * ------------------
30   * (C)opyright 2003, 2004, by Thomas Morgner and Contributors.
31   *
32   * Original Author:  Thomas Morgner;
33   * Contributor(s):   David Gilbert (for Object Refinery Limited);
34   *
35   * $Id: PackageSorter.java,v 1.2 2005/10/18 13:14:50 mungady Exp $
36   *
37   * Changes
38   * -------
39   * 02-Sep-2003 : Initial version
40   * 07-Jun-2004 : Added JCommon header (DG);
41   * 
42   */
43  
44  package org.jfree.base.modules;
45  
46  import java.util.ArrayList  ;
47  import java.util.Arrays  ;
48  import java.util.HashMap  ;
49  import java.util.Iterator  ;
50  import java.util.List  ;
51  
52  import org.jfree.util.Log;
53  
54  /**
55   * Compares two modules for order. A module is considered less than an other
56   * module if the module is a required module of the compared module. Modules
57   * are considered equal if they have no relation.
58   * <p>
59   * When sorting, we match this modules position against all dependent
60   * modules until all positions are stable. Circular references are evil
61   * and are filtered during the module loading process in the package manager. 
62   *
63   * @author Thomas Morgner
64   */
65  public final class PackageSorter
66  {
67    /**
68     * An Internal wrapper class which collects additional information
69     * on the given module. Every module has a position, which is heigher
70     * than the position of all dependent modules.
71     * 
72     * @author Thomas Morgner
73     */
74    private static class SortModule implements Comparable  
75    {
76      /** stores the relative position of the module in the global list. */ 
77      private int position;
78      /** The package state of the to be matched module. */
79      private final PackageState state;
80      /** A list of all directly dependent subsystems. */
81      private ArrayList   dependSubsystems;
82      // direct dependencies, indirect ones are handled by the
83      // dependent classes ...
84  
85      /**
86       * Creates a new SortModule for the given package state. 
87       * 
88       * @param state the package state object, that should be wrapped up
89       * by this class. 
90       */
91      public SortModule(final PackageState state)
92      {
93        this.position = -1;
94        this.state = state;
95      }
96  
97      /**
98       * Returns the list of all dependent subsystems. The list gets defined
99       * when the sorting is started.
100      * 
101      * @return the list of all dependent subsystems.
102      */
103     public ArrayList   getDependSubsystems()
104     {
105       return this.dependSubsystems;
106     }
107 
108     /**
109      * Defines a list of dependent subsystems for this module. The list contains
110      * the names of the dependent subsystems as strings.
111      * 
112      * @param dependSubsystems a list of all dependent subsystems. 
113      */
114     public void setDependSubsystems(final ArrayList   dependSubsystems)
115     {
116       this.dependSubsystems = dependSubsystems;
117     }
118 
119     /**
120      * Returns the current position of this module in the global list.
121      * The position is computed by comparing all positions of all dependent
122      * subsystem modules.
123      * 
124      * @return the current module position.
125      */
126     public int getPosition()
127     {
128       return this.position;
129     }
130 
131     /**
132      * Defines the position of this module in the global list of all
133      * known modules.
134      * 
135      * @param position the position.
136      */
137     public void setPosition(final int position)
138     {
139       this.position = position;
140     }
141 
142     /**
143      * Returns the package state contained in this SortModule.
144      * 
145      * @return the package state of this module.
146      */
147     public PackageState getState()
148     {
149       return this.state;
150     }
151 
152     /**
153      * Returns a basic string representation of this SortModule. This
154      * should be used for debugging purposes only. 
155      * @see java.lang.Object#toString()
156      * 
157      * @return a string representation of this module.
158      */
159     public String   toString ()
160     {
161       final StringBuffer   buffer = new StringBuffer  ();
162       buffer.append("SortModule: ");
163       buffer.append(this.position);
164       buffer.append(" ");
165       buffer.append(this.state.getModule().getName());
166       buffer.append(" ");
167       buffer.append(this.state.getModule().getModuleClass());
168       return buffer.toString();
169     }
170 
171     /**
172      * Compares this module against an other sort module.
173      *  
174      * @see java.lang.Comparable#compareTo(java.lang.Object)
175      * 
176      * @param o the other sort module instance.
177      * @return -1 if the other's module position is less than
178      * this modules position, +1 if this module is less than the
179      * other module or 0 if both modules have an equal position in
180      * the list.
181      */
182     public int compareTo(final Object   o)
183     {
184       final SortModule otherModule = (SortModule) o;
185       if (this.position > otherModule.position)
186       {
187         return +1;
188       }
189       if (this.position < otherModule.position)
190       {
191         return -1;
192       }
193       return 0;
194     }
195   }
196 
197   /**
198    * DefaultConstructor.
199    */
200   private PackageSorter() {
201       // nothing required.
202   }
203 
204   /**
205    * Sorts the given list of package states. The packages
206    * are sorted by their dependencies in a way so that all
207    * dependent packages are placed on lower positions than
208    * the packages which declared the dependency. 
209    *
210    * @param modules the list of modules.
211    */
212   public static void sort (final List   modules)
213   {
214     final HashMap   moduleMap = new HashMap  ();
215     final ArrayList   errorModules = new ArrayList  ();
216     final ArrayList   weightModules = new ArrayList  ();
217 
218     for (int i = 0; i < modules.size(); i++)
219     {
220       final PackageState state = (PackageState) modules.get(i);
221       if (state.getState() == PackageState.STATE_ERROR)
222       {
223         errorModules.add (state);
224       }
225       else
226       {
227         final SortModule mod = new SortModule(state);
228         weightModules.add (mod);
229         moduleMap.put(state.getModule().getModuleClass(), mod);
230       }
231     }
232 
233     final SortModule[] weigths = (SortModule[])
234         weightModules.toArray(new SortModule[weightModules.size()]);
235 
236     for (int i = 0; i < weigths.length; i++)
237     {
238       final SortModule sortMod = weigths[i];
239       sortMod.setDependSubsystems
240           (collectSubsystemModules(sortMod.getState().getModule(),
241               moduleMap));
242     }
243 
244 
245     // repeat the computation until all modules have a matching
246     // position. This is not the best algorithm, but it works
247     // and is relativly simple. It will need some optimizations
248     // in the future, but as this is only executed once, we don't
249     // have to care much about it.
250     boolean doneWork = true;
251     while (doneWork)
252     {
253       doneWork = false;
254       for (int i = 0; i < weigths.length; i++)
255       {
256         final SortModule mod = weigths[i];
257         final int position = searchModulePosition(mod, moduleMap);
258         if (position != mod.getPosition())
259         {
260           mod.setPosition(position);
261           doneWork = true;
262         }
263       }
264     }
265 
266     Arrays.sort(weigths);
267     modules.clear();
268     for (int i = 0; i < weigths.length; i++)
269     {
270       modules.add (weigths[i].getState());
271     }
272     for (int i = 0; i < errorModules.size(); i++)
273     {
274       modules.add (errorModules.get(i));
275     }
276   }
277 
278   /**
279    * Computes the new module position. This position is computed
280    * according to the dependent modules and subsystems. The returned
281    * position will be higher than the highest dependent module position.
282    *
283    * @param smodule the sort module for that we compute the new positon.
284    * @param moduleMap the map with all modules.
285    * @return the new positon.
286    */
287   private static int searchModulePosition
288       (final SortModule smodule, final HashMap   moduleMap)
289   {
290     final Module module = smodule.getState().getModule();
291     int position = 0;
292 
293     // check the required modules. Increase our level to at least
294     // one point over the highest dependent module
295     // ignore missing modules.
296     ModuleInfo[] modInfo = module.getOptionalModules();
297     for (int modPos = 0; modPos < modInfo.length; modPos++)
298     {
299       final String   moduleName = modInfo[modPos].getModuleClass();
300       final SortModule reqMod = (SortModule) moduleMap.get(moduleName);
301       if (reqMod == null)
302       {
303         continue;
304       }
305       if (reqMod.getPosition() >= position)
306       {
307         position = reqMod.getPosition() + 1;
308       }
309     }
310 
311     // check the required modules. Increase our level to at least
312     // one point over the highest dependent module
313     // there are no missing modules here (or the package manager
314     // is invalid)
315     modInfo = module.getRequiredModules();
316     for (int modPos = 0; modPos < modInfo.length; modPos++)
317     {
318       final String   moduleName = modInfo[modPos].getModuleClass();
319       final SortModule reqMod = (SortModule) moduleMap.get(moduleName);
320       if (reqMod.getPosition() >= position)
321       {
322         position = reqMod.getPosition() + 1;
323       }
324     }
325 
326     // check the subsystem dependencies. This way we make sure
327     // that subsystems are fully initialized before we try to use
328     // them.
329     final String   subSystem = module.getSubSystem();
330     final Iterator   it = moduleMap.values().iterator();
331     while (it.hasNext())
332     {
333       final SortModule mod = (SortModule) it.next();
334       // it is evil to compute values on ourself...
335       if (mod.getState().getModule() == module)
336       {
337         // same module ...
338         continue;
339       }
340       final Module subSysMod = mod.getState().getModule();
341       // if the module we check is part of the same subsystem as
342       // we are, then we dont do anything. Within the same subsystem
343       // the dependencies are computed solely by the direct references.
344       if (subSystem.equals(subSysMod.getSubSystem()))
345       {
346         // same subsystem ... ignore
347         continue;
348       }
349 
350       // does the module from the global list <mod> depend on the
351       // subsystem we are part of?
352       //
353       // if yes, we have a relation and may need to adjust the level...
354       if (smodule.getDependSubsystems().contains(subSysMod.getSubSystem()))
355       {
356         // check whether the module is a base module of the given
357         // subsystem. We will not adjust our position in that case,
358         // as this would lead to an infinite loop
359         if (isBaseModule(subSysMod, module) == false)
360         {
361           if (mod.getPosition() >= position)
362           {
363             position = mod.getPosition() + 1;
364           }
365         }
366       }
367     }
368     return position;
369   }
370 
371   /**
372    * Checks, whether a module is a base module of an given module.
373    *
374    * @param mod the module which to check
375    * @param mi the module info of the suspected base module.
376    * @return true, if the given module info describes a base module of the
377    * given module, false otherwise.
378    */
379   private static boolean isBaseModule(final Module mod, final ModuleInfo mi)
380   {
381     ModuleInfo[] info = mod.getRequiredModules();
382     for (int i = 0; i < info.length; i++)
383     {
384       if (info[i].getModuleClass().equals(mi.getModuleClass()))
385       {
386         return true;
387       }
388     }
389     info = mod.getOptionalModules();
390     for (int i = 0; i < info.length; i++)
391     {
392       if (info[i].getModuleClass().equals(mi.getModuleClass()))
393       {
394         return true;
395       }
396     }
397     return false;
398   }
399 
400 
401   /**
402    * Collects all directly dependent subsystems.
403    *
404    * @param childMod the module which to check
405    * @param moduleMap the map of all other modules, keyed by module class.
406    * @return the list of all dependent subsystems.
407    */
408   private static ArrayList   collectSubsystemModules
409       (final Module childMod, final HashMap   moduleMap)
410   {
411     final ArrayList   collector = new ArrayList  ();
412     ModuleInfo[] info = childMod.getRequiredModules();
413     for (int i = 0; i < info.length; i++)
414     {
415       final SortModule dependentModule = (SortModule)
416           moduleMap.get(info[i].getModuleClass());
417       if (dependentModule == null)
418       {
419         Log.warn 
420           (new Log.SimpleMessage
421             ("A dependent module was not found in the list of known modules.",
422             info[i].getModuleClass()));
423         continue;
424       }
425 
426       collector.add (dependentModule.getState().getModule().getSubSystem());
427     }
428 
429     info = childMod.getOptionalModules();
430     for (int i = 0; i < info.length; i++)
431     {
432       final Module dependentModule = (Module)
433           moduleMap.get(info[i].getModuleClass());
434       if (dependentModule == null)
435       {
436         Log.warn ("A dependent module was not found in the list of known modules.");
437         continue;
438       }
439       collector.add (dependentModule.getSubSystem());
440     }
441     return collector;
442   }
443 }
444
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags