//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 4
#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)
{
//广度优先遍历
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)
{
//深度优先遍历
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); //设置根节点数据为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");
//初始化二叉树
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");
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;
}
//设置位值
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);
}
//打印序列号
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) //没有标签应答
{
printf("$No tag response\n\n");
return;
}
else if(detect_result==1)//只有一个标签应答
{
printf("$Only one tag response, the tag ID is ");
Print_Bit_Data(&tag);
printf("\n\n");
return;
}
else //多个标签
{
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_