将定界文件转换为树

java list sorting treeset delimited

387 观看

2回复

我正在将定界文件转换为有序的树结构。以下是输入示例...

1.2.3.4.5
1.3.2.4.5
1.2.4.5.6

我需要能够将其转换为如下所示的输出(在可搜索树结构中)...

1
-2
--3
---4
----5
--4
---5
----6
-3
--2
---4
----5

我对解决方案的想法是...

  1. 迭代文本文件并创建一个代表每行的arraylist
  2. 使用Collections.sort()使arraylist排序
  3. 使用TreeMap将“基本”记录存储为键(在本例中为1)和包含所有记录的字符串arrayList
  4. 迭代TreeMap的键,并将其arrayList转换为LinkedHashSet,该LinkedHashSet包含代表每个条目的Node
  5. 迭代树的键并打印每个节点购买其索引值

我以为一切都很好,但是当我开始测试这种方法时,我发现我的输出如下图所示。

1
-2
--3
---4
----5
--4
---5
----6
-3
--2

可以看出,不存在低于3/2 / xx的节点,这是由于我用于为Node值(Node(3,4))构建LinkedHashSet的逻辑将被忽略,因为其重复项节点。我以为我朝着正确的方向前进,但现在我可以看到我的逻辑显然有缺陷。有人对这种方法有任何建议吗?我当前的代码如下...

TreeBuilder.java

public class TreeBuilder {

 public static void main(String[] args) {

    // Get a list of records
    List<String> data = new ArrayList<String>();
    data.add("1.2.3.4.5");
    data.add("1.3.2.4.5");
    data.add("1.2.4.5.6");

    Collections.sort(data);

    // Build the "Base" tree
    TreeMap<String, List<String>> tree = buildBaseTree(data);

    // Build the target tree structure
    TreeMap<String, LinkedHashSet<Node>> finalTree = convertListToSet(tree);

    printRecords(finalTree);

 }

 public static void printRecords(
        TreeMap<String, LinkedHashSet<Node>> recordTree) {

    System.out.println("---------Records---------");

    for (Map.Entry<String, LinkedHashSet<Node>> entry : recordTree
            .entrySet()) {

        System.out.println(entry.getKey());

        // Print out the structured data
        StringBuilder stringBuilder = new StringBuilder();
        Iterator<Node> iterator = entry.getValue().iterator();
        while (iterator.hasNext()) {

            Node node = iterator.next();
            for (int i = 0; i < node.index; i++) {
                stringBuilder.append("-");
            }

            System.out.println(stringBuilder.toString() + node.value);

            // "reset" the builder
            stringBuilder.setLength(0);
        }
    }

 }

 private static TreeMap<String, LinkedHashSet<Node>> convertListToSet(
        TreeMap<String, List<String>> tree) {

    TreeMap<String, LinkedHashSet<Node>> finalMap = new TreeMap<String, LinkedHashSet<Node>>();
    LinkedHashSet<Node> linkedHashSet = new LinkedHashSet<Node>();

    // Iterate the entry set
    for (Map.Entry<String, List<String>> entry : tree.entrySet()) {

        List<String> records = entry.getValue();
        for (String record : records) {
            String[] recordArray = record.split("\\.");

            for (int i = 1; i < recordArray.length; i++) {
                Node node = new Node(i, Integer.parseInt(recordArray[i]));
                linkedHashSet.add(node);
            }
        }

        finalMap.put(entry.getKey(), linkedHashSet);

        // reset our linkedHashSet
        linkedHashSet = new LinkedHashSet<Node>();

    }

    System.out.println("Final map " + finalMap);

    return finalMap;
 }

 /**
  * Builds a tree with base record keys and a list of records for each key.
  * 
  * @param data
  * @return
  */
 private static TreeMap<String, List<String>> buildBaseTree(List<String> data) {

    TreeMap<String, List<String>> tree = new TreeMap<String, List<String>>();
    List<String> recordList = null;

    // First find all base records
    for (String record : data) {

        String[] baseEntry = record.split("\\.");
        if (!tree.containsKey(baseEntry[0])) {
            recordList = new ArrayList<String>();
            tree.put(baseEntry[0], recordList);
        }
    }

    // Now place all sub-records in each base record
    for (String record : data) {

        String[] baseEntry = record.split("\\.");
        tree.get(baseEntry[0]).add(record);
    }

    System.out.println("------------------Base Tree---------------");
    System.out.println(tree);
    System.out.println("------------------------------------------");

    return tree;
 }

 private static List<String> readData(String file) {

    BufferedReader bufferedReader = null;
    try {
        bufferedReader = new BufferedReader(new FileReader(new File(file)));
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    }
    List<String> data = new ArrayList<String>();

    // Get a list of all the records
    String line = null;
    try {
        while ((line = bufferedReader.readLine()) != null) {
            data.add(line);
        }
    } catch (IOException e) {
        e.printStackTrace();
    }

    // Sort the list so its ordered
    System.out.println("-------------Sorted Data Set-----------");
    Collections.sort(data);
    for (String record : data) {
        System.out.println(record);
    }
    System.out.println("---------------------------------------");

    return data;
 }
}

Node.java

public class Node implements Comparable<Node> {

 int index;
 int value;

 public Node(int index, int value) {
    this.index = index;
    this.value = value;
 }

 public int getIndex() {
    return index;
 }

 @Override
 public String toString() {
    return "Node [index=" + index + ", value=" + value + "]";
 }

 public void setIndex(int index) {
    this.index = index;
 }

 public int getValue() {
    return value;
 }

 public void setValue(int value) {
    this.value = value;
 }

 @Override
 public int compareTo(Node o) {

    Node otherNode = (Node) o;

    if (this.index > otherNode.index)
        return 1;

    if (this.index < otherNode.index) {
        return -1;
    }

    return 0;
 }

 @Override
 public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + index;
    result = prime * result + value;
    return result;
 }

 @Override
 public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Node other = (Node) obj;
    if (index != other.index)
        return false;
    if (value != other.value)
        return false;
    return true;
 }

}
作者: Jason 的来源 发布者: 2019 年 10 月 21 日

回应 (2)


1

决定

不必太复杂。所有你需要的是一个SortedMapSortedMap情况下,有只有一个窍门是:递归是参数化类型安全(如果需要)。

package com.acme;

import java.util.ArrayList;
import java.util.List;
import java.util.Map.Entry;
import java.util.TreeMap;

public class Main {

    public static void main(String[] args) {
        List<String> rows = new ArrayList<>();
        rows.add("1.2.3.4.5");
        rows.add("1.3.2.4.5");
        rows.add("1.2.4.5.6");

        MyTreeMap root = new MyTreeMap();
        for (String row : rows) {
            MyTreeMap n = root;
            String[] cells = row.split("\\.");
            for (String cell : cells) {
                MyTreeMap child = n.get(cell);
                if (child == null) {
                    n.put(cell, child = new MyTreeMap());
                }
                n = child;
            }
        }

        print(root, "", "-");
    }

    static void print(MyTreeMap m, String indentationStr, String indentationStrAddition) {
        for (Entry<String, MyTreeMap> o : m.entrySet()) {
            System.out.println(indentationStr + o.getKey());
            print(o.getValue(), indentationStr + indentationStrAddition, indentationStrAddition);
        }
    }

    /**
     * This is just a construct that helps us to parameterize recursively.
     */
    static class MyTreeMap extends TreeMap<String, MyTreeMap> {private static final long serialVersionUID = 1L;}
}
作者: Brian 发布者: 15.02.2016 10:17

0

如果我了解您的问题,则想从共享公用前缀的整数列表中创建搜索树。如果是这种情况,那么我认为您可以用更少的代码来实现:

private static class TreeNode {

    private final Map<Integer, TreeNode> children = new HashMap<>();

    public void insert(List<Integer> values) {
        if (!values.isEmpty()) {
            children.putIfAbsent(values.get(0), new TreeNode());
            children.get(values.get(0)).insert(values.subList(1, values.size()));
        }
    }

    public void print(int level) {
        for (Map.Entry<Integer, TreeNode> entry : children.entrySet()) {
            System.out.print(String.join("", Collections.nCopies(level, "-")));
            System.out.println(entry.getKey());
            entry.getValue().print(level + 1);
        }
    }
}

我不确定您是否打算对整数列表进行排序。如果是这样,您可以Collections.sort在代码中的适当位置添加一个。

作者: sprinter 发布者: 16.02.2016 01:47
32x32