1
|
/**
|
2
|
*
|
3
|
*/
|
4
|
package eu.etaxonomy.cdm.io.markup;
|
5
|
|
6
|
import java.util.ArrayList;
|
7
|
import java.util.Collection;
|
8
|
import java.util.HashMap;
|
9
|
import java.util.HashSet;
|
10
|
import java.util.Iterator;
|
11
|
import java.util.List;
|
12
|
import java.util.Map;
|
13
|
import java.util.Set;
|
14
|
import java.util.UUID;
|
15
|
|
16
|
/**
|
17
|
* This class is supposed to find the best sorting order for features (descriptive and other).
|
18
|
* Currently it is not yet very sophisticated.
|
19
|
*
|
20
|
* @author a.mueller
|
21
|
*/
|
22
|
public class FeatureSorter {
|
23
|
|
24
|
class FeatureStatistic{
|
25
|
|
26
|
private UUID uuid;
|
27
|
boolean isAlwaysHighest = true;
|
28
|
private int before = 0; //number of features before this feature
|
29
|
private int after = 0; //number of features after this feature
|
30
|
private int n = 0; //number of occurrences of this feature
|
31
|
|
32
|
public FeatureStatistic(UUID uuid) {
|
33
|
this.uuid = uuid;
|
34
|
}
|
35
|
public void addValue(int index, int total) {
|
36
|
if (index != 0){
|
37
|
isAlwaysHighest = false;
|
38
|
}
|
39
|
n++;
|
40
|
before += index;
|
41
|
after += (total - index);
|
42
|
}
|
43
|
@Override
|
44
|
public String toString(){
|
45
|
return uuid != null? uuid.toString(): super.toString();
|
46
|
}
|
47
|
}
|
48
|
|
49
|
/**
|
50
|
* Compute the order of features.
|
51
|
* @param orderLists
|
52
|
* @return
|
53
|
*/
|
54
|
public List<UUID> getSortOrder(Map<String,List<FeatureSorterInfo>> listMap){
|
55
|
List<UUID> result = new ArrayList<UUID>();
|
56
|
//compute highest feature until all lists are empty
|
57
|
removeEmptyLists(listMap);
|
58
|
while (! listMap.isEmpty()){
|
59
|
Map<UUID,FeatureStatistic> statisticMap = computeStatistic(listMap);
|
60
|
FeatureStatistic best = findBest(statisticMap);
|
61
|
result.add(best.uuid);
|
62
|
Map<String, List<FeatureSorterInfo>> subFeatures = removeFromLists(listMap, best.uuid);
|
63
|
List<UUID> subFeatureOrder = getSortOrder(subFeatures);
|
64
|
result.addAll(subFeatureOrder);
|
65
|
}
|
66
|
return result;
|
67
|
}
|
68
|
|
69
|
|
70
|
private void removeEmptyLists(Map<String, List<FeatureSorterInfo>> listMap) {
|
71
|
Set<String> keysToRemove = new HashSet<>();
|
72
|
for(String key : listMap.keySet()){
|
73
|
List<FeatureSorterInfo> list = listMap.get(key);
|
74
|
if (list.isEmpty()){
|
75
|
keysToRemove.add(key);
|
76
|
}
|
77
|
}
|
78
|
for (String key : keysToRemove){
|
79
|
listMap.remove(key);
|
80
|
}
|
81
|
|
82
|
}
|
83
|
|
84
|
|
85
|
/**
|
86
|
* Removes all entries for given uuid from orderLists and removes empty lists from map.
|
87
|
* @param orderLists
|
88
|
* @param uuid
|
89
|
*/
|
90
|
private Map<String, List<FeatureSorterInfo>> removeFromLists(Map<String, List<FeatureSorterInfo>> orderListsMap, UUID uuid) {
|
91
|
Map<String, List<FeatureSorterInfo>> childLists = new HashMap<>();
|
92
|
|
93
|
Set<String> keySet = orderListsMap.keySet();
|
94
|
Iterator<String> keySetIterator = keySet.iterator();
|
95
|
while (keySetIterator.hasNext()){
|
96
|
String key = keySetIterator.next();
|
97
|
List<FeatureSorterInfo> list = orderListsMap.get(key);
|
98
|
Iterator<FeatureSorterInfo> it = list.listIterator();
|
99
|
while (it.hasNext()){
|
100
|
FeatureSorterInfo info = it.next();
|
101
|
if (info.getUuid().equals(uuid)){
|
102
|
if (! info.getSubFeatures().isEmpty()){
|
103
|
childLists.put(key, info.getSubFeatures());
|
104
|
}
|
105
|
it.remove();
|
106
|
if (list.isEmpty()){
|
107
|
keySetIterator.remove();
|
108
|
}
|
109
|
}
|
110
|
}
|
111
|
}
|
112
|
return childLists;
|
113
|
}
|
114
|
|
115
|
private FeatureStatistic findBest(Map<UUID, FeatureStatistic> statisticMap) {
|
116
|
FeatureStatistic result;
|
117
|
Set<FeatureStatistic> highest = getOnlyHighestFeatures(statisticMap);
|
118
|
if (highest.size() == 1){
|
119
|
result = highest.iterator().next();
|
120
|
}else if (highest.size() > 1){
|
121
|
result = findBestOfHighest(highest);
|
122
|
}else{ //<1
|
123
|
result = findBestOfNonHighest(statisticMap);
|
124
|
}
|
125
|
return result;
|
126
|
}
|
127
|
|
128
|
|
129
|
/**
|
130
|
* If multiple features do all have no higher feature in any list, this method
|
131
|
* can be called to use an alternative criteria to find the "highest" feature.
|
132
|
* @param highest
|
133
|
* @return
|
134
|
*/
|
135
|
private FeatureStatistic findBestOfHighest(Set<FeatureStatistic> highest) {
|
136
|
//current implementation: find the one with the highest "after" value
|
137
|
FeatureStatistic result = highest.iterator().next();
|
138
|
int bestAfter = result.after;
|
139
|
for (FeatureStatistic statistic : highest){
|
140
|
if (statistic.after > bestAfter){
|
141
|
result = statistic;
|
142
|
bestAfter = statistic.after;
|
143
|
}
|
144
|
}
|
145
|
return result;
|
146
|
}
|
147
|
|
148
|
/**
|
149
|
* If no feature is always highest this method can be called to use an alternative criteria
|
150
|
* to find the "highest" feature.
|
151
|
*
|
152
|
* @param statisticMap
|
153
|
* @return
|
154
|
*/
|
155
|
private FeatureStatistic findBestOfNonHighest(Map<UUID, FeatureStatistic> statisticMap) {
|
156
|
//current implementation: find the one with the lowest "before" value
|
157
|
//TODO better use before/n ??
|
158
|
Collection<FeatureStatistic> statistics = statisticMap.values();
|
159
|
FeatureStatistic result = statistics.iterator().next();
|
160
|
int bestBefore = result.before;
|
161
|
for (FeatureStatistic statistic : statistics){
|
162
|
if (statistic.before < bestBefore){
|
163
|
result = statistic;
|
164
|
bestBefore = statistic.before;
|
165
|
}
|
166
|
}
|
167
|
return result;
|
168
|
}
|
169
|
|
170
|
private Set<FeatureStatistic> getOnlyHighestFeatures(Map<UUID, FeatureStatistic> statisticMap) {
|
171
|
Set<FeatureStatistic> result = new HashSet<>();
|
172
|
for (FeatureStatistic statistic : statisticMap.values()){
|
173
|
if (statistic.isAlwaysHighest){
|
174
|
result.add(statistic);
|
175
|
}
|
176
|
}
|
177
|
return result;
|
178
|
}
|
179
|
|
180
|
|
181
|
private Map<UUID, FeatureStatistic> computeStatistic(Map<String,List<FeatureSorterInfo>> orderLists) {
|
182
|
Map<UUID, FeatureStatistic> result = new HashMap<>();
|
183
|
for (String key : orderLists.keySet()){
|
184
|
List<FeatureSorterInfo> list = orderLists.get(key);
|
185
|
int n = list.size();
|
186
|
for (FeatureSorterInfo info : list){
|
187
|
FeatureStatistic statistic = getFeatureStatistic(info, result);
|
188
|
int index = list.indexOf(info);
|
189
|
statistic.addValue(index,n);
|
190
|
}
|
191
|
}
|
192
|
return result;
|
193
|
}
|
194
|
|
195
|
private FeatureStatistic getFeatureStatistic(FeatureSorterInfo info, Map<UUID, FeatureStatistic> statisticMap) {
|
196
|
UUID uuid = info.getUuid();
|
197
|
FeatureStatistic result = statisticMap.get(uuid);
|
198
|
if (result == null){
|
199
|
result = new FeatureStatistic(uuid);
|
200
|
statisticMap.put(uuid, result);
|
201
|
}
|
202
|
return result;
|
203
|
}
|
204
|
}
|