1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
package com.yahoo.searchdefinition.derived;
import com.yahoo.document.DataTypeName;
import com.yahoo.searchdefinition.document.SDDocumentType;
import com.yahoo.searchdefinition.Search;
import java.util.*;
/**
* <p>A class which can reorder a list of search definitions such that any supertype
* always preceed any subtype. Subject to this condition the given order
* is preserved (the minimal reordering is done).</p>
*
* <p>This class is <b>not</b> multithread safe. Only one ordering must be done
* at the time in any instance.</p>
*
* @author bratseth
*/
public class SearchOrderer {
/** A map from DataTypeName to the Search defining them */
private Map<DataTypeName, Search> documentNameToSearch=new java.util.HashMap<>();
/**
* Reorders the given list of search definitions such that any supertype
* always preceed any subtype. Subject to this condition the given order
* is preserved (the minimal reordering is done).
*
* @return a new list containing the same search instances in the right order
*/
public List<Search> order(List<Search> unordered) {
Collections.sort(unordered, new Comparator<Search>() {
@Override
public int compare(Search lhs, Search rhs) {
return lhs.getName().compareTo(rhs.getName());
}
});
// No, this is not a fast algorithm...
indexOnDocumentName(unordered);
List<Search> ordered=new java.util.ArrayList<>(unordered.size());
List<Search> moveOutwards=new java.util.ArrayList<>();
for (Search search: unordered) {
if (containsInherited(ordered,search)) {
addOrdered(ordered,search,moveOutwards);
}
else {
moveOutwards.add(search);
}
}
// Any leftovers means we have search definitions with undefined inheritants.
// This is warned about elsewhere.
ordered.addAll(moveOutwards);
documentNameToSearch.clear();
return ordered;
}
private void addOrdered(List<Search> ordered,Search search,List<Search> moveOutwards) {
ordered.add(search);
Search eligibleMove;
do {
eligibleMove=removeFirstEligibleMoveOutwards(moveOutwards,ordered);
if (eligibleMove!=null)
ordered.add(eligibleMove);
} while (eligibleMove!=null);
}
/** Removes and returns the first search from the move list which can now be added, or null if none */
private Search removeFirstEligibleMoveOutwards(List<Search> moveOutwards,List<Search> ordered) {
for (Search move : moveOutwards) {
if (containsInherited(ordered,move)) {
moveOutwards.remove(move);
return move;
}
}
return null;
}
private boolean containsInherited(List<Search> list,Search search) {
if (search.getDocument() == null) {
return true;
}
for (SDDocumentType sdoc : search.getDocument().getInheritedTypes() ) {
DataTypeName inheritedName=sdoc.getDocumentName();
if ("document".equals(inheritedName.getName())) continue;
Search inheritedSearch=documentNameToSearch.get(inheritedName);
if (!list.contains(inheritedSearch))
return false;
}
return true;
}
private void indexOnDocumentName(List<Search> searches) {
documentNameToSearch.clear();
for (Search search : searches) {
if (search.getDocument() != null) {
documentNameToSearch.put(search.getDocument().getDocumentName(),search);
}
}
}
}
|
