文字列照合・探索ライブラリ 使用例（バイナリ探索）

/*		t_search.c		探索テストルーチン		*/
#include <stdio.h>
#include <stdlib.h>
#include "match.h"

#define		MASK		987612345L
#define		uchar		unsigned char

long _idum_o0;		/* ornd0()〜ornd2()の乱数核 */

void init_ornd0(long seed);
int irnd(int max, int min);
double ornd0(void);
int *mkdata_i(int n, int min, int max);
uchar *mkdata_c(int n, uchar min, uchar max);
double *mkdata_d(int n, double min, double max);
uchar **mkdata_s(int n, int smin, int smax, uchar min, uchar max);
uchar **mkdata_sd(int n, int smin, int smax, uchar min, uchar max);
void qsort_i(int a[], int n);
void subquick_i(int *first, int *last);
void qsort_d(double a[], int n);
void subquick_d(double *first,double *last);
void qsort_c(uchar *a[], int n);
int dbldel_i(int a[], int n, int flag);
int dbldel_d(double a[], int n, int flag);
int dbldel_c(uchar *a[], int n, int flag);
void inssort_i(int a[], int n);
void inssort_d(double a[], int n);
void inssort_c(uchar *a[], int n);
int strcomp(uchar *a, uchar *b);
void shuffle_c(uchar **a, int n);

int main(void)
{
	int *data_i, *ip, srch_i;
	double *data_d, *dp, srch_d;
	uchar **data_c, **cp, *srch_c;
	int i, n = 100, nn;

	init_ornd0(1L);

	data_i = mkdata_i(n, 1, 299);
	qsort_i(data_i, n);
	nn = dbldel_i(data_i, n, 1);
	printf("[int data   %d ]\n", nn);
	for(i = 0, ip = data_i; i < nn; )	printf("%3d:%3d ", i++, *ip++);
	putchar('\n');
	for(i = 0; i < 10; i++)
	{
		srch_i = irnd(299, 1);
		printf("search %3d -->  result = %d\n", srch_i, bsrch_i(srch_i, data_i, nn));
	}
	printf("\n\n");

	data_d = mkdata_d(n, 1., 299.);
	for(i = 0, dp = data_d; i < n; i++)	*dp++ = (int)(*dp);
	qsort_d(data_d, n);
	nn = dbldel_d(data_d, n, 1);
	printf("[double data   %d ]\n", nn);
	for(i = 0, dp = data_d; i < nn; )	printf("%3d:%3.0f ", i++, *dp++);
	putchar('\n');
	for(i = 0; i < 20; i++)
	{
		srch_d = irnd(299, 1);
		printf("search %3.0f -->  result = %d\n", srch_d, bsrch_d(srch_d, data_d, nn));
	}
	printf("\n\n");

	data_c = mkdata_sd(n, 2, 2, 'a', 'k');
	qsort_c(data_c, n);
	printf("[string data   %d ]\n", n);
	for(i = 0, cp = data_c; i < n; )	printf("%3d:%2s  ", i++, *cp++);
	putchar('\n');
	for(i = 0; i < 10; i++)
	{
		srch_c = mkdata_c(2, 'a', 'k');
		printf("search %2s -->  result = %d\n", srch_c, bsrch_c(srch_c, data_c, n));
	}
	printf("\n\n");
	return 1;
}

double ornd0(void)					/* Park and Miller の「最低基準」乱数 */
{
	long w;
	double d = 1. / 2147483647.;

	w = _idum_o0 / 127773L;
	if((_idum_o0 = (_idum_o0 - w * 127773L) * 16807L - w * 2836L) <= 0)
		_idum_o0 += 2147483647L;
	return (double)_idum_o0 * d;
}

int irnd(int max, int min)
{
	return min + (int)(ornd0() * (double)(max - min + 1));
}

void init_ornd0(long seed)
{
	_idum_o0 = seed ^ MASK;
}

int *mkdata_i(int n, int min, int max)
{
	int i, *data, *p;

	if(n < 1 || max < min)
	{
		fprintf(stderr, "Error : illegal input  in mkdata_i()\n");
		fprintf(stderr, "    n=%d, min=%d, max=%d\n", n, min, max);
		return NULL;
	}
	data = (int *)malloc(n * sizeof(int));
	if(data == NULL)
	{
		fprintf(stderr, "Error : out of memory  in mkdata_i()\n");
		return NULL;
	}
	for(i = 0, p = data; i < n; i++)	*p++ = irnd(max, min);
	return data;
}

uchar *mkdata_c(int n, uchar min, uchar max)
{
	int i;
	uchar *data, *p;

	if(n < 1 || max < min)
	{
		fprintf(stderr, "Error : illegal input  in mkdata_c()\n");
		fprintf(stderr, "    n=%d, min=%u, max=%u\n", n, min, max);
		return NULL;
	}
	data = (uchar *)malloc((n + 1) * sizeof(uchar));
	if(data == NULL)
	{
		fprintf(stderr, "Error : out of memory  in mkdata_c()\n");
		return NULL;
	}
	for(i = 0, p = data; i < n; i++)	*p++ = (uchar)irnd(max, min);
	*p = '\0';
	return data;
}

double *mkdata_d(int n, double min, double max)
{
	int i;
	double *data, *p;

	if(n < 1 || max < min)
	{
		fprintf(stderr, "Error : illegal input  in mkdata_d()\n");
		fprintf(stderr, "    n=%d, min=%e, max=%e\n", n, min, max);
		return NULL;
	}
	data = (double *)malloc(n * sizeof(double));
	if(data == NULL)
	{
		fprintf(stderr, "Error : out of memory  in mkdata_d()\n");
		return NULL;
	}
	for(i = 0, p = data; i < n; i++)	*p++ = min + (max - min) * ornd0();
	return data;
}

uchar **mkdata_s(int n, int smin, int smax, uchar min, uchar max)
{
	int i, *len, *lp;
	uchar **data, **p, *pp;

	if(n < 1 || max < min || smax < smin || smin < 1)
	{
		fprintf(stderr, "Error : illegal input  in mkdata_s()\n");
		fprintf(stderr, "    n=%d, smin=%d, smax=%d, min=%u, max=%u\n",
			n, smin, smax, min, max);
		return NULL;
	}
	data = (uchar **)malloc(n * sizeof(uchar *));
	len = mkdata_i(n, smin, smax); 
	if(data == NULL || len == NULL)
	{
		fprintf(stderr, "Error : out of memory  in mkdata_s()\n");
		return NULL;
	}
	for(i = 0, p = data, lp = len; i < n; i++, lp++)
	{
		pp = *p++ = (uchar *)malloc((smax + 1) * sizeof(uchar *));
		while((*lp)--)	*pp++ = irnd(max, min);
		*pp = '\0';
	}
	free((char *)len);
	return data;
}

uchar **mkdata_sd(int n, int smin, int smax, uchar min, uchar max)
{
	uchar **data, **dp, *dpp; 
	int i, len, nn;

	data = mkdata_s(n, smin, smax, min, max);
	while(1)
	{
		qsort_c(data, n);
		if((nn = n - dbldel_c(data, n, 1)) == 0)	break;
		dp = data;
		while(nn--) 
		{
			while(**dp)	dp++;
			len = irnd(smax, smin);
			dpp = *dp;
			while(len--)	*dpp++ = irnd(max, min);
			*dpp = '\0';
		} 
	}
	shuffle_c(data, n);
	return data;
}

void qsort_i(int a[], int n)
{
	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in qsort_i()\n");
		return;
	}
	subquick_i(a, a + n - 1);
}

void subquick_i(int *first, int *last)
{
	int w;
	int *i, *j, *p;
	int x, t;

	if((w = last - first) < 11)	inssort_i(first, w + 1);
	else
	{
		x = *(first + (int)((last - first) / 2));
		i = first;
		j = last;
		do
		{
			while(x > *i)	i++;
			while(*j > x)	j--;
			if(i > j)	break;
			t = *i;
			*i++ = *j;
			*j-- = t;
		} while(i <= j);
		if(i - 1 > first)	subquick_i(first, i - 1);
		if(j + 1 < last)	subquick_i(j + 1, last);
	}
}

void qsort_d(double a[], int n)
{
	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in qsort_d()\n");
		return;
	}
	subquick_d(a, a + n - 1);
}

void subquick_d(double *first,double *last)
{
	int w;
	double *i, *j, *p;
	double x, t;

	if((w = last - first) < 11)	inssort_d(first, w + 1);
	else
	{
		x = *(first + (int)((last - first) / 2));
		i = first;
		j = last;
		do
		{
			while(x > *i)	i++;
			while(*j > x)	j--;
			if(i > j)	break;
			t = *i;
			*i++ = *j;
			*j-- = t;
		} while(i <= j);
		if(i - 1 > first)	subquick_d(first, i - 1);
		if(j + 1 < last)	subquick_d(j + 1, last);
	}
}

void qsort_c(uchar *a[], int n)
{
	uchar **i, **j, **l, **r;
	uchar **st1[32], **st2[32], ***s1, ***s2;
	uchar *x, *w;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in qsort_c()\n");
		return;
	}

	s1 = st1;
	s2 = st2;
	*s1 = a;
	*s2 = a + n - 1;
	do
	{
		l = *s1--;
		r = *s2--;
		if(r - l < 11)	inssort_c(l, r - l + 1);
		else
		{
			do
			{
				i = l;
				j = r;
				x = *(l + (int)((r - l) / 2));
				do
				{
					while(strcomp(x, *i) > 0)	i++;
					while(strcomp(*j, x) > 0)	j--;
					if(i > j)	break;
					w = *i;
					*i++ = *j;
					*j-- = w;
				} while(i <= j);
				if(j - l < r - i)
				{
					if(i < r)
					{
						*(++s1) = i;
						*(++s2) = r;
					}
					r = j;
				}
				else
				{
					if(l < j)
					{
						*(++s1) = l;
						*(++s2) = j;
					}
					l = i;
				}
			} while(l < r);
		}
	}while (s1 >= st1);
	return;
}

int dbldel_i(int a[], int n, int flag)
{
	int i, nn;
	int *dp, *wp;

	nn = 1;
	wp = dp = a + 1;
	for(i = 1; i < n; i++, dp++)
	{
		if(*(dp - 1) - *dp)
		{
			if(wp != dp && flag)	*wp = *dp;
			wp++;
			nn++;
		}
	}
	if(nn != n && flag)	for(i = nn; i < n; i++)	*wp++ = 0;
	return nn;
}

int dbldel_d(double a[], int n, int flag)
{
	int i, nn;
	double *dp, *wp;

	nn = 1;
	wp = dp = a + 1;
	for(i = 1; i < n; i++, dp++)
	{
		if(*(dp - 1) - *dp)
		{
			if(wp != dp && flag)	*wp = *dp;
			wp++;
			nn++;
		}
	}
	if(nn != n && flag)	for(i = nn; i < n; i++)	*wp++ = 0.;
	return nn;
}

int dbldel_c(uchar *a[], int n, int flag)
{
	int i, len, nn;
	uchar **dp;

	if(flag)
	{
		for(i = nn = 1, dp = a + 1; i < n; i++, dp++)
		{
			if(strcmp(*(dp - 1), *dp))	nn++;
			else 	**dp = '\0';
		}
	}
	else
	{
		for(i = nn = 1, dp = a + 1; i < n; i++, dp++)
			if(strcmp(*(dp - 1), *dp))	nn++;
	}
	return nn;
}

void inssort_i(int a[], int n)
{
	int *p, *pj, *alast, *q, x;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in inssort_i()\n");
		return;
	}
	alast = (p = a) + n - 1;
	while(++p <= alast)
	{
		q = (pj = p) - 1;
		x = *p;
		while(q >= a && *q > x)	*pj-- = *q--;
		*pj = x;
	}
}

void inssort_d(double a[], int n)
{
	double *p, *pj, *alast, *q, x;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in inssort_d()\n");
		return;
	}
	alast = (p = a) + n - 1;
	while(++p <= alast)
	{
		q = (pj = p) - 1;
		x = *p;
		while(q >= a && *q > x)	*pj-- = *q--;
		*pj = x;
	}
}

void inssort_c(uchar *a[], int n)
{
	uchar **p, **pj, **alast, **q, *x;

	if(n <= 1)
	{
		fprintf(stderr, "Error : n <= 1  in inssort_c()\n");
		return;
	}
	alast = (p = a) + n - 1;
	while(++p <= alast)
	{
		q = (pj = p) - 1;
		x = *p;
		while(q >= a && strcomp(*q, x) > 0)	*pj-- = *q--;
		*pj = x;
	}
}

int strcomp(uchar *a, uchar *b)
{
	uchar *p, *q;

	p = a;
	q = b;
	while(*p)
	{
		if(*p > *q)	return 1;
		if(*p++ < *q++)	return -1;
	}
	if(*q)	return -1;
	return 0;
}

void shuffle_c(uchar **a, int n)
{
	int i, m;
	uchar **p, **q, *w;

	for(i = 0, m = n * 5; i < m; i++)
	{
		p = a + (int)(ornd0() * n);
		q = a + (int)(ornd0() * n);
		w = *p;
		*p = *q;
		*q = w;
	}
}