glplib11.c

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

/* glplib11.c (miscellaneous routines) */

/***********************************************************************
*  This code is part of GLPK (GNU Linear Programming Kit).
*
*  Copyright (C) 2000,01,02,03,04,05,06,07,08,2009 Andrew Makhorin,
*  Department for Applied Informatics, Moscow Aviation Institute,
*  Moscow, Russia. All rights reserved. E-mail: <[e-mail]>.
*
*  GLPK 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 3 of the License, or
*  (at your option) any later version.
*
*  GLPK 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 GLPK. If not, see <http://www.gnu.org/licenses/>.
***********************************************************************/

#include "glplib.h"

/***********************************************************************
*  NAME
*
*  str2int - convert character string to value of int type
*
*  SYNOPSIS
*
*  #include "util.h"
*  int str2int(const char *str, int *val);
*
*  DESCRIPTION
*
*  The routine str2int converts the character string str to a value of
*  integer type and stores the value into location, which the parameter
*  val points to (in the case of error content of this location is not
*  changed).
*
*  RETURNS
*
*  The routine returns one of the following error codes:
*
*  0 - no error;
*  1 - value out of range;
*  2 - character string is syntactically incorrect. */

int str2int(const char *str, int *_val)
{     int d, k, s, val = 0;
      /* scan optional sign */
      if (str[0] == '+')
         s = +1, k = 1;
      else if (str[0] == '-')
         s = -1, k = 1;
      else
         s = +1, k = 0;
      /* check for the first digit */
      if (!isdigit((unsigned char)str[k])) return 2;
      /* scan digits */
      while (isdigit((unsigned char)str[k]))
      {  d = str[k++] - '0';
         if (s > 0)
         {  if (val > INT_MAX / 10) return 1;
            val *= 10;
            if (val > INT_MAX - d) return 1;
            val += d;
         }
         else
         {  if (val < INT_MIN / 10) return 1;
            val *= 10;
            if (val < INT_MIN + d) return 1;
            val -= d;
         }
      }
      /* check for terminator */
      if (str[k] != '\0') return 2;
      /* conversion has been done */
      *_val = val;
      return 0;
}

/***********************************************************************
*  NAME
*
*  str2num - convert character string to value of double type
*
*  SYNOPSIS
*
*  #include "util.h"
*  int str2num(const char *str, double *val);
*
*  DESCRIPTION
*
*  The routine str2num converts the character string str to a value of
*  double type and stores the value into location, which the parameter
*  val points to (in the case of error content of this location is not
*  changed).
*
*  RETURNS
*
*  The routine returns one of the following error codes:
*
*  0 - no error;
*  1 - value out of range;
*  2 - character string is syntactically incorrect. */

int str2num(const char *str, double *_val)
{     int k;
      double val;
      /* scan optional sign */
      k = (str[0] == '+' || str[0] == '-' ? 1 : 0);
      /* check for decimal point */
      if (str[k] == '.')
      {  k++;
         /* a digit should follow it */
         if (!isdigit((unsigned char)str[k])) return 2;
         k++;
         goto frac;
      }
      /* integer part should start with a digit */
      if (!isdigit((unsigned char)str[k])) return 2;
      /* scan integer part */
      while (isdigit((unsigned char)str[k])) k++;
      /* check for decimal point */
      if (str[k] == '.') k++;
frac: /* scan optional fraction part */
      while (isdigit((unsigned char)str[k])) k++;
      /* check for decimal exponent */
      if (str[k] == 'E' || str[k] == 'e')
      {  k++;
         /* scan optional sign */
         if (str[k] == '+' || str[k] == '-') k++;
         /* a digit should follow E, E+ or E- */
         if (!isdigit((unsigned char)str[k])) return 2;
      }
      /* scan optional exponent part */
      while (isdigit((unsigned char)str[k])) k++;
      /* check for terminator */
      if (str[k] != '\0') return 2;
      /* perform conversion */
      {  char *endptr;
         val = strtod(str, &endptr);
         if (*endptr != '\0') return 2;
      }
      /* check for overflow */
      if (!(-DBL_MAX <= val && val <= +DBL_MAX)) return 1;
      /* check for underflow */
      if (-DBL_MIN < val && val < +DBL_MIN) val = 0.0;
      /* conversion has been done */
      *_val = val;
      return 0;
}

/***********************************************************************
*  NAME
*
*  strspx - remove all spaces from character string
*
*  SYNOPSIS
*
*  #include "glplib.h"
*  char *strspx(char *str);
*
*  DESCRIPTION
*
*  The routine strspx removes all spaces from the character string str.
*
*  RETURNS
*
*  The routine returns a pointer to the character string.
*
*  EXAMPLES
*
*  strspx("   Errare   humanum   est   ") => "Errarehumanumest"
*
*  strspx("      ")                       => "" */

char *strspx(char *str)
{     char *s, *t;
      for (s = t = str; *s; s++) if (*s != ' ') *t++ = *s;
      *t = '\0';
      return str;
}

/***********************************************************************
*  NAME
*
*  strtrim - remove trailing spaces from character string
*
*  SYNOPSIS
*
*  #include "glplib.h"
*  char *strtrim(char *str);
*
*  DESCRIPTION
*
*  The routine strtrim removes trailing spaces from the character
*  string str.
*
*  RETURNS
*
*  The routine returns a pointer to the character string.
*
*  EXAMPLES
*
*  strtrim("Errare humanum est   ") => "Errare humanum est"
*
*  strtrim("      ")                => "" */

char *strtrim(char *str)
{     char *t;
      for (t = strrchr(str, '\0') - 1; t >= str; t--)
      {  if (*t != ' ') break;
         *t = '\0';
      }
      return str;
}

/***********************************************************************
*  NAME
*
*  strrev - reverse character string
*
*  SYNOPSIS
*
*  #include "glplib.h"
*  char *strrev(char *s);
*
*  DESCRIPTION
*
*  The routine strrev changes characters in a character string s to the
*  reverse order, except the terminating null character.
*
*  RETURNS
*
*  The routine returns the pointer s.
*
*  EXAMPLES
*
*  strrev("")                => ""
*
*  strrev("Today is Monday") => "yadnoM si yadoT" */

char *strrev(char *s)
{     int i, j;
      char t;
      for (i = 0, j = strlen(s)-1; i < j; i++, j--)
         t = s[i], s[i] = s[j], s[j] = t;
      return s;
}

/***********************************************************************
*  NAME
*
*  gcd - compute greatest common divisor of two integers
*
*  SYNOPSIS
*
*  #include "glplib.h"
*  int gcd(int x, int y);
*
*  RETURNS
*
*  The routine gcd returns gcd(x, y), the greatest common divisor of
*  the two non-negative integers given.
*
*  ALGORITHM
*
*  The routine gcd is based on the Euclidean algorithm.
*
*  REFERENCES
*
*  Don Knuth, The Art of Computer Programming, Vol.2: Seminumerical
*  Algorithms, 3rd Edition, Addison-Wesley, 1997. Section 4.5.2: The
*  Greatest Common Divisor, pp. 333-56. */

int gcd(int x, int y)
{     int r;
      xassert(x >= 0);
      xassert(y >= 0);
      while (y > 0)
         r = x % y, x = y, y = r;
      return x;
}

/***********************************************************************
*  NAME
*
*  gcdn - compute greatest common divisor of n integers
*
*  SYNOPSIS
*
*  #include "glplib.h"
*  int gcdn(int n, int x[]);
*
*  RETURNS
*
*  The routine gcdn returns gcd(x[1], x[2], ..., x[n]), the greatest
*  common divisor of the non-negative integers given.
*
*  BACKGROUND
*
*  The routine gcdn is based on the following identity:
*
*     gcd(x, y, z) = gcd(gcd(x, y), z).
*
*  REFERENCES
*