src/SUIT/SUIT_TreeSync.h

   1
   2 #ifndef SUIT_TREE_SYNC_HEADER
   3 #define SUIT_TREE_SYNC_HEADER
   4
   5 #include <qptrlist.h>
   6 #include <qvaluelist.h>
   7
   8 template <class SrcItem, class TrgItem>
   9 struct DiffItem
  10 {
  11   SrcItem  mySrc;  //if it is null, then this item is to deleted
  12   TrgItem  myTrg;  //if it is null, then this item is to added
  13   //if both fields aren't null, then this item is to update
  14 };
  15
  16 template <class SrcItem, class TrgItem, class TreeData>
  17 TrgItem synchronize( const SrcItem&, const TrgItem&, const TreeData& );
  18
  19 template <class SrcItem, class TrgItem, class TreeData>
  20 void diffSiblings( const SrcItem&, const TrgItem&,
  21                    QValueList < DiffItem < SrcItem,TrgItem > >&,
  22                    const TreeData& );
  23
  24 template <class SrcItem, class TrgItem, class TreeData>
  25 TrgItem createSubTree( const SrcItem&, const TrgItem&, const TrgItem&, const bool, const TreeData& );
  26
  27 template <class SrcItem, class TrgItem, class TreeData>
  28 const typename QValueList<TrgItem>::const_iterator findEqual( const QValueList<TrgItem>& l,
  29                                                               const typename QValueList<TrgItem>::const_iterator& first,
  30                                                               const SrcItem& it,
  31                                                               const TreeData& td );
  32
  33
  34
  35
  36
  37 //int gSync = 0;
  38 template <class SrcItem, class TrgItem, class TreeData>
  39 TrgItem synchronize( const SrcItem& r1, const TrgItem& r2, const TreeData& td )
  40 {
  41   //  printf( "--- synchronize : %d ---\n", ++gSync );
  42
  43   if( td.isEqual( r1, r2 ) )
  44   {
  45     QValueList< DiffItem< SrcItem, TrgItem > > d;
  46     diffSiblings( r1, r2, d, td );
  47
  48     typename QValueList< DiffItem< SrcItem, TrgItem > >::const_iterator anIt = d.begin(), aLast = d.end();
  49     bool isFirst = true;
  50     TrgItem lastItem = td.nullTrg();
  51     //    TrgItem tail = td.nullTrg();
  52     for( ; anIt!=aLast; anIt++ )
  53     {
  54       const DiffItem<SrcItem,TrgItem>& item = *anIt;
  55       if( item.mySrc==td.nullSrc() )
  56         if( item.myTrg==td.nullTrg() )
  57           qDebug( "error: both null" );
  58         else
  59           //to delete
  60           td.deleteItemWithChildren( item.myTrg );
  61       else {
  62         if( item.myTrg==td.nullTrg() )
  63         {
  64           //to add
  65           lastItem = createSubTree( item.mySrc, r2, lastItem, isFirst, td );
  66         }
  67         else
  68         {
  69           //to update
  70           td.updateItem( item.myTrg );
  71           synchronize( item.mySrc, item.myTrg, td );
  72           lastItem = item.myTrg;
  73         }
  74         isFirst = false;
  75       }
  76     }
  77
  78     return r2;
  79   }
  80   else
  81   {
  82     TrgItem new_r2 = createSubTree( r1, td.parent( r2 ), r2, false, td );
  83     if( r2!=td.nullTrg() )
  84       td.deleteItemWithChildren( r2 );
  85     return new_r2;
  86   }
  87 }
  88
  89 template <class SrcItem, class TrgItem, class TreeData>
  90 const typename QValueList<TrgItem>::const_iterator findEqual( const QValueList<TrgItem>& l,
  91                                                               const typename QValueList<TrgItem>::const_iterator& first,
  92                                                               const SrcItem& it,
  93                                                               const TreeData& td )
  94 {
  95   typename QValueList<TrgItem>::const_iterator cur = first, last = l.end();
  96   for( ; cur!=last; cur++ )
  97     if( td.isEqual( it, *cur ) )
  98       return cur;
  99   return last;
 100 }
 101
 102 template <class SrcItem, class TrgItem, class TreeData>
 103 void diffSiblings( const SrcItem& src, const TrgItem& trg,
 104                    QValueList < DiffItem < SrcItem,TrgItem > >& d,
 105                    const TreeData& td )
 106 {
 107   if( src==td.nullSrc() || trg==td.nullTrg() )
 108     return;
 109
 110   QValueList<SrcItem> src_ch;
 111   QValueList<TrgItem> trg_ch;
 112   td.children( src, src_ch );
 113   td.children( trg, trg_ch );
 114
 115   typename QValueList<SrcItem>::const_iterator src_it = src_ch.begin(), src_last = src_ch.end();
 116   typename QValueList<TrgItem>::const_iterator cur = trg_ch.begin(), trg_last = trg_ch.end();
 117
 118   for( ; src_it!=src_last; src_it++ )
 119   {
 120     typename QValueList<TrgItem>::const_iterator f =
 121       findEqual<SrcItem, TrgItem, TreeData>( trg_ch, cur, *src_it, td );
 122     if( f!=trg_last )  //is found
 123     {
 124       //mark all items before found as "to be deleted"
 125       for( typename QValueList<TrgItem>::const_iterator it = cur; it!=f; it++ )
 126       {
 127         DiffItem<SrcItem,TrgItem> ndiff;
 128         ndiff.mySrc = td.nullSrc();
 129         ndiff.myTrg = *it; //to delete;
 130         d.append( ndiff );
 131       }
 132       cur = f;
 133       DiffItem<SrcItem,TrgItem> ndiff;
 134       ndiff.mySrc = *src_it;
 135       ndiff.myTrg = *cur; //update this item
 136       d.append( ndiff );
 137       cur++;
 138     }
 139     else //not found
 140     {
 141       DiffItem<SrcItem,TrgItem> ndiff;
 142       ndiff.mySrc = *src_it;
 143       ndiff.myTrg = td.nullTrg(); //add this item
 144       d.append( ndiff );
 145     }
 146   }
 147   for( ; cur!=trg_last; cur++ )
 148   {
 149     DiffItem<SrcItem,TrgItem> ndiff;
 150     ndiff.mySrc = td.nullSrc();
 151     ndiff.myTrg = *cur; //to delete;
 152     d.append( ndiff );
 153   }
 154 }
 155
 156 template <class SrcItem, class TrgItem, class TreeData>
 157 TrgItem createSubTree( const SrcItem& src, const TrgItem& parent,
 158                        const TrgItem& after, const bool asFirst,
 159                        const TreeData& td )
 160 {
 161   if( src==td.nullSrc() )
 162     return td.nullTrg();
 163
 164   TrgItem nitem = td.createItem( src, parent, after, asFirst );
 165   if( nitem==td.nullTrg() )
 166     return nitem;
 167
 168   QValueList<SrcItem> ch;
 169   td.children( src, ch );
 170   typename QValueList<SrcItem>::const_iterator anIt = ch.begin(), aLast = ch.end();
 171   for( ; anIt!=aLast; anIt++ )
 172     createSubTree( *anIt, nitem, td.nullTrg(), false, td );
 173
 174   return nitem;
 175 }
 176
 177 #endif