X-Git-Url: http://git.salome-platform.org/gitweb/?a=blobdiff_plain;f=src%2FSUIT%2FSUIT_TreeSync.h;h=71d01ccd79de02b3532f90672344af8a2400fa7b;hb=bad17fa10a9ee5177948f9494855cd49e5e7c958;hp=61d8fde064081ab4b271bda586b0668aaa4661bb;hpb=f830c97c748d8f8a6a7eccc8e3a58e19066a1181;p=modules%2Fgui.git diff --git a/src/SUIT/SUIT_TreeSync.h b/src/SUIT/SUIT_TreeSync.h index 61d8fde06..71d01ccd7 100644 --- a/src/SUIT/SUIT_TreeSync.h +++ b/src/SUIT/SUIT_TreeSync.h @@ -1,11 +1,14 @@ -// Copyright (C) 2005 CEA/DEN, EDF R&D, OPEN CASCADE, PRINCIPIA R&D +// Copyright (C) 2007-2014 CEA/DEN, EDF R&D, OPEN CASCADE +// +// Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN, +// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS // // This library is free software; you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public // License as published by the Free Software Foundation; either -// version 2.1 of the License. +// version 2.1 of the License, or (at your option) any later version. // -// This library is distributed in the hope that it will be useful +// This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // Lesser General Public License for more details. @@ -17,252 +20,264 @@ // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com // -#ifndef SUIT_TREE_SYNC_HEADER -#define SUIT_TREE_SYNC_HEADER +// File : SUIT_TreeSync.h +// Author : Alexander SOLOVYOV +// +#ifndef SUIT_TREESYNC_H +#define SUIT_TREESYNC_H -#include -#include +#include /*! - \struct DiffItem - \brief Struct representing difference between items + \brief The structure representing difference between source and destination items. + + The different combinations of source and target items values imply the different actions + to be performed in the target data tree: + - source item is null, target item is not null : the item should be removed from the target tree + - source item is not null, target item is null : new item should be added to the target tree + - both source and target items are not null : the target item can be updated if necessary + - both source and target items are null : error */ template struct DiffItem { - SrcItem mySrc; - /*! - \var mySrc - if it is null, then this item is to deleted - */ - TrgItem myTrg; - /*! - \var myTrg - if it is null, then this item is to added - if both fields aren't null, then this item is to update - */ + SrcItem mySrc; //!< source tree item + TrgItem myTrg; //!< target tree item }; -/*! - \brief synchronizes two trees -*/ + +// +// Function prototypes. +// + template TrgItem synchronize( const SrcItem&, const TrgItem&, const TreeData& ); -/*! - \brief compares children -*/ template -void diffSiblings( const SrcItem&, const TrgItem&, - QValueList < DiffItem < SrcItem,TrgItem > >&, - const TreeData& ); +QList< DiffItem > diffSiblings( const SrcItem&, + const TrgItem&, + const TreeData& ); -/*! - \brief create item with children (subtree) -*/ template -TrgItem createSubTree( const SrcItem&, const TrgItem&, const TrgItem&, const bool, const TreeData& ); +TrgItem createSubTree( const SrcItem&, const TrgItem&, const TrgItem&, const TreeData& ); -/*! - \brief find equal element in list -*/ template -const typename QValueList::const_iterator findEqual( const QValueList& l, - const typename QValueList::const_iterator& first, - const SrcItem& it, - const TreeData& td ); - +const typename QList::const_iterator findEqual( const SrcItem& it, + const typename QList::const_iterator& first, + const typename QList::const_iterator& last, + const TreeData& td ); +// +// Function imlpementation. +// /*! - Synchronizes two trees by comparing corresponding items - \param r1 - start item from first tree - \param r2 - start item from second tree - \param td - auxiliary class providing following methods: -
    -
  • bool isEqual( const SrcItem&, const TrgItem& ) const - returns true if items are equal -
  • SrcItem nullSrc() const - returns null SrcItem -
  • TrgItem nullTrg() const - returns null TrgItem -
  • TrgItem createItem( -
      -
    1. const SrcItem& src, - corresponding SrcItem -
    2. const TrgItem& parent, - parent TrgItem -
    3. const TrgItem& after, - TrgItem after that new item must be added -
    4. const bool prepend - whether new item must be added as first -
    - ) const - creates new TrgItem -
  • void updateItem( const TrgItem& ) const - updates TrgItem without recreation -
  • void deleteItemWithChildren( const TrgItem& ) const - deletes TrgItem with all children -
  • void children( const SrcItem&, QValueList& ) const - fills list with children -
  • void children( const TrgItem&, QValueList& ) const - fills list with children -
  • SrcItem parent( const SrcItem& ) const - return parent SrcItem -
  • TrgItem parent( const TrgItem& ) const - return parent SrcItem -
+ \brief Synchronize two data trees by recurive comparing of the corresponding items. + + \param r1 starting item from the source data tree + \param r2 starting item from the target data tree + \param td functor class + \return the target tree item (updated or just created) corresponding to the starting + data object + + Actual comparing of the items and the syncronization of the trees is performed by the + functor class which is passed as the last parameter of the function. + The functor class should implement the following methods: + - \b bool \b isEqual( \b const \b SrcItem& \p src, \b const \b TrgItem& \p tgt ) \b const; + - \a src source tree item + - \a tgt target tree item + - compares items and returns \c true if the items are equal (correspond to each other) + - \b SrcItem \b nullSrc() \b const; + - returns null source tree itemm + - \b TrgItem \b nullTrg() \b const + - returns null target tree item + - \b TrgItem \b createItem( \b const \b SrcItem& \p src, \b const \b TrgItem& \p parent, \b const \b TrgItem& \p after ) \b const; + - \a src source item + - \a parent parent target item + - \a after target tree item after which new item shoud be inserted (if null, the item is added to the end) + - creates new ite in the target tree which correspond to the source item and returns created item + - \b void \b updateItem( \b const \b SrcItem& \p src, \b const \b TrgItem& \p tgt ) \b const; + - \a src source tree item + - \a tgt the item in the target tree to be updated + - updates target treeitem + - \b void \b deleteItemWithChildren( \b const \b TrgItem& \p tgt ) \b const; + - \a tgt the item in the target tree to be removed + - deletes target tree item (recursively) + - \b QList \b children( \b const \b SrcItem& \p parent ) \b const; + - \a parent the parent item in the source tree + - returns the child items list + - \b QList \b children( \b const \b TrgItem& \p parent ) \b const; + - \a parent the parent item in the target tree + - returns the child items list + - \b TrgItem \b parent( \b const \b TrgItem& \p tgt ) \b const; + - \a tgt target tree item + - returns the item which is parent for the specified source tree item */ template TrgItem synchronize( const SrcItem& r1, const TrgItem& r2, const TreeData& td ) { - if( td.isEqual( r1, r2 ) ) - { + if ( td.isEqual( r1, r2 ) ) { // update items themselves td.updateItem( r1, r2 ); - - // iterate 'siblings' (direct children) - QValueList< DiffItem< SrcItem, TrgItem > > d; - diffSiblings( r1, r2, d, td ); - - typename QValueList< DiffItem< SrcItem, TrgItem > >::const_iterator anIt = d.begin(), aLast = d.end(); + + // iterate through children + QList< DiffItem< SrcItem, TrgItem > > d = diffSiblings( r1, r2, td ); + + typename QList< DiffItem< SrcItem, TrgItem > >::const_iterator anIt = d.begin(), aLast = d.end(); TrgItem lastItem = td.nullTrg(); - // TrgItem tail = td.nullTrg(); - for( ; anIt!=aLast; anIt++ ) - { + + for ( ; anIt != aLast; anIt++ ) { const DiffItem& item = *anIt; - if( item.mySrc==td.nullSrc() ) - if( item.myTrg==td.nullTrg() ) - qDebug( "error: both null" ); + if ( item.mySrc == td.nullSrc() ) { + if ( item.myTrg == td.nullTrg() ) + qDebug( "error: both null" ); else - //to delete - td.deleteItemWithChildren( item.myTrg ); + // delete item + td.deleteItemWithChildren( item.myTrg ); + } else { - if( item.myTrg==td.nullTrg() ) - { - //to add - TrgItem nitem = createSubTree( item.mySrc, r2, lastItem, lastItem==td.nullTrg(), td ); - if( nitem!=td.nullTrg() ) - lastItem = nitem; - } - else - { - //to update - td.updateItem( item.mySrc, item.myTrg ); - synchronize( item.mySrc, item.myTrg, td ); - lastItem = item.myTrg; - } + if ( item.myTrg == td.nullTrg() ) { + // add item (recursively) + TrgItem nitem = createSubTree( item.mySrc, r2, lastItem, td ); + if ( nitem != td.nullTrg() ) + lastItem = nitem; + } + else { + // update item + synchronize( item.mySrc, item.myTrg, td ); + lastItem = item.myTrg; + } } } - return r2; } - else - { - TrgItem new_r2 = createSubTree( r1, td.parent( r2 ), r2, false, td ); - if( r2!=td.nullTrg() ) + else { + TrgItem new_r2 = td.nullTrg(); + if ( r1 != td.nullSrc() ) { + // add new item (recursively) + new_r2 = createSubTree( r1, td.parent( r2 ), r2, td ); + } + if ( r2 != td.nullTrg() ) { + // delete old one (if it is not null) td.deleteItemWithChildren( r2 ); + } return new_r2; } } /*! - Finds equal element in list - \return iterator - \param l - list to search - \param first - start iterator - \param it - item to be found - \param td - tree data object (provides auxiliary methods) + \brief Find the item in the target tree which correspond to the specified source tree item. + \param it source item for which correspondence is to be found + \param first iterator pointing to the item in the list \a l from which search shoud be started + \param last iterator pointing to the item in the list \a l the search to be finished at + \param td functor class + \return iterator pointing to the item in the list \l if the correspondence is found or iterator + \a last if the correspondence is not found + \sa synchronize() */ template -const typename QValueList::const_iterator findEqual( const QValueList& l, - const typename QValueList::const_iterator& first, - const SrcItem& it, - const TreeData& td ) +const typename QList::const_iterator findEqual( const SrcItem& it, + const typename QList::const_iterator& first, + const typename QList::const_iterator& last, + const TreeData& td ) { - typename QValueList::const_iterator cur = first, last = l.end(); - for( ; cur!=last; cur++ ) - if( td.isEqual( it, *cur ) ) + typename QList::const_iterator cur = first; + for ( ; cur != last; cur++ ) { + if ( td.isEqual( it, *cur ) ) return cur; + } return last; } /*! - Compares children of objects src and trg - \param src - SrcItem to be checked - \param trg - TrgItem to be checked - \param d - map of difference to be filled - \param td - tree data object (provides auxiliary methods) + \brief Compare children of the source and target trees to find differences. + \param src parent source item + \param trg parent target item + \param td functor class + \return list of the differences + \sa synchronize() */ template -void diffSiblings( const SrcItem& src, const TrgItem& trg, - QValueList < DiffItem < SrcItem,TrgItem > >& d, - const TreeData& td ) +QList< DiffItem > diffSiblings( const SrcItem& src, const TrgItem& trg, + const TreeData& td ) { //if( src==td.nullSrc() || trg==td.nullTrg() ) // return; + + QList< DiffItem > d; + + QList src_ch = td.children( src ); + QList trg_ch = td.children( trg ); - QValueList src_ch; - QValueList trg_ch; - td.children( src, src_ch ); - td.children( trg, trg_ch ); - - typename QValueList::const_iterator src_it = src_ch.begin(), src_last = src_ch.end(); - typename QValueList::const_iterator cur = trg_ch.begin(), trg_last = trg_ch.end(); + typename QList::const_iterator src_it = src_ch.begin(), src_last = src_ch.end(); + typename QList::const_iterator cur = trg_ch.begin(), trg_last = trg_ch.end(); - for( ; src_it!=src_last; src_it++ ) - { - typename QValueList::const_iterator f = - findEqual( trg_ch, cur, *src_it, td ); - if( f!=trg_last ) //is found - { - //mark all items before found as "to be deleted" - for( typename QValueList::const_iterator it = cur; it!=f; it++ ) - { - DiffItem ndiff; - ndiff.mySrc = td.nullSrc(); - ndiff.myTrg = *it; //to delete; - d.append( ndiff ); + for ( ; src_it != src_last; src_it++ ) { + typename QList::const_iterator f = + findEqual( *src_it, cur, trg_last, td ); + if ( f != trg_last ) { + // target is found + // mark all items before found one as "to be deleted" + for ( typename QList::const_iterator it = cur; it != f; it++ ) { + DiffItem ndiff; + ndiff.mySrc = td.nullSrc(); + ndiff.myTrg = *it; // delete item + d.append( ndiff ); } cur = f; DiffItem ndiff; ndiff.mySrc = *src_it; - ndiff.myTrg = *cur; //update this item + ndiff.myTrg = *cur; // update this (found) item d.append( ndiff ); cur++; } - else //not found - { + else { + // target is not found DiffItem ndiff; ndiff.mySrc = *src_it; - ndiff.myTrg = td.nullTrg(); //add this item + ndiff.myTrg = td.nullTrg(); // add item d.append( ndiff ); } } - for( ; cur!=trg_last; cur++ ) - { + // delete rest items + for ( ; cur != trg_last; cur++ ) { DiffItem ndiff; ndiff.mySrc = td.nullSrc(); - ndiff.myTrg = *cur; //to delete; + ndiff.myTrg = *cur; // delete item d.append( ndiff ); } + + return d; } /*! - Creates sub-tree - \return root of just created sub-tree - \param src - corresponding SrcItem - \param parent - parent of new TrgItem - \param after - TrgItem, after that new item must be added - \param asFirst - true if TrgItem must be added as first - \param td - tree data object (provides auxiliary methods) + \brief Create an item with all its children recursively in the target tree. + \param src source tree item + \param parent parent item in the target tree + \param after item in the target tree after which new item shoud be inserted + \param td functor class + \return created item + \sa synchronize() */ template TrgItem createSubTree( const SrcItem& src, const TrgItem& parent, - const TrgItem& after, const bool asFirst, - const TreeData& td ) + const TrgItem& after, const TreeData& td ) { - if( src==td.nullSrc() ) + if ( src == td.nullSrc() ) return td.nullTrg(); - TrgItem nitem = td.createItem( src, parent, after, asFirst ); - if( nitem==td.nullTrg() ) + TrgItem nitem = td.createItem( src, parent, after ); + if ( nitem == td.nullTrg() ) return nitem; - QValueList ch; - td.children( src, ch ); - typename QValueList::const_iterator anIt = ch.begin(), aLast = ch.end(); - for( ; anIt!=aLast; anIt++ ) - createSubTree( *anIt, nitem, td.nullTrg(), false, td ); + QList ch = td.children( src ); + typename QList::const_iterator anIt = ch.begin(), aLast = ch.end(); + TrgItem last = td.nullTrg(); + for( ; anIt != aLast; anIt++ ) + last = createSubTree( *anIt, nitem, last, td ); return nitem; } -#endif +#endif // SUIT_TREESYNC_H