SUIT_TreeSync.h

Go to the documentation of this file.

// Copyright (C) 2007-2016  CEA/DEN, EDF R&D, OPEN CASCADE
//
// Copyright (C) 2003-2007  OPEN CASCADE, EADS/CCR, LIP6, CEA/DEN,
// CEDRAT, EDF R&D, LEG, PRINCIPIA R&D, BUREAU VERITAS
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
//
// See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
//

// File   : SUIT_TreeSync.h
// Author : Alexander SOLOVYOV
//
#ifndef SUIT_TREESYNC_H
#define SUIT_TREESYNC_H

#include <QList>

template <class SrcItem, class TrgItem>
struct DiffItem
{
  SrcItem  mySrc;      
  TrgItem  myTrg;      
};


//
// Function prototypes.
//

template <class SrcItem, class TrgItem, class TreeData>
TrgItem synchronize( const SrcItem&, const TrgItem&, const TreeData& );

template <class SrcItem, class TrgItem, class TreeData>
QList< DiffItem<SrcItem,TrgItem> > diffSiblings( const SrcItem&, 
                                                 const TrgItem&, 
                                                 const TreeData& );

template <class SrcItem, class TrgItem, class TreeData>
TrgItem createSubTree( const SrcItem&, const TrgItem&, const TrgItem&, const TreeData& );

template <class SrcItem, class TrgItem, class TreeData>
const typename QList<TrgItem>::const_iterator findEqual( const SrcItem& it,
                                                         const typename QList<TrgItem>::const_iterator& first,
                                                         const typename QList<TrgItem>::const_iterator& last,
                                                         const TreeData& td );


//
// Function imlpementation.
//

template <class SrcItem, class TrgItem, class TreeData>
TrgItem synchronize( const SrcItem& r1, const TrgItem& r2, const TreeData& td )
{
  if ( td.isEqual( r1, r2 ) ) {
    // update items themselves
    td.updateItem( r1, r2 );
    
    // iterate through children
    QList< DiffItem< SrcItem, TrgItem > > d =  diffSiblings( r1, r2, td );
    
    typename QList< DiffItem< SrcItem, TrgItem > >::const_iterator anIt = d.begin(), aLast = d.end();
    TrgItem lastItem = td.nullTrg();

    for ( ; anIt != aLast; anIt++ ) {
      const DiffItem<SrcItem,TrgItem>& item = *anIt;
      if ( item.mySrc == td.nullSrc() ) {
        if ( item.myTrg == td.nullTrg() )
          qDebug( "error: both null" );
        else
          // delete item
          td.deleteItemWithChildren( item.myTrg );
      }
      else {
        if ( item.myTrg == td.nullTrg() ) {
          // add item (recursively)
          TrgItem nitem = createSubTree( item.mySrc, r2, lastItem, td );
          if ( nitem != td.nullTrg() )
            lastItem = nitem;
        }
        else {
          // update item
          synchronize( item.mySrc, item.myTrg, td );
          lastItem = item.myTrg;
        }
      }
    }
    return r2;
  }
  else {
    TrgItem new_r2 = td.nullTrg();
    if ( r1 != td.nullSrc() ) {
      // add new item (recursively)
      new_r2 = createSubTree( r1, td.parent( r2 ), r2, td );
    }
    if ( r2 != td.nullTrg() ) {
      // delete old one (if it is not null)
      td.deleteItemWithChildren( r2 );
    }
    return new_r2;
  }
}

template <class SrcItem, class TrgItem, class TreeData>
const typename QList<TrgItem>::const_iterator findEqual( const SrcItem& it,
                                                         const typename QList<TrgItem>::const_iterator& first,
                                                         const typename QList<TrgItem>::const_iterator& last,
                                                         const TreeData& td )
{
  typename QList<TrgItem>::const_iterator cur = first;
  for ( ; cur != last; cur++ ) {
    if ( td.isEqual( it, *cur ) )
      return cur;
  }
  return last;
}

template <class SrcItem, class TrgItem, class TreeData>
QList< DiffItem<SrcItem,TrgItem> > diffSiblings( const SrcItem& src, const TrgItem& trg,
                                                 const TreeData& td )
{
  //if( src==td.nullSrc() || trg==td.nullTrg() )
  //  return;
  
  QList< DiffItem<SrcItem,TrgItem> > d;
   
  QList<SrcItem> src_ch = td.children( src );
  QList<TrgItem> trg_ch = td.children( trg );

  typename QList<SrcItem>::const_iterator src_it = src_ch.begin(), src_last = src_ch.end();
  typename QList<TrgItem>::const_iterator cur    = trg_ch.begin(), trg_last = trg_ch.end();

  for ( ; src_it != src_last; src_it++ ) {
    typename QList<TrgItem>::const_iterator f =
      findEqual<SrcItem, TrgItem, TreeData>( *src_it, cur, trg_last, td );
    if ( f != trg_last )  { 
      // target is found
      // mark all items before found one as "to be deleted"
      for ( typename QList<TrgItem>::const_iterator it = cur; it != f; it++ ) {
        DiffItem<SrcItem,TrgItem> ndiff;
        ndiff.mySrc = td.nullSrc();
        ndiff.myTrg = *it;        // delete item
        d.append( ndiff );
      }
      cur = f;
      DiffItem<SrcItem,TrgItem> ndiff;
      ndiff.mySrc = *src_it;
      ndiff.myTrg = *cur;         // update this (found) item
      d.append( ndiff );
      cur++;
    }
    else {
      // target is not found
      DiffItem<SrcItem,TrgItem> ndiff;
      ndiff.mySrc = *src_it;
      ndiff.myTrg = td.nullTrg(); // add item
      d.append( ndiff );
    }
  }
  // delete rest items
  for ( ; cur != trg_last; cur++ ) {
    DiffItem<SrcItem,TrgItem> ndiff;
    ndiff.mySrc = td.nullSrc();
    ndiff.myTrg = *cur;           // delete item
    d.append( ndiff );
  }
  
  return d;
}

template <class SrcItem, class TrgItem, class TreeData>
TrgItem createSubTree( const SrcItem& src, const TrgItem& parent,
                       const TrgItem& after, const TreeData& td )
{
  if ( src == td.nullSrc() )
    return td.nullTrg();

  TrgItem nitem = td.createItem( src, parent, after );
  if ( nitem == td.nullTrg() )
    return nitem;

  QList<SrcItem> ch = td.children( src );
  typename QList<SrcItem>::const_iterator anIt = ch.begin(), aLast = ch.end();
  TrgItem last = td.nullTrg();
  for( ; anIt != aLast; anIt++ )
    last = createSubTree( *anIt, nitem, last, td );

  return nitem;
}

#endif // SUIT_TREESYNC_H