1 // Copyright (C) 2005 CEA/DEN, EDF R&D, OPEN CASCADE, PRINCIPIA R&D
3 // This library is free software; you can redistribute it and/or
4 // modify it under the terms of the GNU Lesser General Public
5 // License as published by the Free Software Foundation; either
6 // version 2.1 of the License.
8 // This library is distributed in the hope that it will be useful
9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 // Lesser General Public License for more details.
13 // You should have received a copy of the GNU Lesser General Public
14 // License along with this library; if not, write to the Free Software
15 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 // See http://www.salome-platform.org/
20 #ifndef SUIT_TREE_SYNC_HEADER
21 #define SUIT_TREE_SYNC_HEADER
24 #include <qvaluelist.h>
28 \brief Struct representing difference between items
30 template <class SrcItem, class TrgItem>
36 if it is null, then this item is to deleted
41 if it is null, then this item is to added
42 if both fields aren't null, then this item is to update
47 \brief synchronizes two trees
49 template <class SrcItem, class TrgItem, class TreeData>
50 TrgItem synchronize( const SrcItem&, const TrgItem&, const TreeData& );
53 \brief compares children
55 template <class SrcItem, class TrgItem, class TreeData>
56 void diffSiblings( const SrcItem&, const TrgItem&,
57 QValueList < DiffItem < SrcItem,TrgItem > >&,
61 \brief create item with children (subtree)
63 template <class SrcItem, class TrgItem, class TreeData>
64 TrgItem createSubTree( const SrcItem&, const TrgItem&, const TrgItem&, const bool, const TreeData& );
67 \brief find equal element in list
69 template <class SrcItem, class TrgItem, class TreeData>
70 const typename QValueList<TrgItem>::const_iterator findEqual( const QValueList<TrgItem>& l,
71 const typename QValueList<TrgItem>::const_iterator& first,
79 Synchronizes two trees by comparing corresponding items
80 \param r1 - start item from first tree
81 \param r2 - start item from second tree
82 \param td - auxiliary class providing following methods:
84 <li> bool isEqual( const SrcItem&, const TrgItem& ) const - returns true if items are equal
85 <li> SrcItem nullSrc() const - returns null SrcItem
86 <li> TrgItem nullTrg() const - returns null TrgItem
87 <li> TrgItem createItem(
89 <li> const SrcItem& src, - corresponding SrcItem
90 <li> const TrgItem& parent, - parent TrgItem
91 <li> const TrgItem& after, - TrgItem after that new item must be added
92 <li> const bool prepend - whether new item must be added as first
94 ) const - creates new TrgItem
95 <li> void updateItem( const TrgItem& ) const - updates TrgItem without recreation
96 <li> void deleteItemWithChildren( const TrgItem& ) const - deletes TrgItem with all children
97 <li> void children( const SrcItem&, QValueList<SrcItem>& ) const - fills list with children
98 <li> void children( const TrgItem&, QValueList<TrgItem>& ) const - fills list with children
99 <li> SrcItem parent( const SrcItem& ) const - return parent SrcItem
100 <li> TrgItem parent( const TrgItem& ) const - return parent SrcItem
103 template <class SrcItem, class TrgItem, class TreeData>
104 TrgItem synchronize( const SrcItem& r1, const TrgItem& r2, const TreeData& td )
106 if( td.isEqual( r1, r2 ) )
108 // update items themselves
111 // iterate 'siblings' (direct children)
112 QValueList< DiffItem< SrcItem, TrgItem > > d;
113 diffSiblings( r1, r2, d, td );
115 typename QValueList< DiffItem< SrcItem, TrgItem > >::const_iterator anIt = d.begin(), aLast = d.end();
116 TrgItem lastItem = td.nullTrg();
117 // TrgItem tail = td.nullTrg();
118 for( ; anIt!=aLast; anIt++ )
120 const DiffItem<SrcItem,TrgItem>& item = *anIt;
121 if( item.mySrc==td.nullSrc() )
122 if( item.myTrg==td.nullTrg() )
123 qDebug( "error: both null" );
126 td.deleteItemWithChildren( item.myTrg );
128 if( item.myTrg==td.nullTrg() )
131 TrgItem nitem = createSubTree( item.mySrc, r2, lastItem, lastItem==td.nullTrg(), td );
132 if( nitem!=td.nullTrg() )
138 td.updateItem( item.myTrg );
139 synchronize( item.mySrc, item.myTrg, td );
140 lastItem = item.myTrg;
149 TrgItem new_r2 = createSubTree( r1, td.parent( r2 ), r2, false, td );
150 if( r2!=td.nullTrg() )
151 td.deleteItemWithChildren( r2 );
157 Finds equal element in list
159 \param l - list to search
160 \param first - start iterator
161 \param it - item to be found
162 \param td - tree data object (provides auxiliary methods)
164 template <class SrcItem, class TrgItem, class TreeData>
165 const typename QValueList<TrgItem>::const_iterator findEqual( const QValueList<TrgItem>& l,
166 const typename QValueList<TrgItem>::const_iterator& first,
170 typename QValueList<TrgItem>::const_iterator cur = first, last = l.end();
171 for( ; cur!=last; cur++ )
172 if( td.isEqual( it, *cur ) )
178 Compares children of objects src and trg
179 \param src - SrcItem to be checked
180 \param trg - TrgItem to be checked
181 \param d - map of difference to be filled
182 \param td - tree data object (provides auxiliary methods)
184 template <class SrcItem, class TrgItem, class TreeData>
185 void diffSiblings( const SrcItem& src, const TrgItem& trg,
186 QValueList < DiffItem < SrcItem,TrgItem > >& d,
189 //if( src==td.nullSrc() || trg==td.nullTrg() )
192 QValueList<SrcItem> src_ch;
193 QValueList<TrgItem> trg_ch;
194 td.children( src, src_ch );
195 td.children( trg, trg_ch );
197 typename QValueList<SrcItem>::const_iterator src_it = src_ch.begin(), src_last = src_ch.end();
198 typename QValueList<TrgItem>::const_iterator cur = trg_ch.begin(), trg_last = trg_ch.end();
200 for( ; src_it!=src_last; src_it++ )
202 typename QValueList<TrgItem>::const_iterator f =
203 findEqual<SrcItem, TrgItem, TreeData>( trg_ch, cur, *src_it, td );
204 if( f!=trg_last ) //is found
206 //mark all items before found as "to be deleted"
207 for( typename QValueList<TrgItem>::const_iterator it = cur; it!=f; it++ )
209 DiffItem<SrcItem,TrgItem> ndiff;
210 ndiff.mySrc = td.nullSrc();
211 ndiff.myTrg = *it; //to delete;
215 DiffItem<SrcItem,TrgItem> ndiff;
216 ndiff.mySrc = *src_it;
217 ndiff.myTrg = *cur; //update this item
223 DiffItem<SrcItem,TrgItem> ndiff;
224 ndiff.mySrc = *src_it;
225 ndiff.myTrg = td.nullTrg(); //add this item
229 for( ; cur!=trg_last; cur++ )
231 DiffItem<SrcItem,TrgItem> ndiff;
232 ndiff.mySrc = td.nullSrc();
233 ndiff.myTrg = *cur; //to delete;
240 \return root of just created sub-tree
241 \param src - corresponding SrcItem
242 \param parent - parent of new TrgItem
243 \param after - TrgItem, after that new item must be added
244 \param asFirst - true if TrgItem must be added as first
245 \param td - tree data object (provides auxiliary methods)
247 template <class SrcItem, class TrgItem, class TreeData>
248 TrgItem createSubTree( const SrcItem& src, const TrgItem& parent,
249 const TrgItem& after, const bool asFirst,
252 if( src==td.nullSrc() )
255 TrgItem nitem = td.createItem( src, parent, after, asFirst );
256 if( nitem==td.nullTrg() )
259 QValueList<SrcItem> ch;
260 td.children( src, ch );
261 typename QValueList<SrcItem>::const_iterator anIt = ch.begin(), aLast = ch.end();
262 for( ; anIt!=aLast; anIt++ )
263 createSubTree( *anIt, nitem, td.nullTrg(), false, td );