Navigation

Changeset 17

Timestamp:

10/10/08 14:57:31 (4 years ago)

Author:

sean

Message:

Merged in changes from Phobos SVN.

Files:

r8	r17
593	593
594	594	*paa.a = newb;
	595	_aaBalance(paa);
595	596	}
596	597	return (*paa).a;
597	598	}
598	599
599
	600	/********************************************
	601	* Balance an array.
	602	*/
	603
	604	void _aaBalance(AA* paa)
	605	{
	606	//printf("_aaBalance()\n");
	607	if (paa.a)
	608	{
	609	aaA*[16] tmp;
	610	aaA*[] array = tmp;
	611	auto aa = paa.a;
	612	foreach (j, e; aa.b)
	613	{
	614	/* Temporarily store contents of bucket in array[]
	615	*/
	616	size_t k = 0;
	617	void addToArray(aaA* e)
	618	{
	619	while (e)
	620	{ addToArray(e.left);
	621	if (k == array.length)
	622	array.length = array.length * 2;
	623	array[k++] = e;
	624	e = e.right;
	625	}
	626	}
	627	addToArray(e);
	628	/* The contents of the bucket are now sorted into array[].
	629	* Rebuild the tree.
	630	*/
	631	void buildTree(aaA** p, size_t x1, size_t x2)
	632	{
	633	if (x1 >= x2)
	634	*p = null;
	635	else
	636	{ auto mid = (x1 + x2) >> 1;
	637	*p = array[mid];
	638	buildTree(&(*p).left, x1, mid);
	639	buildTree(&(*p).right, mid + 1, x2);
	640	}
	641	}
	642	auto p = &aa.b[j];
	643	buildTree(p, 0, k);
	644	}
	645	}
	646	}
600	647	/********************************************
601	648	* Produce array of N byte keys from aa.

r5	r17
593	593
594	594	*paa.a = newb;
	595	_aaBalance(paa);
595	596	}
596	597	return (*paa).a;
597	598	}
598	599
599
	600	/********************************************
	601	* Balance an array.
	602	*/
	603
	604	void _aaBalance(AA* paa)
	605	{
	606	//printf("_aaBalance()\n");
	607	if (paa.a)
	608	{
	609	aaA*[16] tmp;
	610	aaA*[] array = tmp;
	611	auto aa = paa.a;
	612	foreach (j, e; aa.b)
	613	{
	614	/* Temporarily store contents of bucket in array[]
	615	*/
	616	size_t k = 0;
	617	void addToArray(aaA* e)
	618	{
	619	while (e)
	620	{ addToArray(e.left);
	621	if (k == array.length)
	622	array.length = array.length * 2;
	623	array[k++] = e;
	624	e = e.right;
	625	}
	626	}
	627	addToArray(e);
	628	/* The contents of the bucket are now sorted into array[].
	629	* Rebuild the tree.
	630	*/
	631	void buildTree(aaA** p, size_t x1, size_t x2)
	632	{
	633	if (x1 >= x2)
	634	*p = null;
	635	else
	636	{ auto mid = (x1 + x2) >> 1;
	637	*p = array[mid];
	638	buildTree(&(*p).left, x1, mid);
	639	buildTree(&(*p).right, mid + 1, x2);
	640	}
	641	}
	642	auto p = &aa.b[j];
	643	buildTree(p, 0, k);
	644	}
	645	}
	646	}
600	647	/********************************************
601	648	* Produce array of N byte keys from aa.