1 /**********************************************************************
2  * Copyright (c) 2008, 2014 Technical University Berlin, Germany and others.
3  *
4  * This program and the accompanying materials
5  * are made available under the terms of the Eclipse Public License 2.0
6  * which accompanies this distribution, and is available at
7  * https://www.eclipse.org/legal/epl-2.0/
8  *
9  * SPDX-License-Identifier: EPL-2.0
10  *
11  * Contributors:
12  *		Stephan Herrmann - Initial API and implementation
13  **********************************************************************/
14 package org.eclipse.jdt.internal.compiler.util;
15 
16 import java.util.Arrays;
17 import java.util.Comparator;
18 
19 import org.eclipse.jdt.internal.compiler.lookup.InferenceVariable;
20 import org.eclipse.jdt.internal.compiler.lookup.MethodBinding;
21 import org.eclipse.jdt.internal.compiler.lookup.ReferenceBinding;
22 import org.eclipse.jdt.internal.compiler.lookup.TypeBinding;
23 import org.eclipse.jdt.internal.compiler.lookup.TypeIds;
24 
25 /**
26  * Sorting utilities.
27  * Originally developed for the <a href="http://www.eclipse.org/objectteams">Object Teams project</a>.
28  */
29 public class Sorting {
30 
31 	/**
32 	 * Topological sort for types
33 	 * Guarantee: supertypes come before subtypes.
34 	 */
sortTypes(ReferenceBinding[] types)35 	public static ReferenceBinding[] sortTypes(ReferenceBinding[] types) {
36 		int len = types.length;
37 
38 		ReferenceBinding[] unsorted = new ReferenceBinding[len];
39 		ReferenceBinding[] sorted = new ReferenceBinding[len];
40 		System.arraycopy(types, 0, unsorted, 0, len);
41 
42 		int o = 0;
43 		for(int i=0; i<len; i++)
44 			o = sort(unsorted, i, sorted, o);
45 
46 		return sorted;
47 	}
48 	// Transfer input[i] and all its supers into output[o] ff.
sort(ReferenceBinding[] input, int i, ReferenceBinding[] output, int o)49 	private static int sort(ReferenceBinding[] input, int i,
50 							ReferenceBinding[] output, int o)
51 	{
52 		if (input[i] == null)
53 			return o;
54 
55 		ReferenceBinding superclass = input[i].superclass();
56 		o = sortSuper(superclass, input, output, o);
57 
58 		ReferenceBinding[] superInterfaces = input[i].superInterfaces();
59 		for (int j=0; j<superInterfaces.length; j++) {
60 			o = sortSuper(superInterfaces[j], input, output, o);
61 		}
62 
63 		// done with supers, now input[i] can safely be transferred:
64 		output[o++] = input[i];
65 		input[i] = null;
66 
67 		return o;
68 	}
69 	// if superclass is within the set of types to sort,
70 	// transfer it and all its supers to output[o] ff.
sortSuper(ReferenceBinding superclass, ReferenceBinding[] input, ReferenceBinding[] output, int o)71 	private static int sortSuper(ReferenceBinding superclass,
72 						  		 ReferenceBinding[] input,
73 						  		 ReferenceBinding[] output, int o)
74 	{
75 		if (superclass.id != TypeIds.T_JavaLangObject) {
76 			// search superclass within input:
77 			int j = 0;
78 			for(j=0; j<input.length; j++)
79 				if (TypeBinding.equalsEquals(input[j], superclass))
80 					break;
81 			if (j < input.length)
82 				// depth first traversal:
83 				o = sort(input, j, output, o);
84 			// otherwise assume super was already transferred.
85 		}
86 		return o;
87 	}
concreteFirst(MethodBinding[] methods, int length)88 	public static MethodBinding[] concreteFirst(MethodBinding[] methods, int length) {
89 		if (length == 0 || (length > 0 && !methods[0].isAbstract()))
90 			return methods;
91 		MethodBinding[] copy = new MethodBinding[length];
92 		int idx = 0;
93 		for (int i=0; i<length; i++)
94 			if (!methods[i].isAbstract())
95 				copy[idx++] = methods[i];
96 		for (int i=0; i<length; i++)
97 			if (methods[i].isAbstract())
98 				copy[idx++] = methods[i];
99 		return copy;
100 	}
abstractFirst(MethodBinding[] methods, int length)101 	public static MethodBinding[] abstractFirst(MethodBinding[] methods, int length) {
102 		if (length == 0 || (length > 0 && methods[0].isAbstract()))
103 			return methods;
104 		MethodBinding[] copy = new MethodBinding[length];
105 		int idx = 0;
106 		for (int i=0; i<length; i++)
107 			if (methods[i].isAbstract())
108 				copy[idx++] = methods[i];
109 		for (int i=0; i<length; i++)
110 			if (!methods[i].isAbstract())
111 				copy[idx++] = methods[i];
112 		return copy;
113 	}
114 
115 	/** Sort inference variables by rank. */
sortInferenceVariables(InferenceVariable[] variables)116 	public static void sortInferenceVariables(InferenceVariable[] variables) {
117 		Arrays.sort(variables, new Comparator<InferenceVariable>() {
118 			@Override
119 			public int compare(InferenceVariable iv1, InferenceVariable iv2) {
120 				return iv1.rank - iv2.rank;
121 			}
122 		});
123 	}
124 }
125