001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: *
017: */
018: package org.apache.ivy.core.sort;
019:
020: import java.util.ArrayList;
021: import java.util.Collection;
022: import java.util.Iterator;
023: import java.util.LinkedHashMap;
024: import java.util.List;
025: import java.util.Map;
026:
027: import org.apache.ivy.core.module.descriptor.ModuleDescriptor;
028: import org.apache.ivy.core.resolve.IvyNode;
029: import org.apache.ivy.plugins.circular.CircularDependencyException;
030: import org.apache.ivy.plugins.circular.CircularDependencyStrategy;
031: import org.apache.ivy.plugins.version.VersionMatcher;
032:
033: public class SortEngine {
034:
035: private SortEngineSettings settings;
036:
037: public SortEngine(SortEngineSettings settings) {
038: if (settings == null) {
039: throw new NullPointerException(
040: "SortEngine.settings can not be null");
041: }
042: this .settings = settings;
043: }
044:
045: public List sortNodes(Collection nodes)
046: throws CircularDependencyException {
047: /*
048: * here we want to use the sort algorithm which work on module descriptors : so we first put
049: * dependencies on a map from descriptors to dependency, then we sort the keySet (i.e. a
050: * collection of descriptors), then we replace in the sorted list each descriptor by the
051: * corresponding dependency
052: */
053:
054: Map dependenciesMap = new LinkedHashMap();
055: List nulls = new ArrayList();
056: for (Iterator iter = nodes.iterator(); iter.hasNext();) {
057: IvyNode node = (IvyNode) iter.next();
058: if (node.getDescriptor() == null) {
059: nulls.add(node);
060: } else {
061: List n = (List) dependenciesMap.get(node
062: .getDescriptor());
063: if (n == null) {
064: n = new ArrayList();
065: dependenciesMap.put(node.getDescriptor(), n);
066: }
067: n.add(node);
068: }
069: }
070: List list = sortModuleDescriptors(dependenciesMap.keySet(),
071: new SilentNonMatchingVersionReporter());
072: final double adjustFactor = 1.3;
073: List ret = new ArrayList(
074: (int) (list.size() * adjustFactor + nulls.size()));
075: // attempt to adjust the size to avoid too much list resizing
076: for (int i = 0; i < list.size(); i++) {
077: ModuleDescriptor md = (ModuleDescriptor) list.get(i);
078: List n = (List) dependenciesMap.get(md);
079: ret.addAll(n);
080: }
081: ret.addAll(0, nulls);
082: return ret;
083: }
084:
085: /**
086: * Sorts the given ModuleDescriptors from the less dependent to the more dependent. This sort
087: * ensures that a ModuleDescriptor is always found in the list before all ModuleDescriptors
088: * depending directly on it.
089: *
090: * @param moduleDescriptors
091: * a Collection of ModuleDescriptor to sort
092: * @param nonMatchingVersionReporter
093: * Used to report some non matching version (when a modules depends on a specific
094: * revision of an other modules present in the of modules to sort with a different
095: * revision.
096: * @return a List of sorted ModuleDescriptors
097: * @throws CircularDependencyException
098: * if a circular dependency exists
099: */
100: public List sortModuleDescriptors(Collection moduleDescriptors,
101: NonMatchingVersionReporter nonMatchingVersionReporter)
102: throws CircularDependencyException {
103: if (nonMatchingVersionReporter == null) {
104: throw new NullPointerException(
105: "nonMatchingVersionReporter can not be null");
106: }
107: ModuleDescriptorSorter sorter = new ModuleDescriptorSorter(
108: moduleDescriptors, getVersionMatcher(),
109: nonMatchingVersionReporter, getCircularStrategy());
110: return sorter.sortModuleDescriptors();
111: }
112:
113: protected CircularDependencyStrategy getCircularStrategy() {
114: return settings.getCircularDependencyStrategy();
115: }
116:
117: protected VersionMatcher getVersionMatcher() {
118: return settings.getVersionMatcher();
119: }
120:
121: }
|