The problem was more challenging than I thought :-).
Basically, I read testcases and output the resulting XML.
For every testcase I first determine the possible relationships between tables (assuming that primary keys can consist of one or more columns), I collect the root nodes (the nodes to be added under <DB>) which are the records from tables that do not have a reference to other tables (the problem states that there is exactly one such table but if there are more then I just add them under <DB> as well) AND the records from tables that point to another table but where the foreign key is empty or not existing.
Before adding a node, I collect the underlying nodes using recursion so that for new underlying nodes their underlying nodes will be collected as well.
Nodes will be sorted, both on name and on attributes.
That should be it. Am I missing something? (For example, what about spaces in the input?)
Here are some testcases:
and my output:S(#C,A,D)
R(#A,B)
T(E,A)
data
T(e1,a2)
S(c3,a1,d1)
S(c1,a2,d2)
S(c2,a1,d3)
R(a1,b1)
R(a2,b2)
QQ(#Q,Q,W)
data
QQ(q5,,w5)
QQ(q1,q0,w1)
QQ(q2,q1,w2)
QQ(q3,q1,w3)
QQ(q4,q2,w4)
XXX(#X,X1,X2,X3,X4,Y1,Y2)
YYY(#Y1,#Y2,Y3)
ZZZ(#Z,Y2,Z1,Z2)
data
YYY(y1,y1,yvalue1)
YYY(y2,y2,yvalue2)
XXX(x1,1,2,3,4,y1,y1)
XXX(x2,1,2,3,4,y2,y2)
XXX(x3,1,2,3,4,y2,y2)
XXX(x4,1,2,3,4,,)
ZZZ(z1,y2,v1,v2)
ZZZ(z2,y2,v1,v2)
ZZZ(z3,y2,v1,v2)
I did try to find some more test input but could not find any at the site of the Porto University (where the problem originates) but it could be that my Portuguese is very bad :-).<DB>
<R #A="a1" B="b1">
<S #C="c2" D="d3">
</S>
<S #C="c3" D="d1">
</S>
</R>
<R #A="a2" B="b2">
<S #C="c1" D="d2">
</S>
<T E="e1">
</T>
</R>
</DB>
<DB>
<QQ #Q="q1" Q="q0" W="w1">
<QQ #Q="q2" W="w2">
<QQ #Q="q4" W="w4">
</QQ>
</QQ>
<QQ #Q="q3" W="w3">
</QQ>
</QQ>
<QQ #Q="q5" Q="" W="w5">
</QQ>
</DB>
<DB>
<XXX #X="x4" X1="1" X2="2" X3="3" X4="4" Y1="" Y2="">
</XXX>
<YYY #Y1="y1" #Y2="y1" Y3="yvalue1">
<XXX #X="x1" X1="1" X2="2" X3="3" X4="4">
</XXX>
</YYY>
<YYY #Y1="y2" #Y2="y2" Y3="yvalue2">
<XXX #X="x2" X1="1" X2="2" X3="3" X4="4">
</XXX>
<XXX #X="x3" X1="1" X2="2" X3="3" X4="4">
</XXX>
</YYY>
<ZZZ #Z="z1" Y2="y2" Z1="v1" Z2="v2">
</ZZZ>
<ZZZ #Z="z2" Y2="y2" Z1="v1" Z2="v2">
</ZZZ>
<ZZZ #Z="z3" Y2="y2" Z1="v1" Z2="v2">
</ZZZ>
</DB>
To be complete, I'll enclose a copy of my program:
Code: Select all
#include <iostream>
#include <algorithm>
#include <functional>
#include <iterator>
#include <vector>
#include <string>
#include <map>
struct TableData {
std::string sName;
std::vector<std::string> vColumns;
std::vector< std::vector<std::string> > vData;
};
struct TableRelation {
std::string sReferencedTable;
std::map<size_t, size_t> mapColumns;
};
struct XMLElement {
std::string sName;
std::map<std::string, std::string> mapAttributes;
std::vector<XMLElement> vChildElements;
friend std::ostream& operator<<(std::ostream& strm, const XMLElement& element) {
strm << '<' << element.sName;
for ( std::map<std::string, std::string>::const_iterator p = element.mapAttributes.begin(); p != element.mapAttributes.end(); ++p )
strm << ' ' << p->first << "=\"" << p->second << '"';
strm << '>' << std::endl;
std::copy(element.vChildElements.begin(), element.vChildElements.end(), std::ostream_iterator<XMLElement>(strm));
strm << "</" << element.sName << '>' << std::endl;
return strm;
}
};
struct IsTable : std::binary_function<std::string, TableData, bool> {
bool operator()(const std::string& s, const TableData& table) const {
return table.sName == s;
}
};
struct IsKeyColumn : std::unary_function<std::string, bool> {
bool operator()(const std::string& s) const {
return s.length() && s[0] == '#';
}
};
struct Key2Column : std::unary_function<std::string, std::string> {
std::string operator()(const std::string& s) const {
return s.substr(1);
}
};
struct IsSourceColumn : std::binary_function<std::string, std::string, bool> {
bool operator()(const std::string& s1, const std::string& s2) const {
return s1 == s2.substr(1);
}
};
struct IsRelated : std::binary_function<std::vector<std::string>, std::vector<std::string>, bool> {
const std::map<size_t, size_t>& mapColumns;
IsRelated(const std::map<size_t, size_t>& _mapColumns)
: mapColumns(_mapColumns)
{}
bool operator()(const std::vector<std::string> data, const std::vector<std::string>& sourceData) const {
bool related = true;
for ( std::map<size_t, size_t>::const_iterator p = mapColumns.begin(); related && p != mapColumns.end(); ++p )
related = data[p->first] == sourceData[p->second];
return related;
}
};
struct Cmp_XMLElement : std::binary_function<XMLElement, XMLElement, bool> {
bool operator()(const XMLElement& e1, const XMLElement& e2) const {
bool cmp = false;
if ( e1.sName < e2.sName )
cmp = true;
else if ( e1.sName == e2.sName ) {
for ( std::map<std::string, std::string>::const_iterator p = e1.mapAttributes.begin(); p != e1.mapAttributes.end(); ++p ) {
std::map<std::string, std::string>::const_iterator q = e2.mapAttributes.find(p->first);
if ( p->second != q->second ) {
if ( p->second < q->second )
cmp = true;
break;
}
}
}
return cmp;
}
};
struct Problem {
std::vector<TableData> vTables;
friend std::istream& operator>>(std::istream& strm, Problem& problem) {
bool bReadHeaders = true;
std::string sLine;
problem.vTables.clear();
for ( bool bRead = true; bRead; ) {
if ( strm.peek() != -1 ) { // no std::char_traits<char>::eof()
if ( std::getline(strm, sLine) && sLine != "" ) {
if ( bReadHeaders && sLine == "data" )
bReadHeaders = false;
else {
TableData data;
std::string::size_type pos = sLine.find('(');
std::string::size_type pos_orig = 0;
data.sName = sLine.substr(0, pos);
sLine = sLine.substr(pos + 1);
sLine.resize(sLine.length() - 1);
while ( (pos = sLine.find(',', pos_orig)) != std::string::npos ) {
data.vColumns.push_back(sLine.substr(pos_orig, pos - pos_orig));
pos_orig = pos + 1;
}
data.vColumns.push_back(sLine.substr(pos_orig));
if ( bReadHeaders )
problem.vTables.push_back(data);
else {
std::vector<TableData>::iterator p = std::find_if(problem.vTables.begin(), problem.vTables.end(), std::bind1st(IsTable(), data.sName));
p->vData.push_back(data.vColumns);
}
}
}
else
bRead = false;
}
else {
if ( !problem.vTables.size() )
std::getline(strm, sLine);
bRead = false;
}
}
return strm;
}
};
struct Solution {
bool first;
XMLElement xml;
friend std::ostream& operator<<(std::ostream& strm, const Solution& solution) {
if ( !solution.first )
strm << std::endl;
return strm << solution.xml;
}
};
class ProblemSolver {
bool first;
public:
ProblemSolver(void)
: first(true)
{}
Solution operator()(const Problem& problem) {
Solution solution;
solution.first = first;
first = false;
solution.xml.sName = "DB";
std::map<std::string, TableRelation> mapRelations = _FindRelations(problem);
_AddRootElements(problem.vTables.begin(), problem.vTables.end(), mapRelations, solution.xml);
return solution;
}
private:
void _AddRootElements(const std::vector<TableData>::const_iterator begin, const std::vector<TableData>::const_iterator end, const std::map<std::string, TableRelation>& mapRelations, XMLElement& xmlroot) {
for ( std::vector<TableData>::const_iterator p = begin; p != end; ++p ) {
std::map<std::string, TableRelation>::const_iterator pRelation = mapRelations.find(p->sName);
if ( pRelation != mapRelations.end() ) {
std::vector<TableData>::const_iterator q = std::find_if(begin, end, std::bind1st(IsTable(), pRelation->second.sReferencedTable));
for ( std::vector< std::vector<std::string> >::const_iterator d = p->vData.begin(); d != p->vData.end(); ++d ) {
if ( std::find_if(q->vData.begin(), q->vData.end(), std::bind1st(IsRelated(pRelation->second.mapColumns), *d)) == q->vData.end() )
xmlroot.vChildElements.push_back(_NewElement(begin, end, mapRelations, *p, d, false));
}
}
else {
for ( std::vector< std::vector<std::string> >::const_iterator d = p->vData.begin(); d != p->vData.end(); ++d )
xmlroot.vChildElements.push_back(_NewElement(begin, end, mapRelations, *p, d, false));
}
}
std::sort(xmlroot.vChildElements.begin(), xmlroot.vChildElements.end(), Cmp_XMLElement());
}
XMLElement _NewElement(const std::vector<TableData>::const_iterator begin, const std::vector<TableData>::const_iterator end, const std::map<std::string, TableRelation>& mapRelations, const TableData& table, const std::vector< std::vector<std::string> >::const_iterator d, bool nested) {
XMLElement node;
node.sName = table.sName;
if ( nested ) {
std::map<std::string, TableRelation>::const_iterator p = mapRelations.find(table.sName);
for ( size_t i = 0; i < table.vColumns.size(); ++i )
if ( p->second.mapColumns.find(i) == p->second.mapColumns.end() )
node.mapAttributes.insert(std::make_pair(table.vColumns[i], (*d)[i]));
}
else
for ( size_t i = 0; i < table.vColumns.size(); ++i )
node.mapAttributes.insert(std::make_pair(table.vColumns[i], (*d)[i]));
for ( std::map<std::string, TableRelation>::const_iterator p = mapRelations.begin(); p != mapRelations.end(); ++p ) {
if ( p->second.sReferencedTable == table.sName ) {
std::vector<TableData>::const_iterator q = std::find_if(begin, end, std::bind1st(IsTable(), p->first));
IsRelated isRelated(p->second.mapColumns);
for ( std::vector< std::vector<std::string> >::const_iterator d2 = q->vData.begin(); d2 != q->vData.end(); ++d2 ) {
if ( isRelated(*d2, *d) )
node.vChildElements.push_back(_NewElement(begin, end, mapRelations, *q, d2, true));
}
}
}
std::sort(node.vChildElements.begin(), node.vChildElements.end(), Cmp_XMLElement());
return node;
}
std::map<std::string, TableRelation> _FindRelations(const Problem& problem) {
std::map<std::string, TableRelation> mapRelations;
for ( std::vector<TableData>::const_iterator p = problem.vTables.begin(); p != problem.vTables.end(); ++p ) {
std::vector<std::string> vKeys;
std::remove_copy_if(p->vColumns.begin(), p->vColumns.end(), std::back_inserter(vKeys), std::not1(IsKeyColumn()));
if ( vKeys.size() ) {
std::transform(vKeys.begin(), vKeys.end(), vKeys.begin(), Key2Column());
for ( std::vector<TableData>::const_iterator q = problem.vTables.begin(); q != problem.vTables.end(); ++q ) {
std::vector<std::string> vColumns;
std::remove_copy_if(q->vColumns.begin(), q->vColumns.end(), std::back_inserter(vColumns), IsKeyColumn());
if ( vColumns.size() ) {
std::vector<std::string> vForeignKeys;
std::sort(vKeys.begin(), vKeys.end());
std::sort(vColumns.begin(), vColumns.end());
std::set_intersection(vKeys.begin(), vKeys.end(), vColumns.begin(), vColumns.end(), std::back_inserter(vForeignKeys));
if ( vKeys.size() == vForeignKeys.size() ) {
TableRelation relation;
relation.sReferencedTable = p->sName;
for ( std::vector<std::string>::const_iterator k = vForeignKeys.begin(); k != vForeignKeys.end(); ++k )
relation.mapColumns.insert(std::make_pair(std::find(q->vColumns.begin(), q->vColumns.end(), *k) - q->vColumns.begin(), std::find_if(p->vColumns.begin(), p->vColumns.end(), std::bind1st(IsSourceColumn(), *k)) - p->vColumns.begin()));
mapRelations.insert(std::make_pair(q->sName, relation));
}
}
}
}
}
return mapRelations;
}
};
void main(void) {
std::transform(std::istream_iterator<Problem>(std::cin), std::istream_iterator<Problem>(), std::ostream_iterator<Solution>(std::cout), ProblemSolver());
}
Jeroen