--- a/Changes	Sat Jun 05 14:54:13 2004 +0900
+++ b/Changes	Sun Jun 06 01:46:58 2004 +0900
@@ -4633,3 +4633,69 @@
 switch をまとめるのはやったけど、現状のコードだとtable
 は、ほとんどでないね。2分木は出るけど。IDが連続するように
 工夫した方がいいのかな。
+
+chunk の merge のalgorithm だけど.... O(N^2) だよね。
+
+     c0,  c1,  c2, ... cn
+
+で、(なんか見たことある...)
+
+     c0,  c1,  c2, ... cn
+     +------------------+ rate
+     +---------------+    rate
+     +----------+         rate
+     +----+               rate
+          +-------------+ rate
+          +----------+    rate
+          +-----+         rate
+                   ...
+
+というのを作る。((n-1)*(n-2)/2) か。で、一番、rate の高いものを
+取るのが、正しいとは限らない.... rate じゃなくて、cover 率が
+高いものの方が良い。消去法が良くて、まず、
+
+     RATE 以下のものを消去する (生成しない)
+     そして、cover 率の高いものをとって、すべてを取り尽くす
+
+           +------------+ rate 75%
+     +-------++------+    rate 80%
+
+みたいなのをどうするかだけど... テーブルが少ない方を優先?
+テーブルが一つが良いとは限らない。
+
+count が多いのに delta が異なると一般的にはだめ。
+
+     +-------++---------+ rate 80%
+          <------>   みたいな形で取り合う場合もある。
+
+この場合は cover rate が変わらないので、table rate で計算する?
+
+えーと、生成した全ての区間の組合せが許されるわけではない。
+
+     c0,  c1,  c2, ... cn
+     +----+               rate   これが fix すると、
+              +---------+ rate
+          +-------------+ rate
+          +-----+         rate
+                   ...           などしか許されない。
+
+後ろから計算しても前から計算してもおんなじはず。
+ただ、飛び値が多い場合の計算量がなぁ。
+
+まぁ、やっぱり、
+
+  for i (0..n) {
+    c_i を可能な限り拡大する
+    できなかったら、それを生成
+  }
+
+でしょ?
+
+まぁ、だいたいできたんだけど、細かいバグが残っていそうだね。
+
+    < # chunks 1 = sum  1/123 sum = 1
+    ---
+    > # chunks 1 = sum  1/2 sum = 1
+
+なんてのもあるし。
+

--- a/mc-codegen.c	Sat Jun 05 14:54:13 2004 +0900
+++ b/mc-codegen.c	Sun Jun 06 01:46:58 2004 +0900
@@ -1774,7 +1774,11 @@
 
 /*
       cslist = list3(value,next,label)  label==0 means skip
-      chunk  = list3(cslist,next,delta,count)
+      chunk  = list4(cslist,next,delta,list3(count,min,max))
+ */
+
+/*
+   group continous case value
  */
 
 static int
@@ -1782,7 +1786,8 @@
 {
     int delta,delta1,list,p,count;
     // cslist is already sorted
-    list = list4(cslist,0,delta=0,0); 
+    delta = 0;
+    list = list4(cslist,0,1,list3(0,car(cslist) /* min */,0)); 
     count=1;
     for(p=0;cadr(cslist);cslist = cadr(cslist),count++) {
 	delta1 = car(cadr(cslist))-car(cslist);
@@ -1791,44 +1796,154 @@
 	    caddr(list) = delta = delta1;
 	    if (p) cadr(p)=0;  // terminate previous chunk
 	} else if (delta1!=delta) {
-	    // start new list
-	    cadddr(list) = count; count=0;
-	    list = list4(cadr(cslist),list,delta=0,0);
+	    // not contiguous, start new list
+	    caddr(cadddr(list)) = car(cslist);      // max
+	    car(cadddr(list)) = count; count=0;
+            delta = 0;
+	    list = list4(cadr(cslist),list,1,list3(0,0,0));
+	    cadr(cadddr(list)) = car(cadr(cslist)); // min
 	    p=cslist;
 	}
     }
     if (p) cadr(p)=0;  // terminate previous chunk
-    cadddr(list) = count;
+    car(cadddr(list)) = count;
+    caddr(cadddr(list)) = car(cslist);   // max
     return list;
 }
 
+#define CASE_MERGE_RATE 80
+/*
+    rate = (sum count(c_i))/(max-min)
+      list3(count,min,max)
+ */
+
+static int gcd(int i,int j)
+{
+    int k;
+    if (i<j) { k=i; i=j; j=k;}
+    for(;;) {
+	if ((k=i%j)==0) return j;
+	i = j; j = k;
+    }
+}
+
+/*
+    check two chunks are mergeable or not.
+ */
+
+int
+merge_chunk_p(int *delta,int max,int min,int *count,int delta1,int count1) 
+{
+    int range = max-min;
+    int g;
+    g = gcd(*delta,delta1);
+    g = gcd(g,range);
+    range /= g;
+    *count = count1 = count1+*count;
+    *delta = g;
+#if 1
+    printf("# min %d, max %d, count %d, delta %d, rate %g t=%d\n",
+	min,max,count1,g,
+	     ((double)count1)*100.0/range,
+           count1*128>(range*128*CASE_MERGE_RATE/100)
+    );
+#endif
+    return count1*128>(range*128*CASE_MERGE_RATE/100);
+}
+
+/*
+     merge possible chunk
+      input:  list4(cslist,next,delta,list3(count,min,max))
+      output: list3(continuous number of chunk,next,delta);
+ */
+
+static int
+merge_chunk(int cslist)
+{
+    int list = cslist;
+    int tail,last,max,min,i;
+    int count,p,widest,delta=1;
+    int chunks = 0;
+    while(cadr(list)) {
+	p = cadddr(list);
+	count = car(p); max=caddr(p);
+	widest = 1; last = list;
+	delta = caddr(list);
+	for(i=1,tail=cadr(list);cadr(tail); tail=cadr(tail),i++) {
+	    p = cadddr(tail);
+	    min = cadr(p);
+	    if (merge_chunk_p(&delta,max,min,&count,caddr(tail),car(p))) {
+		widest = i+1; last = tail;
+	    }
+	}
+	chunks = list3(widest,chunks,delta);
+	list = cadr(last);
+    }
+    if (list) chunks = list3(1,chunks,delta);
+    return reverse0(chunks);
+}
+
 static void
-cascade_compare(int cslist,int cslabel,int dlabel)
+table_jump(int cslist)
 {
-    if (cslabel)
-	fwddef(cslabel);
     for(;cslist; cslist=cadr(cslist)) {
 	if (caddr(cslist))
 	    cmpdimm(car(cslist),csvalue1,caddr(cslist),0);
     }
-    if (dlabel) jmp(dlabel);
 }
 
+static void
+cascade_compare(int cslist)
+{
+    for(;cslist; cslist=cadr(cslist)) {
+	if (caddr(cslist))
+	    cmpdimm(car(cslist),csvalue1,caddr(cslist),0);
+    }
+}
+
+#define CASE_TABLE_COUNT 10
+
 void
 switch_table(int cslist,int cslabel,int dlabel)
 {
-#if 1
-    int i;
+    int chunks;
+    int i,j;
+#if 0
     for(i=cslist;i;i=cadr(i)) {
 	printf("# case %d L_%d\n",car(i),caddr(i));
     }
 #endif
-    cslist = make_chunk(cslist);
+    cslist=make_chunk(cslist);
+#if 1
+    chunks = 0;
+    for(i=cslist;i;i=cadr(i)) {
+        chunks++;
+    }
+    j = chunks;
+#endif
+    chunks = merge_chunk(cslist);
+#if 1
+    //  chunks: list3(widest,next,delta);
+    printf("# chunks %d = sum ",j);
+    j = 0;
+    for(i=chunks;i;i=cadr(i)) {
+	printf(" %d/%d",car(i),caddr(i));
+	j+=car(i);
+    }
+    printf(" sum = %d\n",j);
+#endif
     fwddef(cslabel);
     for(;cslist;cslist=cadr(cslist)) {
-	printf("# case chunk delta=%d count=%d\n",caddr(cslist),cadddr(cslist));
-	cascade_compare(car(cslist),0,cadr(cslist)?0:dlabel);
+	printf("# case chunk delta=%d count=%d min=%d max=%d\n",
+		caddr(cslist),car(cadddr(cslist)),
+				cadr(cadddr(cslist)),caddr(cadddr(cslist))
+		);
+	if (cadddr(cslist)>CASE_TABLE_COUNT)
+	    table_jump(car(cslist));
+	else
+	    cascade_compare(car(cslist));
     }
+    if (dlabel) jmp(dlabel);
 }
 
 #endif