Add files via upload

1 files changed, 511 insertions, 0 deletions

diff --git a/sourcecodes/k-best/src/UpdateHR2.h b/sourcecodes/k-best/src/UpdateHR2.h
new file mode 100644
index 00000000..c7deefe8
--- /dev/null
+++ b/sourcecodes/k-best/src/UpdateHR2.h
@@ -0,0 +1,511 @@
+#include<stdio.h>
+#include<stdlib.h>
+
+#include<iostream>
+#include<vector>
+#include<deque>
+#include<string>
+#include<fstream>
+#include<math.h>
+
+#include"Arguments.h"
+#include"Model.h"
+
+using namespace std;
+
+
+struct ADTreenode{
+	int count;
+	
+	//i.e. start attr which = *;
+	int startVaryNodeInd;
+	
+	//struct ADVarynode * ADVaryNodePs[];
+	struct ADVarynode ** ADVaryNodePs;
+};
+
+typedef struct ADTreenode ADTreeNode;
+
+struct ADVarynode{
+	//Represent Vary Index
+	int index;
+	
+	int mcv;
+	
+	//struct ADTreenode * ADTreeNodePs[];
+	struct ADTreenode ** ADTreeNodePs;
+	
+};
+
+typedef struct ADVarynode ADVaryNode;
+
+
+typedef struct {
+	//the count for each arrangment of contiTableAttrs
+	//contiTableCounts.size() == the product of the arity of each element in contiTableAttrs
+	//do not explicitly record the whole contiTable
+	vector<int> contiTableCounts;
+	
+	//invariant: in the decreasing order
+	vector<int> contiTableAttrs;
+	
+	//condiAttrs.size() == condiVals.size()
+	//invariant: in the increasing order
+	vector<int> condiAttrs;
+	vector<int> condiVals;
+	
+	//invariant: contiTableAttrs.size() + condiAttrs.size() == the whole original inquiry length
+	//			finally: condiAttrs.size() == 0
+} CondiContiTable;
+
+
+
+
+
+ADTreeNode * MakeADTree(int, vector<int> &, vector< vector<int> > &, vector<int> &);
+ADVaryNode * MakeVaryNode(int, vector<int> &, vector< vector<int> > &, vector<int> &);
+void PrintADTreeNode(ADTreeNode *, int, const int, vector<int> &);
+void PrintADVaryNode(ADVaryNode *, int, const int, vector<int> &);
+void FreeADTreeNode(ADTreeNode *, const int, vector<int> &);
+void FreeADVaryNode(ADVaryNode *, const int, vector<int> &);
+
+
+CondiContiTable MakeContab(deque<int>, ADTreeNode *, 
+		vector<int> &, vector<int> &, const vector<int> &);
+		
+void MinusContab(CondiContiTable &, CondiContiTable *, int, int);
+
+void ConcatContab(CondiContiTable *, int, int, CondiContiTable &);
+
+		
+
+
+
+//HR:
+//	a_i is in {0, ..., M-1}
+//  dm: the data matrix: R * M
+//  dmIndex: initially stores {0, 1, ..., R - 1}, it is just the light-weight index for dm
+//  arities: stores the arity of each attr
+//  could use vector<int> & dmIndex instead of vector<int> dmIndex
+ADTreeNode * MakeADTree(int a_i, vector<int> & dmIndex, vector< vector<int> > & dm, vector<int> & arities){
+	//M = num of attr
+	int M = dm[0].size();
+	
+	ADTreeNode * ADTreeNodeP1 = (ADTreeNode *) malloc(sizeof(ADTreeNode));
+	ADTreeNodeP1->count = dmIndex.size();
+	ADTreeNodeP1->startVaryNodeInd = a_i;
+	//base
+	if(a_i >= M){
+		ADTreeNodeP1->ADVaryNodePs = NULL;
+	}
+	else{
+		ADTreeNodeP1->ADVaryNodePs = (ADVaryNode **) malloc(sizeof(ADVaryNode*) * 
+	                              (M - 1 - a_i + 1));
+	}
+	for(int a_j = a_i; a_j <= M-1; a_j++){
+		ADTreeNodeP1->ADVaryNodePs[a_j - a_i] = MakeVaryNode(a_j, dmIndex, dm, arities);
+	}
+	return ADTreeNodeP1;
+	                              
+}//end ADTreeNode * MakeADTree()
+
+
+
+//HR:
+//	a_i is in {0, ..., M-1}
+//  dm: the data matrix: R * M
+//  dmIndex: initially stores {0, 1, ..., R - 1}
+//  arities: stores the arity of each attr
+//  could use vector<int> & dmIndex instead of vector<int> dmIndex
+ADVaryNode * MakeVaryNode(int a_i, vector<int> & dmIndex, vector< vector<int> > & dm, vector<int> & arities){
+	ADVaryNode * ADVaryNodeP1 = (ADVaryNode *) malloc(sizeof(ADVaryNode));
+	ADVaryNodeP1->index = a_i;
+	int n_i = arities[a_i];//may be used as global var
+	ADVaryNodeP1->ADTreeNodePs = (ADTreeNode **) malloc(sizeof(ADTreeNode *) * n_i);
+	vector<int> dmIndexSub[n_i];
+	for(unsigned int j = 0; j <= dmIndex.size() - 1; j++){
+		int v = dm[dmIndex[j]][a_i];
+		dmIndexSub[v].push_back(dmIndex[j]);
+	}
+	ADVaryNodeP1->mcv = 0;
+	int maxCount = dmIndexSub[0].size();
+	for(int j = 1; j <= n_i - 1; j++){
+		if((int) dmIndexSub[j].size() > maxCount){
+			maxCount = dmIndexSub[j].size();
+			ADVaryNodeP1->mcv = j;
+		}
+	}
+	for(int j = 0; j <= n_i - 1; j++){
+		if(dmIndexSub[j].size() == 0 || j == ADVaryNodeP1->mcv){
+			ADVaryNodeP1->ADTreeNodePs[j] = NULL;
+		}
+		else{
+			ADVaryNodeP1->ADTreeNodePs[j] = MakeADTree(a_i+1, dmIndexSub[j], dm, arities);
+		}
+	}
+	//not necessary in fact
+	//dmIndex.clear();
+	//HR: Neither necessary nor correct
+	//delete dmIndex;
+	return ADVaryNodeP1;
+	
+	
+}//end ADVaryNode * MakeVaryNode()
+
+
+//HR:
+//  ADTreeNodeP1: pointers to the ADTreeNode
+//  level: starting from 0 
+//  M: the num of attr
+//  arities: stores the arity of each attr 
+//  initial call: PrintADTreeNode(ADTreeNodeP1, 0, M, arities) in Model.h
+//  pre-order to print the ADtree
+void PrintADTreeNode(ADTreeNode * ADTreeNodeP1, int level, const int M, vector<int> & arities){
+	string strSpace = "";
+	for(int i = 0; i < level; i++){
+		strSpace += "  ";
+	}
+	cout << strSpace << "ADTreeNode" << endl;
+	cout << strSpace << "Count = " << ADTreeNodeP1->count << endl;
+	cout << strSpace << "startVaryNodeInd = " << ADTreeNodeP1->startVaryNodeInd << endl;
+	if(ADTreeNodeP1->ADVaryNodePs == NULL){
+		return;
+	}
+	else{
+		for(int i = 0; i < M - 1 - ADTreeNodeP1->startVaryNodeInd + 1; i++){
+			PrintADVaryNode(ADTreeNodeP1->ADVaryNodePs[i], level+1, M, arities);
+		}
+	}
+} //end void PrintADTreeNode()
+
+
+//HR:
+//  ADVaryNodeP1: pointers to the ADVaryNode
+//  level: starting from 0 
+//  M: the num of attr
+//  arities: stores the arity of each attr 
+//  pre-order to print the ADtree
+void PrintADVaryNode(ADVaryNode * ADVaryNodeP1, int level, const int M, vector<int> & arities){
+	string strSpace = "";
+	for(int i = 0; i < level; i++){
+		strSpace += "  ";
+	}
+	cout << strSpace << "ADVaryNode" << endl;
+	cout << strSpace << "index = " << ADVaryNodeP1->index << endl;
+	cout << strSpace << "mcv = " << ADVaryNodeP1->mcv << endl;
+	int n_i = arities[ADVaryNodeP1->index]; //may be changed to global var
+	for(int j = 0; j <= n_i - 1; j++){
+		if(j == ADVaryNodeP1->mcv){
+			cout << strSpace << "  mcv" << endl;		
+		}
+		else if(ADVaryNodeP1->ADTreeNodePs[j] == NULL){
+			cout << strSpace << "  NULL" << endl;
+		}
+		else{
+			PrintADTreeNode(ADVaryNodeP1->ADTreeNodePs[j], level+1, M, arities);
+		}
+	}
+
+}//end void PrintADVaryNode()
+
+
+
+//HR:
+//  ADTreeNodeP1: pointers to the ADTreeNode
+//  M: the num of attr
+//  arities: stores the arity of each attr 
+//  initial call: FreeADTreeNode(ADTreeNodeP1, M, arities) in Model.h
+//  pre-order to free the ADtree
+void FreeADTreeNode(ADTreeNode * ADTreeNodeP1, const int M, vector<int> & arities){
+
+	if(ADTreeNodeP1->ADVaryNodePs != NULL){
+		for(int i = 0; i < M - 1 - ADTreeNodeP1->startVaryNodeInd + 1; i++){
+			FreeADVaryNode(ADTreeNodeP1->ADVaryNodePs[i], M, arities);
+		}
+		free(ADTreeNodeP1->ADVaryNodePs);
+	}
+
+	free(ADTreeNodeP1);
+}  //end void FreeADTreeNode()
+
+
+//HR:
+//  ADVaryNodeP1: pointers to the ADVaryNode
+//  M: the num of attr
+//  arities: stores the arity of each attr 
+//  pre-order to free the ADtree
+void FreeADVaryNode(ADVaryNode * ADVaryNodeP1, const int M, vector<int> & arities){
+
+	int n_i = arities[ADVaryNodeP1->index]; //may be changed to global var
+	for(int j = 0; j <= n_i - 1; j++){
+		if(j == ADVaryNodeP1->mcv){
+			;		
+		}
+		else if(ADVaryNodeP1->ADTreeNodePs[j] == NULL){
+			;
+		}
+		else{
+			FreeADTreeNode(ADVaryNodeP1->ADTreeNodePs[j], M, arities);
+		}
+	}
+	free(ADVaryNodeP1->ADTreeNodePs);
+	free(ADVaryNodeP1);
+
+}//end void FreeADVaryNode()
+
+
+
+//Error: if use ofstream of1 instead of ofstream & of1
+//In file included from Model.h:19,
+//                 from main.cc:6:
+//UpdateHR2.h: In copy constructor `std::basic_ios<char, std::char_traits<char> >::basic_ios(const std::basic_ios<char, std::char_traits<char> >&)':
+///usr/lib/gcc/i386-redhat-linux/3.4.6/../../../../include/c++/3.4.6/bits/ios_base.h:781: error: `std::ios_base::ios_base(const std::ios_base&)' is private
+//UpdateHR2.h:220: error: within this context
+//UpdateHR2.h: In copy constructor `std::basic_filebuf<char, std::char_traits<char> >::basic_filebuf(const std::basic_filebuf<char, std::char_traits<char> >&)':
+///usr/lib/gcc/i386-redhat-linux/3.4.6/../../../../include/c++/3.4.6/streambuf:769: error: `std::basic_streambuf<_CharT, _Traits>::basic_streambuf(const std::basic_streambuf<_CharT, _Traits>&) [with _CharT = char, _Traits = std::char_traits<char>]' is private
+//UpdateHR2.h:220: error: within this context
+//UpdateHR2.h: In function `void print_CondiContiTable(CondiContiTable&, std::ofstream)':
+//UpdateHR2.h:220: error:   initializing argument 2 of `void print_vec(std::vector<int, std::allocator<int> >, std::ofstream)'
+
+
+void print_vec(vector<int> & vec1, ofstream & of1){
+	for(int i = 0; i < (int) vec1.size(); i++){
+		of1 << vec1[i] << " ";
+	}
+	of1 << endl;
+}
+
+void print_deque(deque<int> & v1, ofstream & of1){
+	for(int i = 0; i < (int) v1.size(); i++){
+		of1 << v1[i] << " ";
+	}
+	of1 << endl;
+}
+
+void print_CondiContiTable(CondiContiTable & ccTable1, ofstream & of1){
+	of1 << "ccTable1.contiTableCounts: " << endl;
+	print_vec(ccTable1.contiTableCounts, of1);
+	
+	of1 << "ccTable1.contiTableAttrs: " << endl;
+	print_vec(ccTable1.contiTableAttrs, of1);
+	
+	of1 << "ccTable1.condiAttrs: " << endl;
+	print_vec(ccTable1.condiAttrs, of1);
+	
+	of1 << "ccTable1.condiVals: " << endl;
+	print_vec(ccTable1.condiVals, of1);
+	
+}
+
+
+
+void print_vec(vector<int> & vec1){
+	for(int i = 0; i < (int) vec1.size(); i++){
+		cout << vec1[i] << " ";
+	}
+	cout << endl;
+}
+
+
+void print_deque(deque<int> & v1){
+	for(int i = 0; i < (int) v1.size(); i++){
+		cout << v1[i] << " ";
+	}
+	cout << endl;
+}
+
+void print_CondiContiTable(CondiContiTable & ccTable1){
+	cout << "ccTable1.contiTableCounts: " << endl;
+	print_vec(ccTable1.contiTableCounts);
+	
+	cout << "ccTable1.contiTableAttrs: " << endl;
+	print_vec(ccTable1.contiTableAttrs);
+	
+	cout << "ccTable1.condiAttrs: " << endl;
+	print_vec(ccTable1.condiAttrs);
+	
+	cout << "ccTable1.condiVals: " << endl;
+	print_vec(ccTable1.condiVals);
+	
+}
+
+
+
+//HR: 
+//	inquiryAttrs: {a_i_1, ..., a_i_n}
+//	ADNP: The current pointer to ADTreeNode
+//	givenAttrs, givenVals explicilty record the meaning of ADNP
+//	{b_i_1, ..., b_i_m} = {value_b_i_1, .. value_b_i_m}
+//	pre:
+//	inquiryAttrs is in the increasing order
+//	givenAttrs is in the increasing order
+CondiContiTable MakeContab(deque<int> inquiryAttrs, ADTreeNode * ADNP, 
+		vector<int> & givenAttrs, vector<int> & givenVals, const vector<int> & arities){
+			
+//	cout << "\nMakeContab()" << endl;
+//	cout << "inquiryAttrs" << endl;
+//	print_deque(inquiryAttrs);
+//	cout << "givenAttrs" << endl;
+//	print_vec(givenAttrs);
+//	cout << "givenVals" << endl;
+//	print_vec(givenVals);
+	
+	
+	
+	
+	//base 1
+	if(ADNP == NULL){
+		CondiContiTable bottomTable;
+		
+		//base 1.1
+		//if(inquiryAttrs.size() == 0){
+		if(inquiryAttrs.empty()){
+			bottomTable.contiTableCounts.push_back(0);
+			//bottomTable.contiTableAttrs is empty
+			bottomTable.condiAttrs = givenAttrs;
+			bottomTable.condiVals = givenVals;
+			
+			//cout << "//base 1.1: if(ADNP == NULL) and if(inquiryAttrs.empty())" << endl;
+			//print_CondiContiTable(bottomTable);
+			
+		}
+		//base 1.2
+		//if(inquiryAttrs.size() > 0)
+		else{
+			int rowNum = 1;
+			for(unsigned int i = 0; i < inquiryAttrs.size(); i++){
+				//Note: I explicitly write inquiryAttrs[inquiryAttrs.size() - 1 - i ] instead of 
+				//	inquiryAttrs[i] because this is really the ordering to create the whole contiTable
+				int lastAttr = inquiryAttrs[inquiryAttrs.size() - 1 - i ];
+				rowNum *= arities[lastAttr];
+				
+				bottomTable.contiTableAttrs.push_back(lastAttr);
+			}		
+			bottomTable.condiAttrs = givenAttrs;
+			bottomTable.condiVals = givenVals;
+			
+			for(int i = 0; i < rowNum; i++){
+				bottomTable.contiTableCounts.push_back(0);
+			}
+			
+			//cout << "//base 1.2: if(ADNP == NULL) and if(!inquiryAttrs.empty())" << endl;
+			//print_CondiContiTable(bottomTable);
+		}
+		
+		
+		
+		return bottomTable;
+		
+	}// end if(ADNP == NULL)
+	
+	//base 2
+	else if (inquiryAttrs.empty()){
+		CondiContiTable bottomTable;
+		bottomTable.contiTableCounts.push_back(ADNP->count);
+		//bottomTable.contiTableAttrs is empty
+		bottomTable.condiAttrs = givenAttrs;
+		bottomTable.condiVals = givenVals;
+		
+		//cout << "//base 2: if(ADNP != NULL) and if(inquiryAttrs.empty())" << endl;
+		//print_CondiContiTable(bottomTable);
+			
+		return bottomTable;
+	}
+	else{
+		int a_i_1 = inquiryAttrs.front();
+		int VNIndex = a_i_1 - ADNP->startVaryNodeInd;
+		ADVaryNode * VNP = ADNP->ADVaryNodePs[VNIndex];
+		int mcv = VNP->mcv;
+		int n_i_1 = arities[a_i_1];
+		CondiContiTable CTs[n_i_1];
+		
+		//delete the 1st element a_i_1 of inquiryAtts, will never use the 1st element a_i_1 again
+		//but does not allow the sub_program to delete more elements, so use deque<int> inquiryAttrs instead of deque<int> & inquiryAttrs
+		//vector<int> & givenAttrs, vector<int> & givenVals can be used because the sub_program will change but then restore it
+		inquiryAttrs.pop_front();
+		
+		for(int k = 0; k < n_i_1; k++){
+			if(k != mcv){
+				ADTreeNode * ADNP_k = VNP -> ADTreeNodePs[k];
+
+				vector<int> newGivenAttrs = givenAttrs;
+				newGivenAttrs.push_back(a_i_1);
+				vector<int> newGivenVals = givenVals;
+				newGivenVals.push_back(k);
+				CTs[k] = MakeContab(inquiryAttrs, ADNP_k, newGivenAttrs, newGivenVals, arities);
+				
+			}
+		}
+		CondiContiTable sumCTs = MakeContab(inquiryAttrs, ADNP, givenAttrs, givenVals, arities);
+		MinusContab(sumCTs, CTs, n_i_1, mcv);
+		
+		CondiContiTable result;
+		ConcatContab(CTs, n_i_1, a_i_1, result);
+		
+		//cout << "//non-base: " << endl;
+		//print_CondiContiTable(result);
+		
+		return result;
+	}
+	
+}// end CondiContiTable MakeContab()
+
+
+void MinusContab(CondiContiTable & sumCTs, CondiContiTable * CTs, int n_i_1, int mcv){
+	CTs[mcv].contiTableCounts = sumCTs.contiTableCounts;
+	CTs[mcv].contiTableAttrs = sumCTs.contiTableAttrs;
+	for(unsigned int i = 0; i < CTs[mcv].contiTableCounts.size(); i++){
+		for(int k = 0; k < n_i_1; k++){
+			if(k != mcv){
+				CTs[mcv].contiTableCounts[i] -= CTs[k].contiTableCounts[i];
+			}
+		}
+	}
+	//assume arities of each attr >=2
+	if(mcv != 0){
+		CTs[mcv].condiAttrs = CTs[0].condiAttrs;
+		CTs[mcv].condiVals = CTs[0].condiVals;
+	}
+	else{
+		CTs[mcv].condiAttrs = CTs[1].condiAttrs;
+		CTs[mcv].condiVals = CTs[1].condiVals;
+	}
+	CTs[mcv].condiVals.pop_back();
+	CTs[mcv].condiVals.push_back(mcv);
+	
+} //end void MinusContab()
+
+
+void ConcatContab(CondiContiTable * CTs, int n_i_1, int a_i_1, CondiContiTable & concatedTable){
+	for(int i = 0; i < n_i_1; i++){
+		//for each i, CTs[i].contiTableCounts.size() is the same
+		for(unsigned int j = 0; j < CTs[i].contiTableCounts.size(); j++){
+			concatedTable.contiTableCounts.push_back(CTs[i].contiTableCounts[j]);
+		}
+	}
+	
+	//check: a_i_1 == CTs[0].condiAttrs.back();
+	if(a_i_1 != CTs[0].condiAttrs.back()){
+		cout << "Error: a_i_1 != CTs[0].condiAttrs.back()" << endl;
+		cout << "a_i_1 = " << a_i_1 << endl;
+		cout << "CTs[0].condiAttrs.back() = " << CTs[0].condiAttrs.back() << endl;
+	}
+	
+	//move a_i_1 from the end of CTs[0].condiAttrs to the end of concatedTable.contiTableAttrs
+	concatedTable.contiTableAttrs = CTs[0].contiTableAttrs;
+	concatedTable.contiTableAttrs.push_back(a_i_1);
+	
+	concatedTable.condiAttrs = CTs[0].condiAttrs;
+	concatedTable.condiAttrs.pop_back();
+	
+	concatedTable.condiVals = CTs[0].condiVals;
+	concatedTable.condiVals.pop_back();
+	
+} //end void ContatContab()
+
+
+		
+
+
+
+