Сравните два xpath_node_set в C++ с pugixml 1.4

Question

У меня есть два файла XML, и я хочу сравнить его подраздел, если он равен. XML-файлы могут быть разными, но я приведу пример. У меня есть следующие XML-файлы:

<EXECUTION_SET> 
    <RESULT query_id="7" > 
    <OP> 
     <PROJ> 
     <COLUMN col_name="City.ID" col_type="3" col_length="11" /> 
     <OP> 
      <JOIN> 
      <OP> 
       <TABLE name="City" alias="City" access_type="5" total_record_length="67"> 
       <COLUMN col_name="ID" col_type="3" col_length="11" raw_length="4" /> 
       <COLUMN col_name="Name" col_type="254" col_length="35" raw_length="35" /> 
       <COLUMN col_name="CountryCode" col_type="254" col_length="3" raw_length="3" /> 
       <COLUMN col_name="District" col_type="254" col_length="20" raw_length="20" /> 
       <COLUMN col_name="Population" col_type="3" col_length="11" raw_length="4" /> 
       </TABLE> 
      </OP> 
      <OP> 
       <SEL> 
       <COND> 
        <COND> 
        <VALUE><VARIABLE>Country.Population</VARIABLE></VALUE> 
        </COND> 
        <BOP><![CDATA[>]]></BOP> 
        <COND> 
        <VALUE><CONSTANT>80000000</CONSTANT></VALUE> 
        </COND> 
       </COND> 
       <OP> 
       <OP> 
        <TABLE name="Country" alias="Country" access_type="5" total_record_length="261"> 
        <COLUMN col_name="Code" col_type="254" col_length="3" raw_length="3" /> 
        <COLUMN col_name="Name" col_type="254" col_length="52" raw_length="52" /> 
        <COLUMN col_name="Continent" col_type="254" col_length="13" raw_length="1" /> 
        <COLUMN col_name="Region" col_type="254" col_length="26" raw_length="26" /> 
        <COLUMN col_name="SurfaceArea" col_type="4" col_length="10" raw_length="4" /> 
        <COLUMN col_name="IndepYear" col_type="2" col_length="6" raw_length="2" /> 
        <COLUMN col_name="Population" col_type="3" col_length="11" raw_length="4" /> 
        <COLUMN col_name="LifeExpectancy" col_type="4" col_length="3" raw_length="4" /> 
        <COLUMN col_name="GNP" col_type="4" col_length="10" raw_length="4" /> 
        <COLUMN col_name="GNPOld" col_type="4" col_length="10" raw_length="4" /> 
        <COLUMN col_name="LocalName" col_type="254" col_length="45" raw_length="45" /> 
        <COLUMN col_name="GovernmentForm" col_type="254" col_length="45" raw_length="45" /> 
        <COLUMN col_name="HeadOfState" col_type="254" col_length="60" raw_length="60" /> 
        <COLUMN col_name="Capital" col_type="3" col_length="11" raw_length="4" /> 
        <COLUMN col_name="Code2" col_type="254" col_length="2" raw_length="2" /> 
        </TABLE> 
       </OP> 
       </OP> 
       </SEL> 
      </OP> 
      </JOIN> 
     </OP> 
     </PROJ> 
    </OP> 
    </RESULT> 
</EXECUTION_SET> 

И второй XML-файл:

<EXECUTION_SET> 
    <RESULT query_id="13" > 
    <OP> 
     <PROJ> 
     <COLUMN col_name="Country.Code" col_type="254" col_length="3" /> 
     <OP> 
      <SEL> 
      <COND> 
       <COND> 
       <VALUE><VARIABLE>Country.Population</VARIABLE></VALUE> 
       </COND> 
       <BOP><![CDATA[>]]></BOP> 
       <COND> 
       <VALUE><CONSTANT>80000000</CONSTANT></VALUE> 
       </COND> 
      </COND> 
      <OP> 
      <OP> 
       <TABLE name="Country" alias="Country" access_type="5" total_record_length="261"> 
       <COLUMN col_name="Code" col_type="254" col_length="3" raw_length="3" /> 
       <COLUMN col_name="Name" col_type="254" col_length="52" raw_length="52" /> 
       <COLUMN col_name="Continent" col_type="254" col_length="13" raw_length="1" /> 
       <COLUMN col_name="Region" col_type="254" col_length="26" raw_length="26" /> 
       <COLUMN col_name="SurfaceArea" col_type="4" col_length="10" raw_length="4" /> 
       <COLUMN col_name="IndepYear" col_type="2" col_length="6" raw_length="2" /> 
       <COLUMN col_name="Population" col_type="3" col_length="11" raw_length="4" /> 
       <COLUMN col_name="LifeExpectancy" col_type="4" col_length="3" raw_length="4" /> 
       <COLUMN col_name="GNP" col_type="4" col_length="10" raw_length="4" /> 
       <COLUMN col_name="GNPOld" col_type="4" col_length="10" raw_length="4" /> 
       <COLUMN col_name="LocalName" col_type="254" col_length="45" raw_length="45" /> 
       <COLUMN col_name="GovernmentForm" col_type="254" col_length="45" raw_length="45" /> 
       <COLUMN col_name="HeadOfState" col_type="254" col_length="60" raw_length="60" /> 
       <COLUMN col_name="Capital" col_type="3" col_length="11" raw_length="4" /> 
       <COLUMN col_name="Code2" col_type="254" col_length="2" raw_length="2" /> 
       </TABLE> 
      </OP> 
      </OP> 
      </SEL> 
     </OP> 
     </PROJ> 
    </OP> 
    </RESULT> 
</EXECUTION_SET> 

С этих двух файлов XML, я хочу сравнить подраздел под тегом, если этот подраздел равно. Для этого я выполняю для обоих запросов xpath следующее: doc.select_nodes(std::string("//TABLE[@name='Country']/ancestor::SEL/COND").c_str()); и записываю его в переменные pugi::xpath_node_set partialTree1 и partialTree2.

Итак, я получаю подразделы обоих файлов xml. Теперь я хочу сравнить оба подраздела. Это должен быть хороший эффективный способ.

У меня есть решение, но мне оно не нравится, потому что оно требует много времени и пространства. В настоящий момент я использую функцию traverse, чтобы перейти в подразделы и написать все в строке для обоих подразделов. Затем я сравниваю это. Но для этого должен быть лучший способ.

Было бы неплохо, если бы у кого-то были идеи.

Answer 1

В результате вашего запроса у вас есть набор узлов из разных документов. Каждый узел имеет определенное количество потомков, и для сравнения двух узлов вы должны сравнить всех своих потомков - если вы пропустите один, вы не знаете, равны ли деревья.

Это предполагает, что подход сравнения дампа строк узлов является оптимальным с точки зрения времени с точки зрения времени. Он не является оптимальным с точки зрения пространства - оптимальный алгоритм с точки зрения пространства проходит через оба дерева в синхронизации и напрямую сравнивает значения. Что-то вроде этого должно работать:

template <typename It, typename Pred> 
bool rangeEquals(It lb, It le, It rb, It re, Pred pred) 
{ 
    It li = lb, ri = rb; 

    for (; li != le && ri != re; ++li, ++ri) 
     if (!pred(*li, *ri)) 
      return false; 

    return li == le && ri == re; 
} 

bool attrEquals(pugi::xml_attribute la, pugi::xml_attribute ra) 
{ 
    return 
     strcmp(la.name(), ra.name()) == 0 && 
     strcmp(la.value(), ra.value()) == 0; 
} 

bool nodeEquals(pugi::xml_node ln, pugi::xml_node rn) 
{ 
    return 
     ln.type() == rn.type() && 
     strcmp(ln.name(), rn.name()) == 0 && 
     strcmp(ln.value(), rn.value()) == 0 && 
     rangeEquals(ln.attributes_begin(), ln.attributes_end(), rn.attributes_begin(), rn.attributes_end(), attrEquals) && 
     rangeEquals(ln.begin(), ln.end(), rn.begin(), rn.end(), nodeEquals); 
}