Logo
Distributed Genetic Programming Framework
print print

File org.jfree.base.modules.PackageSorter.java

Here you can find all the information about the file org.jfree.base.modules.PackageSorter.java. You may explore it here or download it onto your local disk.
/* ========================================================================
 * JCommon : a free general purpose class library for the Java(tm) platform
 * ========================================================================
 *
 * (C) Copyright 2000-2005, by Object Refinery Limited and Contributors.
 * 
 * Project Info:  http://www.jfree.org/jcommon/index.html
 *
 * This library is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU Lesser General Public License as published by 
 * the Free Software Foundation; either version 2.1 of the License, or 
 * (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but 
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, 
 * USA.  
 *
 * [Java is a trademark or registered trademark of Sun Microsystems, Inc. 
 * in the United States and other countries.]
 * 
 * ------------------
 * PackageSorter.java
 * ------------------
 * (C)opyright 2003, 2004, by Thomas Morgner and Contributors.
 *
 * Original Author:  Thomas Morgner;
 * Contributor(s):   David Gilbert (for Object Refinery Limited);
 *
 * $Id: PackageSorter.java,v 1.2 2005/10/18 13:14:50 mungady Exp $
 *
 * Changes
 * -------
 * 02-Sep-2003 : Initial version
 * 07-Jun-2004 : Added JCommon header (DG);
 * 
 */


package org.jfree.base.modules;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;

import org.jfree.util.Log;

/**
 * Compares two modules for order. A module is considered less than an other
 * module if the module is a required module of the compared module. Modules
 * are considered equal if they have no relation.
 * <p>
 * When sorting, we match this modules position against all dependent
 * modules until all positions are stable. Circular references are evil
 * and are filtered during the module loading process in the package manager. 
 *
 * @author Thomas Morgner
 */

public final class PackageSorter
{
  /**
   * An Internal wrapper class which collects additional information
   * on the given module. Every module has a position, which is heigher
   * than the position of all dependent modules.
   * 
   * @author Thomas Morgner
   */

  private static class SortModule implements Comparable
  {
    /** stores the relative position of the module in the global list. */ 
    private int position;
    /** The package state of the to be matched module. */
    private final PackageState state;
    /** A list of all directly dependent subsystems. */
    private ArrayList dependSubsystems;
    // direct dependencies, indirect ones are handled by the
    // dependent classes ...

    /**
     * Creates a new SortModule for the given package state. 
     * 
     * @param state the package state object, that should be wrapped up
     * by this class. 
     */

    public SortModule(final PackageState state)
    {
      this.position = -1;
      this.state = state;
    }

    /**
     * Returns the list of all dependent subsystems. The list gets defined
     * when the sorting is started.
     * 
     * @return the list of all dependent subsystems.
     */

    public ArrayList getDependSubsystems()
    {
      return this.dependSubsystems;
    }

    /**
     * Defines a list of dependent subsystems for this module. The list contains
     * the names of the dependent subsystems as strings.
     * 
     * @param dependSubsystems a list of all dependent subsystems. 
     */

    public void setDependSubsystems(final ArrayList dependSubsystems)
    {
      this.dependSubsystems = dependSubsystems;
    }

    /**
     * Returns the current position of this module in the global list.
     * The position is computed by comparing all positions of all dependent
     * subsystem modules.
     * 
     * @return the current module position.
     */

    public int getPosition()
    {
      return this.position;
    }

    /**
     * Defines the position of this module in the global list of all
     * known modules.
     * 
     * @param position the position.
     */

    public void setPosition(final int position)
    {
      this.position = position;
    }

    /**
     * Returns the package state contained in this SortModule.
     * 
     * @return the package state of this module.
     */

    public PackageState getState()
    {
      return this.state;
    }

    /**
     * Returns a basic string representation of this SortModule. This
     * should be used for debugging purposes only. 
     * @see java.lang.Object#toString()
     * 
     * @return a string representation of this module.
     */

    public String toString ()
    {
      final StringBuffer buffer = new StringBuffer();
      buffer.append("SortModule: ");
      buffer.append(this.position);
      buffer.append(" ");
      buffer.append(this.state.getModule().getName());
      buffer.append(" ");
      buffer.append(this.state.getModule().getModuleClass());
      return buffer.toString();
    }

    /**
     * Compares this module against an other sort module.
     *  
     * @see java.lang.Comparable#compareTo(java.lang.Object)
     * 
     * @param o the other sort module instance.
     * @return -1 if the other's module position is less than
     * this modules position, +1 if this module is less than the
     * other module or 0 if both modules have an equal position in
     * the list.
     */

    public int compareTo(final Object o)
    {
      final SortModule otherModule = (SortModule) o;
      if (this.position > otherModule.position)
      {
        return +1;
      }
      if (this.position < otherModule.position)
      {
        return -1;
      }
      return 0;
    }
  }

  /**
   * DefaultConstructor.
   */

  private PackageSorter() {
      // nothing required.
  }

  /**
   * Sorts the given list of package states. The packages
   * are sorted by their dependencies in a way so that all
   * dependent packages are placed on lower positions than
   * the packages which declared the dependency. 
   *
   * @param modules the list of modules.
   */

  public static void sort (final List modules)
  {
    final HashMap moduleMap = new HashMap();
    final ArrayList errorModules = new ArrayList();
    final ArrayList weightModules = new ArrayList();

    for (int i = 0; i < modules.size(); i++)
    {
      final PackageState state = (PackageState) modules.get(i);
      if (state.getState() == PackageState.STATE_ERROR)
      {
        errorModules.add (state);
      }
      else
      {
        final SortModule mod = new SortModule(state);
        weightModules.add (mod);
        moduleMap.put(state.getModule().getModuleClass(), mod);
      }
    }

    final SortModule[] weigths = (SortModule[])
        weightModules.toArray(new SortModule[weightModules.size()]);

    for (int i = 0; i < weigths.length; i++)
    {
      final SortModule sortMod = weigths[i];
      sortMod.setDependSubsystems
          (collectSubsystemModules(sortMod.getState().getModule(),
              moduleMap));
    }


    // repeat the computation until all modules have a matching
    // position. This is not the best algorithm, but it works
    // and is relativly simple. It will need some optimizations
    // in the future, but as this is only executed once, we don't
    // have to care much about it.
    boolean doneWork = true;
    while (doneWork)
    {
      doneWork = false;
      for (int i = 0; i < weigths.length; i++)
      {
        final SortModule mod = weigths[i];
        final int position = searchModulePosition(mod, moduleMap);
        if (position != mod.getPosition())
        {
          mod.setPosition(position);
          doneWork = true;
        }
      }
    }

    Arrays.sort(weigths);
    modules.clear();
    for (int i = 0; i < weigths.length; i++)
    {
      modules.add (weigths[i].getState());
    }
    for (int i = 0; i < errorModules.size(); i++)
    {
      modules.add (errorModules.get(i));
    }
  }

  /**
   * Computes the new module position. This position is computed
   * according to the dependent modules and subsystems. The returned
   * position will be higher than the highest dependent module position.
   *
   * @param smodule the sort module for that we compute the new positon.
   * @param moduleMap the map with all modules.
   * @return the new positon.
   */

  private static int searchModulePosition
      (final SortModule smodule, final HashMap moduleMap)
  {
    final Module module = smodule.getState().getModule();
    int position = 0;

    // check the required modules. Increase our level to at least
    // one point over the highest dependent module
    // ignore missing modules.
    ModuleInfo[] modInfo = module.getOptionalModules();
    for (int modPos = 0; modPos < modInfo.length; modPos++)
    {
      final String moduleName = modInfo[modPos].getModuleClass();
      final SortModule reqMod = (SortModule) moduleMap.get(moduleName);
      if (reqMod == null)
      {
        continue;
      }
      if (reqMod.getPosition() >= position)
      {
        position = reqMod.getPosition() + 1;
      }
    }

    // check the required modules. Increase our level to at least
    // one point over the highest dependent module
    // there are no missing modules here (or the package manager
    // is invalid)
    modInfo = module.getRequiredModules();
    for (int modPos = 0; modPos < modInfo.length; modPos++)
    {
      final String moduleName = modInfo[modPos].getModuleClass();
      final SortModule reqMod = (SortModule) moduleMap.get(moduleName);
      if (reqMod.getPosition() >= position)
      {
        position = reqMod.getPosition() + 1;
      }
    }

    // check the subsystem dependencies. This way we make sure
    // that subsystems are fully initialized before we try to use
    // them.
    final String subSystem = module.getSubSystem();
    final Iterator it = moduleMap.values().iterator();
    while (it.hasNext())
    {
      final SortModule mod = (SortModule) it.next();
      // it is evil to compute values on ourself...
      if (mod.getState().getModule() == module)
      {
        // same module ...
        continue;
      }
      final Module subSysMod = mod.getState().getModule();
      // if the module we check is part of the same subsystem as
      // we are, then we dont do anything. Within the same subsystem
      // the dependencies are computed solely by the direct references.
      if (subSystem.equals(subSysMod.getSubSystem()))
      {
        // same subsystem ... ignore
        continue;
      }

      // does the module from the global list <mod> depend on the
      // subsystem we are part of?
      //
      // if yes, we have a relation and may need to adjust the level...
      if (smodule.getDependSubsystems().contains(subSysMod.getSubSystem()))
      {
        // check whether the module is a base module of the given
        // subsystem. We will not adjust our position in that case,
        // as this would lead to an infinite loop
        if (isBaseModule(subSysMod, module) == false)
        {
          if (mod.getPosition() >= position)
          {
            position = mod.getPosition() + 1;
          }
        }
      }
    }
    return position;
  }

  /**
   * Checks, whether a module is a base module of an given module.
   *
   * @param mod the module which to check
   * @param mi the module info of the suspected base module.
   * @return true, if the given module info describes a base module of the
   * given module, false otherwise.
   */

  private static boolean isBaseModule(final Module mod, final ModuleInfo mi)
  {
    ModuleInfo[] info = mod.getRequiredModules();
    for (int i = 0; i < info.length; i++)
    {
      if (info[i].getModuleClass().equals(mi.getModuleClass()))
      {
        return true;
      }
    }
    info = mod.getOptionalModules();
    for (int i = 0; i < info.length; i++)
    {
      if (info[i].getModuleClass().equals(mi.getModuleClass()))
      {
        return true;
      }
    }
    return false;
  }


  /**
   * Collects all directly dependent subsystems.
   *
   * @param childMod the module which to check
   * @param moduleMap the map of all other modules, keyed by module class.
   * @return the list of all dependent subsystems.
   */

  private static ArrayList collectSubsystemModules
      (final Module childMod, final HashMap moduleMap)
  {
    final ArrayList collector = new ArrayList();
    ModuleInfo[] info = childMod.getRequiredModules();
    for (int i = 0; i < info.length; i++)
    {
      final SortModule dependentModule = (SortModule)
          moduleMap.get(info[i].getModuleClass());
      if (dependentModule == null)
      {
        Log.warn 
          (new Log.SimpleMessage
            ("A dependent module was not found in the list of known modules.",
            info[i].getModuleClass()));
        continue;
      }

      collector.add (dependentModule.getState().getModule().getSubSystem());
    }

    info = childMod.getOptionalModules();
    for (int i = 0; i < info.length; i++)
    {
      final Module dependentModule = (Module)
          moduleMap.get(info[i].getModuleClass());
      if (dependentModule == null)
      {
        Log.warn ("A dependent module was not found in the list of known modules.");
        continue;
      }
      collector.add (dependentModule.getSubSystem());
    }
    return collector;
  }
}

File Information:

file name:PackageSorter.java
package:org.jfree.base.modules
qualified name:org.jfree.base.modules.PackageSorter.java
file type:Java Source File
download location:download http://dgpf.sourceforge.net/source/org/jfree/base/modules/PackageSorter.java
size:13.862 KB (14195 B)
uploaded: 2015-07-22 04:11:00 GMT+0000
last update: 2006-09-26 10:30:32 GMT+0000
last access: 2017-11-19 04:39:24 GMT+0000

statistics online since 2006-01-02.   RSS Feed
Contact us by sending an email to tweise@gmx.de to receive further information, to report errors, or to join our project.
All content on this site (http://dgpf.sourceforge.net/) is LGPL-licensed.
http://dgpf.sourceforge.net/scripts/source/source.php last modified at 2015-07-22 04:10:53 GMT+0000 served at 2017-11-19 04:39:24 GMT+0000.
Valid CSS Valid XHTML 1.1
Valid RSS SourceForge.net Logo