From a7300c7a1c4dbffee3ac5242e50b05191176dd0c Mon Sep 17 00:00:00 2001 From: asv Date: Thu, 26 Jan 2006 09:15:09 +0000 Subject: [PATCH] SUIT_TreeSync.h is added to CVS and Makefile.in. This file introduces general synchronization algorithm between tree structures. It is implemented using templates, and instanciated in: - ObjBrowser package: synchronization between trees of SUIT_DataObjects and OB_ListItems - SalomeApp package: synchronization between trees of SObjects and SUIT_DataObjects --- src/SUIT/Makefile.in | 3 +- src/SUIT/SUIT_TreeSync.h | 176 +++++++++++++++++++++++++++++++++++++++ 2 files changed, 178 insertions(+), 1 deletion(-) create mode 100644 src/SUIT/SUIT_TreeSync.h diff --git a/src/SUIT/Makefile.in b/src/SUIT/Makefile.in index f08c897d0..a6bab14a7 100755 --- a/src/SUIT/Makefile.in +++ b/src/SUIT/Makefile.in @@ -41,7 +41,8 @@ EXPORT_HEADERS= SUIT.h \ SUIT_ViewModel.h \ SUIT_ViewWindow.h \ SUIT_SelectionFilter.h \ - SUIT_Accel.h + SUIT_Accel.h \ + SUIT_TreeSync.h # .po files to transform in .qm PO_FILES = SUIT_images.po \ diff --git a/src/SUIT/SUIT_TreeSync.h b/src/SUIT/SUIT_TreeSync.h new file mode 100644 index 000000000..8dd99f5da --- /dev/null +++ b/src/SUIT/SUIT_TreeSync.h @@ -0,0 +1,176 @@ + +#ifndef SUIT_TREE_SYNC_HEADER +#define SUIT_TREE_SYNC_HEADER + +#include +#include + +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 +}; + +template +TrgItem synchronize( const SrcItem&, const TrgItem&, const TreeData& ); + +template +void diffSiblings( const SrcItem&, const TrgItem&, + QValueList < DiffItem < SrcItem,TrgItem > >&, + const TreeData& ); + +template +TrgItem createSubTree( const SrcItem&, const TrgItem&, const TrgItem&, const bool, const TreeData& ); + +template +const typename QValueList::const_iterator findEqual( const QValueList& l, + const typename QValueList::const_iterator& first, + const SrcItem& it, + const TreeData& td ); + + + + + +//int gSync = 0; +template +TrgItem synchronize( const SrcItem& r1, const TrgItem& r2, const TreeData& td ) +{ + // printf( "--- synchronize : %d ---\n", ++gSync ); + + if( td.isEqual( r1, r2 ) ) + { + 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; + TrgItem lastItem = td.nullTrg(); + // TrgItem tail = td.nullTrg(); + for( ; anIt!=aLast; anIt++ ) + { + const DiffItem& item = *anIt; + if( item.mySrc==td.nullSrc() ) + if( item.myTrg==td.nullTrg() ) + qDebug( "error: both null" ); + else + //to delete + 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; + } + } + + return r2; + } + else + { + TrgItem new_r2 = createSubTree( r1, td.parent( r2 ), r2, false, td ); + if( r2!=td.nullTrg() ) + td.deleteItemWithChildren( r2 ); + return new_r2; + } +} + +template +const typename QValueList::const_iterator findEqual( const QValueList& l, + const typename QValueList::const_iterator& first, + const SrcItem& it, + const TreeData& td ) +{ + typename QValueList::const_iterator cur = first, last = l.end(); + for( ; cur!=last; cur++ ) + if( td.isEqual( it, *cur ) ) + return cur; + return last; +} + +template +void diffSiblings( const SrcItem& src, const TrgItem& trg, + QValueList < DiffItem < SrcItem,TrgItem > >& d, + 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 ); + } + cur = f; + DiffItem ndiff; + ndiff.mySrc = *src_it; + ndiff.myTrg = *cur; //update this item + d.append( ndiff ); + cur++; + } + else //not found + { + DiffItem ndiff; + ndiff.mySrc = *src_it; + ndiff.myTrg = td.nullTrg(); //add this item + d.append( ndiff ); + } + } + for( ; cur!=trg_last; cur++ ) + { + DiffItem ndiff; + ndiff.mySrc = td.nullSrc(); + ndiff.myTrg = *cur; //to delete; + d.append( ndiff ); + } +} + +template +TrgItem createSubTree( const SrcItem& src, const TrgItem& parent, + const TrgItem& after, const bool asFirst, + const TreeData& td ) +{ + if( src==td.nullSrc() ) + return td.nullTrg(); + + TrgItem nitem = td.createItem( src, parent, after, asFirst ); + 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 ); + + return nitem; +} + +#endif -- 2.39.2