src/SUIT/SUIT_TreeSync.h

   1 //  Copyright (C) 2007-2008  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.
  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 // File   : SUIT_TreeSync.h
  23 // Author : Alexander SOLOVYOV
  24 //
  25 #ifndef SUIT_TREESYNC_H
  26 #define SUIT_TREESYNC_H
  27
  28 #include <QList>
  29
  30 /*!
  31   \brief The structure representing difference between source and destination items.
  32
  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
  39 */
  40 template <class SrcItem, class TrgItem>
  41 struct DiffItem
  42 {
  43   SrcItem  mySrc;      //!< source tree item
  44   TrgItem  myTrg;      //!< target tree item
  45 };
  46
  47
  48 //
  49 // Function prototypes.
  50 //
  51
  52 template <class SrcItem, class TrgItem, class TreeData>
  53 TrgItem synchronize( const SrcItem&, const TrgItem&, const TreeData& );
  54
  55 template <class SrcItem, class TrgItem, class TreeData>
  56 QList< DiffItem<SrcItem,TrgItem> > diffSiblings( const SrcItem&,
  57                                                  const TrgItem&,
  58                                                  const TreeData& );
  59
  60 template <class SrcItem, class TrgItem, class TreeData>
  61 TrgItem createSubTree( const SrcItem&, const TrgItem&, const TrgItem&, const TreeData& );
  62
  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,
  67                                                          const TreeData& td );
  68
  69
  70 //
  71 // Function imlpementation.
  72 //
  73
  74 /*!
  75   \brief Synchronize two data trees by recurive comparing of the corresponding items.
  76
  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
  81      data object
  82
  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;
  95     - \a src source item
  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
 115 */
 116 template <class SrcItem, class TrgItem, class TreeData>
 117 TrgItem synchronize( const SrcItem& r1, const TrgItem& r2, const TreeData& td )
 118 {
 119   if ( td.isEqual( r1, r2 ) ) {
 120     // update items themselves
 121     td.updateItem( r1, r2 );
 122
 123     // iterate through children
 124     QList< DiffItem< SrcItem, TrgItem > > d =  diffSiblings( r1, r2, td );
 125
 126     typename QList< DiffItem< SrcItem, TrgItem > >::const_iterator anIt = d.begin(), aLast = d.end();
 127     TrgItem lastItem = td.nullTrg();
 128
 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" );
 134         else
 135           // delete item
 136           td.deleteItemWithChildren( item.myTrg );
 137       }
 138       else {
 139         if ( item.myTrg == td.nullTrg() ) {
 140           // add item (recursively)
 141           TrgItem nitem = createSubTree( item.mySrc, r2, lastItem, td );
 142           if ( nitem != td.nullTrg() )
 143             lastItem = nitem;
 144         }
 145         else {
 146           // update item
 147           synchronize( item.mySrc, item.myTrg, td );
 148           lastItem = item.myTrg;
 149         }
 150       }
 151     }
 152     return r2;
 153   }
 154   else {
 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 );
 159     }
 160     if ( r2 != td.nullTrg() ) {
 161       // delete old one (if it is not null)
 162       td.deleteItemWithChildren( r2 );
 163     }
 164     return new_r2;
 165   }
 166 }
 167
 168 /*!
 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
 176   \sa synchronize()
 177 */
 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,
 182                                                          const TreeData& td )
 183 {
 184   typename QList<TrgItem>::const_iterator cur = first;
 185   for ( ; cur != last; cur++ ) {
 186     if ( td.isEqual( it, *cur ) )
 187       return cur;
 188   }
 189   return last;
 190 }
 191
 192 /*!
 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
 198   \sa synchronize()
 199 */
 200 template <class SrcItem, class TrgItem, class TreeData>
 201 QList< DiffItem<SrcItem,TrgItem> > diffSiblings( const SrcItem& src, const TrgItem& trg,
 202                                                  const TreeData& td )
 203 {
 204   //if( src==td.nullSrc() || trg==td.nullTrg() )
 205   //  return;
 206
 207   QList< DiffItem<SrcItem,TrgItem> > d;
 208
 209   QList<SrcItem> src_ch = td.children( src );
 210   QList<TrgItem> trg_ch = td.children( trg );
 211
 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();
 214
 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 )  {
 219       // target is found
 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
 225         d.append( ndiff );
 226       }
 227       cur = f;
 228       DiffItem<SrcItem,TrgItem> ndiff;
 229       ndiff.mySrc = *src_it;
 230       ndiff.myTrg = *cur;         // update this (found) item
 231       d.append( ndiff );
 232       cur++;
 233     }
 234     else {
 235       // target is not found
 236       DiffItem<SrcItem,TrgItem> ndiff;
 237       ndiff.mySrc = *src_it;
 238       ndiff.myTrg = td.nullTrg(); // add item
 239       d.append( ndiff );
 240     }
 241   }
 242   // delete rest items
 243   for ( ; cur != trg_last; cur++ ) {
 244     DiffItem<SrcItem,TrgItem> ndiff;
 245     ndiff.mySrc = td.nullSrc();
 246     ndiff.myTrg = *cur;           // delete item
 247     d.append( ndiff );
 248   }
 249
 250   return d;
 251 }
 252
 253 /*!
 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
 259   \return created item
 260   \sa synchronize()
 261 */
 262 template <class SrcItem, class TrgItem, class TreeData>
 263 TrgItem createSubTree( const SrcItem& src, const TrgItem& parent,
 264                        const TrgItem& after, const TreeData& td )
 265 {
 266   if ( src == td.nullSrc() )
 267     return td.nullTrg();
 268
 269   TrgItem nitem = td.createItem( src, parent, after );
 270   if ( nitem == td.nullTrg() )
 271     return nitem;
 272
 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 );
 278
 279   return nitem;
 280 }
 281
 282 #endif // SUIT_TREESYNC_H