001: /* ========================================================================
002: * JCommon : a free general purpose class library for the Java(tm) platform
003: * ========================================================================
004: *
005: * (C) Copyright 2000-2005, by Object Refinery Limited and Contributors.
006: *
007: * Project Info: http://www.jfree.org/jcommon/index.html
008: *
009: * This library is free software; you can redistribute it and/or modify it
010: * under the terms of the GNU Lesser General Public License as published by
011: * the Free Software Foundation; either version 2.1 of the License, or
012: * (at your option) any later version.
013: *
014: * This library is distributed in the hope that it will be useful, but
015: * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
016: * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
017: * License for more details.
018: *
019: * You should have received a copy of the GNU Lesser General Public
020: * License along with this library; if not, write to the Free Software
021: * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
022: * USA.
023: *
024: * [Java is a trademark or registered trademark of Sun Microsystems, Inc.
025: * in the United States and other countries.]
026: *
027: * ------------------
028: * PackageSorter.java
029: * ------------------
030: * (C)opyright 2003, 2004, by Thomas Morgner and Contributors.
031: *
032: * Original Author: Thomas Morgner;
033: * Contributor(s): David Gilbert (for Object Refinery Limited);
034: *
035: * $Id: PackageSorter.java,v 1.3 2007/05/15 12:32:15 taqua Exp $
036: *
037: * Changes
038: * -------
039: * 02-Sep-2003 : Initial version
040: * 07-Jun-2004 : Added JCommon header (DG);
041: *
042: */
043:
044: package org.jfree.base.modules;
045:
046: import java.util.ArrayList;
047: import java.util.Arrays;
048: import java.util.HashMap;
049: import java.util.Iterator;
050: import java.util.List;
051:
052: import org.jfree.util.Log;
053:
054: /**
055: * Compares two modules for order. A module is considered less than an other
056: * module if the module is a required module of the compared module. Modules
057: * are considered equal if they have no relation.
058: * <p>
059: * When sorting, we match this modules position against all dependent
060: * modules until all positions are stable. Circular references are evil
061: * and are filtered during the module loading process in the package manager.
062: *
063: * @author Thomas Morgner
064: */
065: public final class PackageSorter {
066: /**
067: * An Internal wrapper class which collects additional information
068: * on the given module. Every module has a position, which is heigher
069: * than the position of all dependent modules.
070: *
071: * @author Thomas Morgner
072: */
073: private static class SortModule implements Comparable {
074: /** stores the relative position of the module in the global list. */
075: private int position;
076: /** The package state of the to be matched module. */
077: private final PackageState state;
078: /** A list of all directly dependent subsystems. */
079: private ArrayList dependSubsystems;
080:
081: // direct dependencies, indirect ones are handled by the
082: // dependent classes ...
083:
084: /**
085: * Creates a new SortModule for the given package state.
086: *
087: * @param state the package state object, that should be wrapped up
088: * by this class.
089: */
090: public SortModule(final PackageState state) {
091: this .position = -1;
092: this .state = state;
093: }
094:
095: /**
096: * Returns the list of all dependent subsystems. The list gets defined
097: * when the sorting is started.
098: *
099: * @return the list of all dependent subsystems.
100: */
101: public ArrayList getDependSubsystems() {
102: return this .dependSubsystems;
103: }
104:
105: /**
106: * Defines a list of dependent subsystems for this module. The list contains
107: * the names of the dependent subsystems as strings.
108: *
109: * @param dependSubsystems a list of all dependent subsystems.
110: */
111: public void setDependSubsystems(final ArrayList dependSubsystems) {
112: this .dependSubsystems = dependSubsystems;
113: }
114:
115: /**
116: * Returns the current position of this module in the global list.
117: * The position is computed by comparing all positions of all dependent
118: * subsystem modules.
119: *
120: * @return the current module position.
121: */
122: public int getPosition() {
123: return this .position;
124: }
125:
126: /**
127: * Defines the position of this module in the global list of all
128: * known modules.
129: *
130: * @param position the position.
131: */
132: public void setPosition(final int position) {
133: this .position = position;
134: }
135:
136: /**
137: * Returns the package state contained in this SortModule.
138: *
139: * @return the package state of this module.
140: */
141: public PackageState getState() {
142: return this .state;
143: }
144:
145: /**
146: * Returns a basic string representation of this SortModule. This
147: * should be used for debugging purposes only.
148: * @see java.lang.Object#toString()
149: *
150: * @return a string representation of this module.
151: */
152: public String toString() {
153: final StringBuffer buffer = new StringBuffer();
154: buffer.append("SortModule: ");
155: buffer.append(this .position);
156: buffer.append(" ");
157: buffer.append(this .state.getModule().getName());
158: buffer.append(" ");
159: buffer.append(this .state.getModule().getModuleClass());
160: return buffer.toString();
161: }
162:
163: /**
164: * Compares this module against an other sort module.
165: *
166: * @see java.lang.Comparable#compareTo(java.lang.Object)
167: *
168: * @param o the other sort module instance.
169: * @return -1 if the other's module position is less than
170: * this modules position, +1 if this module is less than the
171: * other module or 0 if both modules have an equal position in
172: * the list.
173: */
174: public int compareTo(final Object o) {
175: final SortModule otherModule = (SortModule) o;
176: if (this .position > otherModule.position) {
177: return +1;
178: }
179: if (this .position < otherModule.position) {
180: return -1;
181: }
182: return 0;
183: }
184: }
185:
186: /**
187: * DefaultConstructor.
188: */
189: private PackageSorter() {
190: // nothing required.
191: }
192:
193: /**
194: * Sorts the given list of package states. The packages
195: * are sorted by their dependencies in a way so that all
196: * dependent packages are placed on lower positions than
197: * the packages which declared the dependency.
198: *
199: * @param modules the list of modules.
200: */
201: public static void sort(final List modules) {
202: final HashMap moduleMap = new HashMap();
203: final ArrayList errorModules = new ArrayList();
204: final ArrayList weightModules = new ArrayList();
205:
206: for (int i = 0; i < modules.size(); i++) {
207: final PackageState state = (PackageState) modules.get(i);
208: if (state.getState() == PackageState.STATE_ERROR) {
209: errorModules.add(state);
210: } else {
211: final SortModule mod = new SortModule(state);
212: weightModules.add(mod);
213: moduleMap.put(state.getModule().getModuleClass(), mod);
214: }
215: }
216:
217: final SortModule[] weigths = (SortModule[]) weightModules
218: .toArray(new SortModule[weightModules.size()]);
219:
220: for (int i = 0; i < weigths.length; i++) {
221: final SortModule sortMod = weigths[i];
222: sortMod.setDependSubsystems(collectSubsystemModules(sortMod
223: .getState().getModule(), moduleMap));
224: }
225:
226: // repeat the computation until all modules have a matching
227: // position. This is not the best algorithm, but it works
228: // and is relativly simple. It will need some optimizations
229: // in the future, but as this is only executed once, we don't
230: // have to care much about it.
231: boolean doneWork = true;
232: while (doneWork) {
233: doneWork = false;
234: for (int i = 0; i < weigths.length; i++) {
235: final SortModule mod = weigths[i];
236: final int position = searchModulePosition(mod,
237: moduleMap);
238: if (position != mod.getPosition()) {
239: mod.setPosition(position);
240: doneWork = true;
241: }
242: }
243: }
244:
245: Arrays.sort(weigths);
246: modules.clear();
247: for (int i = 0; i < weigths.length; i++) {
248: modules.add(weigths[i].getState());
249: }
250: for (int i = 0; i < errorModules.size(); i++) {
251: modules.add(errorModules.get(i));
252: }
253: }
254:
255: /**
256: * Computes the new module position. This position is computed
257: * according to the dependent modules and subsystems. The returned
258: * position will be higher than the highest dependent module position.
259: *
260: * @param smodule the sort module for that we compute the new positon.
261: * @param moduleMap the map with all modules.
262: * @return the new positon.
263: */
264: private static int searchModulePosition(final SortModule smodule,
265: final HashMap moduleMap) {
266: final Module module = smodule.getState().getModule();
267: int position = 0;
268:
269: // check the required modules. Increase our level to at least
270: // one point over the highest dependent module
271: // ignore missing modules.
272: ModuleInfo[] modInfo = module.getOptionalModules();
273: for (int modPos = 0; modPos < modInfo.length; modPos++) {
274: final String moduleName = modInfo[modPos].getModuleClass();
275: final SortModule reqMod = (SortModule) moduleMap
276: .get(moduleName);
277: if (reqMod == null) {
278: continue;
279: }
280: if (reqMod.getPosition() >= position) {
281: position = reqMod.getPosition() + 1;
282: }
283: }
284:
285: // check the required modules. Increase our level to at least
286: // one point over the highest dependent module
287: // there are no missing modules here (or the package manager
288: // is invalid)
289: modInfo = module.getRequiredModules();
290: for (int modPos = 0; modPos < modInfo.length; modPos++) {
291: final String moduleName = modInfo[modPos].getModuleClass();
292: final SortModule reqMod = (SortModule) moduleMap
293: .get(moduleName);
294: if (reqMod == null) {
295: Log.warn("Invalid state: Required dependency of '"
296: + moduleName + "' had an error.");
297: continue;
298: }
299: if (reqMod.getPosition() >= position) {
300: position = reqMod.getPosition() + 1;
301: }
302: }
303:
304: // check the subsystem dependencies. This way we make sure
305: // that subsystems are fully initialized before we try to use
306: // them.
307: final String subSystem = module.getSubSystem();
308: final Iterator it = moduleMap.values().iterator();
309: while (it.hasNext()) {
310: final SortModule mod = (SortModule) it.next();
311: // it is evil to compute values on ourself...
312: if (mod.getState().getModule() == module) {
313: // same module ...
314: continue;
315: }
316: final Module subSysMod = mod.getState().getModule();
317: // if the module we check is part of the same subsystem as
318: // we are, then we dont do anything. Within the same subsystem
319: // the dependencies are computed solely by the direct references.
320: if (subSystem.equals(subSysMod.getSubSystem())) {
321: // same subsystem ... ignore
322: continue;
323: }
324:
325: // does the module from the global list <mod> depend on the
326: // subsystem we are part of?
327: //
328: // if yes, we have a relation and may need to adjust the level...
329: if (smodule.getDependSubsystems().contains(
330: subSysMod.getSubSystem())) {
331: // check whether the module is a base module of the given
332: // subsystem. We will not adjust our position in that case,
333: // as this would lead to an infinite loop
334: if (isBaseModule(subSysMod, module) == false) {
335: if (mod.getPosition() >= position) {
336: position = mod.getPosition() + 1;
337: }
338: }
339: }
340: }
341: return position;
342: }
343:
344: /**
345: * Checks, whether a module is a base module of an given module.
346: *
347: * @param mod the module which to check
348: * @param mi the module info of the suspected base module.
349: * @return true, if the given module info describes a base module of the
350: * given module, false otherwise.
351: */
352: private static boolean isBaseModule(final Module mod,
353: final ModuleInfo mi) {
354: ModuleInfo[] info = mod.getRequiredModules();
355: for (int i = 0; i < info.length; i++) {
356: if (info[i].getModuleClass().equals(mi.getModuleClass())) {
357: return true;
358: }
359: }
360: info = mod.getOptionalModules();
361: for (int i = 0; i < info.length; i++) {
362: if (info[i].getModuleClass().equals(mi.getModuleClass())) {
363: return true;
364: }
365: }
366: return false;
367: }
368:
369: /**
370: * Collects all directly dependent subsystems.
371: *
372: * @param childMod the module which to check
373: * @param moduleMap the map of all other modules, keyed by module class.
374: * @return the list of all dependent subsystems.
375: */
376: private static ArrayList collectSubsystemModules(
377: final Module childMod, final HashMap moduleMap) {
378: final ArrayList collector = new ArrayList();
379: ModuleInfo[] info = childMod.getRequiredModules();
380: for (int i = 0; i < info.length; i++) {
381: final SortModule dependentModule = (SortModule) moduleMap
382: .get(info[i].getModuleClass());
383: if (dependentModule == null) {
384: Log
385: .warn(new Log.SimpleMessage(
386: "A dependent module was not found in the list of known modules.",
387: info[i].getModuleClass()));
388: continue;
389: }
390:
391: collector.add(dependentModule.getState().getModule()
392: .getSubSystem());
393: }
394:
395: info = childMod.getOptionalModules();
396: for (int i = 0; i < info.length; i++) {
397: final Module dependentModule = (Module) moduleMap
398: .get(info[i].getModuleClass());
399: if (dependentModule == null) {
400: Log
401: .warn("A dependent module was not found in the list of known modules.");
402: continue;
403: }
404: collector.add(dependentModule.getSubSystem());
405: }
406: return collector;
407: }
408: }
|