glpmpl03.c

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

/*----------------------------------------------------------------------
-- create_string - create character string.
--
-- This routine creates a segmented character string, which is exactly
-- equivalent to specified character string. */

STRING *create_string
(     MPL *mpl,
      char buf[MAX_LENGTH+1]  /* not changed */
)
#if 0
{     STRING *head, *tail;
      int i, j;
      xassert(buf != NULL);
      xassert(strlen(buf) <= MAX_LENGTH);
      head = tail = dmp_get_atom(mpl->strings, sizeof(STRING));
      for (i = j = 0; ; i++)
      {  if ((tail->seg[j++] = buf[i]) == '\0') break;
         if (j == STRSEG_SIZE)
tail = (tail->next = dmp_get_atom(mpl->strings, sizeof(STRING))), j = 0;
      }
      tail->next = NULL;
      return head;
}
#else
{     STRING *str;
      xassert(strlen(buf) <= MAX_LENGTH);
      str = dmp_get_atom(mpl->strings, strlen(buf)+1);
      strcpy(str, buf);
      return str;
}
#endif

/*----------------------------------------------------------------------
-- copy_string - make copy of character string.
--
-- This routine returns an exact copy of segmented character string. */

STRING *copy_string
(     MPL *mpl,
      STRING *str             /* not changed */
)
#if 0
{     STRING *head, *tail;
      xassert(str != NULL);
      head = tail = dmp_get_atom(mpl->strings, sizeof(STRING));
      for (; str != NULL; str = str->next)
      {  memcpy(tail->seg, str->seg, STRSEG_SIZE);
         if (str->next != NULL)
tail = (tail->next = dmp_get_atom(mpl->strings, sizeof(STRING)));
      }
      tail->next = NULL;
      return head;
}
#else
{     xassert(mpl == mpl);
      return create_string(mpl, str);
}
#endif

/*----------------------------------------------------------------------
-- compare_strings - compare one character string with another.
--
-- This routine compares one segmented character strings with another
-- and returns the result of comparison as follows:
--
-- = 0 - both strings are identical;
-- < 0 - the first string precedes the second one;
-- > 0 - the first string follows the second one. */

int compare_strings
(     MPL *mpl,
      STRING *str1,           /* not changed */
      STRING *str2            /* not changed */
)
#if 0
{     int j, c1, c2;
      xassert(mpl == mpl);
      for (;; str1 = str1->next, str2 = str2->next)
      {  xassert(str1 != NULL);
         xassert(str2 != NULL);
         for (j = 0; j < STRSEG_SIZE; j++)
         {  c1 = (unsigned char)str1->seg[j];
            c2 = (unsigned char)str2->seg[j];
            if (c1 < c2) return -1;
            if (c1 > c2) return +1;
            if (c1 == '\0') goto done;
         }
      }
done: return 0;
}
#else
{     xassert(mpl == mpl);
      return strcmp(str1, str2);
}
#endif

/*----------------------------------------------------------------------
-- fetch_string - extract content of character string.
--
-- This routine returns a character string, which is exactly equivalent
-- to specified segmented character string. */

char *fetch_string
(     MPL *mpl,
      STRING *str,            /* not changed */
      char buf[MAX_LENGTH+1]  /* modified */
)
#if 0
{     int i, j;
      xassert(mpl == mpl);
      xassert(buf != NULL);
      for (i = 0; ; str = str->next)
      {  xassert(str != NULL);
         for (j = 0; j < STRSEG_SIZE; j++)
            if ((buf[i++] = str->seg[j]) == '\0') goto done;
      }
done: xassert(strlen(buf) <= MAX_LENGTH);
      return buf;
}
#else
{     xassert(mpl == mpl);
      return strcpy(buf, str);
}
#endif

/*----------------------------------------------------------------------
-- delete_string - delete character string.
--
-- This routine deletes specified segmented character string. */

void delete_string
(     MPL *mpl,
      STRING *str             /* destroyed */
)
#if 0
{     STRING *temp;
      xassert(str != NULL);
      while (str != NULL)
      {  temp = str;
         str = str->next;
         dmp_free_atom(mpl->strings, temp, sizeof(STRING));
      }
      return;
}
#else
{     dmp_free_atom(mpl->strings, str, strlen(str)+1);
      return;
}
#endif

/**********************************************************************/
/* * *                          SYMBOLS                           * * */
/**********************************************************************/

/*----------------------------------------------------------------------
-- create_symbol_num - create symbol of numeric type.
--
-- This routine creates a symbol, which has a numeric value specified
-- as floating-point number. */

SYMBOL *create_symbol_num(MPL *mpl, double num)
{     SYMBOL *sym;
      sym = dmp_get_atom(mpl->symbols, sizeof(SYMBOL));
      sym->num = num;
      sym->str = NULL;
      return sym;
}

/*----------------------------------------------------------------------
-- create_symbol_str - create symbol of abstract type.
--
-- This routine creates a symbol, which has an abstract value specified
-- as segmented character string. */

SYMBOL *create_symbol_str
(     MPL *mpl,
      STRING *str             /* destroyed */
)
{     SYMBOL *sym;
      xassert(str != NULL);
      sym = dmp_get_atom(mpl->symbols, sizeof(SYMBOL));
      sym->num = 0.0;
      sym->str = str;
      return sym;
}

/*----------------------------------------------------------------------
-- copy_symbol - make copy of symbol.
--
-- This routine returns an exact copy of symbol. */

SYMBOL *copy_symbol
(     MPL *mpl,
      SYMBOL *sym             /* not changed */
)
{     SYMBOL *copy;
      xassert(sym != NULL);
      copy = dmp_get_atom(mpl->symbols, sizeof(SYMBOL));
      if (sym->str == NULL)
      {  copy->num = sym->num;
         copy->str = NULL;
      }
      else
      {  copy->num = 0.0;
         copy->str = copy_string(mpl, sym->str);
      }
      return copy;
}

/*----------------------------------------------------------------------
-- compare_symbols - compare one symbol with another.
--
-- This routine compares one symbol with another and returns the result
-- of comparison as follows:
--
-- = 0 - both symbols are identical;
-- < 0 - the first symbol precedes the second one;
-- > 0 - the first symbol follows the second one.
--
-- Note that the linear order, in which symbols follow each other, is
-- implementation-dependent. It may be not an alphabetical order. */

int compare_symbols
(     MPL *mpl,
      SYMBOL *sym1,           /* not changed */
      SYMBOL *sym2            /* not changed */
)
{     xassert(sym1 != NULL);
      xassert(sym2 != NULL);
      /* let all numeric quantities precede all symbolic quantities */
      if (sym1->str == NULL && sym2->str == NULL)
      {  if (sym1->num < sym2->num) return -1;
         if (sym1->num > sym2->num) return +1;
         return 0;
      }
      if (sym1->str == NULL) return -1;
      if (sym2->str == NULL) return +1;
      return compare_strings(mpl, sym1->str, sym2->str);
}

/*----------------------------------------------------------------------
-- delete_symbol - delete symbol.
--
-- This routine deletes specified symbol. */

void delete_symbol
(     MPL *mpl,
      SYMBOL *sym             /* destroyed */
)
{     xassert(sym != NULL);
      if (sym->str != NULL) delete_string(mpl, sym->str);
      dmp_free_atom(mpl->symbols, sym, sizeof(SYMBOL));
      return;
}

/*----------------------------------------------------------------------
-- format_symbol - format symbol for displaying or printing.
--
-- This routine converts specified symbol to a charater string, which
-- is suitable for displaying or printing.
--
-- The resultant string is never longer than 255 characters. If it gets
-- longer, it is truncated from the right and appended by dots. */

char *format_symbol
(     MPL *mpl,
      SYMBOL *sym             /* not changed */
)
{     char *buf = mpl->sym_buf;
      xassert(sym != NULL);
      if (sym->str == NULL)
         sprintf(buf, "%.*g", DBL_DIG, sym->num);
      else
      {  char str[MAX_LENGTH+1];
         int quoted, j, len;
         fetch_string(mpl, sym->str, str);
         if (!(isalpha((unsigned char)str[0]) || str[0] == '_'))
            quoted = 1;
         else
         {  quoted = 0;
            for (j = 1; str[j] != '\0'; j++)
            {  if (!(isalnum((unsigned char)str[j]) ||
                     strchr("+-._", (unsigned char)str[j]) != NULL))
               {  quoted = 1;
                  break;
               }
            }
         }
#        define safe_append(c) \
            (void)(len < 255 ? (buf[len++] = (char)(c)) : 0)
         buf[0] = '\0', len = 0;
         if (quoted) safe_append('\'');
         for (j = 0; str[j] != '\0'; j++)
         {  if (quoted && str[j] == '\'') safe_append('\'');
            safe_append(str[j]);
         }
         if (quoted) safe_append('\'');
#        undef safe_append
         buf[len] = '\0';
         if (len == 255) strcpy(buf+252, "...");
      }
      xassert(strlen(buf) <= 255);
      return buf;
}

/*----------------------------------------------------------------------
-- concat_symbols - concatenate one symbol with another.
--
-- This routine concatenates values of two given symbols and assigns
-- the resultant character string to a new symbol, which is returned on
-- exit. Both original symbols are destroyed. */

SYMBOL *concat_symbols
(     MPL *mpl,
      SYMBOL *sym1,           /* destroyed */
      SYMBOL *sym2            /* destroyed */
)
{     char str1[MAX_LENGTH+1], str2[MAX_LENGTH+1];
      xassert(MAX_LENGTH >= DBL_DIG + DBL_DIG);
      if (sym1->str == NULL)
         sprintf(str1, "%.*g", DBL_DIG, sym1->num);
      else
         fetch_string(mpl, sym1->str, str1);
      if (sym2->str == NULL)
         sprintf(str2, "%.*g", DBL_DIG, sym2->num);
      else
         fetch_string(mpl, sym2->str, str2);
      if (strlen(str1) + strlen(str2) > MAX_LENGTH)
      {  char buf[255+1];
         strcpy(buf, format_symbol(mpl, sym1));
         xassert(strlen(buf) < sizeof(buf));
         error(mpl, "%s & %s; resultant symbol exceeds %d characters",
            buf, format_symbol(mpl, sym2), MAX_LENGTH);
      }
      delete_symbol(mpl, sym1);
      delete_symbol(mpl, sym2);
      return create_symbol_str(mpl, create_string(mpl, strcat(str1,
         str2)));
}

/**********************************************************************/
/* * *                          N-TUPLES                          * * */
/**********************************************************************/

/*----------------------------------------------------------------------
-- create_tuple - create n-tuple.
--
-- This routine creates a n-tuple, which initially has no components,
-- i.e. which is 0-tuple. */

TUPLE *create_tuple(MPL *mpl)
{     TUPLE *tuple;
      xassert(mpl == mpl);
      tuple = NULL;
      return tuple;
}

/*----------------------------------------------------------------------
-- expand_tuple - append symbol to n-tuple.
--
-- This routine expands n-tuple appending to it a given symbol, which
-- becomes its new last component. */

TUPLE *expand_tuple
(     MPL *mpl,
      TUPLE *tuple,           /* destroyed */
      SYMBOL *sym             /* destroyed */
)
{     TUPLE *tail, *temp;
      xassert(sym != NULL);
      /* create a new component */
      tail = dmp_get_atom(mpl->tuples, sizeof(TUPLE));
      tail->sym = sym;
      tail->next = NULL;
      /* and append it to the component list */
      if (tuple == NULL)
         tuple = tail;
      else
      {  for (temp = tuple; temp->next != NULL; temp = temp->next);
         temp->next = tail;
      }
      return tuple;
}

/*----------------------------------------------------------------------
-- tuple_dimen - determine dimension of n-tuple.
--
-- This routine returns dimension of n-tuple, i.e. number of components
-- in the n-tuple. */

int tuple_dimen
(     MPL *mpl,
      TUPLE *tuple            /* not changed */