Redmineのプロジェクトの並びが気に入らないという話なのにHaskell書いてた

Redmineを使おうと思ってセットアップしてみたんですけど、なんか、プロジェクトのソート順が気に食わないというか。
プロジェクト1, 2, 3があって、そのサブプロジェクトがそれぞれあって、

1.
        1-1
        1-2
        1-3
2.
        2-1
        2-2
3.
        3-1
        3-2

という風に、当たり前のように並んでほしいんですが、なんかそうはいかないというか。プロジェクトの登録順が影響しているのかなんなのか、プロジェクト1,2,3の並びかえができないしちゃんと並んでくれないし、サブプロジェクトも1-1,1-2,1-3なんて素直にならんでくれるわけじゃない。色々プロジェクトの設定をいじってみたけど、それで順序が変わってくれるわけじゃない。
こういうところでケチがついてRedmineやめましょうとかなるのが一番つまらない。なんとかせねば。いやよく文句言うのは私ですけど。
で、テキトウにググってみると、この点で悩んでいる人はいなくはないっぽい。けど解決してる人がいるわけでもないし、pluginとかがあるわけでもないっぽい。そんなに真面目に調べてないけど。

ということで、この順序が何に依存して決まっているのか調べてみました。Rubyだし、Railsだし、いざとなったら読めるってのは助かりますね。やっててよかったRuby on Rails。
Redmineのバージョンは1.3-stableです。
http://redmine.rubyforge.org/svn/branches/1.3-stable/

app/controllers/projects_controller.rb

 47   # Lists visible projects
 48   def index
 49     respond_to do |format|
 50       format.html {
 51         @projects = Project.visible.find(:all, :order => 'lft')
 52       }

このあたりをざっと見てみると、まずDBっていうかモデルから取り出す時にlftってカラムでソートしてる。

で、実際に表示している部分を見てみると、
app/views/projects/index.html.erb

 13 
 14 <%= render_project_hierarchy(@projects)%>
 15 

ここで一覧を描画してるっぽい。っていうかしてる。

じゃあ次、HTMLの組立ルーチン。
app/helpers/projects_helper.rb

 54   # Renders a tree of projects as a nested set of unordered lists
 55   # The given collection may be a subset of the whole project tree
 56   # (eg. some intermediate nodes are private and can not be seen)
 57   def render_project_hierarchy(projects)
 58     s = ''
 59     if projects.any?
 60       ancestors = []
 61       original_project = @project
 62       projects.each do |project|
 63         # set the project environment to please macros.
 64         @project = project
 65         if (ancestors.empty? || project.is_descendant_of?(ancestors.last))
 66           s << "<ul class='projects #{ ancestors.empty? ? 'root' : nil}'>\n"
 67         else
 68           ancestors.pop
 69           s << "</li>"
 70           while (ancestors.any? && !project.is_descendant_of?(ancestors.last))
 71             ancestors.pop
 72             s << "</ul></li>\n"
 73           end
 74         end
 75         classes = (ancestors.empty? ? 'root' : 'child')
 76         s << "<li class='#{classes}'><div class='#{classes}'>" +
 77                link_to_project(project, {}, :class => "project #{User.current.member_of?(project) ? 'my-project' : nil}")
 78         s << "<div class='wiki description'>#{textilizable(project.short_description, :project => project)}</div>" unless project.description.blank?
 79         s << "</div>\n"
 80         ancestors << project
 81       end
 82       s << ("</li></ul>\n" * ancestors.size)
 83       @project = original_project
 84     end
 85     s.html_safe
 86   end

ここでHTMLを組立ててる。

projectの配列を順に読んで、なにがしかのタイミングでリストの開始タグや閉じタグを書いて、それで表示上の階層構造を作っているっぽい。すごい、意図も気持ちもわかるけど私には絶対書けない、ややこしすぎて。
じゃあ最初にソートしてたlftってなんじゃいと思ってDBを覗いてみると、こんな感じになってた。index以外の項目は省略。

idx|lft|rgt
  1| 14| 21
  2|  8| 13
  3|  2|  7
  4| 15| 16
  5| 17| 18
  6|  9| 10
  7| 11| 12
  8|  3|  4
  9|  5|  6
 10|  1| 22
 11| 19| 20

rgtがある。lft,rgtってleft,rightか！

で、調べてみると、こういうのがあるらしい。
第5回 SQLで木構造を扱う～入れ子集合モデル （1）入れ子集合モデルとは何か ｜gihyo.jp … 技術評論社

入れ子集合モデルは，RDBの寄って立つ集合概念を，そのまま木構造の記述にも応用できないだろうか，という発想で作られました。その根幹のアイデアは非常に簡単で，次の一文で表現できます。
木構造のノードを円（集合）とみなし，階層関係を円の包含関係として捉えなおす。

なるほど、わからん。
ざっくり言うと、RDBで階層構造を表現する方法らしい。そういや親のidとかそんなカラム無かったなっていうか、要するにカラムに親のidを持つようなポインタ的な構造はRDBは苦手なので、階層構造を改めて集合演算的に考えなおして作ったデータ構造らしい。

つまり、lftとrgtで範囲を表していて、

親lft < 子孫lft < 子孫rgt < 親rgt

ってなるようになってて、それで親子関係を表している。なるほど頭いいねぇ。
こういう構造だと、lftの値でソートしてから順に眺めていくと、HTML的にはリストタグを付けたり閉じたりするだけでうまいこと階層が表現できる。そう言われてみるとヘルパのあのコードも納得がいく。きっとテンション上がった時に一気呵成に書き上げたのでしょう。

まああれはあれでデータがでかいと確かにこうすればメモリが節約できそう……だけど、さっきのヘルパの中で表示項目を全部文字列変数(s)に蓄積してたから意味無いじゃん！
けどつまり逆に、私はそこら辺は気にせずに同レベルの項目は蓄積してソートするようにすればいいわけで。それはそれでなんか難しそうだけども。

ということで、やってみる。
とりあえずデータとしてはこんなのを用意してみました。

idx,lft,rgt
10,1,22
3,2,7
8,3,4
9,5,6
2,8,13
6,9,10
7,11,12
1,14,21
4,15,16
5,17,18
11,19,20
12,23,24

さっきのをlftの順にソートして、最後に要素を1個追加しただけです。今回はviewだけをいじりたいので、データを取り出すmodelとcontrollerの部分は変えない。ってことはviewに渡ってくるデータはこのlftでソートされたものになる。というシミュレーション。

で、これを読んでツリー構造を作るプログラムを、なぜかHaskellで書いてしまった。「そこはRubyで書けよ！」って自分でも思ってる。でもなんか意外にサクッと実装できてしまって、いい加減Haskellも慣れてきたなぁ。まあなんだかんだで半日かかりましたけど。
どっちにしろRedmineに組み込む時に書き直すんだからいいかなぁって。RubyもHaskellも大して変わんないよ（？）

コードはこれ。
exercises/rdbtree/sort.hs at master · yunomu/exercises · GitHub

今回は、CSV読み取りにcsvってライブラリを使ってみました。cabal install csvで入るやつ。
mainはいいとして、読み取ったデータの処理をする実際のメイン部分はproc関数です。

proc :: CSV -> IO ()
proc = printTree . sortTree . construct . csvToNodeList

CSVをNodeのリストに変換して(csvToNodeList)、それを木構造に組み立てて(construct)、木のっていうか枝の順序を並べ換えて(sortTree)、画面に表示する(printTree)。

もうちょっと詳しく。

csvToNodeList

読み込んだデータが文字列(type Field)のリスト(type Record)のリスト(type CSV)として返ってくるので、それをNodeっていうかタプルのリストに変換する。tailはヘッダを除去してて、initIf (==[""])はCSVファイルの末尾に改行があった時にできる空エントリを除去してる。

csvToNodeList :: CSV -> [Node]
csvToNodeList = map recordToNode . initIf (==[""]) . tail

construct

Nodeのリストを前から順に見ていって、木構造を作ってる。lft順に並んでいることに依存しているのでこんなのでいい。isSubsetがまさに見ての通り、cがpの子孫だったらTrueを返します。あとfilterの結果とそれに引っかからなかったものを両方返すやつが欲しくてfilter2を書いたけど、なんかそういうの無いのかな。最初はもう少し効率いいの書いてたけど読みづらかったのでこうした。

construct :: [Node] -> [Tree]
construct []     = []
construct (x:xs) = (T (x, construct as)):construct bs
                   where
                     (as, bs) = filter2 (isSubset x) xs

isSubset

isSubset :: Node -> Node -> Bool
isSubset p c = lft p < lft c && rgt c < rgt p

filter2

filter2 :: (a -> Bool) -> [a] -> ([a], [a])
filter2 _ [] = ([], [])
filter2 f xs = (filter f xs, filter (not . f) xs)

sortTree

最初の時点ではsortTree = idって定義してた。これについては後で。

printTree

Treeの画面表示って毎度めんどいよね。

結果

(10,1,22)
        (3,2,7) 
                (8,3,4)
                (9,5,6)
        (2,8,13)
                (6,9,10)
                (7,11,12)
        (1,14,21)
                (4,15,16)
                (5,17,18)
                (11,19,20)
(12,23,24)

うまくいってるっぽい。

で、これをソートすればいいわけで。さしあたりこの結果を見ただけでも子と孫でidxの並び順が合ってないから、ここらへんからいってみようか。リストの中を並べ変えればいいわけだから、なんかできそうな気がしてきた。

とかなんとかやって、githubに上がってるのが最終版です。sortTreeを、Treeのリストをidx順にソートして、それぞれのTreeの子もソートするように実装した。

コードがこれ。

sortTree :: [Tree] -> [Tree]
--sortTree = id
sortTree [] = []
sortTree ts = sort cmp $ map sortChild ts
              where
                cmp (T (n1, _)) (T (n2, _)) = idx n1 < idx n2
                sortChild (T (n, cs)) = T (n, sortTree cs)

sortは比較関数とリストを取ってソートする関数です。簡単なので挿入ソートです。

実行結果がこれ。

(10,1,22)
        (1,14,21)
                (4,15,16)
                (5,17,18)
                (11,19,20)
        (2,8,13)
                (6,9,10)
                (7,11,12)
        (3,2,7) 
                (8,3,4)
                (9,5,6)
(12,23,24)

できてるっぽい。全体的に効率は無視してるけども。

で、これをRubyで書きなおして、pluginにでもできたらいいんだけど。めんどくさっ！！

Redmineのpluginって基本的にRailsだと思って書いていいのかな？　まあそこら辺も含めてまた今度。
あ、今日はビール1000mlくらい飲んでます。お疲れ様でした。