// fk_node.cpp: implementation of the fk_node
// class.
//////////////////////////////////////////////////////////////////////

#include <stdlib.h>
#include <assert.h>
#include <math.h>
//#include "fk_node.h"
#include "fk_tree.h"
#include "common.h"

static int KNODESIZE=sizeof(Knode);

//copy one set to another, space should be allocated first.
bool Copy(int *dst, int &dstLen, int *src, int len)
{
  for(dstLen=0;dstLen<len;dstLen++)
	  dst[dstLen]=src[dstLen];

  return true;
}


//intersection of the two sets.
bool Intersection(int *&dst, int & len1, int * src, int len2, bool reverse)
{
   int len=len1;
   if(len>len2)
	   len=len2;
   int *temp=(int *)fp_buf->newbuf(len,INTSIZE); 
   int cur1=0; 
   int cur2=0;
   len=0;
   while((cur1<len1)&&(cur2<len2))
   {
     if(dst[cur1]==src[cur2])
	 {
        temp[len++]=dst[cur1];
		cur1++;
		cur2++;
		continue;
     }else if(reverse)
	 {
		  if(dst[cur1]>src[cur2])
		    cur1++;
	      else cur2++;
     }else
	 {
		  if(dst[cur1]<src[cur2])
		    cur1++;
	      else cur2++;

	 }
   }
   Copy(dst,len1,temp, len); //may be cost
   return true;
}

bool Insert(int *dstSet, int &dstLen, int item) //dstSet should have one more space
{
   for(int i=dstLen-1;i>=0;i--)
   {
     if(item<dstSet[i])
		 dstSet[i+1]=dstSet[i];
	 else if(item>dstSet[i])
     {
        dstSet[i+1]=item;
		dstLen++;
		return true;
     }else
     {
	   for(int j=i+1;j<dstLen;j++)
		   dstSet[j]=dstSet[j+1];
	   return false;
     }//the item is equal to some item, copy back
   }
   dstSet[0]=item;
   dstLen++;
   return true;
}


void Knode::init(Knode* parent, int Itemname, int Count)
{
	itemname = Itemname;
	par = parent;
	leftchild = NULL;
	rightsibling = NULL;
	count = Count;
	next = NULL;

	blmark = false;

	tailSet=NULL;
	tailSize=0;
	tailSupport=0;
    
	nodeCount++;
}

Knode::~Knode()
{
}

void Knode::addTail(int * & inTailSet, int inTailSize, int support)
{
  if(tailSize==0)
  {
    tailSize=inTailSize;  
    tailSet=inTailSet;  
	tailSupport=support;
	return;
  }else //inTailSize should >0
    {
	  Intersection(tailSet,tailSize, inTailSet, inTailSize, false);
	  if(tailSize>0)
	    tailSupport+=support;
	  else
		tailSupport=0;
	}
}

Knode* Knode::append(FK_tree* fptree, Knode* sib, int itemno, int Count)
{
	Knode* child;

	child = (Knode*)fp_buf->newbuf(1, KNODESIZE);
    //child ->init(this, itemno, Count, PosCount);
	child ->init(this, itemno, Count);
    
	nodeCount++; //for debug
	
	if(this->leftchild==NULL)this->leftchild=child;
	else
		sib->rightsibling = child;

	int itemOrd=fptree->order[itemno];
	Knode * linkHead=fptree->head[itemOrd];
	child->next = linkHead->next;
	linkHead->next = child;
    //linkHead->posCount+=PosCount;

	return child;
}

void Knode::detach(FK_tree* fptree, Knode* sib)
{
	Knode* par = this->par;
	Knode* curr, *child;
	Knode* previous=NULL;

	nodeCount--; //for debug

	//remove from tree
	if(par->leftchild == this) 
		par->leftchild = this->rightsibling;
	else
		sib->rightsibling = this->rightsibling;

	//remove from header
	removeNodeFromHeader(fptree, 0); //already deacreased in fptree->deletepath()
	
	//remove children from header as well
	child = this->leftchild;
	
	while(child)
	{
		child->removeNodeFromHeader(fptree, 1);

		child = child->leftchild;
	}
}

void Knode::removeNodeFromHeader(FK_tree* fptree, int decCount)
{
	Knode* curr, *previous = NULL;

	curr = fptree->head[this->itemname]->next;
	
	//if(curr->itemname!=this->itemname) //for debug
	//{
	//	printf("tree removal error!\n");
	//	scanf("exit");
	//	exit(1);
	//}
	
	//update header count
	fptree->head[this->itemname]->count -= decCount;

	while(curr)
	{
		if(curr == this)
		{
			if(previous)
				previous->next = curr->next;
			else
				fptree->head[this->itemname]->next = curr->next;

			break;
		}

		previous = curr;
		curr = curr->next;
	}
}