[mhc:01319] Re: conflict detection

[KOIE Hidetaka (鯉江英隆) <hide@xxxxxxxx>]

  From:       Yoshinari Nomura <nom@xxxxxxxxxxxxxxxxxxx>
  Subject:    [mhc:01318] Re: conflict detection
  Date:       Tue, 3 Apr 2001 20:01:17 +0900
  Message-Id: <20010403200117P.nom@xxxxxxxxxxxxxxxxxxx>

  | えっと、多分そんな感じでいいと思います。
  | 後でちょっと落ち着いて考えてみます。

いろいろかんがえたのですが、
endがnilのときの判定を追加してはどうでしょう。

Index: mhc-summary.el
===================================================================
RCS file: /cvsroot/mhc/emacs/mhc-summary.el,v
retrieving revision 1.25
diff -p -u -b -B -r1.25 mhc-summary.el
--- mhc-summary.el	2001/01/31 11:26:37	1.25
+++ mhc-summary.el	2001/04/04 06:15:43
@@ -485,6 +485,8 @@ If optional argument FOR-DRAFT is non-ni
 					(car (cdr schedules))))
 			mhc-tmp-conflict (or (and mhc-tmp-end next-begin
 						  (< next-begin mhc-tmp-end))
+                                             (and (null mhc-tmp-end) mhc-tmp-begin next-begin
+						  (= next-begin mhc-tmp-begin))
 					     (and mhc-tmp-begin time-max 
 						  (< mhc-tmp-begin time-max))))
 		  (if mhc-tmp-end (setq time-max (max mhc-tmp-end time-max)))

  | > 区間木というデータ構造をつかうと
  | > 全conflictを検出できますがコストはO(n log n)になります。
  | 
  | ありがとうございます。
  | 間違ってるかもしれませんが、二色木とかは、
  | 挿入とか削除をすることが前提で、そのときの効率まで考えるから
  | こうなるんですよね。

いや、区間木に1個の区間データを蓄積するのにO(log n)の時間が必要なので
n個の区間データを蓄積するのにはO(n log n)ですが、それとは別に
n個の区間データを蓄積されているときに、区間を入力してそれが
蓄積データと衝突しているかどうかの判定がO(n log n)ということです。

  | mhc は、summary を作るときに、時間順にソートして、
  | それぞれを順番になめて、表示する必要があるので、
  | その中に conflict の判定も入れられるのが一番いいです。

そのとおりですね。
あらためてよくできているとおもいました。

--
KOIE Hidetaka 鯉江英隆 <hide@xxxxxxxx>