-// Copyright (C) 2005 CEA/DEN, EDF R&D, OPEN CASCADE, PRINCIPIA R&D
+// Copyright (C) 2007-2023 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.
// 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 <qptrlist.h>
-#include <qvaluelist.h>
+#include <QList>
/*!
- \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 <class SrcItem, class TrgItem>
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 <class SrcItem, class TrgItem, class TreeData>
TrgItem synchronize( const SrcItem&, const TrgItem&, const TreeData& );
-/*!
- \brief compares children
-*/
template <class SrcItem, class TrgItem, class TreeData>
-void diffSiblings( const SrcItem&, const TrgItem&,
- QValueList < DiffItem < SrcItem,TrgItem > >&,
- const TreeData& );
+QList< DiffItem<SrcItem,TrgItem> > diffSiblings( const SrcItem&,
+ const TrgItem&,
+ const TreeData& );
-/*!
- \brief create item with children (subtree)
-*/
template <class SrcItem, class TrgItem, class TreeData>
-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 <class SrcItem, class TrgItem, class TreeData>
-const typename QValueList<TrgItem>::const_iterator findEqual( const QValueList<TrgItem>& l,
- const typename QValueList<TrgItem>::const_iterator& first,
- const SrcItem& it,
- const TreeData& td );
-
+const typename QList<TrgItem>::const_iterator findEqual( const SrcItem& it,
+ const typename QList<TrgItem>::const_iterator& first,
+ const typename QList<TrgItem>::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:
- <ul>
- <li> bool isEqual( const SrcItem&, const TrgItem& ) const - returns true if items are equal
- <li> SrcItem nullSrc() const - returns null SrcItem
- <li> TrgItem nullTrg() const - returns null TrgItem
- <li> TrgItem createItem(
- <ol>
- <li> const SrcItem& src, - corresponding SrcItem
- <li> const TrgItem& parent, - parent TrgItem
- <li> const TrgItem& after, - TrgItem after that new item must be added
- <li> const bool prepend - whether new item must be added as first
- </ol>
- ) const - creates new TrgItem
- <li> void updateItem( const TrgItem& ) const - updates TrgItem without recreation
- <li> void deleteItemWithChildren( const TrgItem& ) const - deletes TrgItem with all children
- <li> void children( const SrcItem&, QValueList<SrcItem>& ) const - fills list with children
- <li> void children( const TrgItem&, QValueList<TrgItem>& ) const - fills list with children
- <li> SrcItem parent( const SrcItem& ) const - return parent SrcItem
- <li> TrgItem parent( const TrgItem& ) const - return parent SrcItem
- </ul>
+ \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<SrcItem> \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<TrgItem> \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 <class SrcItem, class TrgItem, class TreeData>
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<SrcItem,TrgItem>& 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() )
+ {
+#ifdef _DEBUG_
+ qDebug( "error: both null" );
+#endif
+ }
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 <class SrcItem, class TrgItem, class TreeData>
-const typename QValueList<TrgItem>::const_iterator findEqual( const QValueList<TrgItem>& l,
- const typename QValueList<TrgItem>::const_iterator& first,
- const SrcItem& it,
- const TreeData& td )
+const typename QList<TrgItem>::const_iterator findEqual( const SrcItem& it,
+ const typename QList<TrgItem>::const_iterator& first,
+ const typename QList<TrgItem>::const_iterator& last,
+ const TreeData& td )
{
- typename QValueList<TrgItem>::const_iterator cur = first, last = l.end();
- for( ; cur!=last; cur++ )
- if( td.isEqual( it, *cur ) )
+ typename QList<TrgItem>::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 <class SrcItem, class TrgItem, class TreeData>
-void diffSiblings( const SrcItem& src, const TrgItem& trg,
- QValueList < DiffItem < SrcItem,TrgItem > >& d,
- const TreeData& td )
+QList< DiffItem<SrcItem,TrgItem> > diffSiblings( const SrcItem& src, const TrgItem& trg,
+ const TreeData& td )
{
//if( src==td.nullSrc() || trg==td.nullTrg() )
// return;
+
+ QList< DiffItem<SrcItem,TrgItem> > d;
+
+ QList<SrcItem> src_ch = td.children( src );
+ QList<TrgItem> trg_ch = td.children( trg );
- QValueList<SrcItem> src_ch;
- QValueList<TrgItem> trg_ch;
- td.children( src, src_ch );
- td.children( trg, trg_ch );
+ typename QList<SrcItem>::const_iterator src_it = src_ch.begin(), src_last = src_ch.end();
+ typename QList<TrgItem>::const_iterator cur = trg_ch.begin(), trg_last = trg_ch.end();
- typename QValueList<SrcItem>::const_iterator src_it = src_ch.begin(), src_last = src_ch.end();
- typename QValueList<TrgItem>::const_iterator cur = trg_ch.begin(), trg_last = trg_ch.end();
-
- for( ; src_it!=src_last; src_it++ )
- {
- typename QValueList<TrgItem>::const_iterator f =
- findEqual<SrcItem, TrgItem, TreeData>( trg_ch, cur, *src_it, td );
- if( f!=trg_last ) //is found
- {
- //mark all items before found as "to be deleted"
- for( typename QValueList<TrgItem>::const_iterator it = cur; it!=f; it++ )
- {
- DiffItem<SrcItem,TrgItem> ndiff;
- ndiff.mySrc = td.nullSrc();
- ndiff.myTrg = *it; //to delete;
- d.append( ndiff );
+ for ( ; src_it != src_last; src_it++ ) {
+ typename QList<TrgItem>::const_iterator f =
+ findEqual<SrcItem, TrgItem, TreeData>( *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<TrgItem>::const_iterator it = cur; it != f; it++ ) {
+ DiffItem<SrcItem,TrgItem> ndiff;
+ ndiff.mySrc = td.nullSrc();
+ ndiff.myTrg = *it; // delete item
+ d.append( ndiff );
}
cur = f;
DiffItem<SrcItem,TrgItem> 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<SrcItem,TrgItem> 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<SrcItem,TrgItem> 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 <class SrcItem, class TrgItem, class TreeData>
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<SrcItem> ch;
- td.children( src, ch );
- typename QValueList<SrcItem>::const_iterator anIt = ch.begin(), aLast = ch.end();
- for( ; anIt!=aLast; anIt++ )
- createSubTree( *anIt, nitem, td.nullTrg(), false, td );
+ QList<SrcItem> ch = td.children( src );
+ typename QList<SrcItem>::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
