Purely Functional Data Structures exercise 3.9 (Red-Black Tree 赤黒木)
第3回PFDS(Purely Functional Data Structures)読書会で
exercise 3.9 のときに紹介された論文「Constructing Red-Black Trees」(この名前でググるとPDF版が見つかる。Postscript版はこちら)に載っている関数 bottom-up の計算量が O(n) であることを確認する。
コードは
data Color = R | B data RBTree a = E | N Color (RBTree a) a (RBTree a) data Digit a = One a (RBTree a) | Two a (RBTree a) a (RBTree a) incr :: Digit a -> [Digit a] -> [Digit a] incr (One a t) [] = [One a t] incr (One a1 t1) (One a2 t2 : ps) = Two a1 t1 a2 t2 : ps incr (One a1 t1) (Two a2 t2 a3 t3 : ps) = One a1 t1 : incr (One a2 (N B t2 a3 t3)) ps bottomUp :: [a] -> RBTree a bottomUp = linkAll . foldr add [] add a ps = incr (One a E) ps linkAll = foldl link E link l (One a t) = N B l a t link l (Two a1 t1 a2 t2) = N B (N R l a1 t1) a2 t2
linkAll は O(n) なので foldr add [] が O(n) であることを確認すればよい。
n回目だけの add で結果[Digit a]がどうなるかと incr が何回呼ばれるかを表にしてみる。
One a t は "1" と、Two a1 t1 a2 t2 は "2" と略記する。
n回目 | [Digit a] | 回数 |
---|---|---|
0 | [] | 0 |
1 | [1] | 1 |
2 | [2] | 1 |
3 | [1 1] | 2 |
4 | [2 1] | 1 |
5 | [1 2] | 2 |
6 | [2 2] | 1 |
7 | [1 1 1] | 3 |
8 | [2 1 1] | 1 |
9 | [1 2 1] | 2 |
10 | [2 2 1] | 1 |
11 | [1 1 2] | 3 |
12 | [2 1 2] | 1 |
13 | [1 2 2] | 2 |
14 | [2 2 2] | 1 |
15 | [1 1 1 1] | 4 |
16 | [2 1 1 1] | 1 |
17 | [1 2 1 1] | 2 |
18 | [2 2 1 1] | 1 |
19 | [1 1 2 1] | 3 |
20 | [2 1 2 1] | 1 |
21 | [1 2 2 1] | 2 |
22 | [2 2 2 1] | 1 |
23 | [1 1 1 2] | 4 |
24 | [2 1 1 2] | 1 |
じっと眺めると
4〜5 の incrの呼ばれた回数は 2〜3 の incrの呼ばれた回数と同じで
6〜7 の incrの呼ばれた回数は 2〜3 の incrの呼ばれた回数の最後だけ 1 増えていて、
8〜11 の incrの呼ばれた回数は 4〜7 の incrの呼ばれた回数と同じで
12〜15 の incrの呼ばれた回数は 4〜7 のincrの呼ばれた回数の最後だけ 1 増えていて、
16〜23 の incrの呼ばれた回数は 8〜15 の incrの呼ばれた回数と同じで
24〜31 の incrの呼ばれた回数は 8〜15 の incrの呼ばれた回数の最後だけ 1 増えていて、
...
2^i〜2^i+2^(i-1)-1 の incrの呼ばれた回数は 2^(n-1)〜2^(n-1)+2^(i-2)-1 の incrの呼ばれた回数と同じで
2^i+2^(i-1)-1〜2^(i+1)-1 の incrの呼ばれた回数は 2^(n-1)〜2^(n-1)+2^(i-2)-1 の incrの呼ばれた回数の最後だけ 1 増えている
ことが見えてくる。
これは
[d1, d2, d3 ... , di, 1]に add するときの処理は[d1, d2, d3 ... , di]に add するときの処理とほぼ同じで
[d1, d2, d3 ... , di, 2]に add するときの処理は[d1, d2, d3 ... , di]に add するときの処理とほぼ同じものの
d1, ... di すべて 2 のときは特別に繰り上がり処理が一手間増えるということから納得できる。(ちゃんとやるには数学的帰納法で証明)
incrの呼ばれた回数の合計で見直すと
4〜5 の 回数の合計は 2〜3 の 回数の合計 3 と同じで 3。
6〜7 の 回数の合計は 2〜3 の 回数の合計 3 足すことの 1 で 4。
つまり 4〜7 の 回数の合計は 2〜3 の 回数の合計 3 の倍足すことの 1 で 7。
同様に 8〜15 の 回数の合計は 4〜7 の 回数の合計 7 の倍足すことの 1 で 15。
同様に 16〜31 の 回数の合計は 8〜15 の 回数の合計 15 の倍足すことの 1 で 31。
...
同様に 2^i〜2^(i+1)-1 の 回数の合計は 2^(i-1)〜2^i-1 の 回数の合計 2^i-1 の倍足すことの 1 で 2^(i+1)-1。
これらを合計すると
1〜2^i-1 の 回数の合計は 1 + 3 + 7 + 15 + ... + (2^i - 1) 。
2^i回目 の incrの呼ばれる回数は 1回なので
1〜2^i の 回数の合計は 1 + 3 + 7 + 15 + ... + (2^i - 1) + 1。
これは
1 + 2 + 4 + 8 + 16 + ... + 2^i == 2*(2^i) - 1 より小さくなる。
f(n) で n回 add するときの incrの呼ばれた回数の合計を表すと上記の考察から
n == 2^i のときは f(n) < 2*n
ということがわかる。
2のベキ乗に限らない一般の n に対して
n <= 2^i < 2*n
という i を取ると、f は単調増加関数ということに注意して
f(n) <= f(2^i) < 2*(2^i) < 2*(2*n) == 4*n
f(n) < 4*n つまり f(n) は O(n) である。
Redmine importer の改造
この記事はRedmine Advent Calendar 2011の26日目の記事です。(もう28日になったけど)
本題に入る前に宣伝。
@tech_machii さんと共同で添付ファイルやアップロードしたファイルの全文検索機能の日本語対応化する
プラグインXapian_search_pluginの検索エンジンをHyper_Estraierへ替える
プラグインDMSFの検索エンジンをHyper_Estraierへ替える
の作業を進めています。
来年1月の品川Redmine勉強会(東京での Redmineの勉強会)で @tech_machii さんがこのことについて解説しますので興味がある方はご参加ください。
さて本題。
Redmine Advent Calendar 2011 の15日目の changeworldさんの記事
【15日目】Redmine の plugin に手を出すならまずこれから - Change The World
でも話題に出てきた CSV からのimport(インポート)ですが私も以前からいろいろといじっていました。
半年前までの成果をredmine importerで紹介したのですがその後もいじっていていろいろ強化したので改めて紹介します。
前回での主な変更点は
- エラーが起きたときその原因も表示するようにした。(ただし最初のエラーだけ)
- 日付型のカスタムフィールドには "YYYY-MM-DD"形式しか許されなかったので Date.parse がわかる形式(例えば "YYYY/MM/DD" や "YYYY/M/D" などいろいろ)ならOKにした。
- カテゴリの find方法の間違いの修正。
でした。
今回追加した主な変更点は
- 履歴の作成者と作成日をインポートできるようにした。
- 履歴に関連する部分だけインポートできるようにした。(オリジナルでは題名とか説明なども上書きしていた)
- 作成者/担当者の指定をログインID以外に姓名表示(「東京 太郎」とか「太郎 東京」とか)形式でもできるようにした。(管理者による「管理」=>「設定」=>「表示」=>「ユーザ名の表示書式」の設定に従います。姓と名の間はasciiスペース)
- 指定された作成者がアカウント一覧から見つからないときエラーにすることもできるようにした。(オリジナルではエラーではなくインポート実行者のアカウントが作成者になる)
- リスト型のカスタムフィールドに存在しない値がきたとき自動的に追加することができるようにした。(オリジナルではエラー)
- Internal Server エラーにできるだけならないように事前にチェックを追加。
- エラー原因/箇所がわかるようにエラーメッセージを詳細にした。
です。
ラベルの説明文がわかりにくいのはご容赦を。
IdlySphere版 redmine importer のバージョン0.9 からの差分は以下のとおりです。(半年前に紹介した差分も含んでいます)
Redmine-1.1系の場合にはこれ以外のパッチも必要なので半年前の記事を見てください。
--- redmine_importer.org/app/controllers/importer_controller.rb +++ redmine_importer/app/controllers/importer_controller.rb @@ -16,5 +16,5 @@ :author, :description, :category, :priority, :tracker, :status, :start_date, :due_date, :done_ratio, :estimated_hours, - :parent_issue, :watchers ] + :parent_issue, :watchers, :created_on ] def index @@ -43,4 +43,5 @@ @samples = [] + begin FasterCSV.new(iip.csv_data, {:headers=>true, :encoding=>iip.encoding, :quote_char=>iip.quote_char, :col_sep=>iip.col_sep}).each do |row| @@ -52,7 +53,20 @@ end end # do + rescue => e + msg = e.message + "\n" + e.backtrace.join("\n") + logger.debug msg + render :text => "CSV file read error: encoding error or " + e.message + return + end if @samples.size > 0 @headers = @samples[0].headers + + (0..@headers.size-1).each do |i| + unless @headers[i] + @headers[i] = '------' + flash[:warning] = "Column name empty error" + end + end end @@ -89,5 +103,5 @@ if issues.size > 1 - flash[:warning] = "Unique field #{unique_attr} with value '#{attr_value}' has duplicate record" + flash[:warning] = "Unique field #{unique_attr}#{unique_attr == @unique_attr ? '': '('+@unique_attr+')'} with value '#{attr_value}' has duplicate record" raise MultipleIssuesForUniqueValue, "Unique field #{unique_attr} with value '#{attr_value}' has duplicate record" else @@ -126,5 +140,8 @@ update_issue = params[:update_issue] unique_field = params[:unique_field].empty? ? nil : params[:unique_field] + update_journal_only = params[:update_journal_only] journal_field = params[:journal_field] + journal_author = params[:journal_author] + journal_created_on = params[:journal_created_on] update_other_project = params[:update_other_project] ignore_non_exist = params[:ignore_non_exist] @@ -133,5 +150,9 @@ add_categories = params[:add_categories] add_versions = params[:add_versions] + add_custom_fields = params[:add_custom_fields] + use_user_name = params[:use_user_name] + @check_non_exist_user = params[:check_non_exist_user] unique_attr = fields_map[unique_field] + @unique_attr = unique_attr # attrs_map is fields_map's invert @@ -165,7 +186,16 @@ end + if use_user_name + @users = {} + User.find(:all).each do |u| @users[u.name] = u; end + end + FasterCSV.new(iip.csv_data, {:headers=>true, :encoding=>iip.encoding, :quote_char=>iip.quote_char, :col_sep=>iip.col_sep}).each do |row| + ["author", "assigned_to", "parent_issue"].each do |a| + row[attrs_map[a]] = nil if row[attrs_map[a]] == '' + end + project = Project.find_by_name(row[attrs_map["project"]]) if !project @@ -174,13 +204,13 @@ tracker = Tracker.find_by_name(row[attrs_map["tracker"]]) status = IssueStatus.find_by_name(row[attrs_map["status"]]) - author = attrs_map["author"] ? User.find_by_login(row[attrs_map["author"]]) : User.current + author = find_user('author', row[attrs_map["author"]], User.current) priority = Enumeration.find_by_name(row[attrs_map["priority"]]) category_name = row[attrs_map["category"]] - category = IssueCategory.find_by_name(category_name) + category = IssueCategory.find_by_project_id_and_name(project.id, category_name) if (!category) && category_name && category_name.length > 0 && add_categories category = project.issue_categories.build(:name => category_name) category.save end - assigned_to = row[attrs_map["assigned_to"]] != nil ? User.find_by_login(row[attrs_map["assigned_to"]]) : nil + assigned_to = find_user('assigned_to', row[attrs_map["assigned_to"]]) if row[attrs_map["assigned_to"]] fixed_version_name = row[attrs_map["fixed_version"]] fixed_version = Version.find_by_name(fixed_version_name) @@ -196,8 +226,10 @@ issue.tracker_id = tracker != nil ? tracker.id : default_tracker issue.author_id = author != nil ? author.id : User.current.id + issue.created_on = issue.updated_on = row[attrs_map["created_on"]] if update_issue begin issue = issue_for_unique_attr(unique_attr,row[unique_field]) + issue.instance_eval { @current_journal = nil } # ignore other project's issue or not @@ -208,15 +240,16 @@ # ignore closed issue except reopen - if issue.status.is_closed? - if status == nil || status.is_closed? - @skip_count += 1 - next - end - end + #if issue.status.is_closed? + # if status == nil || status.is_closed? + # @skip_count += 1 + # next + # end + #end # init journal note = row[journal_field] || '' - journal = issue.init_journal(author || User.current, - note || '') + jauthor = find_user('journal author', row[journal_author], User.current) + journal = issue.init_journal(jauthor, note || '') + issue.updated_on = journal.created_on = row[journal_created_on] @update_count += 1 @@ -242,4 +275,5 @@ @affect_projects_issues[project.name] += 1 : @affect_projects_issues[project.name] = 1 +if issue.new_record? || (update_issue && !update_journal_only) # required attributes issue.status_id = status != nil ? status.id : issue.status_id @@ -276,4 +310,11 @@ issue.custom_field_values = issue.available_custom_fields.inject({}) do |h, c| if value = row[attrs_map[c.name]] + if c.field_format == 'date' + org_value = value + value = Date.parse(value).strftime("%Y-%m-%d") rescue value = org_value + elsif add_custom_fields && c.field_format == 'list' && !value.empty? && !c.possible_values.include?(value) + c.possible_values << value + c.save! + end h[c.id] = value end @@ -285,5 +326,5 @@ addable_watcher_users = issue.addable_watcher_users watchers.split(',').each do |watcher| - watcher_user = User.find_by_login(watcher) + watcher_user = find_user('watcher', watcher) if (!watcher_user) || (issue.watcher_users.include?(watcher_user)) next @@ -294,6 +335,18 @@ end end +end + + begin + issue.save! + success = true + rescue => e + success = false + unless @failed_first_error + @failed_first_error = e.message + end + end - if (!issue.save) +# if (!issue.save) + if (!success) # 记录错误 @failed_count += 1 @@ -366,4 +419,16 @@ end + def find_user(attr, name, default_user = nil) + if name + user = @users ? @users[name]: User.find_by_login(name) + if @check_non_exist_user && !user + flash[:warning] = "#{attr}: Unknown user '#{name}'" + user = '' + end + end + user = default_user unless user + user + end + def convert_string(string, encoding) nkf_option = --- redmine_importer.org/app/views/importer/match.html.erb +++ redmine_importer/app/views/importer/match.html.erb @@ -11,4 +11,5 @@ </fieldset> --> + <% form_tag({:action => 'result'}, {:multipart => true}) do %> <%= hidden_field_tag 'project_id', @project.id %> @@ -36,8 +37,14 @@ <label><%= check_box_tag "add_categories", true, true %> <%= l(:label_importer_add_categories) %> </label><br/> <label><%= check_box_tag "add_versions", true, true %> <%= l(:label_importer_add_versions) %> </label><br/> + <label><%= check_box_tag "add_custom_fields", true, true %> <%= l(:label_importer_add_custom_fields) %> </label><br/> + <label><%= check_box_tag "check_non_exist_user", true, false %> <%= l(:label_check_non_exist_user) %> </label><br/> + <label><%= check_box_tag "use_user_name", true, false %> <%= l(:label_use_user_name) %> </label><br/> <label><%= check_box_tag "update_issue", true, false %> <%= l(:label_update_issue) %> </label><br/> <%= observe_field("update_issue", :function => <<END_OF_STRING +document.getElementById("update_journal_only").disabled = !element.checked; document.getElementById("journal_field").disabled = !element.checked; +document.getElementById("journal_author").disabled = !element.checked; +document.getElementById("journal_created_on").disabled = !element.checked; document.getElementById("update_other_project").disabled = !element.checked; document.getElementById("ignore_non_exist").disabled = !element.checked; @@ -46,7 +53,15 @@ %> + <label><%= check_box_tag "update_journal_only", true, false, {:disabled => true} %> <%= l(:label_update_journal_only) %></label><br/> + <label><%= l(:label_journal_field) %> <%= select_tag "journal_field", "<option value=\"\">#{l(:option_ignore)}</option>" + options_for_select(@headers), {:disabled => true} %></label><br/> + <label><%= l(:label_journal_author) %> + <%= select_tag "journal_author", "<option value=\"\">#{l(:option_ignore)}</option>" + options_for_select(@headers), {:disabled => true} %></label><br/> + + <label><%= l(:label_journal_created_on) %> + <%= select_tag "journal_created_on", "<option value=\"\">#{l(:option_ignore)}</option>" + options_for_select(@headers), {:disabled => true} %></label><br/> + <label><%= check_box_tag "update_other_project", true, false, {:disabled => true} %> <%= l(:label_update_other_project) %></label><br/> --- redmine_importer.org/app/views/importer/result.html.erb +++ redmine_importer/app/views/importer/result.html.erb @@ -12,5 +12,5 @@ <% if @failed_count > 0 %> -<%= l(:label_result_failed, @failed_count) %> +<%= l(:label_result_failed, :count => @failed_count, :error => @failed_first_error) %> <table class="list"> <thead><tr> --- redmine_importer.org/config/locales/ja.yml +++ redmine_importer/config/locales/ja.yml @@ -10,23 +10,29 @@ label_load_rules: "保存されたルールを読み込む" label_toplines: "{{value}}の上の行を参考:" - label_match_columns: "コラムの対象のフィールド" - label_match_select: "コラム毎の対象のフィールドを選択:" + label_match_columns: "カラムの対象のフィールド" + label_match_select: "カラム毎の対象のフィールドを選択:" label_import_rule: "インポートのルール" - label_default_tracker: "トラッカーのディフォルト:" - label_update_issue: "存在があるチケットを更新:" - label_journal_field: "メモとして入るフィールドを選択:" - label_importer_send_emails: "通常にメールを転送" + label_default_tracker: "トラッカーのデフォルト:" + label_update_issue: "既存のチケットを更新する(上記の「チケットの特定に使うユニークなカラムを選択」も必ず設定すること)" + label_update_journal_only: "履歴関連フィールドのみ更新する" + label_journal_field: "履歴として使用するカラムを選択:" + label_journal_author: "履歴の作成者として使用するカラムを選択:" + label_journal_created_on: "履歴の作成日として使用するカラムを選択:" + label_importer_send_emails: "通知メールを送る" label_importer_add_categories: "新しいカテゴリなら自動的に追加" label_importer_add_versions: "新しいターゲットのバージョンなら自動的に追加" - label_unique_field: "一意な値がある欄を選択(存在がある更新または連携をインポートする際に必須):" - label_update_other_project: "他のプロジェクトのチケットでも更新" - label_ignore_non_exist: "チケットの存在がなくても無視" - label_rule_name: "ルール舞を入れる:" + label_importer_add_custom_fields: "新しいカスタムフィールドリスト値なら自動的に追加" + label_use_user_name: "ユーザの特定に名前を使う(デフォルトはログインID)" + label_check_non_exist_user: "存在しないユーザはエラーする" + label_unique_field: "チケットの特定に使うユニークなカラムを選択(既存のチケットの更新または連携のインポートの際に必須):" + label_update_other_project: "他プロジェクトのチケット更新を許可する" + label_ignore_non_exist: "存在しないチケットの指定を無視する" + label_rule_name: "ルール名を入力" label_import_result: "インポートの結果" - label_result_notice: "{{handle_count}}行整理された。{{success_count}}行がうまく行った。" - label_result_projects: "関われるプロジェクト:" + label_result_notice: "{{handle_count}}件のチケットを処理し、{{success_count}} 件のチケットをインポートしました。" + label_result_projects: "更新したプロジェクト:" label_result_issues: "{{count}}行" - label_result_failed: "{{count}}行が失敗:" + label_result_failed: "{{count}}行が失敗: 最初のエラー {{error}}" option_ignore: "無視" @@ -36,2 +42,6 @@ button_save_rules_and_submit: "マッチルールを保存して確認" + activerecord: + errors: + messages: + record_invalid: "Validationエラー %{errors}"
カレンダー表示でチケットのカテゴリに応じて背景色を変える
これは Redmine Advent Calendar jp: 2011 の14日目の記事です。
今日記事を書きそこなったときの保険として昨日「Redmineで冷蔵庫内食品賞味期限管理」という記事も書きましたのでついでにご覧ください。
さて本題。
今週一週間何曜日にどんなチケットの期日がくるか一覧するにはカレンダー表示が便利です。
デフォルトではすべてチケットの背景色は同じで題名を読んでみないと区別ができません。
実はカレンダー表示で(チケット一覧表示ででもですが)はチケット毎に
<a href="/redmine/issues/123" class="issue status-1 priority-2 overdue created-by-me">
のようにステータスと重要度のクラスがすでに設定されていますのでそれに合わせて public/styleseets/application.css にスタイルを記述すると色や見た目を変えることができます。
でも「うちはステータスや重要度での分類とはちょっと違うんだ。カテゴリを【打ち合わせ】【作業】とかで分類してそれで背景色変えたいんだよね」というとこありますよね。(あるということにしてください)
そういうときは次の簡単なパッチで対応できます。
バージョン0.9系以降
--- app/models/issue.rb.org +++ app/models/issue.rb @@ -565,5 +565,5 @@ # Returns a string of css classes that apply to the issue def css_classes - s = "issue status-#{status.position} priority-#{priority.position}" + s = "issue #{"category-"+category.id.to_s if category} status-#{status.position} priority-#{priority.position}" s << ' closed' if closed? s << ' overdue' if overdue?
これによってカレンダー表示での出力に
<a href="/redmine/issues/123" class="issue category-10 status-1 priority-2 overdue created-by-me">
のように「category-数」が追加されます。
こうしておいて public/stylesheets/application.css に
table.cal div.category-10 {background:#ffcccc;} table.cal div.category-11 {background:#ccccff;}
のような記述を追加するとカテゴリーに応じて背景色を変えることができます。
「table.cal」の部分はカレンダー表示のときだけ色を変えるためです。
category-10, status-1, priority-2 などハイフンの後ろの数字はそれぞれの値に割り振られる内部番号値です。
あー、討ち入りに行かないといけないので時間がない。
討ち入りから帰ってきたらもうちょっと修正します。
-- 追記 --
討ち入りに時間がかかって14日のうちに修正できませんでしたので補足します。
バージョン0.8系では修正するファイルも修正内容も少し違い以下のパッチになります。
--- app/helpers/issues_helper.rb.org +++ app/helpers/issues_helper.rb @@ -36,5 +36,5 @@ # Returns a string of css classes that apply to the given issue def css_issue_classes(issue) - s = "issue status-#{issue.status.position} priority-#{issue.priority.position}" + s = "issue #{"category-"+issue.category.id.to_s if issue.category} status-#{issue.status.position} s << ' closed' if issue.closed? s << ' overdue' if issue.overdue?
category-10 などのハイフンの後ろの数字がどのカテゴリー値に対応しているか調べるには「新しいチケット」を実行しブラウザ機能の「ソースを表示」させると
<p><label for="issue_category_id">カテゴリ</label><select id="issue_category_id" name="issue[category_id]"><option value="" selected="selected"></option> <option value="10">打ち合わせ</option> <option value="11">作業</option>
のように【打ち合わせ】には 10 が、【作業】には 11 が対応することがわかります。
(他にもっと簡単に調べる方法はありませんかね?)
Redmineで冷蔵庫内食品賞味期限管理
Redmine Advent Calendar jp: 2011 の順番が明日来ますがしょぼい記事を補うための保険として別に一ネタ書いておきます。
最近自宅の Ubuntuマシンに Redmine を入れてスケジュールと冷蔵庫内の食品賞味期限管理に使っています。チケットには期日(賞味期限)を必ず入れることにしています。
スケジュール、賞味期限確認はカレンダー表示やチケット一覧で見ることができますが、カレンダーは1ヶ月以上の前後を見るのには適していませんし、チケット一覧は今日という期日がどこまで迫っているのかすぐにわかりません。
そこでチケット一覧表示に今日を境にして以前と以後がわかるように区切り線を入れるようにしています。
まずどう表示されるかご覧いただきましょう。
焼き魚やばっ!ということが一目でわかります。焼そばは炒めたら大丈夫でしょう。たくあんはあきらめ気味です。マヨネーズに至っては平常心で対応です。
使いそうにない項目の予定工数と進捗%を右側に表示しているのは題名と期日を左側に寄せて見やすくするためです。
区切り線を入れるのは期日でソートしているときだけです。
いじった差分は以下のとおりです。
(バージョン1.3 に対する差分ですが 1.2 でも同様です)
--- app/controllers/issues_controller.rb.org +++ app/controllers/issues_controller.rb @@ -64,7 +64,7 @@ def index retrieve_query - sort_init(@query.sort_criteria.empty? ? [['id', 'desc']] : @query.sort_criteria) + sort_init(@query.sort_criteria.empty? ? ['due_date'] : @query.sort_criteria) sort_update(@query.sortable_columns) if @query.valid? --- app/views/issues/_list.html.erb.org +++ app/views/issues/_list.html.erb @@ -1,3 +1,5 @@ +<% prev_due_date = nil; ncol = query.columns.size + 2; linedate = Date.today if session['issues_index_sort'] =~ /^due_date\b/ %> + <% form_tag({}) do -%> <%= hidden_field_tag 'back_url', url_for(params) %> <div class="autoscroll"> @@ -25,6 +27,15 @@ </tr> <% previous_group = group %> <% end %> + + <% if linedate && prev_due_date && issue.due_date %> + <% if (prev_due_date <= linedate && linedate < issue.due_date) || (prev_due_date > linedate && linedate >= issue.due_date) %> + <tr><td colspan='<%= ncol %>'><hr></td></tr> + <% linedate = nil %> + <% end %> + <% end %> + <% prev_due_date = issue.due_date %> + <tr id="issue-<%= issue.id %>" class="hascontextmenu <%= cycle('odd', 'even') %> <%= issue.css_classes %> <%= level > 0 ? "idnt idnt-#{level}" : nil %>"> <td class="checkbox hide-when-print"><%= check_box_tag("ids[]", issue.id, false, :id => nil) %></td> <td class="id"><%= link_to issue.id, :controller => 'issues', :action => 'show', :id => issue %></td>
issues_controller.rb でチケットのデフォルトのソート順を期日昇順にし、_list.html.erb で期日ソート順のとき区切り線を入れています。
優先度に応じてチケットの背景色を変えると賞味期限の切迫度が増してよりグッドです。
Redmine importer
Redmine importer とはチケットをCSVファイルから一括でimport(インポート)する Redmine のプラグイン。
現在 Redmine importer にはいろいろな版があってどれがよいのか混乱していたが IdlySphere版 redmine importer というのを教えてもらってなかなかよかったのでさらにいじってみた。
確認は redmine-1.2.0 にて。
追記:
redmine-1.1系では私がいじったパッチをあてると多国語対応に問題が出てうまくいかないことがわかりました。次のパッチを config/initializers/30-redmine.rb にあてるとうまくいきます。(パッチの出典は http://www.redmine.org/projects/redmine/repository/revisions/4679)
--- config/initializers/30-redmine.rb.org +++ config/initializers/30-redmine.rb @@ -1,3 +1,5 @@ I18n.default_locale = 'en' +# Adds fallback to default locale for untranslated strings +I18n::Backend::Simple.send(:include, I18n::Backend::Fallbacks) require 'redmine'
追記終わり 2011-06-10
主な変更点は
- エラーが起きたときその原因も表示するようにした。(ただし最初のエラーだけ)
- 日付型のカスタムフィールドには "YYYY-MM-DD"形式しか許されなかったので Date.parse がわかる形式(例えば "YYYY/MM/DD" や "YYYY/M/D" などいろいろ)ならOKにした。
- カテゴリの find方法の間違いの修正。
いい加減な英語メッセージはご勘弁を。
diff -ru redmine_importer.org/app/controllers/importer_controller.rb redmine_importer/app/controllers/importer_controller.rb --- redmine_importer.org/app/controllers/importer_controller.rb +++ redmine_importer/app/controllers/importer_controller.rb @@ -1,4 +1,7 @@ -require 'fastercsv' +begin + require 'fastercsv' unless defined? FasterCSV +rescue LoadError +end require 'tempfile' class MultipleIssuesForUniqueValue < Exception @@ -18,6 +21,10 @@ :parent_issue, :watchers ] def index + unless defined? FasterCSV + render :text => '<h1>FasterCSV load error</h1>Please run "gem install fastercsv"' + return + end end def match @@ -176,7 +183,7 @@ author = attrs_map["author"] ? User.find_by_login(row[attrs_map["author"]]) : User.current priority = Enumeration.find_by_name(row[attrs_map["priority"]]) category_name = row[attrs_map["category"]] - category = IssueCategory.find_by_name(category_name) + category = IssueCategory.find_by_project_id_and_name(project.id, category_name) if (!category) && category_name && category_name.length > 0 && add_categories category = project.issue_categories.build(:name => category_name) category.save @@ -275,6 +282,10 @@ # custom fields issue.custom_field_values = issue.available_custom_fields.inject({}) do |h, c| if value = row[attrs_map[c.name]] + if c.field_format == 'date' + org_value = value + value = Date.parse(value).strftime("%Y-%m-%d") rescue value = org_value + end h[c.id] = value end h @@ -294,7 +305,18 @@ end end - if (!issue.save) + begin + issue.save! + success = true + rescue => e + success = false + unless @failed_first_error + @failed_first_error = e.message + end + end + +# if (!issue.save) + if (!success) # 记录错误 @failed_count += 1 @failed_issues[@handle_count + 1] = row diff -ru redmine_importer.org/app/views/importer/result.html.erb redmine_importer/app/views/importer/result.html.erb --- redmine_importer.org/app/views/importer/result.html.erb +++ redmine_importer/app/views/importer/result.html.erb @@ -11,7 +11,7 @@ <hr/> <% if @failed_count > 0 %> -<%= l(:label_result_failed, @failed_count) %> +<%= l(:label_result_failed, :count => @failed_count, :error => @failed_first_error) %> <table class="list"> <thead><tr> <th>#</th> diff -ru redmine_importer.org/config/locales/en.yml redmine_importer/config/locales/en.yml --- redmine_importer.org/config/locales/en.yml +++ redmine_importer/config/locales/en.yml @@ -27,7 +27,7 @@ label_result_notice: "{{handle_count}} issues processed. {{success_count}} issues successfully imported." label_result_projects: "Affected projects:" label_result_issues: "{{count}} issues" - label_result_failed: "Failed {{count}} rows:" + label_result_failed: "Failed {{count}} rows: first error {{error}}" option_ignore: "Ignore" diff -ru redmine_importer.org/config/locales/ja.yml redmine_importer/config/locales/ja.yml --- redmine_importer.org/config/locales/ja.yml +++ redmine_importer/config/locales/ja.yml @@ -12,22 +12,22 @@ label_match_columns: "コラムの対象のフィールド" label_match_select: "コラム毎の対象のフィールドを選択:" label_import_rule: "インポートのルール" - label_default_tracker: "トラッカーのディフォルト:" - label_update_issue: "存在があるチケットを更新:" - label_journal_field: "メモとして入るフィールドを選択:" - label_importer_send_emails: "通常にメールを転送" + label_default_tracker: "トラッカーのデフォルト:" + label_update_issue: "既存のチケットを更新する" + label_journal_field: "履歴として使用するフィールドを選択:" + label_importer_send_emails: "通知メールを送る" label_importer_add_categories: "新しいカテゴリなら自動的に追加" label_importer_add_versions: "新しいターゲットのバージョンなら自動的に追加" - label_unique_field: "一意な値がある欄を選択(存在がある更新または連携をインポートする際に必須):" - label_update_other_project: "他のプロジェクトのチケットでも更新" - label_ignore_non_exist: "チケットの存在がなくても無視" - label_rule_name: "ルール舞を入れる:" + label_unique_field: "チケットの特定に使うユニークなフィールドを選択(既存のチケットの更新または連携のインポートの際に必須):" + label_update_other_project: "他プロジェクトのチケット更新を許可する" + label_ignore_non_exist: "存在しないチケットの指定を無視する" + label_rule_name: "ルール名を入力" label_import_result: "インポートの結果" - label_result_notice: "{{handle_count}}行整理された。{{success_count}}行がうまく行った。" - label_result_projects: "関われるプロジェクト:" + label_result_notice: "{{handle_count}}件のチケットを処理し、{{success_count}} 件のチケットをインポートしました。" + label_result_projects: "更新したプロジェクト:" label_result_issues: "{{count}}行" - label_result_failed: "{{count}}行が失敗:" + label_result_failed: "{{count}}行が失敗: 最初のエラー {{error}}" option_ignore: "無視"
モナド則1が成り立たないと
以前「モナド則1(左単位元)を満たさない偽リストモナド」でモナド則1が成り立たないとどういうとき困るかを書いたのですが通常の場面では出てこないような例だったので別の例をあげます。
あらためて偽リストモナドの定義を書くと
import Monad(sequence) data MyList a = My { unMy :: [a] } deriving (Show,Eq) instance Monad MyList where return x = My [x,x] (My xs) >>= k = My $ xs >>= (unMy.k)
この偽モナドはモナド則3は満たしていますがモナド則1、2を満たしていません。
もしモナド則すべてを満たしているならば次のコード
do x1 <- My [1] x2 <- My [2] x3 <- My [3] x4 <- My [4] x5 <- My [5] return (sum [x1,x2,x3,x4,x5])
は sequence関数を使って
do xs <- sequence [My [1], My [2], My [3], My [4], My [5]] return (sum xs)
と書き換えることができます。
(大雑把にいうと sequence [m1,m2... m_n] は do {x1 <- m1; x2 <- m2; ... x_n <- m_n; return [x1,x2... x_n]} と同じ意味になります)
しかし実際にはモナド則1を満たしていないので
(上に書いた例だと結果が長くなるので x1 x2 だけにした例で試します)
> do {x1 <- My [1]; x2 <- My [2]; return (sum [x1,x2])} My {unMy = [3,3]} > do {xs <- sequence [My [1], My[2]]; return (sum xs)} My {unMy = [3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3]}
と結果が違ってきます。
これは sequence の定義
sequence :: Monad m => [m a] -> m [a] sequence = foldr mcons (return []) where mcons p q = p >>= \x -> q >>= \y -> return (x:y)
の中で return が使われているためモナド則1の破れの影響を受けるからです。(この偽リストモナドの場合は return がかかる度リストの要素数が倍々になっていきます。)
この例のようにモナド則1が成り立たないと内部で return を使っている関数を使っての書き換えができなくなってしまいます。
Mac に rvm を使って ruby と rails をインストール
Mac OS X Snow Leopard に rvm を使って ruby と rails をインストール
目標: ruby-1.8+rails2, ruby-1.8+rails3, ruby-1.9+rails3 の3通りの環境を作る。
コマンドの依存関係:
- rvm を入れるのに git が必要。(2012年2月23日追記:git なくても rvm 入れられるようになっているようだ)
- git を入れるのに brew が必要
- brew を入れるのに ruby が必要
- この ruby にはもともと入っている /usr/bin/ruby が使われる
brew(homebrew) のインストール。途中sudoでパスワード入力が求められる
% ruby -e "$(curl -fsSL https://gist.github.com/raw/323731/install_homebrew.rb)"
homebrew のページがリダイレクトされているので curl のオプションに L をつけていないとエラーになるので注意。
brew の確認
% brew -v 0.7.1
git のインストール
% sudo brew install git
git の確認
% git --version git version 1.7.4.1
rvm のインストール
(2012年2月23日追記:
https://rvm.beginrescueend.com/ を見たら git は必要なく
bash -s stable < <(curl -s https://raw.github.com/wayneeseguin/rvm/master/binscripts/rvm-installer)
でインストールできるようになっているようだ。
一応以前書いた下記も取り消し線つけて残しておく。)
% bash < <( curl http://rvm.beginrescueend.com/releases/rvm-install-head )
後の「rvm がインストールされていることを確認」のところでエラーがでるときは上記の rvm-install-head のところを rvm-install-latest にしてやり直す
rvm の設定
.bash_profile に以下を追記
[[ -s "$HOME/.rvm/scripts/rvm" ]] && source "$HOME/.rvm/scripts/rvm"
上記の設定をすぐに効かすために source
% source .bash_profile
rvm がインストールされていることを確認
% rvm -v rvm 1.2.6 by Wayne E. Seguin (wayneeseguin@gmail.com) [http://rvm.beginrescueend.com/]
ここで「VERSION.yml がない」というエラーがでたら上の rvm のインストールで rvm-install-head のところを rvm-install-latest にしてやり直す
rvm がインストールできる ruby の一覧
% rvm list known [ruby-]1.8.7[-p330] [ruby-]1.9.2[-p136] やらいっぱい出る。 括弧で囲まれている部分は省略可能の意味。
ruby-1.8.7-p330 のインストール
# rvm install ruby-1.8.7-p330 の括弧の部分を省略して % rvm install 1.8.7
1.8.7 を使う設定
# rvm use ruby-1.8.7 でも同じ % rvm use 1.8.7
ruby の位置確認
% which ruby /Users/itto100pen/.rvm/rubies/ruby-1.8.7-p330/bin/ruby
rails2 と rails3 の gem の準備
% rvm gemset create rails2 % rvm gemset create rails3
gemsetが出来ていることを確認
% rvm gemset list gemsets for ruby-1.8.7-p330 (found in /Users/itto100pen/.rvm/gems/ruby-1.8.7-p330) global rails2 rails3
ruby-1.8.7 で rails-2.3.11 のインストール
% rvm use 1.8.7@rails2 % gem install rails -v 2.3.11
rails の確認
% which rails /Users/itto100pen/.rvm/gems/ruby-1.8.7-p330@rails2/bin/rails % rails -v Rails 2.3.11
ruby-1.8.7 で rails-3.0.4 のインストール
% rvm use 1.8.7@rails3 % gem install rails
rails の確認
% which rails /Users/itto100pen/.rvm/gems/ruby-1.8.7-p330@rails3/bin/rails % rails -v Rails 3.0.4
ruby-1.9.2-p136 のインストール
# rvm install ruby-1.9.2-p136 の括弧の部分を省略して % rvm install 1.9.2
1.9.2 を使う設定
# rvm use ruby-1.9.2 でも同じ % rvm use 1.9.2
ruby の位置確認
% which ruby /Users/itto100pen/.rvm/rubies/ruby-1.9.2-p136/bin/ruby
rails3 の gem の準備
% rvm gemset create rails3
gemsetが出来ていることを確認
% rvm gemset list gemsets for ruby-1.9.2-p136 (found in /Users/itto100pen/.rvm/gems/ruby-1.9.2-p136) global rails3
ruby-1.9.2 で rails-3.0.4 のインストール
% rvm use 1.9.2@rails3 % gem install rails
rails の確認
% which rails /Users/itto100pen/.rvm/gems/ruby-1.9.2-p136@rail3/bin/rails % rails -v Rails 3.0.4
logout してしまうと rvm use した情報が消えてしまうのでデフォルトを設定しておく
% rvm use 1.8.7@rails3 --default