[topic] フォルダパス一覧のツリー構造への変換
Posted feedbacks - Flatten
Nested 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)
|
ファイルパスの分解には，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 で。
mamamoto さんの #4473 に感じ入ったあとでは、#groupBy:having: を便利に使っているつもりが使われてしまっているみたいでダメダメですね(^_^;)。
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
"
|
これはすばらしい！
感動したので、Squeak Smalltalk に意訳させていただきました。
感動したので、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
"
|
素直に再帰関数で実装しました。
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に表示させてみました。
see: 貧脚レーサーのサボり日記
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に書き換え。
see: 貧脚レーサーのサボり日記
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
|
matyr
#4491()
[
JavaScript
]
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));
}
}
|
ocean
#5087()
[
JavaScript
]
とりあえず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>
|
モジュール変数をツリー構造に使用しています。
see: モジュール変数でツリー ( Fuji Diablog )
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 );
|
todogzm
#4458()
Rating1/1=1.00
フォルダパスの区切り文字は'\'文字を使用しています。
以下のような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でグラフィカルな結果を表示するプログラムでも構いませんが、データ構造はちゃんと作ってください。
[ reply ]