1 // Copyright (C) 2007-2021 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, or (at your option) any later version.
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
23 // File : SUIT_TreeSync.h
24 // Author : Alexander SOLOVYOV
26 #ifndef SUIT_TREESYNC_H
27 #define SUIT_TREESYNC_H
32 \brief The structure representing difference between source and destination items.
34 The different combinations of source and target items values imply the different actions
35 to be performed in the target data tree:
36 - source item is null, target item is not null : the item should be removed from the target tree
37 - source item is not null, target item is null : new item should be added to the target tree
38 - both source and target items are not null : the target item can be updated if necessary
39 - both source and target items are null : error
41 template <class SrcItem, class TrgItem>
44 SrcItem mySrc; //!< source tree item
45 TrgItem myTrg; //!< target tree item
50 // Function prototypes.
53 template <class SrcItem, class TrgItem, class TreeData>
54 TrgItem synchronize( const SrcItem&, const TrgItem&, const TreeData& );
56 template <class SrcItem, class TrgItem, class TreeData>
57 QList< DiffItem<SrcItem,TrgItem> > diffSiblings( const SrcItem&,
61 template <class SrcItem, class TrgItem, class TreeData>
62 TrgItem createSubTree( const SrcItem&, const TrgItem&, const TrgItem&, const TreeData& );
64 template <class SrcItem, class TrgItem, class TreeData>
65 const typename QList<TrgItem>::const_iterator findEqual( const SrcItem& it,
66 const typename QList<TrgItem>::const_iterator& first,
67 const typename QList<TrgItem>::const_iterator& last,
72 // Function imlpementation.
76 \brief Synchronize two data trees by recurive comparing of the corresponding items.
78 \param r1 starting item from the source data tree
79 \param r2 starting item from the target data tree
80 \param td functor class
81 \return the target tree item (updated or just created) corresponding to the starting
84 Actual comparing of the items and the syncronization of the trees is performed by the
85 functor class which is passed as the last parameter of the function.
86 The functor class should implement the following methods:
87 - \b bool \b isEqual( \b const \b SrcItem& \p src, \b const \b TrgItem& \p tgt ) \b const;
88 - \a src source tree item
89 - \a tgt target tree item
90 - compares items and returns \c true if the items are equal (correspond to each other)
91 - \b SrcItem \b nullSrc() \b const;
92 - returns null source tree itemm
93 - \b TrgItem \b nullTrg() \b const
94 - returns null target tree item
95 - \b TrgItem \b createItem( \b const \b SrcItem& \p src, \b const \b TrgItem& \p parent, \b const \b TrgItem& \p after ) \b const;
97 - \a parent parent target item
98 - \a after target tree item after which new item shoud be inserted (if null, the item is added to the end)
99 - creates new ite in the target tree which correspond to the source item and returns created item
100 - \b void \b updateItem( \b const \b SrcItem& \p src, \b const \b TrgItem& \p tgt ) \b const;
101 - \a src source tree item
102 - \a tgt the item in the target tree to be updated
103 - updates target treeitem
104 - \b void \b deleteItemWithChildren( \b const \b TrgItem& \p tgt ) \b const;
105 - \a tgt the item in the target tree to be removed
106 - deletes target tree item (recursively)
107 - \b QList<SrcItem> \b children( \b const \b SrcItem& \p parent ) \b const;
108 - \a parent the parent item in the source tree
109 - returns the child items list
110 - \b QList<TrgItem> \b children( \b const \b TrgItem& \p parent ) \b const;
111 - \a parent the parent item in the target tree
112 - returns the child items list
113 - \b TrgItem \b parent( \b const \b TrgItem& \p tgt ) \b const;
114 - \a tgt target tree item
115 - returns the item which is parent for the specified source tree item
117 template <class SrcItem, class TrgItem, class TreeData>
118 TrgItem synchronize( const SrcItem& r1, const TrgItem& r2, const TreeData& td )
120 if ( td.isEqual( r1, r2 ) ) {
121 // update items themselves
122 td.updateItem( r1, r2 );
124 // iterate through children
125 QList< DiffItem< SrcItem, TrgItem > > d = diffSiblings( r1, r2, td );
127 typename QList< DiffItem< SrcItem, TrgItem > >::const_iterator anIt = d.begin(), aLast = d.end();
128 TrgItem lastItem = td.nullTrg();
130 for ( ; anIt != aLast; anIt++ ) {
131 const DiffItem<SrcItem,TrgItem>& item = *anIt;
132 if ( item.mySrc == td.nullSrc() ) {
133 if ( item.myTrg == td.nullTrg() )
136 qDebug( "error: both null" );
141 td.deleteItemWithChildren( item.myTrg );
144 if ( item.myTrg == td.nullTrg() ) {
145 // add item (recursively)
146 TrgItem nitem = createSubTree( item.mySrc, r2, lastItem, td );
147 if ( nitem != td.nullTrg() )
152 synchronize( item.mySrc, item.myTrg, td );
153 lastItem = item.myTrg;
160 TrgItem new_r2 = td.nullTrg();
161 if ( r1 != td.nullSrc() ) {
162 // add new item (recursively)
163 new_r2 = createSubTree( r1, td.parent( r2 ), r2, td );
165 if ( r2 != td.nullTrg() ) {
166 // delete old one (if it is not null)
167 td.deleteItemWithChildren( r2 );
174 \brief Find the item in the target tree which correspond to the specified source tree item.
175 \param it source item for which correspondence is to be found
176 \param first iterator pointing to the item in the list \a l from which search shoud be started
177 \param last iterator pointing to the item in the list \a l the search to be finished at
178 \param td functor class
179 \return iterator pointing to the item in the list \l if the correspondence is found or iterator
180 \a last if the correspondence is not found
183 template <class SrcItem, class TrgItem, class TreeData>
184 const typename QList<TrgItem>::const_iterator findEqual( const SrcItem& it,
185 const typename QList<TrgItem>::const_iterator& first,
186 const typename QList<TrgItem>::const_iterator& last,
189 typename QList<TrgItem>::const_iterator cur = first;
190 for ( ; cur != last; cur++ ) {
191 if ( td.isEqual( it, *cur ) )
198 \brief Compare children of the source and target trees to find differences.
199 \param src parent source item
200 \param trg parent target item
201 \param td functor class
202 \return list of the differences
205 template <class SrcItem, class TrgItem, class TreeData>
206 QList< DiffItem<SrcItem,TrgItem> > diffSiblings( const SrcItem& src, const TrgItem& trg,
209 //if( src==td.nullSrc() || trg==td.nullTrg() )
212 QList< DiffItem<SrcItem,TrgItem> > d;
214 QList<SrcItem> src_ch = td.children( src );
215 QList<TrgItem> trg_ch = td.children( trg );
217 typename QList<SrcItem>::const_iterator src_it = src_ch.begin(), src_last = src_ch.end();
218 typename QList<TrgItem>::const_iterator cur = trg_ch.begin(), trg_last = trg_ch.end();
220 for ( ; src_it != src_last; src_it++ ) {
221 typename QList<TrgItem>::const_iterator f =
222 findEqual<SrcItem, TrgItem, TreeData>( *src_it, cur, trg_last, td );
223 if ( f != trg_last ) {
225 // mark all items before found one as "to be deleted"
226 for ( typename QList<TrgItem>::const_iterator it = cur; it != f; it++ ) {
227 DiffItem<SrcItem,TrgItem> ndiff;
228 ndiff.mySrc = td.nullSrc();
229 ndiff.myTrg = *it; // delete item
233 DiffItem<SrcItem,TrgItem> ndiff;
234 ndiff.mySrc = *src_it;
235 ndiff.myTrg = *cur; // update this (found) item
240 // target is not found
241 DiffItem<SrcItem,TrgItem> ndiff;
242 ndiff.mySrc = *src_it;
243 ndiff.myTrg = td.nullTrg(); // add item
248 for ( ; cur != trg_last; cur++ ) {
249 DiffItem<SrcItem,TrgItem> ndiff;
250 ndiff.mySrc = td.nullSrc();
251 ndiff.myTrg = *cur; // delete item
259 \brief Create an item with all its children recursively in the target tree.
260 \param src source tree item
261 \param parent parent item in the target tree
262 \param after item in the target tree after which new item shoud be inserted
263 \param td functor class
267 template <class SrcItem, class TrgItem, class TreeData>
268 TrgItem createSubTree( const SrcItem& src, const TrgItem& parent,
269 const TrgItem& after, const TreeData& td )
271 if ( src == td.nullSrc() )
274 TrgItem nitem = td.createItem( src, parent, after );
275 if ( nitem == td.nullTrg() )
278 QList<SrcItem> ch = td.children( src );
279 typename QList<SrcItem>::const_iterator anIt = ch.begin(), aLast = ch.end();
280 TrgItem last = td.nullTrg();
281 for( ; anIt != aLast; anIt++ )
282 last = createSubTree( *anIt, nitem, last, td );
287 #endif // SUIT_TREESYNC_H