Сравнение XML QDomElement сделано вообще — C ++ / Qt

Я пришел к следующему алгоритму проверки равенства:

Два узла a а также b равны, если a >= b а также b>=a

bool compare( QDomElement  element1, QDomElement  element2 )
{
return ! lessThen(element1, element2) && !lessThen(element2, element1);
}

Теперь нам осталось только ввести

Алгоритм сравнения

Сейчас буду использовать родной QString сравнить функцию

Прежде всего, в общем подходе мы должны сравнивать не только QDomElementс, но каждый QDomNode в дом.

• Если a.nodeType < b.nodeType, затем a < b
• В противном случае, если a.nodeName < b.nodeName, затем a < b
• В противном случае, если a.children.size() < b.children().size(), затем a < b
• В противном случае, если a.children().size() ==0 && b.children().size() ==0сравнить nodeValue(),
  Обратите внимание, что этот подход будет работать как для атрибута, так и для текстовых узлов. Сам QDomElement не имеет nodeValue, Если это некоторый текст, написанный внутри элемента, элемент будет иметь дочерний узел текстового типа. Поэтому element.nodeValue() call всегда возвращает пустую строку
• В противном случае отсортируйте все дочерние элементы заданных узлов, используя lessThen сравнить функцию.
• Затем проверьте для каждого ребенка c принадлежит a а также d принадлежит b:
  • Если d > c, затем a > b
  • Если c < d, затем a < b
  • Иначе (c==d) продолжить сравнение для следующего c а также d,
• я упал c равно d, затем a == bи, видимо, a < b неправильно.

Код, реализующий этот алгоритм:

QList<QDomNode> getChildElements(const QDomNode& e)
{
QList<QDomNode> r;
for (int k = 0; k < e.childNodes().size(); ++k) {
QDomNode n = e.childNodes().at(k);
r << n;
}
return r;
}bool lessThen( QDomNode  element1, QDomNode  element2 )
{
if (element1.nodeType() != element2.nodeType()) {
return element1.nodeType() < element1.nodeType();
}
QString tag1 = element1.nodeName() ;
QString tag2 = element2.nodeName() ;

//qDebug() << tag1 <<tag2;
if ( tag1 != tag2 )
return tag1 < tag2;

QList<QDomNode> elts1 = getChildElements(element1);
QList<QDomNode> elts2 = getChildElements(element2);QString value1, value2 ;

if(elts1.size() != elts2.size())
return elts2.size() < elts1.size() ;

if(elts1.size() == 0)
{
value1 = element1.nodeValue();
value2 = element2.nodeValue();

//qDebug() <<value1 << value2 << (value1 < value2);
return value1 < value2;

}

qSort(elts1.begin(), elts1.end(), lessThen);
qSort(elts2.begin(), elts2.end(), lessThen);
//qDebug() << "comparing sorted lists";
for(int  k = 0; k < elts1.size(); ++k) {
if (!lessThen(elts1[k], elts2[k])) {
if (lessThen(elts2[k], elts1[k])) {
//qDebug() << "false!";
return false;
}
}else {
//qDebug() << "true!";
return true;
}
}
return false;
}

bool compare( QDomElement  element1, QDomElement  element2 )
{
return ! lessThen(element1, element2) && !lessThen(element2, element1);
}

Обратите внимание, что алгоритм сравнения имеет чрезвычайно высокую сложность. Мне потребовалось около 10 минут для обработки 2 МБ XML-файла (с XML-должен-быть-равно к себе тестовое задание)

Формат:

description (desired result)
<xml1>
<xml2>
result

тесты:

different order (true)
"<r>
<a>x</a>
<a>y</a>
</r>
""<r>
<a>y</a>
<a>x</a>
</r>
"true
different text (false)
"<a>x</a>
""<a>y</a>
"false
different text with structure (false)
"<a>x<b/>ddcd</a>
""<a>y<b/>dede</a>
"false
same structure different names (false)
"<r>
<a/>
<a/>
<b/>
</r>
""<r>
<a/>
<b/>
<b/>
</r>
"false
same text with structure (true)
"<a>y<b/>x</a>
""<a>x<b/>y</a>
"true
attributes vs text (false)
"<a b="c"/>
""<a>
<b>c</b>
</a>
"false