src/SUIT/SUIT_TreeSync.h

   1 // Copyright (C) 2005  CEA/DEN, EDF R&D, OPEN CASCADE, PRINCIPIA R&D
   2 //
   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.
   7 //
   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.
  12 //
  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
  16 //
  17 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  18 //
  19
  20 #ifndef SUIT_TREE_SYNC_HEADER
  21 #define SUIT_TREE_SYNC_HEADER
  22
  23 #include <qptrlist.h>
  24 #include <qvaluelist.h>
  25
  26 /*!
  27   \struct DiffItem
  28   \brief Struct representing difference between items
  29 */
  30 template <class SrcItem, class TrgItem>
  31 struct DiffItem
  32 {
  33   SrcItem  mySrc;
  34   /*!
  35     \var mySrc
  36     if it is null, then this item is to deleted
  37   */
  38   TrgItem  myTrg;
  39   /*!
  40     \var myTrg
  41     if it is null, then this item is to added
  42     if both fields aren't null, then this item is to update
  43   */
  44 };
  45
  46 /*!
  47   \brief synchronizes two trees
  48 */
  49 template <class SrcItem, class TrgItem, class TreeData>
  50 TrgItem synchronize( const SrcItem&, const TrgItem&, const TreeData& );
  51
  52 /*!
  53   \brief compares children
  54 */
  55 template <class SrcItem, class TrgItem, class TreeData>
  56 void diffSiblings( const SrcItem&, const TrgItem&,
  57                    QValueList < DiffItem < SrcItem,TrgItem > >&,
  58                    const TreeData& );
  59
  60 /*!
  61   \brief create item with children (subtree)
  62 */
  63 template <class SrcItem, class TrgItem, class TreeData>
  64 TrgItem createSubTree( const SrcItem&, const TrgItem&, const TrgItem&, const bool, const TreeData& );
  65
  66 /*!
  67   \brief find equal element in list
  68 */
  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,
  72                                                               const SrcItem& it,
  73                                                               const TreeData& td );
  74
  75
  76
  77
  78 /*!
  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:
  83   <ul>
  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(
  88     <ol>
  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
  93     </ol>
  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
 101   </ul>
 102 */
 103 template <class SrcItem, class TrgItem, class TreeData>
 104 TrgItem synchronize( const SrcItem& r1, const TrgItem& r2, const TreeData& td )
 105 {
 106   if( td.isEqual( r1, r2 ) )
 107   {
 108     // update items themselves
 109     td.updateItem( r1, r2 );
 110
 111     // iterate 'siblings' (direct children)
 112     QValueList< DiffItem< SrcItem, TrgItem > > d;
 113     diffSiblings( r1, r2, d, td );
 114
 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++ )
 119     {
 120       const DiffItem<SrcItem,TrgItem>& item = *anIt;
 121       if( item.mySrc==td.nullSrc() )
 122         if( item.myTrg==td.nullTrg() )
 123           qDebug( "error: both null" );
 124         else
 125           //to delete
 126           td.deleteItemWithChildren( item.myTrg );
 127       else {
 128         if( item.myTrg==td.nullTrg() )
 129         {
 130           //to add
 131           TrgItem nitem = createSubTree( item.mySrc, r2, lastItem, lastItem==td.nullTrg(), td );
 132           if( nitem!=td.nullTrg() )
 133             lastItem = nitem;
 134         }
 135         else
 136         {
 137           //to update
 138           td.updateItem( item.mySrc, item.myTrg );
 139           synchronize( item.mySrc, item.myTrg, td );
 140           lastItem = item.myTrg;
 141         }
 142       }
 143     }
 144
 145     return r2;
 146   }
 147   else
 148   {
 149     TrgItem new_r2 = createSubTree( r1, td.parent( r2 ), r2, false, td );
 150     if( r2!=td.nullTrg() )
 151       td.deleteItemWithChildren( r2 );
 152     return new_r2;
 153   }
 154 }
 155
 156 /*!
 157   Finds equal element in list
 158   \return iterator
 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)
 163 */
 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,
 167                                                               const SrcItem& it,
 168                                                               const TreeData& td )
 169 {
 170   typename QValueList<TrgItem>::const_iterator cur = first, last = l.end();
 171   for( ; cur!=last; cur++ )
 172     if( td.isEqual( it, *cur ) )
 173       return cur;
 174   return last;
 175 }
 176
 177 /*!
 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)
 183 */
 184 template <class SrcItem, class TrgItem, class TreeData>
 185 void diffSiblings( const SrcItem& src, const TrgItem& trg,
 186                    QValueList < DiffItem < SrcItem,TrgItem > >& d,
 187                    const TreeData& td )
 188 {
 189   //if( src==td.nullSrc() || trg==td.nullTrg() )
 190   //  return;
 191
 192   QValueList<SrcItem> src_ch;
 193   QValueList<TrgItem> trg_ch;
 194   td.children( src, src_ch );
 195   td.children( trg, trg_ch );
 196
 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();
 199
 200   for( ; src_it!=src_last; src_it++ )
 201   {
 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
 205     {
 206       //mark all items before found as "to be deleted"
 207       for( typename QValueList<TrgItem>::const_iterator it = cur; it!=f; it++ )
 208       {
 209         DiffItem<SrcItem,TrgItem> ndiff;
 210         ndiff.mySrc = td.nullSrc();
 211         ndiff.myTrg = *it; //to delete;
 212         d.append( ndiff );
 213       }
 214       cur = f;
 215       DiffItem<SrcItem,TrgItem> ndiff;
 216       ndiff.mySrc = *src_it;
 217       ndiff.myTrg = *cur; //update this item
 218       d.append( ndiff );
 219       cur++;
 220     }
 221     else //not found
 222     {
 223       DiffItem<SrcItem,TrgItem> ndiff;
 224       ndiff.mySrc = *src_it;
 225       ndiff.myTrg = td.nullTrg(); //add this item
 226       d.append( ndiff );
 227     }
 228   }
 229   for( ; cur!=trg_last; cur++ )
 230   {
 231     DiffItem<SrcItem,TrgItem> ndiff;
 232     ndiff.mySrc = td.nullSrc();
 233     ndiff.myTrg = *cur; //to delete;
 234     d.append( ndiff );
 235   }
 236 }
 237
 238 /*!
 239   Creates sub-tree
 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)
 246 */
 247 template <class SrcItem, class TrgItem, class TreeData>
 248 TrgItem createSubTree( const SrcItem& src, const TrgItem& parent,
 249                        const TrgItem& after, const bool asFirst,
 250                        const TreeData& td )
 251 {
 252   if( src==td.nullSrc() )
 253     return td.nullTrg();
 254
 255   TrgItem nitem = td.createItem( src, parent, after, asFirst );
 256   if( nitem==td.nullTrg() )
 257     return nitem;
 258
 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 );
 264
 265   return nitem;
 266 }
 267
 268 #endif