import com.laidw.tree.resolver.RecordResolver;
import java.lang.reflect.Field;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.ArrayList;
import java.util.List;
/**
* 有时我们需要将一些扁平的数据转换成树状的数据
*
* 比如，我们从数据库中查询出了如下的数据：
* countryId countryName provinceId provinceName cityId cityName
* 1 cn 1 gd 1 gz
* 1 cn 1 gd 2 pn
* 1 cn 1 gd 3 jy
* 1 cn 1 gd 4 zs
* 1 cn 2 gx 5 gl
* 1 cn 2 gx 6 lz
*
* 但我们希望用树状结构来展示这些数据：
* {
* countryId: 1,
* countryName: cn,
* provinces: [
* {
* provinceId: 1,
* provinceName: gd,
* cities: [
* {cityId: 1, cityName: gz},
* {cityId: 2, cityName: pn},
* {cityId: 3, cityName: jy},
* {cityId: 4, cityName: gl}
* ]
* },
* {
* provinceId: 2,
* provinceName: gx,
* cities: [
* {cityId: 5, cityName: gl},
* {cityId: 6, cityName: lz},
* ]
* }
* ]
* }
*
* 不妨把扁平的数据称作记录，把树状结构的数据称作树
* 树有级别的概念，比如这个例子中，国家树是一级树，省份树是二级树，城市树是三级树
* 通过本类，我们可以很方便地将List<S>转换成一棵一级树（一级树嵌套二级树，依此类推）
*/
@SuppressWarnings("unchecked")
public class TreeConverter<R> {
private final List<List<Field>> fieldMatrix;
public TreeConverter(RecordResolver<R> resolver, Class<R> recordClass){
fieldMatrix = resolver.getRecordFieldMatrix(recordClass);
}
public <T> T orderedListToTree(List<? extends R> list, Class<T> tCla) throws InstantiationException, IllegalAccessException {
if (list == null || list.size() == 0) return null;
return orderedListToTreeInternal(list, tCla, 0);
}
public <T> T disorderedListToTree(List<? extends R> list, Class<T> tCla) throws InstantiationException, IllegalAccessException {
if (list == null || list.size() == 0) return null;
list.sort((s1, s2) -> {
// 按顺序依次比较记录类中的id字段，只需比较第二个到最后一个，因为：
// 所有记录的第一个id字段一定相同，这是硬性要求，否则最终转换的结果肯定不只是一棵树
for(int i = 1; i < fieldMatrix.size(); i++){
Field idField = fieldMatrix.get(i).get(0);
try{
Object var1 = idField.get(s1), var2 = idField.get(s2);
// var1为null则返回-1，var2为null则返1，确保null值排在最前面
if(var1 == null) return -1;
if(var2 == null) return 1;
// 获取var1和var2的比较结果；如果比较结果不是0，则返回该比较结果，否则继续比较下一个id字段
int compareResult = ((Comparable)var1).compareTo(var2);
if(compareResult != 0) {
return compareResult;
}
} catch (IllegalAccessException e){
throw new RuntimeException("排序失败！无法获得id字段的值！");
}
}
return 0;
});
return orderedListToTreeInternal(list, tCla, 0);
}
/**
* 将记录列表list封装成一棵类型为T的level级树（这里的0级树指的是上面提到的一级树，依此类推）
* 注意，list列表不能为空，并且其所有元素的fieldMatrix[level][0]字段都必须相同，且fieldMatrix[level + 1][0]字段都是排好序的
* 比如，要把list封装成省份树，那么list中所有记录的省份id都必须相同，且城市id必须是递增/递减的（如果城市id为null，则该记录必须排在最前面）
*
* @param list 待转换的记录列表
* @param <T> 要将list转换成的树的类型
* @param tCla 树的类型的Class对象
* @param level 该字段表示转换后的树是level级数
* @return 封装后的树对象
* @throws IllegalAccessException,InstantiationException 反射时常见的异常
*/
private <T> T orderedListToTreeInternal(List<? extends R> list, Class<T> tCla, int level) throws IllegalAccessException, InstantiationException {
// 注意，本方法中的注释都是以"T为Province、level为1"的情况来对代码进行解释的
// 创建Province对象
T t = tCla.newInstance();
// list中所有记录的省份信息都是相同的，因此这里任取一条记录即可
// 我们需要读取出该记录的省份信息，并对Province对象的字段进行赋值
R s = list.get(0);
// 字段矩阵中第level行的字段和Province类中的字段相对应，因此取出该行的数据
List<Field> fieldRow = fieldMatrix.get(level);
// 获取到Province类中的所有字段
Field[] fields = tCla.getDeclaredFields();
// 将s中的省份信息提取出来，并赋给t的相应字段
// 这里我们只是简单地通过声明顺序来进行映射，这就要求记录类和树类中字段的声明顺序要一致
int i = 0;
while(i < fieldRow.size()){
fields[i].setAccessible(true);
fields[i].set(t, fieldRow.get(i).get(s));
i++;
}
// 如果Province类中的字段都映射完了，或者没有下级树了，则直接返回Province对象
if(i == fields.length || level == fieldMatrix.size() - 1){
return t;
}
// 否则我们就认为fields[i]就是该省份树的cities字段（这就要求树类和记录类要严格对应，否则就会解析出错）
// 此时先获取cities字段的带有泛型的类型（即List<City>），然后再获取该类型中的泛型的实际类型（即City）
ParameterizedType type = (ParameterizedType)fields[i].getGenericType();
Type subTreeType = type.getActualTypeArguments()[0];
// 新创建一个List集合，将其赋值给cities字段
fields[i].setAccessible(true);
List children = new ArrayList();
fields[i].set(t, children);
// 获取到记录类中表示城市id的字段
Field nextId = fieldMatrix.get(level + 1).get(0);
// 将begin移至第一个城市id不为null的记录
int begin = 0, size = list.size();
while(begin < size && nextId.get(list.get(begin)) == null){
begin++;
}
// 如果发现所有记录的城市id都为null，则直接返回Province对象
if(begin == size){
return t;
}
// 通过滑动窗口[begin, end)找到找到一组城市id相同的记录，用它们来构造City对象并将其存入children集合中，然后再找下一组，依此类推
int end = begin + 1;
do{
// 将begin指向的记录的城市id作为目标id
Object targetId = nextId.get(list.get(begin));
// end不断自增，直到遍历完列表或end指向的记录的城市id不等于目标id
while(end < list.size() && nextId.get(list.get(end)).equals(targetId)){
end++;
}
// 用list.subList(begin, end)来构建City对象，并将City对象存入children集合；然后将begin更新为当前的end值，end则自增1
children.add(orderedListToTreeInternal(list.subList(begin, end), (Class)subTreeType, level + 1));
begin = end++;
} while (begin < list.size());
// cities字段设置完成，返回Province对象
return t;
}
}
import java.lang.reflect.Field;
import java.util.List;
/**
* 用于解析记录类，获得其字段矩阵
*
* @author NightDW 2022/3/15 23:45
*/
public interface RecordResolver<R> {
/**
* 解析记录类，获取其字段矩阵，字段矩阵的每一行就对应了相应级别的树的普通字段
* [
* ["countryId", "countryName"], // 对应着一级树/Country类的id和名称字段
* ["provinceId", "provinceName"], // 对应着二级树/Province类的id和名称字段
* ["cityId", "cityName"] // 对应着三级树/City类的id和名称字段
* ]
*
* @param recordClass 记录类
* @return 该记录类的字段矩阵，所有字段都应该setAccessible为true，方便转换器后续操作
*/
List<List<Field>> getRecordFieldMatrix(Class<R> recordClass);
}
import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.List;
/**
* 用于解析记录类，获得其字段矩阵
*
* @author NightDW 2022/3/15 23:45
*/
public abstract class AbstractRecordResolver<R> implements RecordResolver<R> {
@Override
public final List<List<Field>> getRecordFieldMatrix(Class<R> recordClass) {
List<List<Field>> fieldMatrix = new ArrayList<>();
// 遍历记录类的每一个字段
for(Field field : recordClass.getDeclaredFields()){
// 先将该字段设置为可访问，这样后续反射时就不需要再手动调用该方法了
field.setAccessible(true);
// 该字段是id字段，说明需要有一棵下级树，因此往矩阵中新插入一行
if (isIdField(field)){
fieldMatrix.add(new ArrayList<>());
}
// 将该字段放到最后一行的最后，每一行的第一个元素都是id字段
fieldMatrix.get(fieldMatrix.size() - 1).add(field);
}
if (fieldMatrix.size() == 0) {
throw new RuntimeException("解析失败：记录类中缺少@TreeId注解标记的字段！");
}
return fieldMatrix;
}
/**
* 判断指定字段是否可以唯一标识一棵树，即是否为id字段
* 假设Record记录类中有如下字段：countryId, countryName, provinceId, provinceName, cityId, cityName
* 那么显然，countryId/provinceId/cityId可以唯一标识一个国家树/省份树/城市树，因此这3个字段都是id字段
*
* 注意，id字段标志着下一级树的开始，因此记录类的字段顺序不能随意更改
* 比如，上面3个字段是id字段，那么解析器会认为countryId, countryName对应着一棵一级树，provinceId, provinceName对应着一棵二级树，cityId, cityName对应着一棵三级树
* 而如果此时将provinceId和provinceName字段调换位置，解析器就会误以为countryId, countryName, provinceName对应着一棵一级树了，那么解析肯定就有问题了
*
* 另外，表示树的类的字段的顺序也是不能随便更改的，需要和记录类字段的顺序相对应
* 比如，Record类中是countryId, countryName这样的顺序，那么Country类中就不能是countryName, countryId的顺序，必须是id先、name后的顺序，否则就会映射错误
* 当然，Country类中表示国家id/名称的字段可以不是countryId/countryName，只需要确保它们和Record类中的countryId/countryName字段类型和顺序相同即可
*/
protected abstract boolean isIdField(Field field);
}
import java.lang.reflect.Field;
/**
* 基于指定字段名后缀进行解析的RecordResolver
*
* @author NightDW 2022/3/15 23:51
*/
public class NameSuffixRecordResolver<R> extends AbstractRecordResolver<R> {
private String suffix;
public NameSuffixRecordResolver(String suffix) {
this.suffix = suffix;
}
@Override
protected boolean isIdField(Field field) {
return field.getName().endsWith(suffix);
}
}
import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;
import java.lang.reflect.Field;
/**
* 基于@TreeId注解进行解析的RecordResolver
*
* @author NightDW 2022/3/15 23:51
*/
public class AnnotationRecordResolver<R> extends AbstractRecordResolver<R> {
@Target(ElementType.FIELD)
@Retention(RetentionPolicy.RUNTIME)
public @interface TreeId { }
@Override
protected boolean isIdField(Field field) {
return field.getAnnotation(TreeId.class) != null;
}
}
查看5道真题和解析