PowerShellで木構造の整形表示コマンドを作った

下記記事が面白そうなのでPowerShellで似たようなのを作ってみた。

* [木構造の整形表示コマンド forest を作った](http://qiita.com/KoharaKazuya/items/b0fe64102421b537b5b4)

実装は[Code](#code)の節を参照のこと。
なお、class構文を使っているのでv5以降でないと動かない。


# 挙動

## 入力ファイル
```sample1.txt
pattern1_root
pattern1_root/pattern2_last_leaf
root_node
root_node/pattern3_non-last_leaf
root_node/pattern3_non-last_leaf/sample
root_node/pattern3_non-last_leaf/pattern4_non-last_node's_child
root_node/leaf_node
```

```sample2.txt
サ
サン
サンプル
forest
forest doesn't specify any characters
forest doesn't specify any characters as separater.
```

## 実行結果

### 通常実行

```
PS C:\demo\tree> cat .\sample1.txt | ConvertTo-Tree | Format-Tree
pattern1_root
└─/pattern2_last_leaf
root_node
├─/pattern3_non-last_leaf
│　├─/sample
│　└─/pattern4_non-last_node's_child
└─/leaf_node

PS C:\demo\tree> cat .\sample2.txt | ConvertTo-Tree | Format-Tree
サ
└─ン
　　└─プル
forest
└─ doesn't specify any characters
　　└─ as separater.

PS C:\demo\tree> 
```

# 枝の表示を変えて実行

```
PS C:\demo\tree> cat .\sample1.txt | ConvertTo-Tree | Format-Tree -e ([EdgeString]::New('+---','`---','|   ','    '))
pattern1_root
`---/pattern2_last_leaf
root_node
+---/pattern3_non-last_leaf
|   +---/sample
|   `---/pattern4_non-last_node's_child
`---/leaf_node

PS C:\demo\tree> 
```

# 空のRootに集約して実行

```
PS C:\demo\tree> cat .\sample1.txt | ConvertTo-Tree | % {$r = [TreeNode]::New('')} {$r.AddChild($_)} {$r} | Format-Tree

├─pattern1_root
│　└─/pattern2_last_leaf
└─root_node
　　├─/pattern3_non-last_leaf
　　│　├─/sample
　　│　└─/pattern4_non-last_node's_child
　　└─/leaf_node

PS C:\demo\tree> cat .\sample1.txt | ConvertTo-Tree | % {$r = [TreeNode]::New('')} {$r.AddChild($_)} {$r} | Format-Tree -e ([EdgeString]::New('+ ','+ ',"`t","`t"))

+ pattern1_root
	+ /pattern2_last_leaf
+ root_node
	+ /pattern3_non-last_leaf
		+ /sample
		+ /pattern4_non-last_node's_child
	+ /leaf_node

PS C:\demo\tree> 
```

# Code

下記パラメータに適当なスクリプトブロックを与えると、親子判定、Rootの表示、Root以外のNodeの表示を好きにイジれる。

* `ConvertTo-Tree -IsChild {...}`
* `Format-Tree -RootFromat {...}`
* `Format-Tree -ChildFromat {...}`


```.ps1
class TreeNode
{
    [System.Object] $Data
    [System.Collections.ArrayList] $Children

    TreeNode ([System.Object] $Data)
    {
        $this.Data = $Data
        $this.Children = New-Object System.Collections.ArrayList
    }

    [void] AddChild ([TreeNode] $Child)
        {[void] $this.Children.Add($Child)}


}

class EdgeString {
    [System.String] $Child
    [System.String] $LastChild
    [System.String] $Descendant
    [System.String] $LastDescendant

    EdgeString (
        [System.String] $Child,
        [System.String] $LastChild,
        [System.String] $Descendant,
        [System.String] $LastDescendant
    )
    {
        $this.Child          = $Child
        $this.LastChild      = $LastChild
        $this.Descendant     = $Descendant
        $this.LastDescendant = $LastDescendant
    }
}

function ConvertTo-Tree
{
    Param
    (
        [Parameter(Mandatory=$true, ValueFromPipeline=$true)]
        $InputObject,

        [ValidateNotNullOrEmpty()]
        [scriptblock] $IsChild = {$_[1].ToString().StartsWith($_[0].ToString())}
    )

    Begin
    {
        $stack = New-Object System.Collections.Stack
    }

    Process
    {
        $node = [TreeNode]::New($InputObject)

        while ($true)
        {
            if ($stack.Count -eq 0)
            {
                $stack.Push($node)
                break
            }

            $peek = $stack.Peek()
            $isC = ,@($peek.Data, $node.Data) | ForEach-Object $IsChild
            if ($isC)
            {
                $peek.AddChild($node)
                $stack.Push($node)
                break
            }

            if ($stack.Count -gt 1)
                {[void] $stack.Pop()}
            else
                {$stack.Pop()}
        }

    }

    End
    {
        while ($stack.Count -gt 1)
            {[void] $stack.Pop()}

        if ($stack.Count -eq 1)
            {return $stack.Pop()}
    }
}

function Format-Tree
{
    Param
    (
        [Parameter(Mandatory=$true, ValueFromPipeline=$true)]
        [TreeNode] $Tree,

        [ValidateNotNullOrEmpty()]
        [scriptblock]$RootFromat = {$_.ToString()},

        [ValidateNotNullOrEmpty()]
        [scriptblock]$ChildFromat = {$_[1].ToString().SubString($_[0].ToString().Length)},

        [ValidateNotNullOrEmpty()]
        [EdgeString] $EdgeString = [EdgeString]::New("├─", "└─", "│　", "　　")
    )
    
    Begin { 
        function writeChild ($stack)
        {
            $str = New-Object "System.Collections.Generic.Stack[string]" 

            $child, $parent = $stack | ForEach-Object {$_[0].Data} | Select-Object -First 2
            $str.Push((,@($parent, $child) | ForEach-Object $ChildFromat))
            
            $stack |
                Select-Object -Skip 1 -First 1 |
                ForEach-Object {
                    $node, $count = $_
                    if ($node.Children.Count -eq $count)
                        {$str.Push(($EdgeString.LastChild))}
                    else
                        {$str.Push(($EdgeString.Child))}
                }

            $stack |
                Select-Object -Skip 2 |
                ForEach-Object {
                    $node, $count = $_
                    if ($node.Children.Count -eq $count)
                        {$str.Push(($EdgeString.LastDescendant))}
                    else
                        {$str.Push(($EdgeString.Descendant))}
                }

            -join $str
        }
    }

    Process
    {
        $stack = New-Object "System.Collections.Stack"

        $stack.Push(@($Tree, 0))
        $Tree.Data | ForEach-Object $RootFromat

        while ($stack.Count -gt 0)
        {
            $node, $count = $stack.Pop()
            if ($node.Children.Count -le $count)
                {continue}

            $stack.Push(@($node, ($count + 1)))
            $stack.Push(@($node.Children[$count], 0))
            writeChild $stack
        }
    }
}
```