ordered_set.tpp

Go to the documentation of this file.

/*
  CLAW - a C++ Library Absolutely Wonderful

  CLAW is a free library without any particular aim but being useful to 
  anyone.

  Copyright (C) 2005-2011 Julien Jorge

  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., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

  contact: julien.jorge@gamned.org
*/
#include <list>

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
Comp claw::math::ordered_set<K,Comp>::s_key_comp;

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::math::ordered_set<K, Comp>&
claw::math::ordered_set<K, Comp>::operator*=( const ordered_set& that )
{
  return intersection( that );
} // ordered_set::operator*=()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::math::ordered_set<K, Comp>&
claw::math::ordered_set<K, Comp>::operator+=( const ordered_set& that )
{
  return join( that );
} // ordered_set::operator+=()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::math::ordered_set<K, Comp>&
claw::math::ordered_set<K, Comp>::operator-=( const ordered_set& that )
{
  return difference( that );
} // ordered_set::operator-=()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::math::ordered_set<K, Comp>&
claw::math::ordered_set<K, Comp>::operator/=( const ordered_set& that )
{
  return symetric_difference( that );
} // ordered_set::operator/=()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
bool
claw::math::ordered_set<K, Comp>::operator>( const ordered_set& that ) const
{
  return strictly_contains( that );
} // ordered_set::operator>()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
bool
claw::math::ordered_set<K, Comp>::operator>=( const ordered_set& that ) const
{
  return contains( that );
} // ordered_set::operator>=()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
bool
claw::math::ordered_set<K, Comp>::operator<( const ordered_set& that ) const
{
  return that.strictly_contains( *this );
} // ordered_set::operator<()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
bool
claw::math::ordered_set<K, Comp>::operator<=( const ordered_set& that ) const
{
  return that.contains( *this );
} // ordered_set::operator<=()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::math::ordered_set<K, Comp>&
claw::math::ordered_set<K, Comp>::intersection( const ordered_set& that )
{
  std::list<K> remove_us;
  const_iterator it;
  
  for (it=super::begin(); it!=super::end(); ++it)
    if ( that.find( *it ) == that.end() )
      remove_us.push_front( *it );

  typename std::list<K>::const_iterator remove_it;

  for (remove_it=remove_us.begin(); remove_it!=remove_us.end(); ++remove_it)
    super::erase( *remove_it );

  return *this;
} // ordered_set::intersection()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::math::ordered_set<K, Comp>&
claw::math::ordered_set<K, Comp>::join( const ordered_set& that )
{
  const_iterator it;
  
  for (it=that.begin(); it!=that.end(); ++it)
    super::insert( *it );

  return *this;
} // ordered_set::join()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::math::ordered_set<K, Comp>&
claw::math::ordered_set<K, Comp>::difference( const ordered_set& that )
{
  std::list<K> remove_us;
  const_iterator it;
  
  for (it=super::begin(); it!=super::end(); ++it)
    if ( that.find( *it ) != that.end() )
      remove_us.push_front( *it );

  typename std::list<K>::const_iterator remove_it;

  for (remove_it=remove_us.begin(); remove_it!=remove_us.end(); ++remove_it)
    super::erase( *remove_it );

  return *this;
} // ordered_set::difference()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
claw::math::ordered_set<K, Comp>&
claw::math::ordered_set<K, Comp>::symetric_difference( const ordered_set& that )
{
  ordered_set<K, Comp> my_copy(*this), his_copy(that);

  return difference( that ).join( his_copy.difference(my_copy) );
} // ordered_set::symetric_difference()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
bool
claw::math::ordered_set<K, Comp>::contains( const ordered_set& that ) const
{
  bool ok = super::size() >= that.size();
  const_iterator it_this( super::begin() );
  const_iterator it_that( that.begin() );

  while ( ok && (it_that != that.end()) && (it_this != super::end()) )
    if ( s_key_comp( *it_this, *it_that ) )
      ++it_this;
    else if ( s_key_comp( *it_that, *it_this ) )
      ok = false;
    else
      {
        ++it_this;
        ++it_that;
      }

  return it_that == that.end();
} // ordered_set::contains()

/*----------------------------------------------------------------------------*/
template<class K, class Comp>
bool
claw::math::ordered_set<K, Comp>::strictly_contains
( const ordered_set& that ) const
{
  return contains(that) && ( super::size() > that.size() );
} // ordered_set::strictly_contains()