Work/bsptree/Rgbtree.cpp

#include <bsptree/rgbtree.hpp>

WORD RGBTree::insertItems(Array<RGBIndex> &rgbItems)
{
  size_t size((size_t)rgbItems.size());
  short indexDescending;
  short indexAscending;

  if(!size)return FALSE;
  indexDescending=middleIndex(rgbItems);
  indexAscending=indexDescending+1;
  for(;indexDescending>=0;indexDescending--)insertItem(rgbItems[indexDescending]);
  for(;indexAscending<size;indexAscending++)insertItem(rgbItems[indexAscending]);
  return size;
}

WORD RGBTree::middleIndex(Array<RGBIndex> &rgbItems)const
{
	RGBColor middleItem(CenterColor,CenterColor,CenterColor);
	size_t size((size_t)rgbItems.size());
	LONG minDistance(0xFFFFFFL);
	LONG tmpDistance;
	WORD centerIndex;

  for(short rgbIndex=0;rgbIndex<size;rgbIndex++)
  {
		tmpDistance=rgbItems[rgbIndex]-middleItem;
	  if(tmpDistance<minDistance){minDistance=tmpDistance;centerIndex=rgbIndex;}
  }
  return centerIndex;
}

TreeNode<RGBIndex> *RGBTree::insertNode(TreeNode<RGBIndex> *lpRootNode,TreeNode<RGBIndex> *lpCurrentNode,const RGBIndex &rgbItem)
{
  if(!lpCurrentNode)
  {
	 lpCurrentNode=new TreeNode<RGBIndex>(rgbItem);
	 assert(0!=lpCurrentNode);
	 if(!lpRootNode)return lpCurrentNode;
	 mColorKey.prevKey();
	 if(mColorKey.isLess(rgbItem,lpRootNode->item()))lpRootNode->leftNode(lpCurrentNode);
	 else lpRootNode->rightNode(lpCurrentNode);
	 return lpCurrentNode;	 
  }
  if(!(rgbItem==lpCurrentNode->item()))
  {
	 if(mColorKey.isLess(rgbItem,lpCurrentNode->item()))
	 {
		mColorKey.nextKey();
		return insertNode(lpCurrentNode,lpCurrentNode->leftNode(),rgbItem);
	 }
	 else
	 {
		mColorKey.nextKey();
		return insertNode(lpCurrentNode,lpCurrentNode->rightNode(),rgbItem);
	 }
  }
  return 0;
}

RGBIndex *RGBTree::searchNodeExact(TreeNode<RGBIndex> *lpRootNode,const RGBIndex &rgbItem)
{
  while(lpRootNode&&!(rgbItem==lpRootNode->item()))
  {
	 if(mColorKey.isLess(rgbItem,lpRootNode->item()))lpRootNode=lpRootNode->leftNode();
	 else	lpRootNode=lpRootNode->rightNode();
	 mColorKey.nextKey();
  }
  if(lpRootNode)return &lpRootNode->item();
  return 0;
}

RGBIndex *RGBTree::searchNodeNearest(TreeNode<RGBIndex> *lpRootNode,const RGBIndex &rgbItem)
{
	TreeNode<RGBIndex> *lpLastNode=0;
	TreeNode<RGBIndex> *lpTempNode;
	LONG minDistance(0xFFFFFFL);
  RGBIndex lowerRGB(rgbItem);
  RGBIndex upperRGB(rgbItem);
	RGBIndex *lpBestRGB=0;
  LONG tmpDistance;
	ColorKey colorKey;

  if(!lpRootNode)return 0;
  rewind();
  lowerRGB-=mThreshold;
  upperRGB+=mThreshold;
  pushNode(TreeNodeEx(*lpRootNode,colorKey));
  while(size()&&minDistance)
  {
	 popNode();
	 lpTempNode=&currentNode();
	 if(lpLastNode==lpRootNode)break;
	 else lpLastNode=lpRootNode;
	 colorKey=currentNode();
	 while(lpTempNode&&minDistance)
	 {
		if(colorKey.isLessEqual(lowerRGB,lpTempNode->item()))
		{
		  if(colorKey.isLessEqual(lpTempNode->item(),upperRGB))
		  {
			 pushNode(TreeNodeEx(*lpTempNode,colorKey));
			 tmpDistance=lpTempNode->item()-rgbItem;
			 if(!tmpDistance)return &lpTempNode->item();
			 if(tmpDistance<minDistance){minDistance=tmpDistance;lpBestRGB=&lpTempNode->item();}
		  }
		}
		if(colorKey.isLess(rgbItem,lpTempNode->item()))lpTempNode=lpTempNode->leftNode();
		else lpTempNode=lpTempNode->rightNode();
		colorKey.nextKey();
	 }
  }
  return lpBestRGB;
}

WORD RGBTree::insertItem(const RGBIndex &rgbItem)
{
  mColorKey.colorKey(ColorKey::RedKey);
	if(!rootNode())
	{
	  if(!rootNode(insertNode(rootNode(),rootNode(),rgbItem)))return FALSE;
		leaves(leaves()+1);
		return TRUE;
	}
	else
	{
	  if(!insertNode(rootNode(),rootNode(),rgbItem))return FALSE;
		leaves(leaves()+1);
		return TRUE;
	}
}

BOOL RGBTree::searchItem(RGBColor &rgbColor,SearchType searchType)
{
	RGBIndex rgbIndex(rgbColor);

	if(!searchItem(rgbIndex,searchType))return FALSE;
  rgbColor=(RGBColor&)rgbIndex;
  return TRUE;
}

BOOL RGBTree::searchItem(RGBIndex &rgbItem,SearchType searchType)
{
	RGBIndex *lpItem;
  WORD currentThreshold(mThreshold);

  if(!rootNode())return FALSE;
	mColorKey.colorKey(ColorKey::RedKey);
	lpItem=searchNodeExact(rootNode(),rgbItem);
	if(lpItem){rgbItem=*lpItem;return TRUE;}
	else if(SearchExact==searchType)return FALSE;
	setThreshold(MaxThreshold);
	lpItem=searchNodeNearest(rootNode(),rgbItem);
	setThreshold(currentThreshold);
  if(lpItem){rgbItem=*lpItem;return TRUE;}
  return FALSE;
}

BOOL RGBTree::searchItem(RGBIndex &rgbItem,SmartPointer<RGBIndex> &rgbIndex,SearchType searchType)
{
	RGBIndex *lpItem;
  WORD currentThreshold(mThreshold);

  if(!rootNode())return FALSE;
	mColorKey.colorKey(ColorKey::RedKey);
	lpItem=searchNodeExact(rootNode(),rgbItem);
	if(lpItem){rgbIndex=lpItem;return TRUE;}
	else if(SearchExact==searchType)return FALSE;
	setThreshold(MaxThreshold);
	lpItem=searchNodeNearest(rootNode(),rgbItem);
	setThreshold(currentThreshold);
  if(lpItem){rgbIndex=lpItem;return TRUE;}
  return FALSE;
}