// Match.c

#ifndef Match_C
#define Match_C

#include <cassert>
#include "InvalidQuality.h"

//**********************************************************************
// Match methods.
//**********************************************************************

// constructor

template<class T1, class T2, class L1, class L2>
Match<T1,T2,L1,L2>::Match() { }

//**********************************************************************

// destructor

template<class T1, class T2, class L1, class L2>
Match<T1,T2,L1,L2>::~Match() { }

//**********************************************************************

// Match the collections.
// Copy input lists and build maps (perform matching).

template<class T1, class T2, class L1, class L2>
void Match<T1,T2,L1,L2>::match(const L1& list1, const L2& list2) {

  // Copy the input collections.
  _list1 = list1;
  _list2 = list2;

  // Build the 21 map.

  // Loop over elements in the 2nd list
  typename L2::const_iterator it2;
  for ( it2=_list2.begin(); it2!=_list2.end(); ++it2 ) { 

    // Intialize the reference quality.
    QualityPtr pquality21(new InvalidQuality);

    // Find the nearest element in the 1st list
    typename L1::const_iterator it1;
    for ( it1=_list1.begin(); it1!=_list1.end(); ++it1 ) {

      // Evaluate the new quality.
      QualityPtr pquality( _quality(*it1,*it2) );

      // If the quality has improved, save it in the 21 map.
      if ( pquality->is_better_than(*pquality21) ) {
        _map21[*it2] = *it1;
        pquality21 = pquality;
      }

    }  // end loop over 1st list

  }  // end loop over second list

  // Build the 12 map and drop 21 entries which point to the same
  // element.

  // Loop over entries in the 21 map.
  Map21::iterator i21 = _map21.begin();
  while( i21 != _map21.end() ) {
    const T2& x2 = (*i21).first;
    const T1& x1 = (*i21).second;

    // If the 12 index is unassigned, assign it.
    Map12::const_iterator i12 = _map12.find(x1);
    if ( i12 == _map12.end() ) {
      _map12[x1] = x2;
      ++i21;
      continue;
    }

    // The index was already assigned.

    // Evaluate the qualities.
    const T2& x2_old = _map12[x1];
    assert( x2 != x2_old );
    QualityPtr pqold( _quality(x1,x2_old) );
    QualityPtr pqnew( _quality(x1,x2) );
    assert( pqold->is_valid() );
    assert( pqnew->is_valid() );

    // If the new quality is better, replace the 12 entry (old -> new)
    // and drop the old 21 entry.
    if ( pqnew->is_better_than(*pqold) ) {
      Map21::iterator i21_old = _map21.find(x2_old);
      assert( i21_old != _map21.end() );
      _map21.erase(i21_old);
      assert( i21 != _map21.end() );
      assert( (*i21).first == x2 );
      i21 = _map21.find(x2);
      assert( i21 != _map21.end() );
      assert( (*i21).first == x2 );
      ++i21;
      _map12[x1] = x2;
    }

    // If the old quality is better, drop the new 21 entry.
    else _map21.erase(i21++);

  }  // end loop over 21 map

  // check maps
  assert( _map12.size() == _map21.size() );

}

//**********************************************************************

// Return the matched elements from list 1.

template<class T1, class T2, class L1, class L2>
L1 Match<T1,T2,L1,L2>::get_matched1() const {

  // create list
  L1 list;

  // Loop over the matches.
  Map12::const_iterator i12;
  for ( i12=_map12.begin(); i12!=_map12.end(); ++i12 )
    list.push_back( (*i12).first );

  return list;

}

//**********************************************************************

// Return the matched elements from list 2.

template<class T1, class T2, class L1, class L2>
L2 Match<T1,T2,L1,L2>::get_matched2() const {

  // create list
  L2 list;

  // Loop over the matches.
  Map21::const_iterator i21;
  for ( i21=_map21.begin(); i21!=_map21.end(); ++i21 ) 
    list.push_back( (*i21).first );

  return list;

}

//**********************************************************************

// Return the unmatched elements from list 1.

template<class T1, class T2, class L1, class L2>
L1 Match<T1,T2,L1,L2>::get_unmatched1() const {

  // create list
  L1 list;

  // Loop over the list and add entries which do not appear
  // in the matched map.
  typename L1::const_iterator i1;
  for ( i1=_list1.begin(); i1!=_list1.end(); ++i1 ) {
    Map12::const_iterator i12 = _map12.find(*i1);
    if ( i12 == _map12.end() ) list.push_back( *i1 );
  }

  return list;
}

//**********************************************************************

// Return the unmatched elements from list 2.

template<class T1, class T2, class L1, class L2>
L2 Match<T1,T2,L1,L2>::get_unmatched2() const {

  // create list
  L2 list;

  // Loop over the list and add entries which do not appear
  // in the matched map.
  typename L2::const_iterator i2;
  for ( i2=_list2.begin(); i2!=_list2.end(); ++i2 ) {
    Map21::const_iterator i21 = _map21.find(*i2);
    if ( i21 == _map21.end() ) list.push_back( *i2 );
  }

  return list;

}

//**********************************************************************

// Return the matched elements from list 1 in the order of list 2.

template<class T1, class T2, class L1, class L2>
L1 Match<T1,T2,L1,L2>::get_matched1_in_order2() const {

  // create list
  L1 list;

  // Loop over the matches.
  Map21::const_iterator i21;
  for ( i21=_map21.begin(); i21!=_map21.end(); ++i21 )
    list.push_back( (*i21).second );

  return list;

}

//**********************************************************************

// Return the matched elements from list 1 in the order of list 2.

template<class T1, class T2, class L1, class L2>
L2 Match<T1,T2,L1,L2>::get_matched2_in_order1() const {

  // create list
  L2 list;

  // Loop over the matches.
  Map12::const_iterator i12;
  for ( i12=_map12.begin(); i12!=_map12.end(); ++i12 )
    list.push_back( (*i12).second );

  return list;

}

//**********************************************************************

// output stream

template<class T1, class T2, class L1, class L2>
void Match<T1,T2,L1,L2>::ostr(std::ostream& stream) const {

  char* line = "----------------------";

  stream << line << endl;
  typename L1::const_iterator i1;
  for ( i1=_list1.begin(); i1!=_list1.end(); ++i1 )
    stream <<  *i1 << endl;

  stream << line << endl;
  typename L2::const_iterator i2;
  for ( i2=_list2.begin(); i2!=_list2.end(); ++i2 )
    stream <<  *i2 << endl;

  stream << line << endl;
  Map12::const_iterator i12;
  for ( i12=_map12.begin(); i12!=_map12.end(); ++i12 )
    stream <<  (*i12).first << "  " << (*i12).second << endl;

  stream << line << endl;
  Map21::const_iterator i21;
  for ( i21=_map21.begin(); i21!=_map21.end(); ++i21 )
    stream <<  (*i21).first << "  " << (*i21).second << endl;

  stream << line;
}

//**********************************************************************
// External functions.
// output stream

//**********************************************************************

template<class T1, class T2, class L1, class L2>
std::ostream& operator<<(std::ostream& stream, const Match<T1,T2,L1,L2>& match) {
  match.ostr(stream);
  return stream;
}

//**********************************************************************

#endif