Writing in the front
How well you know data structures determines how well you can do coding.
You might be surprised by the title, but AOP is starting to talk about sorting. Let me start with something that you’re all familiar with. Remember, what do we do if we want to add custom facets to a container? Two methods:
- We injected our custom Advisor into the container.
- Use @aspect to identify a class as the Aspect configuration class, and use @around, @before, @after, @AfterRETURNING, and @AfterThrowing to define the implementation of some aspects. Finally, inject the Aspect configuration class into the container.
The first method will be dissected later. The second method I think should be more commonly used. And what does this have to do with partial ordering?
Recall from the first article to understand one of AOP, interceptor chains we said that interceptor chains are List structures, and List structures are meant to be ordered. The @around, @before, @after, @Afterreturning, and @AfterThrowing we use will eventually be converted into MethodInterceptor and added to the interceptor chain. So what is the order of @around, @before, @after, @afterreturning, and @afterthrowing in the generated interceptor chain? Who’s first and who’s last? (The order has two meanings. The first is the order of @around, @before, @After, @afterreturning, and @afterthrowing in the same section configuration class. The second is to configure the order of @around, @before, @after, @afterreturning, @afterthrowing.
What is the specific order? I think we all know it when learning Spring, but how to realize this order is what we need to analyze. Knowing what is what, we need to know why. In this article, we will first talk about partial sorting. Based on understanding partial sorting, we will go into the application of partial sorting in AOP in the next article.
Partial order relation
What is the partial order relation? There are two ways to think about it. What is “relationship”? What is a partial order?
I’m going to start by cramming a little bit about discrete mathematics.
Relationship between
“Relation” is a very basic concept in numbers. What does relation look like from the point of view of sets?
Suppose set A={A,b,c, D,e,f}, and the elements in set A represent six people. A is the father of B and C, B is the father of D, and C is the father of E and F.
Then the two persons conforming to the parent-child relationship in the element of set A can be represented by ordered pairs (A,b), (A,c), (b,d), (c,e), (c,f). Then the set R={(a,b), (a, C), (b,d), (c,e), (c,f)} can completely describe the parent-child tube of the elements in the set A, and we call R a relation on the set A.
For another example, the less than relation on the set A={1,2,3} can be expressed as R={(1,2), (1,3), (2,3)}
Now let’s expand the number of sets to two
There are two sets A={A,b, C, D} and b ={x,y,z}. Where A represents four teachers A, B, C and D, x, Y and Z represent three courses: Chinese, mathematics and English. A and B are Chinese teachers, C is math teacher and D is English teacher. Then the set R={(a,x),(b,x),(c,y),(d,z)} represents the relationship between teachers and the courses they teach.
Representation of relation
How do we represent relationships?
1. Relational matrix
Given two sets A={a1,a2… The an} and B = {b1, b1… Bm}, R is the relationship between A and B, then called
It’s called the relational matrix of R. When (ai, bj) (a_i, b_j) (ai, bj) belong to the R, ci, j = 1 c_ {I, j} = 1 ci, j = 1 when (ai, bj) (a_i, b_j) (ai, bj) do not belong to the R, ci, j = 0 c_ {I, j} = 0 ci, j = 0
2. The diagram
Given two sets A={a1,a2… The an} and B = {b1, b1… Bm}, R is the relationship from A to B. I have n points on the plane representing the elements in A and m points representing the elements in B. If (ai,bj)(a_i,b_j)(ai, BJ) is a member of R, draw a directed edge from the points AIA_iai to bjb_jbj, with the arrow pointing to bjb_jbj, otherwise no edge.
Let’s take the example of the teacher and the course, and the corresponding diagram is:
Taking our example of the father-son relationship, the diagram can be expressed as follows:
3. Nature of the relationship
- Reflexivity: R is A binary relation on A. If for every element x in A, there is (x,x) belonging to R, R is said to be reflexive, and R is also said to have reflexivity.
Case 1: A = {A, b, c}, A binary relation R on = {(A, A), (b, b), (c, c), (A, c), (c, b)}, then R is reflexive binary relation. Example 2: set A = {1, 2, 3, 4}, A binary relation R on = {(1, 1), (2, 2), (3, 4), (4, 2)}, because three ∈ a. but (3, 3), so R is not on A reflexive relationship.
- Antireflexivity: R is A binary relation on A. If for every element X in A, there is (x,x) that does not belong to R, then R is said to be antireflexive, and R is also said to have antireflexivity.
Example 1: Let A={A,b,c},R={(A,c),(b, A),(b,c),(b,b)}. Since (b,b) is A member of R, R is not an antireflexive relation on A. Example 2: let A={1,2,3}, R is the less than relation on A, that is, R ={(1,2),(1,3),(2,3)}. Since (1,1),(2,2), and (3,3) do not belong to R, R is an antireflexive relation on A.
- Symmetry: R is A binary relation on A, every time (x,y) belongs to R, there must be (y,x) belongs to R, then R is said to be symmetric, also said to have symmetry.
Case 1: set A = {A, b, c}, R = {(A, b), (b, A), (A, c), (c, A)}, so R is symmetric. Example 2: set A = {1, 2, 3, 4} on the binary relation R = {(1, 1), (1, 2), (2, 1), (3.3), (4, 3), (4)}, because (4, 3) belong to R (3, 4) do not belong to. So R is not symmetric.
- Antisymmetry: R is defined as A binary relation on A. When x≠y, if (x,y) is A member of R, then (y,x) must not be A member of R. R is said to be antisymmetric and also called to have antisymmetry.
Example 1:A={1,2,3} R={(1,2),(2,2),(3,1)} then R is antisymmetric. But S={(1,2),(1,3),(2,2),(3,1)} is not antisymmetric. Because 1≠3 but (1,3) is a member of S, and (3,1) is a member of S.
Symmetric relation and antisymmetric relation are not two concepts that negate each other. There are binary relations that are both symmetric and antisymmetric, and there are binary relations that are neither symmetric nor antisymmetric. Set A = {A, b, c, d} on the relationship between R = {(A, A), (b, c), (c, d), (d, c)}, S = {(A, A), (b, b), (d, d)}. Then R is neither symmetric (because (b, C)∈R but (c,b)) nor anti-symmetric (because (c,d)∈R and (d, C)∈R) and S is both symmetric and anti-symmetric.Copy the code- Transitivity: Let R be A binary relation on A, every time (x,y) belongs to R and (y,z) belongs to R, there must be (x,z) belongs to R, then R is said to be transitive, also said to have transitivity.
After a new understanding of “relation”, let’s look at two kinds of relation, “partial order relation” and “full order relation”.
- Partial order relation: Let R be A relation on A non-empty set A. if R is reflexive, antisymmetric, and transitive, then R is said to be A partial order relation on A.
The set A and the partial order relation R on A are often collectively referred to as the partial order set, denoted by (A, R). Since partial order relation is reflexive, antisymmetric, transitive binary relation, the symbol “≤” is generally used to represent partial order.
The sign “≤” here should not be treated as less than or equal to. To avoid confusion with ≤ (less than or equal to), double quotation marks are used to indicate the partial order relationship. That is, ≤ indicates partial order.
Under partial order relation, when (a, b)∈R, it is often written as A “≤” B, and the partial order set is also often written as (a, “≤”). For example, the less than or equal relation, lexicographical order, divisible relation, and inclusion relation are partial order relations of corresponding sets.
A related concept to partial ordering is total ordering.
-
Total order relation: if R is A partial order relation on A, then for any set of A x,y, x “≤” y, or y “≤” x, then R is said to be A total order relation on A. In a total order relation, any two elements are related. Total order is also called linear order.
For example, in the set of integers, the greater than or equal relationship is linear order.
Given the textbook definition, how can we simply understand the partial order relation and the total order relation?
- A partial ordering relation indicates that only part of the elements of a set are comparable (local).
- A total ordering relation indicates that any pair of elements in a set are comparable to each other under this relation (globally).
- The total order relation is also a partial order relation.
Partial order sorting
Know partial order relation, partial order sort is very simple, according to partial order relation sort is partial order sort.
The sort that we say everyday is to refer to complete sort generally. For example, given an array [8,2,5,1,111,50,0], the array is ordered by fast sorting. We’re talking about full sort, and we’re talking about the size of two elements, because we think that any two elements in an array can be compared.
AOP and partial ordering
So much foreshadowing in front, I believe that we have a deeper understanding of sorting. Back to AOP, what is the application of partial ordering in AOP?
In our projects, @aspect is often used to define an Aspect configuration class, where @before, @around, and so on define various Aspect enhancements. We know that @Around, @before, @after, @afterreturning, and @Afterthrowing have different enhancement opportunities for specific join points. In order to ensure the correct enhancement sequence, it is required that the corresponding Advisor in the interceptor chain be in a certain order. What is the order in which the @Aspect defined section configuration classes are configured from one another?
For example, we use @aspect to define two Aspect configuration classes, LogAspectA and LogAspectB.
LogAspectA
@Component
@Aspect
public class LogAspectA {
@Before("execution(public * com.xyh.study.provider.spring.AOP. Section 1.*.*(..) )"
public void doBefore(JoinPoint joinPoint) {
System.out.println("A doBefore run...");
}
@After("execution(public * com.xyh.study.provider.spring.AOP. Section 1.*.*(..) )"
public void doAfter(JoinPoint joinPoint) {
System.out.println("A doAfter run...");
}
@AfterReturning(value = "execution(public * com.xyh.study.provider.spring.AOP. Section 1.*.*(..) )", returning = "result")
public void doAfterReturning(JoinPoint joinPoint, Object result) {
System.out.println("A doAfterReturning run, result: " + result);
}
@AfterThrowing(value = "execution(public * com.xyh.study.provider.spring.AOP. Section 1.*.*(..) )", throwing = "ex")
public void doAfterThrowing(JoinPoint joinPoint, Exception ex) {
System.out.println("A doAfterThrowing catch exception: " + ex.getMessage());
}
@Around("execution(public * com.xyh.study.provider.spring.AOP. Section 1.*.*(..) )"
public Object doAround(ProceedingJoinPoint joinPoint) {
System.out.println("A doAround run...");
Object result = null;
try {
System.out.println("A method before invoke...");
result = joinPoint.proceed();
System.out.println("A method invoked, result: " + result);
} catch (Throwable throwable) {
System.out.println("A method throws Exception: " + throwable.getMessage());
throwable.printStackTrace();
}
returnresult; }}Copy the codeLogAspectB
@Component
@Aspect
public class LogAspectB {
@Before("execution(public * com.xyh.study.provider.spring.AOP. Section 1.*.*(..) )"
public void doBefore(JoinPoint joinPoint) {
System.out.println("B doBefore run...");
}
@After("execution(public * com.xyh.study.provider.spring.AOP. Section 1.*.*(..) )"
public void doAfter(JoinPoint joinPoint) {
System.out.println("B doAfter run...");
}
@AfterReturning(value = "execution(public * com.xyh.study.provider.spring.AOP. Section 1.*.*(..) )", returning = "result")
public void doAfterReturning(JoinPoint joinPoint, Object result) {
System.out.println("B doAfterReturning run, result: " + result);
}
@AfterThrowing(value = "execution(public * com.xyh.study.provider.spring.AOP. Section 1.*.*(..) )", throwing = "ex")
public void doAfterThrowing(JoinPoint joinPoint, Exception ex) {
System.out.println("B doAfterThrowing catch exception: " + ex.getMessage());
}
@Around("execution(public * com.xyh.study.provider.spring.AOP. Section 1.*.*(..) )"
public Object doAround(ProceedingJoinPoint joinPoint) {
System.out.println("B doAround run...");
Object result = null;
try {
System.out.println("B method before invoke...");
result = joinPoint.proceed();
System.out.println("B method invoked, result: " + result);
} catch (Throwable throwable) {
System.out.println("B method throws Exception: " + throwable.getMessage());
throwable.printStackTrace();
}
returnresult; }}Copy the codeHere to explain, @ Around, @ Before, @ After, @ AfterReturning, @ AfterThrowing corresponding can eventually be parsed into InstantiationModelAwarePointcutAdvisorImpl, This is an Advisor and is added to the interceptor chain. This parsing process will be covered in more detail later and is not the focus of this article.
LogAspectA and LogAspectB will eventually produce 10 advisors, denoted as: Around-a, before-a, after-A, AfterReturning-A, AfterThrowing-A, around-B, before-b, AfterReturning-B, AfterThrowing-B. The interceptor chain is ordered, and Spring uses partial ordering for sorting the 10 advisors.
Let’s look at the spring to sort by Advisor code comments (from AspectJAwareAdvisorAutoProxyCreator) :
/** * Sort the rest by AspectJ precedence. If two pieces of advice have * come from the same aspect they will have the same order. * Advice from the same aspect is then further ordered according to the * following rules: *
*
- if either of the pair is after advice, then the advice declared * last gets highest precedence (runs last)
*
- otherwise the advice declared first gets highest precedence (runs first)
*
* Important: Advisors are sorted in precedence order, from highest * precedence to lowest. "On the way in" to a join point, the highest precedence * advisor should run first. "On the way out" of a join point, the highest precedence * advisor should run last. */
@Override
@SuppressWarnings("unchecked")
protected List<Advisor> sortAdvisors(List<Advisor> advisors) {
/ /... omit
}
Copy the codeFrom the comments we can get the following information:
- Advisors are sorted from highest priority to lowest priority. When entering the join point, the higher-priority Advisor executes first. When it leaves the join point, the high-priority Advisor executes behind (the concept of a stack).
- Aspect implementation Advisors from the same @aspect configuration class have the same priority order.
- The Aspect implementation Advisor of the same @aspect configuration class is further sorted by specific rules (more on that in future articles).
To sum up, globally, you sort from highest to lowest in order of priority. Advisors from the same Aspect are further sorted according to specific rules. This further sort is a partial sort. Because this particular rule is sorted only if the conditions from the same Aspect are met, not all advisors apply this rule to sorting.
Partial order sort implementation
Let’s look at the method used in spring to sort the Advisor, PartialOrder#order.
/ * * *@param objects must all implement PartialComparable
*
* @returns the same members as objects, but sorted according to their partial order. returns null if the objects are cyclical
*
*/
public static <T extends PartialComparable> List<T> sort(List<T> objects) {
if (objects.size() < 2) {
return objects;
}
List<SortObject<T>> sortList = new LinkedList<SortObject<T>>();
for (Iterator<T> i = objects.iterator(); i.hasNext();) {
addNewPartialComparable(sortList, i.next());
}
final int N = objects.size();
for (int index = 0; index < N; index++) {
SortObject<T> leastWithNoSmallers = null;
for (SortObject<T> so: sortList) {
if (so.hasNoSmallerObjects()) {
if (leastWithNoSmallers == null || so.object.fallbackCompareTo(leastWithNoSmallers.object) < 0) { leastWithNoSmallers = so; }}}if (leastWithNoSmallers == null) {
return null;
}
removeFromGraph(sortList, leastWithNoSmallers);
objects.set(index, leastWithNoSmallers.object);
}
return objects;
}
Copy the codeNow we combine the partial order knowledge we learned before to analyze step by step.
PartialComparable
The interface comment indicates that the input parameter (the data to be sorted) must implement the PartialComparable interface. Then take a look at PartialComparable.
/** * All classes that want to be part of a partial order must implement PartialOrder.PartialComparable. * All who want to be part of a partial ordered collection must implement this interface */
public static interface PartialComparable {
/ * * *@returns<ul> * <li>+1 if this is greater than other</li> * <li>-1 if this is less than other</li> * <li>0 if this is not comparable to other</li> * </ul> * * <b> Note: returning 0 from this method doesn't mean the same thing as returning 0 from * java.util.Comparable.compareTo()</b> * Return +1 to indicate that the current object is larger than the input parameter other * Returns -1 to indicate that the current object is smaller than the input parameter other * Returns 0 to indicate that the current object and the input parameter other cannot be compared. With java.util.Comparable.com pareTo () returns 0 is with different meanings, java.util.Comparable.com pareTo () returns 0 is said both equal! * /
public int compareTo(Object other);
/** * This method can provide a deterministic ordering for elements that are strictly not comparable. If you have no Need for * this, this method can just return 0 whenever called. * * For elements that cannot be compared (i.e. compareTo returns 0), this method gives you the opportunity to compare, if you don't need it, Return 0. * /
public int fallbackCompareTo(Object other);
}
Copy the codeI’m afraid the code comments are too small for you to read carefully, so LET me take out the important things again. Notice the meaning of returning 0! Notice the meaning of returning 0! Notice the meaning of returning 0!
The value returned by compareTo means: +1: the current object is larger than the input. Other: -1: the current object is smaller than the input. Other: 0: the current object and the input object other cannot be compared. A partial ordering relationship is a relationship in which only part of the elements of a set are comparable. Parts! Part! Part!) ! With java.util.Comparable.com pareTo () returns 0 is with different meanings, java.util.Comparable.com pareTo () returns 0 is said both equal!
SortObject
A data structure used for sorting.
private static class SortObject<T extends PartialComparable> {
// The current object
T object;
// List of elements in the collection that are smaller than the current object
List<SortObject<T>> smallerObjects = new LinkedList<SortObject<T>>();
// List of elements in the collection that are larger than the current object
List<SortObject<T>> biggerObjects = new LinkedList<SortObject<T>>();
public SortObject(T o) {
object = o;
}
boolean hasNoSmallerObjects(a) {
return smallerObjects.size() == 0;
}
boolean removeSmallerObject(SortObject<T> o) {
smallerObjects.remove(o);
return hasNoSmallerObjects();
}
// Add a directed connection, where smallerObjects and biggerObjects define a connection
// This corresponds to the directed connection in the diagram we talked about earlier
void addDirectedLinks(SortObject<T> other) {
int cmp = object.compareTo(other.object);
if (cmp == 0) {
Sortobobject #compareTo returns 0, the two objects cannot be compared, and no directed connection is established.
return;
}
if (cmp > 0) {
this.smallerObjects.add(other);
other.biggerObjects.add(this);
} else {
this.biggerObjects.add(other);
other.smallerObjects.add(this); }}public String toString(a) {
return object.toString(); // +smallerObjects+biggerObjects;}}Copy the codeCode implementation
Now that we know about PartialComparable and SortObject, let’s go back and take a closer look at PartialOrder#sort.
public static <T extends PartialComparable> List<T> sort(List<T> objects) {
// If the value is less than two elements, return the value.
if (objects.size() < 2) {
return objects;
}
// Create partial sort data structure SortObject
List<SortObject<T>> sortList = new LinkedList<SortObject<T>>();
// The following for loop builds the diagram by establishing a directed join!
for (Iterator<T> i = objects.iterator(); i.hasNext();) {
addNewPartialComparable(sortList, i.next());
}
final int N = objects.size();
// Parse the diagram, which already contains the size relationship. Complete sorting during parsing.
for (int index = 0; index < N; index++) {
// The smallest element in the set
SortObject<T> leastWithNoSmallers = null;
for (SortObject<T> so: sortList) {
// If SortObject has no smaller elements
if (so.hasNoSmallerObjects()) {
if (leastWithNoSmallers == null || so.object.fallbackCompareTo(leastWithNoSmallers.object) < 0) { leastWithNoSmallers = so; }}}if (leastWithNoSmallers == null) {
return null;
}
removeFromGraph(sortList, leastWithNoSmallers);
// Set the sequence
objects.set(index, leastWithNoSmallers.object);
}
// Return the sorted result
return objects;
}
Copy the codeThe specific logic is commented out in the code. Let’s take a look at some examples.
We want to sort the first character of a string in lexicographical descending order, and treat the same first character as unrelated. On the other hand, we also want to use the fallbackCompareTo function of PartialComparable, which sorts by dictionary ascending if the first character is the same.
Create a Token class to hold the elements to be sorted. As described above, the PartialComparable interface must be implemented to be part of a PartialComparable collection.
class Token implements PartialOrder.PartialComparable {
private String s;
Token(String s) {
this.s = s;
}
@Override
public int compareTo(Object other) {
// Sort the first character of a string in lexicographical descending order
Token t = (Token) other;
int cmp = s.charAt(0) - t.s.charAt(0);
if (cmp == 1) {
return 1;
}
if (cmp == -1) {
return -1;
}
return 0;
}
@Override
public int fallbackCompareTo(Object other) {
// If the first character is the same, we sort by dictionary ascending order
return -s.compareTo(((Token) other).s);
}
@Override
public String toString(a) {
returns; }}Copy the codeLet’s test it out:
public static void main(String[] args) {
List<Token> l = new ArrayList<Token>();
l.add(new Token("a1"));
l.add(new Token("c2"));
l.add(new Token("b3"));
l.add(new Token("f4"));
l.add(new Token("e5"));
l.add(new Token("d6"));
l.add(new Token("c7"));
l.add(new Token("b8"));
l.add(new Token("z"));
l.add(new Token("x"));
l.add(new Token("f9"));
l.add(new Token("e10"));
l.add(new Token("a11"));
l.add(new Token("d12"));
l.add(new Token("b13"));
l.add(new Token("c14"));
System.out.println(l);
PartialOrder.sort(l);
System.out.println(l);
}
Copy the codeOutput result:
[a1, c2, b3, f4, e5, d6, c7, b8, z, x, f9, e10, a11, d12, b13, c14]
[z, x, a11, a1, b8, b3, b13, c7, c2, c14, d6, d12, e5, e10, f9, f4]
Copy the codeYeah, no problem. It’s what we want.
conclusion
This paper introduces the concept of partial order relation in discrete mathematics, and introduces partial order sorting. And the application of partial ordering in AOP, namely interceptor chain ordering. With this foundation, we will continue to discuss:
- How @aspect of @around, @before, @after, @afterreturning, and @AfterThrowing are transformed into Advisor and added to the interceptor chain.
- What is the order of @around, @before, @after, @afterreturning, and @afterthrowing?