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   if( td.isEqual( r1, r2 ) )
  42   {
  43     // update items themselves
  44     td.updateItem( r2 );
  45
  46     // iterate 'siblings' (direct children)
  47     QValueList< DiffItem< SrcItem, TrgItem > > d;
  48     diffSiblings( r1, r2, d, td );
  49
  50     typename QValueList< DiffItem< SrcItem, TrgItem > >::const_iterator anIt = d.begin(), aLast = d.end();
  51     bool isFirst = true;
  52     TrgItem lastItem = td.nullTrg();
  53     //    TrgItem tail = td.nullTrg();
  54     for( ; anIt!=aLast; anIt++ )
  55     {
  56       const DiffItem<SrcItem,TrgItem>& item = *anIt;
  57       if( item.mySrc==td.nullSrc() )
  58         if( item.myTrg==td.nullTrg() )
  59           qDebug( "error: both null" );
  60         else
  61           //to delete
  62           td.deleteItemWithChildren( item.myTrg );
  63       else {
  64         if( item.myTrg==td.nullTrg() )
  65         {
  66           //to add
  67           lastItem = createSubTree( item.mySrc, r2, lastItem, isFirst, td );
  68         }
  69         else
  70         {
  71           //to update
  72           td.updateItem( item.myTrg );
  73           synchronize( item.mySrc, item.myTrg, td );
  74           lastItem = item.myTrg;
  75         }
  76         isFirst = false;
  77       }
  78     }
  79
  80     return r2;
  81   }
  82   else
  83   {
  84     TrgItem new_r2 = createSubTree( r1, td.parent( r2 ), r2, false, td );
  85     if( r2!=td.nullTrg() )
  86       td.deleteItemWithChildren( r2 );
  87     return new_r2;
  88   }
  89 }
  90
  91 template <class SrcItem, class TrgItem, class TreeData>
  92 const typename QValueList<TrgItem>::const_iterator findEqual( const QValueList<TrgItem>& l,
  93                                                               const typename QValueList<TrgItem>::const_iterator& first,
  94                                                               const SrcItem& it,
  95                                                               const TreeData& td )
  96 {
  97   typename QValueList<TrgItem>::const_iterator cur = first, last = l.end();
  98   for( ; cur!=last; cur++ )
  99     if( td.isEqual( it, *cur ) )
 100       return cur;
 101   return last;
 102 }
 103
 104 template <class SrcItem, class TrgItem, class TreeData>
 105 void diffSiblings( const SrcItem& src, const TrgItem& trg,
 106                    QValueList < DiffItem < SrcItem,TrgItem > >& d,
 107                    const TreeData& td )
 108 {
 109   if( src==td.nullSrc() || trg==td.nullTrg() )
 110     return;
 111
 112   QValueList<SrcItem> src_ch;
 113   QValueList<TrgItem> trg_ch;
 114   td.children( src, src_ch );
 115   td.children( trg, trg_ch );
 116
 117   typename QValueList<SrcItem>::const_iterator src_it = src_ch.begin(), src_last = src_ch.end();
 118   typename QValueList<TrgItem>::const_iterator cur = trg_ch.begin(), trg_last = trg_ch.end();
 119
 120   for( ; src_it!=src_last; src_it++ )
 121   {
 122     typename QValueList<TrgItem>::const_iterator f =
 123       findEqual<SrcItem, TrgItem, TreeData>( trg_ch, cur, *src_it, td );
 124     if( f!=trg_last )  //is found
 125     {
 126       //mark all items before found as "to be deleted"
 127       for( typename QValueList<TrgItem>::const_iterator it = cur; it!=f; it++ )
 128       {
 129         DiffItem<SrcItem,TrgItem> ndiff;
 130         ndiff.mySrc = td.nullSrc();
 131         ndiff.myTrg = *it; //to delete;
 132         d.append( ndiff );
 133       }
 134       cur = f;
 135       DiffItem<SrcItem,TrgItem> ndiff;
 136       ndiff.mySrc = *src_it;
 137       ndiff.myTrg = *cur; //update this item
 138       d.append( ndiff );
 139       cur++;
 140     }
 141     else //not found
 142     {
 143       DiffItem<SrcItem,TrgItem> ndiff;
 144       ndiff.mySrc = *src_it;
 145       ndiff.myTrg = td.nullTrg(); //add this item
 146       d.append( ndiff );
 147     }
 148   }
 149   for( ; cur!=trg_last; cur++ )
 150   {
 151     DiffItem<SrcItem,TrgItem> ndiff;
 152     ndiff.mySrc = td.nullSrc();
 153     ndiff.myTrg = *cur; //to delete;
 154     d.append( ndiff );
 155   }
 156 }
 157
 158 template <class SrcItem, class TrgItem, class TreeData>
 159 TrgItem createSubTree( const SrcItem& src, const TrgItem& parent,
 160                        const TrgItem& after, const bool asFirst,
 161                        const TreeData& td )
 162 {
 163   if( src==td.nullSrc() )
 164     return td.nullTrg();
 165
 166   TrgItem nitem = td.createItem( src, parent, after, asFirst );
 167   if( nitem==td.nullTrg() )
 168     return nitem;
 169
 170   QValueList<SrcItem> ch;
 171   td.children( src, ch );
 172   typename QValueList<SrcItem>::const_iterator anIt = ch.begin(), aLast = ch.end();
 173   for( ; anIt!=aLast; anIt++ )
 174     createSubTree( *anIt, nitem, td.nullTrg(), false, td );
 175
 176   return nitem;
 177 }
 178
 179 #endif