intervalset.cpp

模糊聚類分析源碼。包含教學文件

/*
  
  Context       : Matrix and Vector Operation

  Author        : Frank Hoeppner, see also AUTHORS file 

  Description   : implementation of class module IntervalSet
                  
  History       :
    

  Comment       : 
    This file was generated automatically. DO NOT EDIT.

  Copyright     : Copyright (C) 1999-2000 Frank Hoeppner

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program 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 General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#ifndef IntervalSet_SOURCE
#define IntervalSet_SOURCE

/* configuration include */
#ifdef HAVE_CONFIG_H
/*
//FILETREE_IFDEF HAVE_CONFIG_H
*/
#include "config.h"
/*
//FILETREE_ENDIF
*/
#endif



// necessary includes
#include "IntervalSet.hpp"
#include "trace.hpp"
#include "hausdorff.hpp"

// data
#define TOUCHED_AFTER_SORT 1
#define TOUCHED_AFTER_CLEAN 2

// implementation
template <class DATA>
IntervalSet<DATA>::IntervalSet
  (
  )
  : m_status(0)
  {
  
  }

template <class DATA>
void IntervalSet<DATA>::insert
  (
  const IntervalSet<DATA>::primitive_type &a_ps
  )
  {
  m_list.push_back(a_ps);
  SET_TAG(m_status,TOUCHED_AFTER_SORT|TOUCHED_AFTER_CLEAN);
  }
template <class DATA>
void IntervalSet<DATA>::operation
  ( 
  const IntervalSet &a_arg,
  operation_enum a_negate
  )
  {
  FUNCLOG("IntervalSet::operation");
  trace("this=",m_list);
  trace("arg =",a_arg.m_list);

  if (IS_TAG(m_status,TOUCHED_AFTER_SORT))
    {
    m_list.sort();
    CLEAR_TAG(m_status,TOUCHED_AFTER_SORT);
    }
  primitive_list_type::iterator i_this_iter( m_list.begin() );
  primitive_list_type::const_iterator i_arg_iter( a_arg.m_list.begin() );
  specifier_enum this_specifier,arg_specifier;
  bool inside_arg(false),inside_this(false),inside_union(false);
  if (i_this_iter!=m_list.end())
    {
    {
      this_specifier = (*i_this_iter).specifier();
      if (IS_TAG(a_negate,NEGATE_THIS)) complement_specifier(this_specifier);
    }
    inside_this = (IS_TAG(this_specifier,ALL_X_LESS_THAN));
    }
  if (i_arg_iter!=a_arg.m_list.end())
    {
    {
      arg_specifier = (*i_arg_iter).specifier();
      if (IS_TAG(a_negate,NEGATE_ARG)) complement_specifier(arg_specifier);
    }
    inside_arg = (IS_TAG(arg_specifier,ALL_X_LESS_THAN));
    } 
  inside_union = inside_this || inside_arg;
  primitive_list_type::const_iterator i_current;
  primitive_list_type::iterator i_previous(m_list.end());
  enum 
    {
      GO_AHEAD_NONE = 0,
      GO_AHEAD_THIS = 1,
      GO_AHEAD_ARG  = 2,
      GO_AHEAD_BOTH = 3
    } goahead;
  do
    {
    if (i_this_iter == m_list.end())
      if (i_arg_iter == a_arg.m_list.end())
        goahead = GO_AHEAD_NONE; // both sets finished
      else
        goahead = GO_AHEAD_ARG; // this is done; arg not yet
    else
      if (i_arg_iter == a_arg.m_list.end())
        goahead = GO_AHEAD_THIS; // arg is done; this not yet
      else // both list not empty, PrimitiveSet values decide
        if ((*i_this_iter).value() > (*i_arg_iter).value())
          goahead = GO_AHEAD_ARG; // arg comes first
        else
          if ((*i_this_iter).value() < (*i_arg_iter).value())
            goahead = GO_AHEAD_THIS; // this comes first
          else
            goahead = GO_AHEAD_BOTH;

    i_current = (goahead==GO_AHEAD_ARG) ? i_arg_iter : i_this_iter;
    if (goahead!=GO_AHEAD_NONE) 
      {
      bool change;
      if (IS_TAG(goahead,GO_AHEAD_THIS))
        {
          this_specifier = (*i_this_iter).specifier();
          if (IS_TAG(a_negate,NEGATE_THIS)) complement_specifier(this_specifier);
        }
      if (IS_TAG(goahead,GO_AHEAD_ARG))
        {
          arg_specifier = (*i_arg_iter).specifier();
          if (IS_TAG(a_negate,NEGATE_ARG)) complement_specifier(arg_specifier);
        }
      {
        if (IS_TAG(goahead,GO_AHEAD_THIS)) inside_this = IS_TAG(this_specifier,NO_X_BUT);
        if (IS_TAG(goahead,GO_AHEAD_ARG)) inside_arg = IS_TAG(arg_specifier,NO_X_BUT);
        bool inside_union_before(inside_union);
        inside_union = inside_this || inside_arg;
        change = (inside_union_before != inside_union);
      }
      {
        if (IS_TAG(goahead,GO_AHEAD_THIS)) inside_this = IS_TAG(this_specifier,ALL_X_GREATER_THAN);
        if (IS_TAG(goahead,GO_AHEAD_ARG)) inside_arg = IS_TAG(arg_specifier,ALL_X_GREATER_THAN);
        bool inside_union_before(inside_union);
        inside_union = inside_this || inside_arg;
        change |= (inside_union_before != inside_union);
      }
      if (change)
        {
        primitive_list_type::iterator i_inserted;
        if (i_current==i_arg_iter)
          { // .insert(iter,value) inserts value _before_ iter
          i_inserted=m_list.insert(i_this_iter,(*i_current));
          (*i_inserted).specifier()=arg_specifier;
          }
        if (goahead==GO_AHEAD_THIS)
          (*i_this_iter).specifier() = this_specifier;
        if (goahead==GO_AHEAD_BOTH) 
          (*i_this_iter).specifier() = (specifier_enum)(this_specifier|arg_specifier);
        if (IS_TAG(a_negate,NEGATE_RESULT))
          if (i_current==i_arg_iter)
            { complement_specifier((*i_inserted).specifier()); }
          else
            { complement_specifier((*i_this_iter).specifier()); }
        }
      else
        {
        if (i_current==i_this_iter) (*i_this_iter).specifier() = NO_X;
        }
      }
    if (IS_TAG(goahead,GO_AHEAD_THIS)) { i_previous=i_this_iter; ++i_this_iter; }
    if (IS_TAG(goahead,GO_AHEAD_ARG)) { ++i_arg_iter; }
    trace("this=",m_list);
    }
  while (goahead!=GO_AHEAD_NONE);

  trace("result=",m_list);
  }
template <class DATA>
DATA IntervalSet<DATA>::size
  (
  )
  const
  {
  FUNCLOG("IntervalSet::size");
  trace("this=",m_list);
  if (m_list.empty()) return 0;
//  clean(); // don't want to handle NO_X and ALL_X
 
  primitive_list_type::const_iterator i_iter(m_list.begin());

  specifier_enum spec((*i_iter).specifier());
  DATA leftvalue(NEG_IMPOSSIBLE_RANGE);
  bool inside(IS_TAG(spec,ALL_X_LESS_THAN));
  DATA length(0);

  do
    {
    spec = (*i_iter).specifier();
    if ((inside) && (IS_TAG(spec,ALL_X_LESS_THAN)))
      { length += (*i_iter).value()-leftvalue; inside=false; }
    if ((!inside) && (IS_TAG(spec,ALL_X_GREATER_THAN)))
      { leftvalue = (*i_iter).value(); inside=true; }
    ++i_iter;
    }
  while (i_iter != m_list.end());

  return length;
  }
template <class DATA>
void IntervalSet<DATA>::write
  (
  ostream& os
  )
  const
  {
  stl_container_output(os,m_list.begin(),m_list.end(),"{"," ","}");
  }
template <class DATA>
void IntervalSet<DATA>::clean
  (
  )
  {
  if (IS_TAG(m_status,TOUCHED_AFTER_CLEAN))
    {
    primitive_list_type::iterator i_this(m_list.begin()),i_next(i_this);
    do
      {
      ++i_next;
      if ((i_next!=m_list.end()) && ((*i_this).value()==(*i_next).value()))
        { // only one case possible= "[x" followed by "x]", reduce to "[x]"
        (*i_next).specifier() = NO_X_BUT;
        m_list.erase(i_this);
        } else
      if (((*i_this).specifier()==NO_X) || ((*i_this).specifier()==ALL_X)) 
        { 
        m_list.erase(i_this); 
        }

      i_this=i_next;
      }
    while (i_this!=m_list.end());
    }
  }
template <class DATA>
DATA IntervalSet<DATA>::hausdorff_distance
  (
  DATA c,
  DATA d
  )
  const
  {
  invariant(!m_list.empty(),"not defined for empty list",SOURCELOC);
  DATA dist(NEG_IMPOSSIBLE_RANGE);
  primitive_list_type::const_iterator a(m_list.begin());

  bool inside_a;
  if (a!=m_list.end()) inside_a =
    IS_TAG((*a).specifier(),ALL_X_LESS_THAN);

  DATA aleft(NEG_IMPOSSIBLE_RANGE),aright;

  while (a!=m_list.end())
    {
    bool call(false);
    specifier_enum spec((*a).specifier());
    if (inside_a) 
      { // is interval continued..?
      invariant( IS_TAG(spec,ALL_X_LESS_THAN),"still inside interval",SOURCELOC );
      if (IS_NO_TAG(spec,ALL_X_GREATER_THAN))
        { aright = (*a).value(); inside_a=false; call=true; }
      }
    else /* !inside_a */ if (spec==NO_X_BUT)
      {
      aright=aleft=(*a).value(); call=true; /* inside remains false */
      }
    if (call)
    dist = max(dist,::hausdorff_distance(aleft,aright,c,d));
    if ((!inside_a) && (!call))
      { // does new interval start..?
      invariant( IS_NO_TAG(spec,ALL_X_LESS_THAN),"still outside interval",SOURCELOC);
      if (IS_TAG((*a).specifier(),ALL_X_GREATER_THAN))
        { aleft = (*a).value(); inside_a=true; }
      }
    ++a;
    }
  return dist;
  }
template <class DATA>
DATA IntervalSet<DATA>::hausdorff_distance
  (
  const IntervalSet<DATA> &B
  )
  const
  {
  invariant(!m_list.empty(),"not defined for empty list",SOURCELOC);
  DATA dist(NEG_IMPOSSIBLE_RANGE);
  primitive_list_type::const_iterator a(m_list.begin());

  bool inside_a;
  if (a!=m_list.end()) inside_a =
    IS_TAG((*a).specifier(),ALL_X_LESS_THAN);

  DATA aleft(NEG_IMPOSSIBLE_RANGE),aright;

  while (a!=m_list.end())
    {
    bool call(false);
    specifier_enum spec((*a).specifier());
    if (inside_a) 
      { // is interval continued..?
      invariant( IS_TAG(spec,ALL_X_LESS_THAN),"still inside interval",SOURCELOC );
      if (IS_NO_TAG(spec,ALL_X_GREATER_THAN))
        { aright = (*a).value(); inside_a=false; call=true; }
      }
    else /* !inside_a */ if (spec==NO_X_BUT)
      {
      aright=aleft=(*a).value(); call=true; /* inside remains false */
      }
    if (call)
    dist = max(dist,B.hausdorff_distance(aleft,aright));
    if ((!inside_a) && (!call))
      { // does new interval start..?
      invariant( IS_NO_TAG(spec,ALL_X_LESS_THAN),"still outside interval",SOURCELOC);
      if (IS_TAG((*a).specifier(),ALL_X_GREATER_THAN))
        { aleft = (*a).value(); inside_a=true; }
      }
    ++a;
    }
  return dist;
  }

// template instantiation



#endif // IntervalSet_SOURCE