src/SUIT/SUIT_TreeSync.h

   1 // Copyright (C) 2007-2023  CEA/DEN, EDF R&D, OPEN CASCADE
   2 //
   3 // Copyright (C) 2003-2007  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
   4 // CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
   5 //
   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.
  10 //
  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.
  15 //
  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
  19 //
  20 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  21 //
  22
  23 // File   : SUIT_TreeSync.h
  24 // Author : Alexander SOLOVYOV
  25 //
  26 #ifndef SUIT_TREESYNC_H
  27 #define SUIT_TREESYNC_H
  28
  29 #include <QList>
  30
  31 /*!
  32   \brief The structure representing difference between source and destination items.
  33
  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
  40 */
  41 template <class SrcItem, class TrgItem>
  42 struct DiffItem
  43 {
  44   SrcItem  mySrc;      //!< source tree item
  45   TrgItem  myTrg;      //!< target tree item
  46 };
  47
  48
  49 //
  50 // Function prototypes.
  51 //
  52
  53 template <class SrcItem, class TrgItem, class TreeData>
  54 TrgItem synchronize( const SrcItem&, const TrgItem&, const TreeData& );
  55
  56 template <class SrcItem, class TrgItem, class TreeData>
  57 QList< DiffItem<SrcItem,TrgItem> > diffSiblings( const SrcItem&,
  58                                                  const TrgItem&,
  59                                                  const TreeData& );
  60
  61 template <class SrcItem, class TrgItem, class TreeData>
  62 TrgItem createSubTree( const SrcItem&, const TrgItem&, const TrgItem&, const TreeData& );
  63
  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,
  68                                                          const TreeData& td );
  69
  70
  71 //
  72 // Function imlpementation.
  73 //
  74
  75 /*!
  76   \brief Synchronize two data trees by recurive comparing of the corresponding items.
  77
  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
  82      data object
  83
  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;
  96     - \a src source item
  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
 116 */
 117 template <class SrcItem, class TrgItem, class TreeData>
 118 TrgItem synchronize( const SrcItem& r1, const TrgItem& r2, const TreeData& td )
 119 {
 120   if ( td.isEqual( r1, r2 ) ) {
 121     // update items themselves
 122     td.updateItem( r1, r2 );
 123
 124     // iterate through children
 125     QList< DiffItem< SrcItem, TrgItem > > d =  diffSiblings( r1, r2, td );
 126
 127     typename QList< DiffItem< SrcItem, TrgItem > >::const_iterator anIt = d.begin(), aLast = d.end();
 128     TrgItem lastItem = td.nullTrg();
 129
 130     for ( ; anIt != aLast; anIt++ ) {
 131       const DiffItem<SrcItem,TrgItem>& item = *anIt;
 132       if ( item.mySrc == td.nullSrc() ) {
 133         if ( item.myTrg == td.nullTrg() )
 134         {
 135 #ifdef _DEBUG_
 136           qDebug( "error: both null" );
 137 #endif
 138         }
 139         else
 140           // delete item
 141           td.deleteItemWithChildren( item.myTrg );
 142       }
 143       else {
 144         if ( item.myTrg == td.nullTrg() ) {
 145           // add item (recursively)
 146           TrgItem nitem = createSubTree( item.mySrc, r2, lastItem, td );
 147           if ( nitem != td.nullTrg() )
 148             lastItem = nitem;
 149         }
 150         else {
 151           // update item
 152           synchronize( item.mySrc, item.myTrg, td );
 153           lastItem = item.myTrg;
 154         }
 155       }
 156     }
 157     return r2;
 158   }
 159   else {
 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 );
 164     }
 165     if ( r2 != td.nullTrg() ) {
 166       // delete old one (if it is not null)
 167       td.deleteItemWithChildren( r2 );
 168     }
 169     return new_r2;
 170   }
 171 }
 172
 173 /*!
 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
 181   \sa synchronize()
 182 */
 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,
 187                                                          const TreeData& td )
 188 {
 189   typename QList<TrgItem>::const_iterator cur = first;
 190   for ( ; cur != last; cur++ ) {
 191     if ( td.isEqual( it, *cur ) )
 192       return cur;
 193   }
 194   return last;
 195 }
 196
 197 /*!
 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
 203   \sa synchronize()
 204 */
 205 template <class SrcItem, class TrgItem, class TreeData>
 206 QList< DiffItem<SrcItem,TrgItem> > diffSiblings( const SrcItem& src, const TrgItem& trg,
 207                                                  const TreeData& td )
 208 {
 209   //if( src==td.nullSrc() || trg==td.nullTrg() )
 210   //  return;
 211
 212   QList< DiffItem<SrcItem,TrgItem> > d;
 213
 214   QList<SrcItem> src_ch = td.children( src );
 215   QList<TrgItem> trg_ch = td.children( trg );
 216
 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();
 219
 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 )  {
 224       // target is found
 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
 230         d.append( ndiff );
 231       }
 232       cur = f;
 233       DiffItem<SrcItem,TrgItem> ndiff;
 234       ndiff.mySrc = *src_it;
 235       ndiff.myTrg = *cur;         // update this (found) item
 236       d.append( ndiff );
 237       cur++;
 238     }
 239     else {
 240       // target is not found
 241       DiffItem<SrcItem,TrgItem> ndiff;
 242       ndiff.mySrc = *src_it;
 243       ndiff.myTrg = td.nullTrg(); // add item
 244       d.append( ndiff );
 245     }
 246   }
 247   // delete rest items
 248   for ( ; cur != trg_last; cur++ ) {
 249     DiffItem<SrcItem,TrgItem> ndiff;
 250     ndiff.mySrc = td.nullSrc();
 251     ndiff.myTrg = *cur;           // delete item
 252     d.append( ndiff );
 253   }
 254
 255   return d;
 256 }
 257
 258 /*!
 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
 264   \return created item
 265   \sa synchronize()
 266 */
 267 template <class SrcItem, class TrgItem, class TreeData>
 268 TrgItem createSubTree( const SrcItem& src, const TrgItem& parent,
 269                        const TrgItem& after, const TreeData& td )
 270 {
 271   if ( src == td.nullSrc() )
 272     return td.nullTrg();
 273
 274   TrgItem nitem = td.createItem( src, parent, after );
 275   if ( nitem == td.nullTrg() )
 276     return nitem;
 277
 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 );
 283
 284   return nitem;
 285 }
 286
 287 #endif // SUIT_TREESYNC_H