/*=============================================================================*\
 * File: gfsmSemiring.def
 * Author: Bryan Jurish <moocow@ling.uni-potsdam.de>
 * Description: finite state machine library: semirings: inline definitions
 *
 * Copyright (c) 2004-2007 Bryan Jurish.
 *
 * 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
 *=============================================================================*/

#include <float.h>
#include <math.h>
#include <string.h>

/*======================================================================
 * Semiring: general utilities
 */

// LOG_BIG = log(1E31)
#define LOG_BIG    71.3801378828154
/*
//#define LOG_ZERO  -FLT_MAX
#define LOG_ZERO  -1E+38F
#define LOG_ONE    0
#define LOG_NONE   1
*/
GFSM_INLINE
gfsmWeight gfsm_log_add(gfsmWeight x, gfsmWeight y)
{
  if      (y-x > LOG_BIG) return y;
  else if (x-y > LOG_BIG) return x;
  /*else        return min(x,y) + log(exp(x-min(x,y)) + exp(y-min(x,y))); */
  else if (x<y) return x        + log( 1              + exp(y-x));
  else          return y        + log(exp(x-y)        + 1);
}
#undef LOG_BIG


/*======================================================================
 * Semiring: methods: constructors etc.
 */

/*--------------------------------------------------------------
 * init()
 */
GFSM_INLINE
void gfsm_semiring_init(gfsmSemiring *sr, gfsmSRType type)
{
  memset(sr, 0, type==gfsmSRTUser ? sizeof(gfsmUserSemiring) : sizeof(gfsmSemiring));
  sr->type = type;
  switch (type) {
  case gfsmSRTBoolean:
    sr->zero = 0;
    sr->one  = 1;
    break;
  case gfsmSRTLog:
    sr->zero = FLT_MAX;
    sr->one  = 0;
    break;
  case gfsmSRTPLog:
    sr->zero = -FLT_MAX;
    sr->one  = 0;
    break;
  case gfsmSRTTrivial:
    sr->zero = 0;
    sr->one  = 0;
    break;
  case gfsmSRTTropical:
    sr->zero = FLT_MAX;
    sr->one  = 0;
    break;
  case gfsmSRTReal:
  default:
    sr->zero = 0;
    sr->one  = 1;
    break;
  }
}

/*--------------------------------------------------------------
 * new()
 */
GFSM_INLINE
gfsmSemiring *gfsm_semiring_new(gfsmSRType type)
{
  gfsmSemiring *sr = (gfsmSemiring*)g_new(gfsmSemiring,1);
  gfsm_semiring_init(sr,type);
  return sr;
}

/*--------------------------------------------------------------
 * user_new()
 */
GFSM_INLINE
gfsmUserSemiring *gfsm_user_semiring_new(gfsmSRBinaryPredicate equal_func,
					 gfsmSRBinaryPredicate less_func,
					 gfsmSRBinaryOp        plus_func,
					 gfsmSRBinaryOp        times_func)
{
  gfsmUserSemiring *sr = g_new(gfsmUserSemiring, 1);
  gfsm_semiring_init((gfsmSemiring*)sr,gfsmSRTUser);
  sr->equal_func = equal_func;
  sr->less_func = less_func;
  sr->plus_func = plus_func;
  sr->times_func = times_func;
  return sr;
}

/*--------------------------------------------------------------
 * copy()
 */
GFSM_INLINE
gfsmSemiring *gfsm_semiring_copy(gfsmSemiring *sr)
{
  if (sr->type==gfsmSRTUser)
    return (gfsmSemiring*)gfsm_user_semiring_new(((gfsmUserSemiring*)sr)->equal_func,
						 ((gfsmUserSemiring*)sr)->less_func,
						 ((gfsmUserSemiring*)sr)->plus_func,
						 ((gfsmUserSemiring*)sr)->times_func);
  return gfsm_semiring_new(sr->type);
}

/*--------------------------------------------------------------
 * free()
 */
GFSM_INLINE
void gfsm_semiring_free(gfsmSemiring *sr)
{
  if (sr->type==gfsmSRTUser) g_free((gfsmUserSemiring*)sr);
  else g_free(sr);
}


/*======================================================================
 * Semiring: methods: general accessors
 */

/*--------------------------------------------------------------
 * zero()
 */
GFSM_INLINE
gfsmWeight gfsm_sr_zero(gfsmSemiring *sr) { return sr ? sr->zero : 0; }

/*--------------------------------------------------------------
 * one()
 */
GFSM_INLINE
gfsmWeight gfsm_sr_one(gfsmSemiring *sr) { return sr ? sr->one : 1; }

/*--------------------------------------------------------------
 * equal()
 */
GFSM_INLINE
gboolean gfsm_sr_equal(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y)
{
  return (sr->type == gfsmSRTUser && ((gfsmUserSemiring*)sr)->equal_func
	  ? ((*((gfsmUserSemiring*)sr)->equal_func)(sr,x,y)) \
	  : (x==y));
}

/*--------------------------------------------------------------
 * less()
 */
GFSM_INLINE
gboolean gfsm_sr_less(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y)
{
  switch (sr->type) {
  case gfsmSRTLog:
  case gfsmSRTTropical: return (x < y);

  case gfsmSRTPLog: return (x > y);

  case gfsmSRTTrivial:  return 0;

  case gfsmSRTUser:
    if (((gfsmUserSemiring*)sr)->less_func)
      return (*((gfsmUserSemiring*)sr)->less_func)(sr,x,y);

  case gfsmSRTBoolean:
  case gfsmSRTReal:
  default:             return (x > y);
  }
  return FALSE; //-- should never happen
}

/*--------------------------------------------------------------
 * plus()
 */
GFSM_INLINE
gfsmWeight gfsm_sr_plus(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y)
{ 
  switch (sr->type) {
  case gfsmSRTBoolean:  return x || y;
  //case gfsmSRTLog:      return -log(exp(-x) + exp(-y));
  case gfsmSRTLog:      return -gfsm_log_add(-x,-y);
  case gfsmSRTPLog:     return  gfsm_log_add( x, y);
  case gfsmSRTTropical: return (x < y ? x : y);
  case gfsmSRTTrivial:  return 0;

  case gfsmSRTUser:
    if (((gfsmUserSemiring*)sr)->plus_func)
      return (*((gfsmUserSemiring*)sr)->plus_func)(sr,x,y);

  case gfsmSRTReal:
  default:             return x + y;
  }
  return sr->zero; //-- should never happen
}

/*--------------------------------------------------------------
 * times()
 */
GFSM_INLINE
gfsmWeight gfsm_sr_times(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y)
{
  switch (sr->type) {
  case gfsmSRTBoolean:  return x && y;
  case gfsmSRTLog:      
  case gfsmSRTPLog:
  case gfsmSRTTropical: return x + y;
  case gfsmSRTTrivial:  return 0;

  case gfsmSRTUser:
    if (((gfsmUserSemiring*)sr)->times_func)
      return (*((gfsmUserSemiring*)sr)->times_func)(sr,x,y);

  case gfsmSRTReal:
  default:             return x * y;
  }
  return sr->zero; //-- should never happen
}

/*--------------------------------------------------------------
 * div()
 */
/*gboolean gfsm_sr_div(gfsmSemiring *sr, gfsmWeight x, gfsmWeight y)
  { return (sr->div_func ? ((*sr->div_func)(sr,x,y)) : (x/y)); }
*/
//@}


/*======================================================================
 * Semiring: string utilities
 */