/*--------------------------------------------------------------*
 *                                                              *
 *         SUFARY --- Suffix Array ΤΥ饤֥       *
 *                                                              *
 *  search.c - ¹Ԥ                                   *
 *                                                              *
 *--------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sufary.h"

#define MINMIN(X,Y) ((X) < (Y) ? (X) : (Y))

/****************************************************************************
 * functions for endian problem
 ***************************************************************************/
static int is_little_endian(void)
{
    int  n = 1;
    char *c;
    
    c = (char *)&n;
    if (*c == 1) {
        return 1;
    } else {
        return 0;
    }
}

long reverse_byte_order_long(long p)
{
    int j;
    unsigned char *c, tmp;

    c = (unsigned char*)(&p);
    for (j = 0; j < (sizeof(long) / 2); j++) {
        tmp = *(c + j);
        *(c + j) = *(c + sizeof(long) - 1 - j);
        *(c + sizeof(long) - 1 - j) = tmp;
    }
    return p;
}


/* sistring  */
int cmp_sistr(char *txt, char *str, int *diffpos, int len);

/******************************************************************************
 *            eresult sa_sel(SUFARY *ary, char *s);
 *
 * purpose
 *   ¹
 *
 * parameters
 *   ary : оݥե
 *   s   : 
 *
 * return value
 *   ץ³⡼
 *
 * description
 *   array ʸõ
 *   2ʬõ3Ȥäϰϸ򤹤
 *
 *                 abxxiabcdefgxyzpoop
 * ary->left       hipdabbbbbbbbbbxaba     ary->right
 *    |            bbbcfffffffffffhllm        |
 *    ------------------##########-------------
 *                     ||        ||
 *                l_out l_in  r_in r_out
 *
 *  "fb" Ǹ㡣
 * (ϰ) left_inside  right_inside ( # Ǽʬ )
 *
 * [] left, right ɬϰϤ¦ؤ 980319
 *
 *   Ѥ
 *       ary->ee : 顼(ɤʥ顼ȯ)
 *       ary->right, ary->left : ưŪ˼θϰϤ򶹤
 *
 *****************************************************************************/
eresult sa_sel(SUFARY *ary, char *s){
  int keylen = strlen(s);
  return sa_search(ary, s, keylen, 0);
}

eresult sa_search(SUFARY *ary, char *s, int keylen, int base_offset)
{
  long left_outside, right_outside, left_inside, right_inside, cur, tmp;
  int hr;
  int prefix_length_L = base_offset, prefix_length_R = base_offset;
  int offset = 0, diffpos /* ۤʤ */;
  /*long *longary;*/

  if (ary == NULL || ary->aryfd == -1){
    printf ("specify target files first.\n");
    return FAIL;
  }

  /* ϰϽ */
  right_outside = ary->right + 1;
  left_outside = ary->left - 1;
  right_inside = ary->right;
  left_inside = ary->left;

  /*longary = (long *)(ary->arymap);*/

  /* step 1. Match 򸫤Ĥ롣*/
  cur = (right_outside - left_outside)/2 + left_outside;
  while(1){
    offset = MINMIN(prefix_length_L,prefix_length_R);
    hr = cmp_sistr(ary->txtmap+ sa_aryidx2txtidx(ary, cur)+offset, 
                   /*s+offset, &diffpos, keylen-offset);*/
		   s-base_offset+offset, &diffpos, keylen+base_offset-offset);
                  /*  981230 base_offset */
   if (hr < 0){ /* LESS */
      left_outside = cur;
      prefix_length_L = offset + diffpos;
    } else if (hr > 0){ /* ABOVE */
      right_outside = cur;
      prefix_length_R = offset + diffpos;
    } else { /* MATCH ... if (hr == 0) */
      left_inside = right_inside = cur;
      break;
    }
    tmp = (right_outside - left_outside)/2 + left_outside;
    /* left_outside  -1 βǽꡣ tmp  -1 ˤʤ뤳Ȥ 980319 */
    if (cur==tmp || tmp < ary->left) return FAIL; /* Ĥʤä... */
    cur = tmp;
  }

  /* step 2. right_inside ꤹ */
  offset = prefix_length_R;
  cur = (right_outside - right_inside)/2 + right_inside;
  while (1){
    hr = cmp_sistr(ary->txtmap+ sa_aryidx2txtidx(ary, cur)+offset,
                   /*s+offset, &diffpos, keylen-offset);*/
		   s-base_offset+offset, &diffpos, keylen+base_offset-offset);
    if (hr > 0){ /* ABOVE */
      right_outside = cur;
      offset += diffpos;
    } else if (hr == 0){ /* MATCH */
      right_inside = cur;
    } else { /* LESS ... if (hr < 0) */
      ary->ee = STRUCTURE;
      return ERROR;
    }
    tmp = (right_outside - right_inside)/2 + right_inside;
    if (cur==tmp) break;
    cur = tmp;
  }

  /* step 3. left_inside ꤹ */
  offset = prefix_length_L;
  cur = left_inside - (left_inside - left_outside)/2; /* 980319 */
  if(cur < 0) cur = 0;
  while (1){
    hr = cmp_sistr(ary->txtmap+ sa_aryidx2txtidx(ary, cur)+offset,
                   /*s+offset, &diffpos, keylen-offset);*/
                   s-base_offset+offset, &diffpos, keylen+base_offset-offset);
    if (hr < 0){ /* LESS */
      left_outside = cur;
      offset += diffpos;
    } else if (hr == 0){ /* MATCH */
      left_inside = cur;
    } else { /* ABOVE ... if (hr > 0) */
      ary->ee = STRUCTURE;
      return ERROR;
    }
    tmp = left_inside - (left_inside - left_outside)/2; /* 980319 */
    if(tmp < 0) tmp = 0;
    if (cur==tmp) break;
    cur = tmp;
  }

  /* ary->left, ary->right κ */
  ary->left = left_inside;
  ary->right = right_inside;
/*  printf("Left %ld, Right %ld\n",ary->left,ary->right); */
  return CONT;
}


/******************************************************************************
 *   int cmp_sistr(char *txt, char *str, int *diffpos, int len);
 *
 * purpose
 *   sistring 
 *
 * parameters
 *   txt : Ӥʸ(оݥƥ)
 *   str : Ӥʸ()
 *   diffpos : ʸܤޤƱä Ϥưۤʤä(ʸ)
 *             񤭴ơ֤ͤȤƻѡ
 *   len : Ӥʸ
 *
 * return value (int)
 *   0 : MATCH 
 *   - : LESS  sistring(pos) < str  ('abc...' < 'ccc')
 *   + : ABOVE sistring(pos) > str  ('abc...' > 'aaa')
 *
 * description
 *   980422 ¤
 *
 *****************************************************************************/
int cmp_sistr(char *txt, char *str, int *diffpos, int len)
{
  int i;
  for(i = 0; i < len; i++,txt++,str++)
    if(*txt != *str) {
      *diffpos = i;
      return ((unsigned char)*txt-(unsigned char)*str);
    }
  *diffpos = len;
  return 0;
}

/******************************************************************************
 *   long sa_left(SUFARY *ary);
 *   long sa_right(SUFARY *ary);
 *
 * purpose
 *   줾졢SUFARYѿaryθߤ left, right ֤ͤ
 *
 * parameters
 *   ary : оarray
 *
 * return value
 *   ary->left (sa_left), ary->right (sa_right)
 *
 * description
 *   SUFARY¤桼ľܸʤɬ
 *****************************************************************************/
long sa_left(SUFARY *ary){return ary->left;}
long sa_right(SUFARY *ary){return ary->right;}
long sa_bottom(SUFARY *ary){return ary->left;} /* ̾ */
long sa_top(SUFARY *ary){return ary->right;} /* ̾ */

/******************************************************************************
 *   void sa_reset(SUFARY *ary);
 *
 * purpose
 *   SUFARYѿaryrightleft򸵤᤹
 *
 * parameters
 *   ary : оarray
 *
 * return value
 *   ʤ
 *
 * description
 *   SUFARY¤桼ľܸʤɬ
 *****************************************************************************/
void sa_reset(SUFARY *ary)
{
  ary->left = 0;
  ary->right = ary->arraysize - 1; /* 980319 */
  if (ary->op_result){
    free(ary->op_result);
    ary->op_result = NULL;
  }
  ary->arymap = ary->aryorig;
  return;
}


/******************************************************************************
 *   long sa_aryidx2txtidx(SUFARY *ary, long idx)
 *   char *sa_txtidx2txtptr(SUFARY *ary, long idx)
 *   char *sa_aryidx2txtptr(SUFARY *ary, long pos)
 *
 * purpose
 *   ƥȥեδؿ
 *
 * parameters
 *   ary : оarray
 *   idx : 
 *
 * description
 *   SUFARY¤桼ľܸʤɬ
 *****************************************************************************/
long sa_aryidx2txtidx(SUFARY *ary, long idx)
/* arrayեidxܤǤ֤   sa_arraytotext() */
{
    if (is_little_endian())
        return reverse_byte_order_long(((long*)(ary->arymap))[idx]);
    else
        return ((long*)(ary->arymap))[idx];
/*
  long *la;
  la = (long *)ary->arymap;
  return la[idx];
  */

/*  caddr_t *ptr;
  ptr = (void *)ary->arymap + idx * sizeof(long);
  return ((long *)ptr)[0];*/
}

char *sa_txtidx2txtptr(SUFARY *ary, long idx)
/* textեidxܤ򤵤ʸݥ󥿤֤ */
{
  return ary->txtmap+idx;
}

char *sa_aryidx2txtptr(SUFARY *ary, long idx)
/* arrayեidxܤǤʸݥ󥿤֤   sa_gettext() */
{
    if (is_little_endian())
        return ary->txtmap +
	    reverse_byte_order_long(((long*)(ary->arymap))[idx]);
    else
        return ary->txtmap + ((long*)(ary->arymap))[idx];
/*
  long *la;
  la = (long *)ary->arymap;
  return ary->txtmap+la[idx];
  */
/*  caddr_t *ptr;
  ptr = (void *)ary->arymap + idx * sizeof(long);
  return ary->txtmap+((long *)ptr)[0];*/
}

/* 켰δؿؿ̾ */
char *sa_gettext(SUFARY *ary, long pos){return sa_aryidx2txtptr(ary,pos);}
long sa_arraytotext(SUFARY *ary, long pos){return sa_aryidx2txtidx(ary,pos);}


/******************************************************************************
 *   char *sa_getline(SUFARY *ary, long pos);
 *
 * purpose
 *   aryβԤǶޤ줿ʸ(Ĥޤꡢ)μ
 *
 * parameters
 *   ary : оarray
 *   pos : åȥե(txtfile)ΰ
 *
 * return value
 *   str Υݥ
 *
 * description
 *   Version 2.0b3 ꡢsa_get_lines() ƤӽФ褦ˤʤä
 *****************************************************************************/
char *sa_getline(SUFARY *ary, long pos)
{
  return sa_getlines(ary, pos, 0, 0);
}

/**********************************************
 *   char *sa_getlines(SUFARY *ary, long pos, int B, int A);
 *
 * purpose
 *   aryβԤǶޤ줿ʸ()
 *   ˤιԤƱ˼ä
 *
 * parameters
 *   ary : оarray
 *   pos : åȥե(txtfile)ΰ
 *   B : Ʊ˼ä褿ιԤιԿ
 *   A : Ʊ˼ä褿ιԤιԿ
 *
 * return value
 *   str Υݥ
 **********************************************/
char *sa_getlines(SUFARY *ary, long pos, int B, int A)
{
  long i,j,k;
  int ii;
  char *str;

  i = pos; j = pos;
  if(*(ary->txtmap+pos) == '\n') i--;

  while(1){
    if(i < 0){i = 0; break;}
    if(*(ary->txtmap+i) == '\n'){
      B--;
      if(B < 0){i++; break;}
    }
    i--;
  }

  while(1){
    if(ary->txtsz <= j){j = ary->txtsz -1; break;}
    if(*(ary->txtmap+j) == '\n'){
      A--;
      if(A < 0){j--; break;}
    }
    j++;
  }
  /*  4 5 6 7 8 9                            *
   * \n a b c d \n   --->   str = "abcd\0"   *
   *    i     j                              */
  str = (char *)malloc(j-i+2);
  /*strncpy(str,ary->txtmap+i,j-i+1);*//* \0 ȥԡߤ㤦 */
  for(k = 0; k < j-i+1; k++){
   str[k] = *(ary->txtmap+i+k);
   if(str[k] == '\0') str[k] = '\1';
  }
  str[j-i+1] = '\0';
  return str;
}


/******************************************************************************
 *   char *sa_getblock(SUFARY *ary, long pos, char *d1, char *d2);
 *   char *sa_getkatamari(SUFARY *ary, long pos, char *d1, char *d2);
 *
 * purpose
 *   ڤʸ d1  d2 Ƕޤ줿ƥȤ
 *
 * parameters
 *   ary : оarray
 *   pos : åȥե(txtfile)ΰ
 *   d1, d2 : ڤʸ
 *
 * return value
 *   str Υݥ
 *
 * description
 *   str nul ʸǥߥ͡Ȥ롣
 *****************************************************************************/
char *sa_getkatamari(SUFARY *ary, long pos, char *d1, char *d2){
  return sa_getblock(ary, pos, d1, d2);
}
char *sa_getblock(SUFARY *ary, long pos, char *d1, char *d2){
  long i, j;
  char *str;
  int d1len = strlen(d1), d2len = strlen(d2);

  i = pos; j = pos +1;

  while(1){
    if(strncmp((ary->txtmap+i),d1,d1len) == 0) break;
    if(i == 0) break;
    i--;
  }

  while(1){ /* եǥ顼βǽ 980429 tatuo-y */
    if(strncmp((ary->txtmap+j),d2,d2len) == 0) break;
    if((*(ary->txtmap+j) == '\0')) break;
    j++;
  }
  j += d2len;

  str = (char *)malloc(j-i+1);
  strncpy(str,ary->txtmap+i,j-i);
  str[j-i] = '\0';
  return str;
}


/******************************************************************************
 * void sa_mojibakebousi(char *buf);
 *
 * purpose
 *    ʸλijĤ֤üʸ(0x00-0x20)Ĥ֤
 *
 * parameters
 *    buf:  ʸ
 *
 * description
 *   ʸɻߥ르ꥺ  ;פʴɤ٤(970126 tatuo-y)
 *    %%%..  Ƭ(0x80ʾ)³硢Ƭΰʸ٤
 *    ....%  Ǹ˴ɤ³硢Ǹΰʸ٤
 *    %%%%%  ƴɤʸĹʤСǸΰʸ٤
 *****************************************************************************/
void sa_mojibakebousi(char *buf){
  int i, top80_ctr = 0, last80_ctr = 0, top80_flag = 1;

  for(i = 0; i < strlen(buf); i++) {
    if((unsigned char)buf[i] < 0x20) buf[i] = '!'; /* üʸ !  */
    if((unsigned char)buf[i] >= 0x80){ /* ɤΤȤν */
      last80_ctr++;
      if(top80_flag == 1) top80_ctr++;
    }else{ /* ̤ʸΤȤν */
      top80_flag = 0;
      last80_ctr = 0;
    }
  }


  if(top80_ctr % 2 == 1 && top80_ctr == strlen(buf)) buf[i-1] = '%';
  else {
    /* ʸɻ: Ƭ˴θʬ褿Ȥ % ˤ롥 */
    if(top80_ctr % 2 == 1) buf[0] = '%';
    /* : Ǹ˴ʬ褿Ȥ % ˤ롥 */
    if(last80_ctr % 2 == 1) buf[i-1] = '%';
  }
}


/******************************************************************************
 * void sa_ctrl_code_tubusi(char *buf);
 *
 * purpose
 *    üʸ(0x00-0x20)Ĥ֤
 *
 * parameters
 *    buf:  ʸ
 *****************************************************************************/
void sa_ctrl_code_tubusi(char *buf){
  int i;
  for(i = 0; i < strlen(buf); i++)
    if((unsigned char)buf[i] < 0x20) buf[i] = '!'; /* üʸ !  */
}


/******************************************************************************
 * int long_cmp(const void *data1, const void *data2);
 *
 * purpose
 *   ʸ
 *
 * parameters
 *   data1 : ʸ1
 *   data2 : ʸ2
 *
 * return value
 *   -1 ʲ : *data1 < *data2   ('abc...' < 'bbc...')
 *    0      : *data1 == *data2  ('abcde' == 'abcde')
 *    1 ʾ : *data1 > *data2   ('abc...' > 'aab...')
 *
 * description
 *   sort ѤӥХåؿ(sa_uniq_nearǻ)
 *****************************************************************************/
static int long_cmp(const void *data1, const void *data2)
{
  long *l1, *l2;
  long ret;

  l1 = (long*) data1;
  l2 = (long*) data2;
  ret = *l1 - *l2;
  return (ret>0)? 1: (ret<0)? -1: 0;
}

/******************************************************************************
 * eresult sa_uniq_near(SUFARY *ret, SUFARY *ary1, SUFARY *ary2,
 *                      int is_near, int width) *
 * purpose
 *   ܥå
 *
 * parameters
 *   ret   : ֤ͳǼSUFARY
 *   ary1,2: ӤSUFARY
 *   is_near: 1..near, 0..exact
 :   width : 
 *
 * return value
 *   ץ³⡼
 *
 * description
 *   줰餤νʤmain.c˰ܤ
 *****************************************************************************/
eresult sa_uniq_near(SUFARY *ret, SUFARY *ary1, SUFARY *ary2, int is_near, int width)
{
  /*  SUFARY *ret = ary1;*/
  long i, j, tmp;
  long size1 = sa_top(ary1) - sa_bottom(ary1) + 1; /* 980327 for NEW sa_sel */
  long size2 = sa_top(ary2) - sa_bottom(ary2) + 1; /* 980327 for NEW sa_sel */
  long size  = (size1 > size2)? size1: size2;
  long *buf1 = (long *)alloca(size1 * sizeof(long));
  long *buf2 = (long *)alloca(size2 * sizeof(long));
  long *buf  = (long *)malloc(size  * sizeof(long));

  for (i = 0; i < size1; i++){ /* 980327 for NEW sa_sel */
    buf1[i] = sa_aryidx2txtidx(ary1, sa_bottom(ary1) + i);
  }
  for (i = 0; i < size2; i++){ /* 980327 for NEW sa_sel */
    buf2[i] = sa_aryidx2txtidx(ary2, sa_bottom(ary2) + i);
  }

  /*  */
  qsort(buf1, size1, sizeof(long),(int(*)(const void*,const void*))(long_cmp));
  qsort(buf2, size2, sizeof(long),(int(*)(const void*,const void*))(long_cmp));

  for(i = 0, j = 0, tmp = 0; i < size1 && j < size2;){
    if (buf1[i] >= buf2[j])
/* if (buf1[i] > buf2[j])  줫顢ѹޤ 980130 tatuo-y */
/* äơ a[near 4]a Ȥ xxxxxxxaxxxxxx ˤޥå㤦 */
      j++;
    else if (is_near && buf2[j] - buf1[i] > width)
      i++;
    else if (!is_near && buf2[j] - buf1[i] != width)
      i++;
    else {
      buf[tmp] = buf1[i];
/*      printf("%ld %ld\n",buf[tmp],buf1[i]);*/
      tmp++; i++;
    }
  }

  if (tmp == 0)
    return FAIL;

  ret->op_result = (caddr_t)buf;
  ret->arymap = (caddr_t)buf;
  ret->left = 0;
  ret->right = tmp-1;
  return CONT;
}


/******************************************************************************
 *   long *sa_common_prefix_search(SUFARY *ary, char *kw, char we);
 *
 * purpose
 *   Suffix Array  TRIE ȤߤʤơDzϥԤʤ
 *
 * parameters
 *   ary : оarray
 *   kw  : 
 *   we  : (ڤ)ʸ
 *
 * return value
 *   ƥȥǥå(long)ؤΥݥ
 *
 * description
 *  [Common Prefix Search Ȥ...] ɡˡPrefixޥå
 *   ʸФָɤפǤϤʤ衣
 *   :             a, abc, any, anybody, anymore, ...
 *         anybody
 *                   a, any, anybody
 * 
 *  [] ֤(longݥ)ؤκǽǤ˸̿äƤ롣
 *         ʹߡƥȥǥå(long)³
 * 
 * since 1998/04/09
 *****************************************************************************/
#define IS_EUC(X) ((unsigned char)(X) & 0x80) /* ɤΤȤν */
long *sa_common_prefix_search(SUFARY *ary, char *kw, char we)
{
  int i, kwlen, ret_idx = 1;
  /*char *s;*/
  long keep_from, keep_to, tmp, pos;
  int total_element = 32; /**/
  long *ret = malloc(total_element * sizeof(long));

/*  ret = (long *)malloc(sizeof(long)); */

  kwlen = strlen(kw);
  /*s = (char *)alloca(kwlen+1);
  memset(s, 0, kwlen+1);*/ /* ʸ '\0' ˤ */

  for(i = 0; i < kwlen;){
    int next;
    /*s[i] = kw[i];*/ /* ʸ䤷ʤ鸡Τǡʸ䤹 */
    if(IS_EUC(kw[i])){
      /*s[i+1] = kw[i+1];*/ /* EUCʤ⤦Х... */
      next = i+2;
    } else
      next = i+1;
    /*s[next] = '\0';*/ /* ǰΤ... */
    /* TRIEõǤȽ */
    /*if(sa_search(ary, s, next, i) != CONT) break;*/
    if(sa_search(ary, kw+i, next-i, i) != CONT) break; /* 981230 */
    /*  */
    keep_from = ary->left;
    keep_to = ary->right;

    /*s[next] = we;*/ /* ߤʸ + (ڤ)ʸ */
    /*printf("[%s]\n",s);*/

    /*if(sa_search(ary, s, next+1, next) == CONT){*/
    if(sa_search(ary, &we, 1, next) == CONT){ /* 981230 */
      /*
      printf("FOUND!!! [%s] %ld-%ld\n", s, ary->left, ary->right);
      printf("size %d\n",ret_idx);
      */
      int a = (ret_idx+(ary->right-ary->left+1));
      /*printf("--- %d %d \n", total_element,a);*/
      if(a >= total_element-1){
	total_element = total_element * 2 + a;
	ret = (long *)realloc(ret, total_element * sizeof(long));
	if(ret == NULL){
	  fprintf(stderr,"SUFARY CPS error: Couldn't exapnd.\n");
	  exit(1);
	}
      }

      /* leftrightޤǥ롼 */
      for (tmp = ary->left; tmp <= ary->right; tmp++){
	ret[ret_idx] = sa_aryidx2txtidx(ary, tmp); /* ƥȰ֤ */
	ret_idx++;
      }
    }

    /* ָߤʸ + (ڤ)ʸפǸξ֤᤹*/
    ary->left = keep_from;
    ary->right = keep_to;

    i = next;
  }
  /* ret[ret_idx] = -1;*/
  ret[0] = ret_idx-1;
/*for(tmp=0;tmp<ret_idx+1;tmp++)printf(" %d",ret[tmp]); printf("\n");*/
  return ret;
}



/******************************************************************************
 *            void sa_didsearch(DID *d, long target);
 *
 * purpose
 *   ¹
 *
 * parameters
 *   *d : DocID
 *   target : оݤǤֿ
 *
 * return value
 *
 * description
 *   2ʬõˤꡢŪǥå̤κõ
 *
 * () S ϥɥȤγϡEϽλ֤ɽ
 *      target=24 ʤ 2056 Ūɥ
 *         d->doc_start = 20, d->doc_size=36  
 *      target=67 ϥɥȳ
 *         d->doc_start = -1, d->doc_size=-1  
 *
 * DocID |  0 | 12 | 20 | 56 | 89 | 97 |
 *          S    E    S    E    S    E 
 *
 *****************************************************************************/
long sa_dididx2txtidx(DID * did, long idx)
{
    if (is_little_endian())
        return reverse_byte_order_long(did->docid[idx]);
    else
        return did->docid[idx];
}

void sa_didsearch(DID *did, long target){
  long l = 0, size = did->didsize, cur;
  long r = size;
  long *la = (long *)did->didmap;
  int inside_doc_flag = 1;

  /*  printf("target = %ld\n",target);*/
  while(1){
    cur = (r + l)/2;
    /*printf("l=[%ld] r=[%ld] cur=[%ld]\n",l,r,cur);*/
    /*    printf("la[%d] = %ld\n",cur,la[cur]);*/
    if (sa_dididx2txtidx(did, cur) < target) {
      if(cur + 1 == size) break;
      if (target < sa_dididx2txtidx(did, cur + 1))
	  break;
      l = cur +1;
    } else if (target < sa_dididx2txtidx(did, cur)) {
      if(cur == 0){inside_doc_flag = 0; break;}
      if (sa_dididx2txtidx(did, cur - 1) < target) {cur--; break;}
      r = cur -1;
    } else break; /* == */

  }
  /*printf(">> la[%ld] = %ld\n",cur,la[cur]);*/
  if(cur % 2 == 1) inside_doc_flag = 0;
  /*printf(">> %d\n",inside_doc_flag);*/
  if(inside_doc_flag == 0){
    did->doc_start = -1;
    did->doc_size = -1;
    did->doc_no = -2; /* sa_doc_no() Ǥ doc_no2 ֤ */
  }else{
    did->doc_start = sa_dididx2txtidx(did, cur);
    did->doc_size = sa_dididx2txtidx(did, cur + 1) - did->doc_start;
    did->doc_no = cur;
  }
}


/**********************************************
 *   char *sa_getstr(SUFARY *ary, long form, long size);
 *
 * purpose
 *   from ʸܤĹ size ʸäƤ
 *
 * parameters
 *   ary : оarray
 *   fram, size : äƤʸꤹ
 *
 * return value
 *   str Υݥ
 **********************************************/
char *sa_getstr(SUFARY *ary, long from, long size)
{
  char *str;
  str = (char *)malloc(size+1);
  strncpy(str, ary->txtmap+from, size);
  str[size] = '\0';
  return str;
}


long sa_doc_start(DID *did){  /* 981022 */
  return did->doc_start;
}

long sa_doc_size(DID *did){  /* 981022 */
  return did->doc_size;
}

long sa_doc_no(DID *did){  /* 981028 ̤DocIDǤΰ(ź) */
  return (did->doc_no)/2;
}

long sa_did_size(DID *did){  /* 981028 DocID礭 */
  return (did->didsize)/2;
}