//Dev-C++ generate, C++ relative
#include <cstdlib>
#include <iostream>
using namespace std;

//Include necessary C libs
#include<stdio.h>
#include <stdarg.h>
#include<math.h>

//Declare function
int Detect_Tags(struct bit_data *transmit_data, struct bit_data *tag_result);
void Set_Bit_Data(struct bit_data *value, int count, ...);
void Merge_Bit_Data(struct bit_data *dest_value, struct bit_data *value1, struct bit_data value2);
void Print_Bit_Data(struct bit_data *transmit_data);
void QTA_Detect_Tags(struct bit_data *transmit_data);
void Set_Node(struct node *tree_node, struct bit_data node_data);
void Print_Node(struct node *tree_node);
void Initial_Binary_Tree(struct node *node_ptr, int level, struct bit_data node_value);
void DFS_Detect_Tags(struct node *node_ptr, struct bit_data transmit_data);

//Define constant
#define TAG_COUNT   5
#define TAG_BIT     4

//Declare struct
struct bit_data
{
    int bit_count;
    int bit_content[TAG_BIT];
};

struct node
{
    struct bit_data value;
    struct node *left_child;
    struct node *right_child;     
};

//Global variables
int tags[TAG_COUNT][TAG_BIT]={ {0, 0, 0, 1}, {0, 1, 0, 0}, {0, 1, 0, 1}, {1, 0, 0, 0}, {1, 0, 1, 0} };
int search_counter=0;

//Program Start
int main(int argc, char *argv[])
{
    int i, j;
    int method;
    
    printf("=====RFID=====\n\n");
    printf("There are 2 searching method:\n");
    printf("1. QTA\n");
    printf("2. DFS\n\n");
    printf("Please choose searching method: ");
    scanf("%d", &method);
    printf("\n\n");
    
    if(method==1)
    {
        //For QTA
        struct bit_data transmit_data;
        transmit_data.bit_count=0;
        
        //Hint
        printf("=====QTA detect tags=====\n\n");
        printf("#Test Case Information:\n");
        printf("Tag Count: %d\n", TAG_COUNT);
        printf("Tag Bits:  %d Bits\n", TAG_BIT);
        printf("Tag List:\n");
        for(i=0; i<TAG_COUNT; i++)
        {
            for(j=0; j<TAG_BIT; j++)
            {
                printf("%d", tags[i][j]);
            }
            printf("\n");
        }
        printf("\n\n");
        
        //Use QTA to detect tags
        printf("#QTA detect tags...\n\n");
        QTA_Detect_Tags(&transmit_data);
        printf("#QTA finish!!!\n\n");
    }
    else if(method==2)
    {
        //For DFS
        struct node *root_ptr;
        struct bit_data root_value;
         
        Set_Bit_Data(&root_value, 5, 1, 2, 3, 4, 9);         //root data, data count = 0
        printf("\n~~~\n");
        Print_Bit_Data(&root_value);
        printf("%d", root_value.bit_count);
        printf("\n~~~\n");
        Set_Bit_Data(&root_value, 0);         //root data, data count = 0
        printf("\n~~~\n");
        Print_Bit_Data(&root_value);
        printf("%d", root_value.bit_count);
        printf("\n~~~\n");
        
        //Hint
        printf("=====DFS Detect tags=====\n\n");
        
        //Initial Binary Tree
        printf("#Initial binary tree...\n\n");
        printf("%d", root_ptr->value.bit_count);
        Initial_Binary_Tree(root_ptr, 0, root_value);
        printf("#Initial success\n\n");
        
        //Use DFS to detect tags
        printf("#DFS detect tags...\n\n");
    	printf("%d", root_ptr->value.bit_count);
    	printf("%d", root_value.bit_count);
        DFS_Detect_Tags(root_ptr, root_value);
        printf("#DFS finish!!!\n\n");
        
    }
    
    system("PAUSE");
    return 0;
}

//Detect Tags
int Detect_Tags(struct bit_data *transmit_data, struct bit_data *tag_result)
{
    int i, j;
    int fit_flag;
    int fit_count=0;
    int fit_tag_index;
    
    for(i=0; i<TAG_COUNT; i++)
    {
        fit_flag=1;
        for(j=0; j<transmit_data->bit_count; j++)
        {
            if(transmit_data->bit_content[j] != tags[i][j])
            {
                fit_flag=0;
                break;
            }
        }
        
        if(fit_flag==1)
        {
            fit_tag_index=i;
            fit_count++;
        }
    }
    
    if(fit_count == 1)
    {
        tag_result->bit_count=TAG_BIT;
        for(i=0; i<TAG_BIT; i++)
        {
            tag_result->bit_content[i]=tags[fit_tag_index][i];
        }
    }
    
    return fit_count;
}

//Set Bit Data
void Set_Bit_Data(struct bit_data *value, int count, ...)
{
    int i;
    
    va_list ap;
    
    value->bit_count=count;
    
    //test
    //printf("!!!IN SetBitData, count=%d\n",value->bit_count);
    
    va_start(ap, count);
    for(i=0; i<count; i++)
    {
        value->bit_content[i]=va_arg(ap, int);
        //test
    	//printf("!!!IN SetBitData, i=%d, content=%d\n", i, value->bit_content[i]);
    }
    va_end(ap);
}

//Merge Bit Data
void Merge_Bit_Data(struct bit_data *dest_value, struct bit_data value1, struct bit_data value2)
{
    int i;
    
    printf("\n***00\n");
    printf("%d", dest_value->bit_count);
    printf("%d", value1.bit_count);
    printf("%d", value2.bit_count);
    Print_Bit_Data(dest_value);
    Print_Bit_Data(&value1);
    Print_Bit_Data(&value2);
    
    
    dest_value->bit_count=value1.bit_count+value2.bit_count;
    
    for(i=0; i<value1.bit_count; i++)
    {
    	dest_value->bit_content[i]=value1.bit_content[i];
    }
    
    for(i=0; i<value2.bit_count; i++)
    {
    	dest_value->bit_content[i+value1.bit_count]=value2.bit_content[i];
    }
    
    printf("\n***01\n");
    printf("%d", dest_value->bit_count);
    printf("%d", value1.bit_count);
    printf("%d", value2.bit_count);
    Print_Bit_Data(&value1);
    Print_Bit_Data(&value2);
    Print_Bit_Data(dest_value);
}

//Print bit_data
void Print_Bit_Data(struct bit_data *transmit_data)
{
    int i;
    for(i=0; i<transmit_data->bit_count; i++)
    {
        printf("%d", transmit_data->bit_content[i]);
    }
}
//QTA(Query Tree Algorithm) detect tags
void QTA_Detect_Tags(struct bit_data *transmit_data)
{
    int level;
    level=transmit_data->bit_count;
    
    printf("#Reader action counter, No. %d\n%s", search_counter++, (level==0)?"\n":"");
    
    if(level > 0)//Not root, reader transmit data
    {
        int i;
        int detect_result;
        struct bit_data tag;
        
        printf("@Reader send ");
        Print_Bit_Data(transmit_data);
        printf("\n");
        
        detect_result=Detect_Tags(transmit_data, &tag);
        
        if(detect_result==0)                //No tag response
        {
            printf("$No tag response\n\n");
            return;
        }
        else if(detect_result==1)           //Only one tag response
        {
            printf("$Only one tag response, the tag ID is ");
            Print_Bit_Data(&tag);
            printf("\n\n");
            return;
        }
        else                                //More than one tag response
        {
            printf("$More than one tag response\n\n");
        }   
    }
    
    //Because more than one tag response, so continue transmit next bit
    
    //Search 0 sub tree
    transmit_data->bit_count=level+1;
    transmit_data->bit_content[level]=0;
    QTA_Detect_Tags(transmit_data);
        
    //Search 1 sub tree
    transmit_data->bit_count=level+1;
    transmit_data->bit_content[level]=1;
    QTA_Detect_Tags(transmit_data);
}

//Set Node
void Set_Node(struct node *tree_node, struct bit_data node_data)
{
    int i;
    
    tree_node->value.bit_count=node_data.bit_count;
    tree_node->left_child=NULL;
    tree_node->right_child=NULL;
    
    for(i=0; i<node_data.bit_count; i++)
    {
        tree_node->value.bit_content[i]=node_data.bit_content[i];
    }
}

//Print Node
void Print_Node(struct node *tree_node)
{
    Print_Bit_Data(&(tree_node->value));
}

//Initial Binary Tree, create by DFS method, for function of DFS_Detect_Tags() useing
void Initial_Binary_Tree(struct node *node_ptr, int level, struct bit_data node_value)
{
    node_ptr=(struct node *)malloc(sizeof(struct node));
    
    //test
    printf("\nIn initial\n");
    if(node_ptr==NULL)
        printf("malloc fail ");
    else
        printf("malloc success ");
     
    Set_Node(node_ptr, node_value);
    
    
    printf("node_ptr->value.bit_count=%d\n\n", node_ptr->value.bit_count);
    //Print_Bit_Data(&node_value);
    //Print_Node(node_ptr);

    if(level<=TAG_BIT)
    {
        //Set left subtree
        Set_Bit_Data(&node_value, 1, 0);         //left node value is 0
        Initial_Binary_Tree(node_ptr->left_child, level+1, node_value);
        
        //Set right subtree
        Set_Bit_Data(&node_value, 1, 1);         //right node value is 1
        Initial_Binary_Tree(node_ptr->right_child, level+1, node_value);
    }
}

//DFS(Depth First Seraching) detect tags
void DFS_Detect_Tags(struct node *node_ptr, struct bit_data transmit_data)
{
    printf("\nDFS 001\n");
    printf("node_ptr->value.bit_count=%d\n", node_ptr->value.bit_count);
    printf("transmit_data.bit_count=%d\n", transmit_data.bit_count);
	
    printf("#Reader action counter, No. %d\n", search_counter++);
    printf("@Reader walk tree, now in ");
    if(transmit_data.bit_count==0)	//root
    {
    	printf("root! ");
    }
    else if(transmit_data.bit_count>0)	//not root
    {
    	//Print_Bit_Data(&transmit_data);
    	printf(", ");
    	Merge_Bit_Data(&transmit_data, transmit_data, node_ptr->value);
    }
	
    printf("\n@@@\n");
    printf("count=%d\n", transmit_data.bit_count);
    
    if(transmit_data.bit_count<TAG_BIT)		//Not leaf, continue walk tree
    {
        printf("not leaf, continue wlak tree...\n\n");
        DFS_Detect_Tags(node_ptr->left_child, transmit_data);
        DFS_Detect_Tags(node_ptr->right_child, transmit_data);
    }
    else if(transmit_data.bit_count==TAG_BIT)	//Is leaf, detect tags
    {
        int detect_result;
        struct bit_data tag;
        
        printf("is leaf, detect tags...\n");
        
        detect_result=Detect_Tags(&transmit_data, &tag);
        
        if(detect_result==1)			//Find tag
        {
        	printf("@Tag response, So ");
        	Print_Bit_Data(&transmit_data);
        	printf(" is one of tags\n\n");
        }
        else
        {
        	printf("@No Tag response!!!\n\n");
        }
    }
    
}