1 // Copyright (C) 2007-2008 CEA/DEN, EDF R&D, OPEN CASCADE
3 // Copyright (C) 2003-2007 OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
4 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
6 // This library is free software; you can redistribute it and/or
7 // modify it under the terms of the GNU Lesser General Public
8 // License as published by the Free Software Foundation; either
9 // version 2.1 of the License.
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // Lesser General Public License for more details.
16 // You should have received a copy of the GNU Lesser General Public
17 // License along with this library; if not, write to the Free Software
18 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
22 // File : SUIT_TreeSync.h
23 // Author : Alexander SOLOVYOV
25 #ifndef SUIT_TREESYNC_H
26 #define SUIT_TREESYNC_H
31 \brief The structure representing difference between source and destination items.
33 The different combinations of source and target items values imply the different actions
34 to be performed in the target data tree:
35 - source item is null, target item is not null : the item should be removed from the target tree
36 - source item is not null, target item is null : new item should be added to the target tree
37 - both source and target items are not null : the target item can be updated if necessary
38 - both source and target items are null : error
40 template <class SrcItem, class TrgItem>
43 SrcItem mySrc; //!< source tree item
44 TrgItem myTrg; //!< target tree item
49 // Function prototypes.
52 template <class SrcItem, class TrgItem, class TreeData>
53 TrgItem synchronize( const SrcItem&, const TrgItem&, const TreeData& );
55 template <class SrcItem, class TrgItem, class TreeData>
56 QList< DiffItem<SrcItem,TrgItem> > diffSiblings( const SrcItem&,
60 template <class SrcItem, class TrgItem, class TreeData>
61 TrgItem createSubTree( const SrcItem&, const TrgItem&, const TrgItem&, const TreeData& );
63 template <class SrcItem, class TrgItem, class TreeData>
64 const typename QList<TrgItem>::const_iterator findEqual( const SrcItem& it,
65 const typename QList<TrgItem>::const_iterator& first,
66 const typename QList<TrgItem>::const_iterator& last,
71 // Function imlpementation.
75 \brief Synchronize two data trees by recurive comparing of the corresponding items.
77 \param r1 starting item from the source data tree
78 \param r2 starting item from the target data tree
79 \param td functor class
80 \return the target tree item (updated or just created) corresponding to the starting
83 Actual comparing of the items and the syncronization of the trees is performed by the
84 functor class which is passed as the last parameter of the function.
85 The functor class should implement the following methods:
86 - \b bool \b isEqual( \b const \b SrcItem& \p src, \b const \b TrgItem& \p tgt ) \b const;
87 - \a src source tree item
88 - \a tgt target tree item
89 - compares items and returns \c true if the items are equal (correspond to each other)
90 - \b SrcItem \b nullSrc() \b const;
91 - returns null source tree itemm
92 - \b TrgItem \b nullTrg() \b const
93 - returns null target tree item
94 - \b TrgItem \b createItem( \b const \b SrcItem& \p src, \b const \b TrgItem& \p parent, \b const \b TrgItem& \p after ) \b const;
96 - \a parent parent target item
97 - \a after target tree item after which new item shoud be inserted (if null, the item is added to the end)
98 - creates new ite in the target tree which correspond to the source item and returns created item
99 - \b void \b updateItem( \b const \b SrcItem& \p src, \b const \b TrgItem& \p tgt ) \b const;
100 - \a src source tree item
101 - \a tgt the item in the target tree to be updated
102 - updates target treeitem
103 - \b void \b deleteItemWithChildren( \b const \b TrgItem& \p tgt ) \b const;
104 - \a tgt the item in the target tree to be removed
105 - deletes target tree item (recursively)
106 - \b QList<SrcItem> \b children( \b const \b SrcItem& \p parent ) \b const;
107 - \a parent the parent item in the source tree
108 - returns the child items list
109 - \b QList<TrgItem> \b children( \b const \b TrgItem& \p parent ) \b const;
110 - \a parent the parent item in the target tree
111 - returns the child items list
112 - \b TrgItem \b parent( \b const \b TrgItem& \p tgt ) \b const;
113 - \a tgt target tree item
114 - returns the item which is parent for the specified source tree item
116 template <class SrcItem, class TrgItem, class TreeData>
117 TrgItem synchronize( const SrcItem& r1, const TrgItem& r2, const TreeData& td )
119 if ( td.isEqual( r1, r2 ) ) {
120 // update items themselves
121 td.updateItem( r1, r2 );
123 // iterate through children
124 QList< DiffItem< SrcItem, TrgItem > > d = diffSiblings( r1, r2, td );
126 typename QList< DiffItem< SrcItem, TrgItem > >::const_iterator anIt = d.begin(), aLast = d.end();
127 TrgItem lastItem = td.nullTrg();
129 for ( ; anIt != aLast; anIt++ ) {
130 const DiffItem<SrcItem,TrgItem>& item = *anIt;
131 if ( item.mySrc == td.nullSrc() ) {
132 if ( item.myTrg == td.nullTrg() )
133 qDebug( "error: both null" );
136 td.deleteItemWithChildren( item.myTrg );
139 if ( item.myTrg == td.nullTrg() ) {
140 // add item (recursively)
141 TrgItem nitem = createSubTree( item.mySrc, r2, lastItem, td );
142 if ( nitem != td.nullTrg() )
147 synchronize( item.mySrc, item.myTrg, td );
148 lastItem = item.myTrg;
155 TrgItem new_r2 = td.nullTrg();
156 if ( r1 != td.nullSrc() ) {
157 // add new item (recursively)
158 new_r2 = createSubTree( r1, td.parent( r2 ), r2, td );
160 if ( r2 != td.nullTrg() ) {
161 // delete old one (if it is not null)
162 td.deleteItemWithChildren( r2 );
169 \brief Find the item in the target tree which correspond to the specified source tree item.
170 \param it source item for which correspondence is to be found
171 \param first iterator pointing to the item in the list \a l from which search shoud be started
172 \param last iterator pointing to the item in the list \a l the search to be finished at
173 \param td functor class
174 \return iterator pointing to the item in the list \l if the correspondence is found or iterator
175 \a last if the correspondence is not found
178 template <class SrcItem, class TrgItem, class TreeData>
179 const typename QList<TrgItem>::const_iterator findEqual( const SrcItem& it,
180 const typename QList<TrgItem>::const_iterator& first,
181 const typename QList<TrgItem>::const_iterator& last,
184 typename QList<TrgItem>::const_iterator cur = first;
185 for ( ; cur != last; cur++ ) {
186 if ( td.isEqual( it, *cur ) )
193 \brief Compare children of the source and target trees to find differences.
194 \param src parent source item
195 \param trg parent target item
196 \param td functor class
197 \return list of the differences
200 template <class SrcItem, class TrgItem, class TreeData>
201 QList< DiffItem<SrcItem,TrgItem> > diffSiblings( const SrcItem& src, const TrgItem& trg,
204 //if( src==td.nullSrc() || trg==td.nullTrg() )
207 QList< DiffItem<SrcItem,TrgItem> > d;
209 QList<SrcItem> src_ch = td.children( src );
210 QList<TrgItem> trg_ch = td.children( trg );
212 typename QList<SrcItem>::const_iterator src_it = src_ch.begin(), src_last = src_ch.end();
213 typename QList<TrgItem>::const_iterator cur = trg_ch.begin(), trg_last = trg_ch.end();
215 for ( ; src_it != src_last; src_it++ ) {
216 typename QList<TrgItem>::const_iterator f =
217 findEqual<SrcItem, TrgItem, TreeData>( *src_it, cur, trg_last, td );
218 if ( f != trg_last ) {
220 // mark all items before found one as "to be deleted"
221 for ( typename QList<TrgItem>::const_iterator it = cur; it != f; it++ ) {
222 DiffItem<SrcItem,TrgItem> ndiff;
223 ndiff.mySrc = td.nullSrc();
224 ndiff.myTrg = *it; // delete item
228 DiffItem<SrcItem,TrgItem> ndiff;
229 ndiff.mySrc = *src_it;
230 ndiff.myTrg = *cur; // update this (found) item
235 // target is not found
236 DiffItem<SrcItem,TrgItem> ndiff;
237 ndiff.mySrc = *src_it;
238 ndiff.myTrg = td.nullTrg(); // add item
243 for ( ; cur != trg_last; cur++ ) {
244 DiffItem<SrcItem,TrgItem> ndiff;
245 ndiff.mySrc = td.nullSrc();
246 ndiff.myTrg = *cur; // delete item
254 \brief Create an item with all its children recursively in the target tree.
255 \param src source tree item
256 \param parent parent item in the target tree
257 \param after item in the target tree after which new item shoud be inserted
258 \param td functor class
262 template <class SrcItem, class TrgItem, class TreeData>
263 TrgItem createSubTree( const SrcItem& src, const TrgItem& parent,
264 const TrgItem& after, const TreeData& td )
266 if ( src == td.nullSrc() )
269 TrgItem nitem = td.createItem( src, parent, after );
270 if ( nitem == td.nullTrg() )
273 QList<SrcItem> ch = td.children( src );
274 typename QList<SrcItem>::const_iterator anIt = ch.begin(), aLast = ch.end();
275 TrgItem last = td.nullTrg();
276 for( ; anIt != aLast; anIt++ )
277 last = createSubTree( *anIt, nitem, last, td );
282 #endif // SUIT_TREESYNC_H