module ytl.map;

/+ // まだ作りかけなのでコンパイルは通らﾅｰ

///	C++のstd::mapに相当するテンプレート
template map(T,S) {	//	TからSへの連想記憶

///	setテンプレートの本体
/**
	奥村 晴彦著『Ｃ言語による最新アルゴリズム事典』
	より、b-treeのソースを参考にさせていただいています。
*/
class map {

	/// デモ用にB木を表示(整数型のみ):setのdebug用。※ 呼び出さないで！
	void printtree()
	{
		Page p = root;
		if (!p) {  printf(".");	return;  }
		printf("(");
		for (int i = 0; i < p.n; ++i) {
			printtree(p.branch[i]);  /* 再帰呼出し */
			printf("%d", cast(int)(p.key[i]));
//			p.key[i].print();
		}
		printtree(p.branch[p.n]);  /* 再帰呼出し */
		printf(")");
	}

private:
	const int M=2;	/* 1ページのデータ数の上限の半分 */

	class Page {				/* ページの定義 */
		int n;					/* このページが保持しているデータ数 */
		T key[2 * M]; 			/* 保持しているキー */
		S data[2 * M];			/* キーに対するデータ */
		page branch[2 * M + 1]; /* 他ページへのポインタ */
	};

	Page root; 				/* B木の根 */

//	bool done, deleted, undersize;	 /* 論理型の変数 */

	/// キーからそれに対するデータを取り出す
	S getData(T key)
	{
		Page p = root;
		int i;
		while (!p) {
			i = 0;
			while (i < p.n && p.key[i] < key) ++i;
			if (i < p.n && p.key[i] == key) {
				//	見つかった！
				return p.data[i];
			}
			p = p.branch[k];
		}
		return S.init; // 見つからﾅｰ
	}



	void insertitem(pageptr p, int k) 
	/* {\tt key} を {\tt p->key[k]} に挿入 */
{
	int i;

	for (i = p->n; i > k; i--) {
		p->key[i] = p->key[i - 1];
		p->branch[i + 1] = p->branch[i];
	}
	p->key[k] = key;  p->branch[k + 1] = newp;	p->n++;
}

void split(pageptr p, int k)  /* {\tt key} を {\tt p->key[k]} に挿入し, ページ {\tt p} を割る */
{
	int j, m;
	pageptr q;

	if (k <= M) m = M;	else m = M + 1;
	q = newpage();
	for (j = m + 1; j <= 2 * M; j++) {
		q->key[j - m - 1] = p->key[j - 1];
		q->branch[j - m] = p->branch[j];
	}
	q->n = 2 * M - m;  p->n = m;
	if (k <= M) insertitem(p, k);
	else		insertitem(q, k - m);
	key = p->key[p->n - 1];
	q->branch[0] = p->branch[p->n];  p->n--;
	newp = q;  /* 新しいページを {\tt newp} に入れて戻る */
}

void insertsub(pageptr p)  /* {\tt p} から木を再帰的にたどって挿入 */
{
	int k;

	if (p == NULL) {
		done = FALSE;  newp = NULL;  return;
	}
	k = 0;
	while (k < p->n && p->key[k] < key) k++;
	if (k < p->n && p->key[k] == key) {
		message = "もう登録されています";  done = TRUE;
		return;
	}
	insertsub(p->branch[k]);
	if (done) return;
	if (p->n < 2 * M) {   /* ページが割れない場合 */
		insertitem(p, k);  done = TRUE;
	} else {			  /* ページが割れる場合 */
		split(p, k);  done = FALSE;
	}
}

void insert(void)  /* キー {\tt key} をB木に挿入 */
{
	pageptr p;

	message = "登録しました";
	insertsub(root);  if (done) return;
	p = newpage();	p->n = 1;  p->key[0] = key;
	p->branch[0] = root;  p->branch[1] = newp;	root = p;
}

void removeitem(pageptr p, int k)
	/* {\tt p->key[k]}, {\tt p->branch[k+1]} を外す. */
	/* ページが小さくなりすぎたら {\tt undersize} フラグを立てる. */
{
	while (++k < p->n) {
		p->key[k - 1] = p->key[k];
		p->branch[k] = p->branch[k + 1];
	}
	undersize = --(p->n) < M;
}

void moveright(pageptr p, int k)
	/* {\tt p->branch[k - 1]} の最右要素を */
	/* {\tt p->key[k - 1]} 経由で {\tt p->branch[k]} に動かす */
{
	int j;
	pageptr left, right;

	left = p->branch[k - 1];  right = p->branch[k];
	for (j = right->n; j > 0; j--) {
		right->key[j] = right->key[j - 1];
		right->branch[j + 1] = right->branch[j];
	}
	right->branch[1] = right->branch[0];
	right->n++;
	right->key[0] = p->key[k - 1];
	p->key[k - 1] = left->key[left->n - 1];
	right->branch[0] = left->branch[left->n];
	left->n--;
}

void moveleft(pageptr p, int k)
	/* {\tt p->branch[k]} の最左要素を */
	/* {\tt p->key[k - 1]} 経由で {\tt p->branch[k - 1]} に動かす */
{
	int j;
	pageptr left, right;

	left = p->branch[k - 1];  right = p->branch[k];
	left->n++;
	left->key[left->n - 1] = p->key[k - 1];
	left->branch[left->n] = right->branch[0];
	p->key[k - 1] = right->key[0];
	right->branch[0] = right->branch[1];
	right->n--;
	for (j = 1; j <= right->n; j++) {
		right->key[j - 1] = right->key[j];
		right->branch[j] = right->branch[j + 1];
	}
}

void combine(pageptr p, int k)	/* {\tt p->branch[k - 1]}, {\tt p->branch[k]} を結合する */
{
	int j;
	pageptr left, right;

	right = p->branch[k];
	left = p->branch[k - 1];
	left->n++;
	left->key[left->n - 1] = p->key[k - 1];
	left->branch[left->n] = right->branch[0];
	for (j = 1; j <= right->n; j++) {
		left->n++;
		left->key[left->n - 1] = right->key[j - 1];
		left->branch[left->n] = right->branch[j];
	}
	removeitem(p, k - 1);
	free(right);
}

void restore(pageptr p, int k)	/* 小さくなりすぎたページ {\tt p->branch[k]} を修復する */
{
	undersize = FALSE;
	if (k > 0) {
		if (p->branch[k - 1]->n > M) moveright(p, k);
		else combine(p, k);
	} else {
		if (p->branch[1]->n > M) moveleft(p, 1);
		else combine(p, 1);
	}
}

void deletesub(pageptr p)  /* ページ {\tt p} から再帰的に木をたどり削除 */
{
	int k;
	pageptr q;

	if (p == NULL) return;	/* 見つからなかった */
	k = 0;
	while (k < p->n && p->key[k] < key) k++;
	if (k < p->n && p->key[k] == key) {  /* 見つかった */
		deleted = TRUE;
		if ((q = p->branch[k + 1]) != NULL) {
			while (q->branch[0] != NULL) q = q->branch[0];
			p->key[k] = key = q->key[0];
			deletesub(p->branch[k + 1]);
			if (undersize) restore(p, k + 1);
		} else removeitem(p, k);
	} else {
		deletesub(p->branch[k]);
		if (undersize) restore(p, k);
	}
}

void delete(void)  /* キー {\tt key} をB木から外す */
{
	pageptr p;

	deleted = undersize = FALSE;
	deletesub(root);  /* 根から再帰的に木をたどり削除する */
	if (deleted) {
		if (root->n == 0) {  /* 根が空になった場合 */
			p = root;  root = root->branch[0];	free(p);
		}
		message = "削除しました";
	} else message = "見つかりません";
}



}}
+/
