[topic] フォルダパス一覧のツリー構造への変換

(相対)フォルダのパスの一覧が与えられ、そのフォルダパスの一覧をツリー構造に変換してください。
フォルダパスの区切り文字は'\'文字を使用しています。

以下のような1行1パスのフォルダのパスがあった場合、
 abc\def
 abc\def\gh
 abc\def\ij
 abc\jk\lm
 de

イメージとして、以下のようなツリー構造を構築できればOKです。
 ROOT
 ┗abc
  ┗def
   ┗gh
   ┗ij
  ┗jk
   ┗lm
 ┗de

ツリーですのでルートがあります。上記のフォルダ一覧はルート以下にぶら下げてください。また、同じフォルダにぶら下がっているサブフォルダの名前は重複させてはいけません。

上記のような出力は結果の分かりやすさとしてあった方がいいですが、なければないで構いません。また、ASやJavaFXでグラフィカルな結果を表示するプログラムでも構いませんが、データ構造はちゃんと作ってください。

Posted feedbacks - Nested

Flatten Hidden

C#で素直に実装してみました。

 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
using System;
using System.Collections;
using System.Text;

class Sample102
{
    private readonly IDictionary dirTree_ = new SortedList();

    public Sample102(string[] pathList) {
        createTree(pathList);
    }
    private void createTree(string[] pathList) {
        foreach (string path in pathList) {
            string[] dirs = path.Split('\\');
            addTree(dirs);
        }
    }
    private void addTree(string[] dirs) {
        IDictionary prevDict = dirTree_;
        for (int index = 0; index < dirs.Length; index++) {
            IDictionary dict = prevDict[dirs[index]] as IDictionary;
            if (dict == null) {
                dict = new SortedList();
                prevDict[dirs[index]] = dict;
            }
            prevDict = dict;
        }
    }

    public void printTree() {
        Console.WriteLine(printTree(0, "", dirTree_));
    }
    private string printTree(int depth, string name, IDictionary innerDir) {
        StringBuilder builder = new StringBuilder();
        for (int index = 0; index < depth; index++) builder.Append("  ");
        builder.Append('/');
        builder.Append(name);
        builder.Append('\n');

        foreach (string dir in innerDir.Keys) {
            builder.Append(printTree(depth + 1, dir, innerDir[dir] as IDictionary));
        }
        return builder.ToString();
    }


    [STAThread]
    static void Main(string[] args) {
        string[] pathList = new string[] {
                 @"abc\def",
                 @"abc\def\gh",
                 @"abc\def\ij",
                 @"abc\jk\lm",
                 @"de",
            };

        Sample102 pathTree = new Sample102(pathList);
        pathTree.printTree();
        Console.ReadLine();
    }
}
擬似lsの実装は実はデータ構造の話を次にもってこようかなぁと思ってたりしていた。

一応10分くらいで実装してみた。
辞書型を使って処理してみる。

以下実行結果
-----------
 abc
  def
   gh
   ij
  jk
   lm
 azc
  def
 de
 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
#-*- coding: utf-8 -*-

pathList = [
"azc\\def",
"abc\\def",
"abc\\def\\gh",
"abc\\def\\ij",
"abc\\jk\\lm",
"de"]

tree = {}
for path in pathList:
    temp = tree
    for dir in path.split("\\"):
        if not temp.has_key(dir):
            temp[dir] = {}
        temp = temp[dir]
def printTree(tree, nest):
    keyList = tree.keys()
    keyList.sort()
    for key in keyList:
        print " "*nest,key
        if len(tree[key].keys()):
            printTree(tree[key], nest+1)
            
printTree(tree,0)
dirが色が付いてると思ったら、組み込み関数なのかこれ。
知らなかった・・・。
ファイルパスの分解には,System.FilePath.Windows モジュールの splitPath
を用いる.Unix系ファイルシステム流の'/'の場合は System.FilePath.Unixを
用いればよい.

ツリーの構築と表示には Data.Tree モジュール unfoldTree および drawTree
をそれぞれ用いる.

実行例:
*Main> putStrLn $ drawTree $ buildFS pathList
ROOT
|
+- abc
|  |
|  +- def
|  |  |
|  |  +- gh
|  |  |
|  |  `- ij
|  |
|  `- jk
|     |
|     `- lm
|
`- de
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
import Data.List
import Data.Tree
import System.FilePath.Windows

binapp o f x y = f x `o` f y

type FS = Tree FilePath

buildFS :: [String] -> FS
buildFS = Node "ROOT" . map buildDir . groupPath . map splitPath . sort

buildDir :: (FilePath,[[FilePath]]) -> FS
buildDir = unfoldTree phi
 where phi (n,ps) = (delete pathSeparator n, groupPath $ filter (not . null) ps)

groupPath :: [[FilePath]] -> [(FilePath,[[FilePath]])]
groupPath = map grouping . groupBy (binapp eqpath head)
  where grouping ss = (head . head $ ss, map tail ss)
        eqpath      = binapp (==) (fst . break (pathSeparator==))

pathList = ["abc\\def","abc\\def\\gh","abc\\def\\ij","abc\\jk\\lm","de"]

作成はちょっと変則的なinjectと破壊的作用の組み合わせでハッシュでツリーを。

表示は素直な再帰で。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
path_list = %w(
abc\\def
abc\\def\\gh
abc\\def\\ij
abc\\jk\\lm
de
)

def dump_tree(h, pad="")
  h.sort_by{|k,v| k}.each{|k,v|
    print(pad, "┗", k, "\n")
    dump_tree(v, pad+"  ")
  }
end

h = {}
path_list.each{|path|
  path.split(/\\/).inject(h){|k,v|
    k[v] ||= {}
  }
}

dump_tree(h)
これはすばらしい!

感動したので、Squeak Smalltalk に意訳させていただきました。
 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
| pathList tree dumpTree |
pathList := #('abc\def' 'abc\def\gh' 'abc\def\ij' 'abc\jk\lm' 'de').

tree := Dictionary new.
pathList do: [:path |
    (path subStrings: #($\)) inject: tree into: [:tr :dir |
        tr at: dir ifAbsentPut: [Dictionary new]]].

dumpTree := [:tr :lev |
    tr keys asSortedCollection do: [:key |
        Transcript crtab: lev; show: key.
        (tr at: key) ifNotEmptyDo: [:child |
            dumpTree copy fixTemps value: child value: lev + 1]]].

World findATranscript: nil.
dumpTree copy fixTemps value: tree value: 0

"=>
abc
    def
        gh
        ij
    jk
        lm
de
"
Squeak Smalltalk で。

mamamoto さんの #4473 に感じ入ったあとでは、#groupBy:having: を便利に使っているつもりが使われてしまっているみたいでダメダメですね(^_^;)。
 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
| genTree printTree pathList tree |
genTree := [:paths |
    | leaf |
    leaf := paths groupBy: [:path | path first] having: [:g | true].
    leaf associationsDo: [:assoc |
        | newValue |
        newValue := assoc value
            collect: [:val | val allButFirst] thenSelect: [:val | val notEmpty].
        assoc value: (newValue isEmpty
            ifTrue: [newValue]
            ifFalse: [genTree copy fixTemps value: newValue])]].

printTree := [:dic :lev |
    dic keys asSortedCollection do: [:key |
        Transcript crtab: lev; show: key.
        (dic at: key) ifNotEmptyDo: [:child |
            printTree copy fixTemps value: child value: lev + 1]]].

pathList := #('abc\def' 'abc\def\gh' 'abc\def\ij' 'abc\jk\lm' 'de').
pathList := pathList collect: [:each | each subStrings: {$\}].

World findATranscript: nil.
tree := genTree copy fixTemps value: pathList.
printTree copy fixTemps value: tree value: 0

"=>
abc
    def
        gh
        ij
    jk
        lm
de
"

素直に再帰関数で実装しました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
# encoding: utf-8
list = [ "abc\\def", "abc\\def\\gh", "abc\\def\\ij", "abc\\jk\\lm", "de" ]

def pathtree(lst):
  def maketree(l):
    s = [x for x in set([v[0] for v in l])]
    s.sort()
    return [[v, maketree([x[1:] for x in l if x[0]==v and len(x)>1])] for v in s]
  return ["ROOT", maketree([s.split("\\") for s in list])]

def printtree(tree):
  def printchild(tree, nest):
    for c in tree:
      if c==[]: continue
      print " "*nest*2 + "┗" + c[0]
      printchild(c[1], nest+1)
  print tree[0]
  printchild(tree[1], 0)

printtree(pathtree(list))

System.Windows.FormsのTreeViewに表示させてみました。

 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
//http://ja.doukaku.org/
//http://ja.doukaku.org/102/投稿用
using System;
using System.Windows.Forms;

namespace どう書く_orgフォルダパス一覧のツリ構造への変換 {
    class Program {
        [STAThread]
        static void Main(string[] args) {
            Application.Run(new Form1());
        }
    }

    class Form1:Form {
        //treeView1
        TreeView treeView1 = new TreeView();

        //起動時引数でパス一覧のファイルを指定
        string pathListFilePath = System.Environment.GetCommandLineArgs()[1];

        public Form1() {
            //Form1
            this.Load += new EventHandler(Form1_Load);
            //treeView1
            treeView1.Parent = this;
            treeView1.Dock = DockStyle.Fill;
        }

        void Form1_Load(object sender, EventArgs e) {
            //ROOTNode
            TreeNode rootNode = new TreeNode("ROOT");
            treeView1.Nodes.Add(rootNode);

            foreach(string fullPath in System.IO.File.ReadAllLines(pathListFilePath)) {
                TreeNode addNode = rootNode;
                foreach(string path in fullPath.Split(new char[] { '\\' })) {
                    bool flag = true;
                    foreach(TreeNode node in addNode.Nodes) {
                        if(node.Text == path) {
                            addNode = node;
                            flag = false;
                        }
                        
                    }
                    if(flag) {
                        TreeNode newnode = new TreeNode(path);
                        addNode.Nodes.Add(newnode);
                        addNode = newnode;
                    }
                }
            }
            rootNode.ExpandAll();
        }
    }
}

VB.NETに書き換え。

 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
'http://ja.doukaku.org/
'http://ja.doukaku.org/102/投稿用
Imports System
Imports System.Windows.Forms

NameSpace どう書く_orgフォルダパス一覧のツリー構造への変換
    Class Program
        <STAThread> _
        Shared Sub Main(byval args() As String)
            Application.Run(new Form1())
        End Sub
    End Class

    class Form1:Inherits Form
        'treeView1
        Dim treeView1 As TreeView = New TreeView()

        '起動時引数でパス一覧のファイルを指定
        Dim pathListFilePath As String = System.Environment.GetCommandLineArgs()(1)

        Public Sub New()
            'treeView1
            treeView1.Parent = Me
            treeView1.Dock = DockStyle.Fill
        End Sub

        Private Sub Form1_Load(byval sender As object, byval e As EventArgs)handles Me.Load
            'ROOTNode
            Dim rootNode As TreeNode = New TreeNode("ROOT")
            treeView1.Nodes.Add(rootNode)

            For Each fullPath As String In System.IO.File.ReadAllLines(pathListFilePath)
                Dim addNode As TreeNode = rootNode
                For Each path As String In fullPath.Split(New char(){"\"c})
                    Dim flag As Boolean = True
                    For Each node As TreeNode in addNode.Nodes
                        If node.Text = path Then
                            addNode = node
                            flag = False
                        End If
                    Next
                    if flag Then
                        Dim newnode As TreeNode = New TreeNode(path)
                        addNode.Nodes.Add(newnode)
                        addNode = newnode
                    End If
                Next
            Next
            rootNode.ExpandAll()
        End Sub
    End Class
End NameSpace
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function doukaku102(lst, sep){ sep || (sep = '/');
  for(var out = [sep], root = {}, rgx = RegExp(sep), mktree = function(tree, path){
    path && rgx.test(path)
      ? mktree(tree[RegExp.leftContext] || (tree[RegExp.leftContext] = {}), RegExp.rightContext)
      : tree[path] = null;
  }, i = 0, l = lst.sort().length; i < l; i++) mktree(root, lst[i]);
  (function ptree(tree, tab){
    for(var dir in tree) out[out.length] = tab +'┗'+ dir, tree[dir] && ptree(tree[dir], tab +' ');
  })(root, '');
  return out.join('\n');
}

「データ構造を作成する」という条件に合うか微妙ですが、DefaultMutableTreeNodeを自分で操作してるので、いいよね。(なお、ノードはソートされません)

 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
import java.io.*;
import java.util.*;
import javax.swing.*;
import javax.swing.tree.*;

class MeApp {
    public static void main(String[] args) throws Exception {
        final DefaultMutableTreeNode root = new DefaultMutableTreeNode("ROOT");
        final BufferedReader r = new BufferedReader(new FileReader(args[0]));
        try {
            String path;
            while ((path = r.readLine()) != null) {
                DefaultMutableTreeNode node = root;
                for (String name : path.split("\\\\")) {
                    node = getChild(node, name);
                }
            }
        } finally {
            r.close();
        }
        SwingUtilities.invokeLater(new Runnable(){
            public void run() {
                final MeFrame frame = new MeFrame(root);
                frame.setDefaultCloseOperation(MeFrame.EXIT_ON_CLOSE);
                frame.pack();
                frame.setVisible(true);
            }
        });
    }

    private static DefaultMutableTreeNode getChild(DefaultMutableTreeNode parent, String name) {
        final Enumeration e = parent.children();
        while (e.hasMoreElements()) {
            final DefaultMutableTreeNode child = (DefaultMutableTreeNode)e.nextElement();
            if (child.getUserObject().equals(name)) {
                return child;
            }
        }
        final DefaultMutableTreeNode child = new DefaultMutableTreeNode(name);
        parent.add(child);
        return child;
    }
}

class MeFrame extends JFrame {
    public MeFrame(TreeNode root) {
        final JTree tree = new JTree(root);
        for (int i = 0; i < tree.getRowCount(); ++i) { // expand all
            tree.expandRow(i);
        }
        setContentPane(new JScrollPane(tree));
    }
}

とりあえずIE6とFirefox2(Win)で動作を確認。

 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
<html>
<head>
<script type="text/javascript">
<!--

function traverse(parentDict, parentNode, text)
{
    parentNode.appendChild(document.createTextNode(text));

    var ul = parentNode.appendChild(document.createElement("ul"));

    for (var name in parentDict)
    {
        var li = ul.appendChild(document.createElement("li"));

        traverse(parentDict[name], li, name);
    }
}

function create()
{
    var text = document.getElementById("textarea").value.replace("\r", "");

    var dict = [];

    var pathes = text.split("\n");

    for (var i = 0; i < pathes.length; ++i)
    {
        var node = dict;

        var names = pathes[i].split("\\");

        for (var j = 0; j < names.length; ++j)
        {
            var name = names[j];

            if (name in node)
            {
                node = node[name];
            }
            else
            {
                node = node[name] = [];
            }
        }
    }

    var div = document.getElementById("div");

    if (div.firstChild)
    {
        div.removeChild(div.firstChild);
    }

    var ul = div.appendChild(document.createElement("ul"));

    var li = ul.appendChild(document.createElement("li"));

    traverse(dict, li, "ROOT");
}

-->
</script>
</head>
<body>
<div><textarea id="textarea" rows="10" cols="50"></textarea></div>
<div><input type="button" value="Create tree" onclick="create()"></input></div>
<div id="div"></div>
</body>
</html>
モジュール変数をツリー構造に使用しています。
 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
#module m_tree children, content

#modinit str _content
#define global new_tree( %1, %2 = "" ) newmod %1, m_tree, %2
    content = _content
    dimtype children, 5, 1
    return

#defcfunc get_tree_content modvar m_tree@
    return content

#modfunc get_tree_child str _content, var result
    f = -1
    foreach children
        if get_tree_content( children.cnt ) != _content : continue
        f = cnt
        break
    loop
    if f >= 0 : result = children.f : return
    new_tree children, _content
    result = children( length(children) - 1 )
    return

#modfunc _show_tree str indent
#define global show_tree( %1, %2 = "" ) _show_tree %1, %2
    if indent == "" {
        mes content
    } else {
        mes indent + "┗" + content
    }
    foreach children
        show_tree children.cnt, indent + "  "
    loop
    return

#global

paths = {"
    abc\\def
    abc\\def\\gh
    abc\\def\\ij
    abc\\jk\\lm
    de"}

new_tree tree, "ROOT"
paths_index = 0
repeat
    getstr path, paths, paths_index
    if strsize == 0 : break
    paths_index += strsize
    t = tree
    path_index = 0
    repeat
        getstr v, path, path_index, '\\'
        if strsize == 0 : break
        path_index += strsize
        get_tree_child t, v, t
    loop
loop

show_tree tree
  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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node {
    char *content;
    int content_size;
    struct Node **children;
    int children_size;
    int num_children;
};

struct Node *new_node( char *content );
struct Node *add_node_child( struct Node *node, char *content );
struct Node *search_node_child( struct Node *node, char *content );
void dump_node( struct Node *node );
void delete_node( struct Node *node );

int main() {
    int size = 32;
    char *dirname;
    int index = 0;
    int c;
    struct Node *tree;
    struct Node *t;
    tree = new_node( "ROOT" );
    dirname = malloc( size );
    if( tree == 0 || dirname == 0 ) {
        goto error;
    }
    t = tree;
    while( ( c = getchar() ) != -1 ) {
        struct Node *new_t;
        switch( c ) {
        case '\\':
        case '\n':
            dirname[index] = 0;
            index = 0;
            new_t = search_node_child( t, dirname );
            if( new_t == 0 ) {
                new_t = add_node_child( t, dirname );
            }
            if( new_t == 0 ) {
                goto error;
            }
            t = new_t;
            if( c == '\n' ) {
                t = tree;
            }
            break;
        default:
            if( size <= index + 1 ) {
                int new_size = size + 32;
                char *new_dirname = realloc( dirname, size );
                if( new_dirname == 0 ) {
                    goto error;
                }
                size = new_size;
                dirname = new_dirname;
            }
            dirname[index] = c;
            index++;
        }
    }
    free( dirname );
    dump_node( tree );
    delete_node( tree );
    return EXIT_SUCCESS;
error:
    fprintf( stderr, "No Memory\n" );
    exit( EXIT_FAILURE );
}

struct Node *new_node( char *content ) {
    struct Node *node = malloc( sizeof( struct Node ) );
    if( node == 0 ) {
        return 0;
    }
    node->content_size = strlen( content ) + 1;
    node->content = malloc( node->content_size );
    if( node->content == 0 ) {
        free( node );
        return 0;
    }
    strcpy( node->content, content );
    node->children_size = 1;
    node->num_children = 0;
    node->children = calloc( node->children_size, sizeof( struct Node ) );
    if( node->children == 0 ) {
        free( node );
        return 0;
    }
    return node;
}

struct Node *add_node_child( struct Node *node, char *content ) {
    struct Node *child_node = 0;
    int new_num_children = node->num_children + 1;
    if( node->children_size < new_num_children ) {
        struct Node **new_children;
        new_children = realloc( node->children, new_num_children * sizeof( struct Node ) );
        if( new_children == 0 ) {
            return 0;
        } else {
            node->children = new_children;
            node->children_size = new_num_children;
        }
    }
    child_node = new_node( content );
    if( child_node == 0 ) {
        return 0;
    }
    node->children[node->num_children] = child_node;
    node->num_children = new_num_children;
    return child_node;
}

struct Node *search_node_child( struct Node *node, char *content ) {
    int i;
    for( i = 0; i < node->num_children; i++ ) {
        struct Node *child = node->children[i];
        if( strcmp( child->content, content ) == 0 ) {
            return child;
        }
    }
    return 0;
}

void dump_node_iter( struct Node *node, int level ) {
    int i;
    if( level != 0 ) {
        for( i = 0; i < level; i++ ) {
            printf( "  " );
        }
        printf( "┗" );
    }
    printf( "%s\n", node->content );
    for( i = 0; i < node->num_children; i++ ) {
        dump_node_iter( node->children[i], level + 1 );
    }
}

void dump_node( struct Node *node ) {
    dump_node_iter( node, 0 );
}

void delete_node( struct Node *node ) {
    int i = 0;
    for( i = 0; i < node->num_children; i++ ) {
        delete_node( node->children[i] );
    }
    free( node->children );
    free( node->content );
    free( node );
}

訂正。

1
2
3
4
54c54
<                 char *new_dirname = realloc( dirname, size );
---
>                 char *new_dirname = realloc( dirname, new_size );

Index

Feed

Other

Link

Pathtraq

loading...