import java.util.*;
public class TreeUtils {
/** 先前的建樹：用 iftPrev 串接父子，回傳所有 root 清單 */
public static List<TreeNodeBean> buildTree(List<TreeNodeBean> flatList) {
Map<String, TreeNodeBean> lookup = new HashMap<>();
for (TreeNodeBean node : flatList) {
lookup.put(node.getIftSid(), node);
node.setChildren(new ArrayList<>()); // 確保 not null
}
List<TreeNodeBean> roots = new ArrayList<>();
for (TreeNodeBean node : flatList) {
String parentId = node.getIftPrev();
if (parentId == null || parentId.isBlank() || "0".equals(parentId)) {
roots.add(node);
} else {
TreeNodeBean parent = lookup.get(parentId);
if (parent != null) parent.getChildren().add(node);
else roots.add(node); // 找不到父節點就先視為 root
}
}
return roots;
}
/** 建立 id → node 的索引（之後取路徑、檢核都會用到） */
public static Map<String, TreeNodeBean> buildIndex(List<TreeNodeBean> flatList) {
Map<String, TreeNodeBean> map = new HashMap<>();
for (TreeNodeBean n : flatList) map.put(n.getIftSid(), n);
return map;
}
/** 從 root 到當前節點的「ID 路徑」；includeSelf 決定是否包含自己 */
public static List<String> getPathIdsFromRoot(TreeNodeBean node,
Map<String, TreeNodeBean> byId,
boolean includeSelf) {
Deque<String> stack = new ArrayDeque<>();
// 先把祖先一路往上塞進前面
String p = node.getIftPrev();
while (p != null && !p.isBlank() && !"0".equals(p)) {
stack.addFirst(p);
TreeNodeBean parent = byId.get(p);
if (parent == null) break; // 資料不完整就停
p = parent.getIftPrev();
}
// 需要時把自己加到最後
if (includeSelf) stack.addLast(node.getIftSid());
return new ArrayList<>(stack);
}
/** 取「名稱路徑」：從 root → ... → 自己（方便顯示） */
public static List<String> getPathNamesFromRoot(TreeNodeBean node,
Map<String, TreeNodeBean> byId,
boolean includeSelf) {
List<String> ids = getPathIdsFromRoot(node, byId, includeSelf);
List<String> names = new ArrayList<>(ids.size());
for (String id : ids) {
TreeNodeBean x = byId.get(id);
names.add(x != null ? x.getFtName() : ("#" + id));
}
return names;
}
/** 檢核 sft_path：\3808\3811\3813\ 需等於實際祖先鏈（不含自己） */
public static boolean validateSftPath(TreeNodeBean node, Map<String, TreeNodeBean> byId) {
// 解析原始 path
List<String> expected = parsePathIds(node.getFtPathRaw());
// 實際父鏈（不含自己）
List<String> actual = getPathIdsFromRoot(node, byId, false);
return expected.equals(actual);
}
/** 把 "\\3808\\3811\\3813\\" 解析成 ["3808","3811","3813"]；容忍前後沒有反斜線 */
public static List<String> parsePathIds(String raw) {
if (raw == null) return List.of();
String s = raw.trim();
if (s.startsWith("\\")) s = s.substring(1);
if (s.endsWith("\\")) s = s.substring(0, s.length() - 1);
if (s.isEmpty()) return List.of();
return Arrays.asList(s.split("\\\\"));
}
/** 簡單印樹（檢查用） */
public static void printTree(List<TreeNodeBean> nodes, int level) {
for (TreeNodeBean n : nodes) {
System.out.println(" ".repeat(level) + n.getIftSid() + " " + n.getFtName());
if (n.getChildren() != null && !n.getChildren().isEmpty()) {
printTree(n.getChildren(), level + 1);
}
}
}
}
aW1wb3J0IGphdmEudXRpbC4qOwoKCgpwdWJsaWMgY2xhc3MgVHJlZVV0aWxzIHsKCgoKICAgIC8qKiDlhYjliY3nmoTlu7rmqLnvvJrnlKggaWZ0UHJldiDkuLLmjqXniLblrZDvvIzlm57lgrPmiYDmnIkgcm9vdCDmuIXllq4gKi8KCiAgICBwdWJsaWMgc3RhdGljIExpc3Q8VHJlZU5vZGVCZWFuPiBidWlsZFRyZWUoTGlzdDxUcmVlTm9kZUJlYW4+IGZsYXRMaXN0KSB7CgogICAgICAgIE1hcDxTdHJpbmcsIFRyZWVOb2RlQmVhbj4gbG9va3VwID0gbmV3IEhhc2hNYXA8PigpOwoKICAgICAgICBmb3IgKFRyZWVOb2RlQmVhbiBub2RlIDogZmxhdExpc3QpIHsKCiAgICAgICAgICAgIGxvb2t1cC5wdXQobm9kZS5nZXRJZnRTaWQoKSwgbm9kZSk7CgogICAgICAgICAgICBub2RlLnNldENoaWxkcmVuKG5ldyBBcnJheUxpc3Q8PigpKTsgLy8g56K65L+dIG5vdCBudWxsCgogICAgICAgIH0KCgoKICAgICAgICBMaXN0PFRyZWVOb2RlQmVhbj4gcm9vdHMgPSBuZXcgQXJyYXlMaXN0PD4oKTsKCiAgICAgICAgZm9yIChUcmVlTm9kZUJlYW4gbm9kZSA6IGZsYXRMaXN0KSB7CgogICAgICAgICAgICBTdHJpbmcgcGFyZW50SWQgPSBub2RlLmdldElmdFByZXYoKTsKCiAgICAgICAgICAgIGlmIChwYXJlbnRJZCA9PSBudWxsIHx8IHBhcmVudElkLmlzQmxhbmsoKSB8fCAiMCIuZXF1YWxzKHBhcmVudElkKSkgewoKICAgICAgICAgICAgICAgIHJvb3RzLmFkZChub2RlKTsKCiAgICAgICAgICAgIH0gZWxzZSB7CgogICAgICAgICAgICAgICAgVHJlZU5vZGVCZWFuIHBhcmVudCA9IGxvb2t1cC5nZXQocGFyZW50SWQpOwoKICAgICAgICAgICAgICAgIGlmIChwYXJlbnQgIT0gbnVsbCkgcGFyZW50LmdldENoaWxkcmVuKCkuYWRkKG5vZGUpOwoKICAgICAgICAgICAgICAgIGVsc2Ugcm9vdHMuYWRkKG5vZGUpOyAvLyDmib7kuI3liLDniLbnr4Dpu57lsLHlhYjoppbngrogcm9vdAoKICAgICAgICAgICAgfQoKICAgICAgICB9CgogICAgICAgIHJldHVybiByb290czsKCiAgICB9CgoKCiAgICAvKiog5bu656uLIGlkIOKGkiBub2RlIOeahOe0ouW8le+8iOS5i+W+jOWPlui3r+W+keOAgeaqouaguOmDveacg+eUqOWIsO+8iSAqLwoKICAgIHB1YmxpYyBzdGF0aWMgTWFwPFN0cmluZywgVHJlZU5vZGVCZWFuPiBidWlsZEluZGV4KExpc3Q8VHJlZU5vZGVCZWFuPiBmbGF0TGlzdCkgewoKICAgICAgICBNYXA8U3RyaW5nLCBUcmVlTm9kZUJlYW4+IG1hcCA9IG5ldyBIYXNoTWFwPD4oKTsKCiAgICAgICAgZm9yIChUcmVlTm9kZUJlYW4gbiA6IGZsYXRMaXN0KSBtYXAucHV0KG4uZ2V0SWZ0U2lkKCksIG4pOwoKICAgICAgICByZXR1cm4gbWFwOwoKICAgIH0KCgoKICAgIC8qKiDlvp4gcm9vdCDliLDnlbbliY3nr4Dpu57nmoTjgIxJRCDot6/lvpHjgI3vvJtpbmNsdWRlU2VsZiDmsbrlrprmmK/lkKbljIXlkKvoh6rlt7EgKi8KCiAgICBwdWJsaWMgc3RhdGljIExpc3Q8U3RyaW5nPiBnZXRQYXRoSWRzRnJvbVJvb3QoVHJlZU5vZGVCZWFuIG5vZGUsCgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIE1hcDxTdHJpbmcsIFRyZWVOb2RlQmVhbj4gYnlJZCwKCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYm9vbGVhbiBpbmNsdWRlU2VsZikgewoKICAgICAgICBEZXF1ZTxTdHJpbmc+IHN0YWNrID0gbmV3IEFycmF5RGVxdWU8PigpOwoKICAgICAgICAvLyDlhYjmiornpZblhYjkuIDot6/lvoDkuIrloZ7pgLLliY3pnaIKCiAgICAgICAgU3RyaW5nIHAgPSBub2RlLmdldElmdFByZXYoKTsKCiAgICAgICAgd2hpbGUgKHAgIT0gbnVsbCAmJiAhcC5pc0JsYW5rKCkgJiYgISIwIi5lcXVhbHMocCkpIHsKCiAgICAgICAgICAgIHN0YWNrLmFkZEZpcnN0KHApOwoKICAgICAgICAgICAgVHJlZU5vZGVCZWFuIHBhcmVudCA9IGJ5SWQuZ2V0KHApOwoKICAgICAgICAgICAgaWYgKHBhcmVudCA9PSBudWxsKSBicmVhazsgLy8g6LOH5paZ5LiN5a6M5pW05bCx5YGcCgogICAgICAgICAgICBwID0gcGFyZW50LmdldElmdFByZXYoKTsKCiAgICAgICAgfQoKICAgICAgICAvLyDpnIDopoHmmYLmioroh6rlt7HliqDliLDmnIDlvowKCiAgICAgICAgaWYgKGluY2x1ZGVTZWxmKSBzdGFjay5hZGRMYXN0KG5vZGUuZ2V0SWZ0U2lkKCkpOwoKICAgICAgICByZXR1cm4gbmV3IEFycmF5TGlzdDw+KHN0YWNrKTsKCiAgICB9CgoKCiAgICAvKiog5Y+W44CM5ZCN56ix6Lev5b6R44CN77ya5b6eIHJvb3Qg4oaSIC4uLiDihpIg6Ieq5bex77yI5pa55L6/6aGv56S677yJICovCgogICAgcHVibGljIHN0YXRpYyBMaXN0PFN0cmluZz4gZ2V0UGF0aE5hbWVzRnJvbVJvb3QoVHJlZU5vZGVCZWFuIG5vZGUsCgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgTWFwPFN0cmluZywgVHJlZU5vZGVCZWFuPiBieUlkLAoKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJvb2xlYW4gaW5jbHVkZVNlbGYpIHsKCiAgICAgICAgTGlzdDxTdHJpbmc+IGlkcyA9IGdldFBhdGhJZHNGcm9tUm9vdChub2RlLCBieUlkLCBpbmNsdWRlU2VsZik7CgogICAgICAgIExpc3Q8U3RyaW5nPiBuYW1lcyA9IG5ldyBBcnJheUxpc3Q8PihpZHMuc2l6ZSgpKTsKCiAgICAgICAgZm9yIChTdHJpbmcgaWQgOiBpZHMpIHsKCiAgICAgICAgICAgIFRyZWVOb2RlQmVhbiB4ID0gYnlJZC5nZXQoaWQpOwoKICAgICAgICAgICAgbmFtZXMuYWRkKHggIT0gbnVsbCA/IHguZ2V0RnROYW1lKCkgOiAoIiMiICsgaWQpKTsKCiAgICAgICAgfQoKICAgICAgICByZXR1cm4gbmFtZXM7CgogICAgfQoKCgogICAgLyoqIOaqouaguCBzZnRfcGF0aO+8mlwzODA4XDM4MTFcMzgxM1wg6ZyA562J5pa85a+m6Zqb56WW5YWI6Y+I77yI5LiN5ZCr6Ieq5bex77yJICovCgogICAgcHVibGljIHN0YXRpYyBib29sZWFuIHZhbGlkYXRlU2Z0UGF0aChUcmVlTm9kZUJlYW4gbm9kZSwgTWFwPFN0cmluZywgVHJlZU5vZGVCZWFuPiBieUlkKSB7CgogICAgICAgIC8vIOino+aekOWOn+WniyBwYXRoCgogICAgICAgIExpc3Q8U3RyaW5nPiBleHBlY3RlZCA9IHBhcnNlUGF0aElkcyhub2RlLmdldEZ0UGF0aFJhdygpKTsKCiAgICAgICAgLy8g5a+m6Zqb54i26Y+I77yI5LiN5ZCr6Ieq5bex77yJCgogICAgICAgIExpc3Q8U3RyaW5nPiBhY3R1YWwgPSBnZXRQYXRoSWRzRnJvbVJvb3Qobm9kZSwgYnlJZCwgZmFsc2UpOwoKICAgICAgICByZXR1cm4gZXhwZWN0ZWQuZXF1YWxzKGFjdHVhbCk7CgogICAgfQoKCgogICAgLyoqIOaKiiAiXFwzODA4XFwzODExXFwzODEzXFwiIOino+aekOaIkCBbIjM4MDgiLCIzODExIiwiMzgxMyJd77yb5a655b+N5YmN5b6M5rKS5pyJ5Y+N5pac57eaICovCgogICAgcHVibGljIHN0YXRpYyBMaXN0PFN0cmluZz4gcGFyc2VQYXRoSWRzKFN0cmluZyByYXcpIHsKCiAgICAgICAgaWYgKHJhdyA9PSBudWxsKSByZXR1cm4gTGlzdC5vZigpOwoKICAgICAgICBTdHJpbmcgcyA9IHJhdy50cmltKCk7CgogICAgICAgIGlmIChzLnN0YXJ0c1dpdGgoIlxcIikpIHMgPSBzLnN1YnN0cmluZygxKTsKCiAgICAgICAgaWYgKHMuZW5kc1dpdGgoIlxcIikpIHMgPSBzLnN1YnN0cmluZygwLCBzLmxlbmd0aCgpIC0gMSk7CgogICAgICAgIGlmIChzLmlzRW1wdHkoKSkgcmV0dXJuIExpc3Qub2YoKTsKCiAgICAgICAgcmV0dXJuIEFycmF5cy5hc0xpc3Qocy5zcGxpdCgiXFxcXCIpKTsKCiAgICB9CgoKCiAgICAvKiog57Ch5Zau5Y2w5qi577yI5qqi5p+l55So77yJICovCgogICAgcHVibGljIHN0YXRpYyB2b2lkIHByaW50VHJlZShMaXN0PFRyZWVOb2RlQmVhbj4gbm9kZXMsIGludCBsZXZlbCkgewoKICAgICAgICBmb3IgKFRyZWVOb2RlQmVhbiBuIDogbm9kZXMpIHsKCiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiICAiLnJlcGVhdChsZXZlbCkgKyBuLmdldElmdFNpZCgpICsgIiAiICsgbi5nZXRGdE5hbWUoKSk7CgogICAgICAgICAgICBpZiAobi5nZXRDaGlsZHJlbigpICE9IG51bGwgJiYgIW4uZ2V0Q2hpbGRyZW4oKS5pc0VtcHR5KCkpIHsKCiAgICAgICAgICAgICAgICBwcmludFRyZWUobi5nZXRDaGlsZHJlbigpLCBsZXZlbCArIDEpOwoKICAgICAgICAgICAgfQoKICAgICAgICB9CgogICAgfQoKfQo=