X-Git-Url: http://git.salome-platform.org/gitweb/?a=blobdiff_plain;f=src%2FSUIT%2FSUIT_TreeSync.h;h=71d01ccd79de02b3532f90672344af8a2400fa7b;hb=bad17fa10a9ee5177948f9494855cd49e5e7c958;hp=19bdf4edd645c9f5220e8efc6b7bca1537721c18;hpb=101fd10f1e736daa5d7f0f0ee5499b951460832a;p=modules%2Fgui.git diff --git a/src/SUIT/SUIT_TreeSync.h b/src/SUIT/SUIT_TreeSync.h index 19bdf4edd..71d01ccd7 100644 --- a/src/SUIT/SUIT_TreeSync.h +++ b/src/SUIT/SUIT_TreeSync.h @@ -1,179 +1,283 @@ +// 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, or (at your option) any later version. +// +// 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. +// +// You should have received a copy of the GNU Lesser General Public +// License along with this library; if not, write to the Free Software +// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +// +// 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 +/*! + \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; //if it is null, then this item is to deleted - TrgItem 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 }; + +// +// Function prototypes. +// + template TrgItem synchronize( const SrcItem&, const TrgItem&, const TreeData& ); template -void diffSiblings( const SrcItem&, const TrgItem&, - QValueList < DiffItem < SrcItem,TrgItem > >&, - const TreeData& ); +QList< DiffItem > diffSiblings( const SrcItem&, + const TrgItem&, + const TreeData& ); template -TrgItem createSubTree( const SrcItem&, const TrgItem&, const TrgItem&, const bool, const TreeData& ); +TrgItem createSubTree( const SrcItem&, const TrgItem&, const TrgItem&, const TreeData& ); 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. +// +/*! + \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 -//int gSync = 0; + 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( 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(); - bool isFirst = true; + td.updateItem( r1, r2 ); + + // 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 - lastItem = createSubTree( item.mySrc, r2, lastItem, isFirst, td ); - } - else - { - //to update - td.updateItem( item.myTrg ); - synchronize( item.mySrc, item.myTrg, td ); - lastItem = item.myTrg; - } - isFirst = false; + 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; } } +/*! + \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; } +/*! + \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; - - 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(); - - 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 ); + //if( src==td.nullSrc() || trg==td.nullTrg() ) + // return; + + QList< DiffItem > d; + + QList src_ch = td.children( src ); + QList trg_ch = td.children( trg ); + + 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 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; } +/*! + \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