fp20_dstruct.c

Go to the documentation of this file.

/****************************************************************************/
/*                                                                          */
/*  This file is part of QSopt_ex.                                          */
/*                                                                          */
/*  (c) Copyright 2006 by David Applegate, William Cook, Sanjeeb Dash,      */
/*  and Daniel Espinoza                                                     */
/*                                                                          */
/*  Sanjeeb Dash ownership of copyright in QSopt_ex is derived from his     */
/*  copyright in QSopt.                                                     */
/*                                                                          */
/*  This code may be used under the terms of the GNU General Public License */
/*  (Version 2.1 or later) as published by the Free Software Foundation.    */
/*                                                                          */
/*  Alternatively, use is granted for research purposes only.               */
/*                                                                          */
/*  It is your choice of which of these two licenses you are operating      */
/*  under.                                                                  */
/*                                                                          */
/*  We make no guarantees about the correctness or usefulness of this code. */
/*                                                                          */
/****************************************************************************/

/* RCS_INFO = "$RCSfile: fp20_dstruct.c,v $ $Revision: 1.2 $ $Date: 2003/11/05 16:49:52 $"; */
static int TRACE = 0;

#include "config.h"
#include "fp20_iqsutil.h"
#include "fp20_dstruct.h"
#include "fp20_qsopt.h"
#include "fp20_lpdefs.h"
#ifdef USEDMALLOC
#include "dmalloc.h"
#endif

/****************************************************************************/
/*                                                                          */
/*                            fp20_svector                                       */
/*                                                                          */
/*  Written by:  Applegate, Cook, Dash                                      */
/*  Date:                                                                   */
/*                                                                          */
/*    EXPORTED FUNCTIONS:                                                   */
/*                                                                          */
/****************************************************************************/

void fp20_ILLsvector_init (
  fp20_svector * s)
{
  s->nzcnt = 0;
  s->indx = 0;
  s->coef = 0;
}

void fp20_ILLsvector_free (
  fp20_svector * s)
{
  ILL_IFFREE (s->indx, int);

  fp20_EGlpNumFreeArray (s->coef);
  s->nzcnt = 0;
}

int fp20_ILLsvector_alloc (
  fp20_svector * s,
  int nzcnt)
{
  int rval = 0;

  s->nzcnt = nzcnt;
  if (nzcnt == 0)
  {
    s->indx = 0;
    s->coef = 0;
  }
  else
  {
    ILL_SAFE_MALLOC (s->indx, nzcnt, int);

    s->coef = fp20_EGlpNumAllocArray (nzcnt);
  }
  return 0;
CLEANUP:
  ILL_IFFREE (s->indx, int);
  fp20_EGlpNumFreeArray (s->coef);
  ILL_RETURN (rval, "fp20_ILLsvector_alloc");
}

int fp20_ILLsvector_copy (
  const fp20_svector * s_in,
  fp20_svector * s_out)
{
  int i;
  int nzcnt = s_in->nzcnt;
  int rval = 0;

  rval = fp20_ILLsvector_alloc (s_out, nzcnt);
  ILL_CLEANUP_IF (rval);
  for (i = 0; i < nzcnt; i++)
  {
    s_out->indx[i] = s_in->indx[i];
    fp20_EGlpNumCopy (s_out->coef[i], s_in->coef[i]);
  }

CLEANUP:
  ILL_RETURN (rval, "fp20_ILLsvector_copy");
}

/****************************************************************************/
/*                                                                          */
/*                            fp20_heap                                          */
/*                                                                          */
/*  Written by:  Applegate, Cook, Dash                                      */
/*  Date:                                                                   */
/*                                                                          */
/*    EXPORTED FUNCTIONS:                                                   */
/*                                                                          */
/****************************************************************************/

#define fp20_DEBUG_HEAP 0

#define fp20_HEAP_D 3
#define fp20_HEAP_UP(x) (((x)-1)/fp20_HEAP_D)
#define fp20_HEAP_DOWN(x) (((x)*fp20_HEAP_D)+1)

static int fp20_siftup (
  fp20_heap * h,
  int hloc,
  int ix),
  fp20_siftdown (
  fp20_heap * h,
  int hloc,
  int ix),
  fp20_maxchild (
  fp20_heap * h,
  int hloc);

static int fp20_siftup (
  fp20_heap * h,
  int hloc,
  int ix)
{
  int i = hloc;
  int p = fp20_HEAP_UP (i);
  EGfp20_t val;

  fp20_EGlpNumInitVar (val);
  fp20_EGlpNumCopy (val, h->key[ix]);

  while (i > 0 && fp20_EGlpNumIsLess (h->key[h->entry[p]], val))
  {
    h->entry[i] = h->entry[p];
    h->loc[h->entry[i]] = i;
    i = p;
    p = fp20_HEAP_UP (p);
  }
  h->entry[i] = ix;
  h->loc[ix] = i;
  ILL_IFTRACE2 ("%s:%la:%d:%d:%d\n", __func__, fp20_EGlpNumToLf (val), hloc, ix, i);
  fp20_EGlpNumClearVar (val);
  return i;
}

static int fp20_siftdown (
  fp20_heap * h,
  int hloc,
  int ix)
{
  int i = hloc;
  int c = fp20_maxchild (h, i);
  EGfp20_t val;

  fp20_EGlpNumInitVar (val);
  fp20_EGlpNumCopy (val, h->key[ix]);
  ILL_IFTRACE2 ("%s:%d:%d:%d:%la", __func__, hloc, ix, c, fp20_EGlpNumToLf (val));

  while (c != -1 && fp20_EGlpNumIsLess (val, h->key[h->entry[c]]))
  {
    h->entry[i] = h->entry[c];
    h->loc[h->entry[i]] = i;
    i = c;
    c = fp20_maxchild (h, c);
  }
  h->entry[i] = ix;
  h->loc[ix] = i;
  fp20_EGlpNumClearVar (val);
  ILL_IFTRACE2 ("%s:%d:%d\n", __func__, ix, i);
  return i;
}

//extern EGfp20_t fp20_ILL_MINDOUBLE;
static int fp20_maxchild (
  fp20_heap * h,
  int hloc)
{
  int i;
  int mc = -1;
  int hmin = fp20_HEAP_D * hloc + 1;
  int hmax = fp20_HEAP_D * hloc + fp20_HEAP_D;
  EGfp20_t val;

  fp20_EGlpNumInitVar (val);
  fp20_EGlpNumCopy (val, fp20_ILL_MINDOUBLE);
  ILL_IFTRACE2 (" %s:%d", __func__, hloc);

  for (i = hmin; i <= hmax && i < h->size; i++)
    if (fp20_EGlpNumIsLess (val, h->key[h->entry[i]]))
    {
      fp20_EGlpNumCopy (val, h->key[h->entry[i]]);
      mc = i;
      ILL_IFTRACE2 (":%d:%la", mc, fp20_EGlpNumToLf (val));
    }
  fp20_EGlpNumClearVar (val);
  ILL_IFTRACE2 ("\n");
  return mc;
}

#if fp20_DEBUG_HEAP > 0

static void fp20_printheap (
  fp20_heap * h)
{
  int i;

  printf ("entry (%d): ", h->size);
  for (i = 0; i < h->size; i++)
    printf ("%d ", h->entry[i]);
  printf ("\n loc: ");
  for (i = 0; i < h->maxsize; i++)
    printf ("%d ", h->loc[i]);
  printf ("\n key: ");
  for (i = 0; i < h->maxsize; i++)
    printf ("%la ", fp20_EGlpNumToLf (h->key[i]));
  printf ("\n key(sorted): ");
  for (i = 0; i < h->size; i++)
    printf ("%la ", fp20_EGlpNumToLf (h->key[h->entry[i]]));
  printf ("\n");
}

static void fp20_heapcheck (
  fp20_heap * h)
{
  int i, tcnt = 0;

  for (i = 0; i < h->maxsize; i++)
  {
    if (h->loc[i] < -1)
      printf ("error in fp20_heap\n");
    else if (h->loc[i] > -1)
      tcnt++;
  }
  if (tcnt != h->size)
    printf ("error 3 in fp20_heap\n");

  for (i = 0; i < h->size; i++)
  {
    if (h->loc[h->entry[i]] != i)
      printf ("error 1 in fp20_heap\n");
    if (!fp20_EGlpNumIsNeqqZero (h->key[h->entry[i]]))
      printf ("error 2 in fp20_heap\n");
    if (fp20_EGlpNumIsLess (h->key[h->entry[fp20_HEAP_UP (i)]], h->key[h->entry[i]]))
      printf ("error 4 in fp20_heap\n");
  }
}

#endif

void fp20_ILLheap_insert (
  fp20_heap * const h,
  int const ix)
{
  int i = h->size;

  ILL_IFTRACE ("%s:%d:%la\n", __func__, ix, fp20_EGlpNumToLf (h->key[ix]));

  i = fp20_siftup (h, i, ix);
  h->size++;

#if fp20_DEBUG_HEAP > 0
  fp20_heapcheck (h);
#endif
#if fp20_DEBUG_HEAP > 1
  fp20_printheap (h);
#endif
}

void fp20_ILLheap_modify (
  fp20_heap * const h,
  int const ix)
{
  int i = h->loc[ix];
  int pi = i;

  ILL_IFTRACE ("%s:%d\n", __func__, ix);

  if (h->loc[ix] == -1)
    return;
  i = fp20_siftup (h, i, ix);
  if (pi == i)
    i = fp20_siftdown (h, i, ix);

#if fp20_DEBUG_HEAP > 0
  fp20_heapcheck (h);
#endif
#if fp20_DEBUG_HEAP > 1
  fp20_printheap (h);
#endif
}

void fp20_ILLheap_delete (
  fp20_heap * const h,
  int const ix)
{
  int i = h->loc[ix];
  int pi = i;
  int nix = h->entry[h->size - 1];

  ILL_IFTRACE ("%s:%d:%d:%d\n", __func__, ix, nix, pi);

  h->loc[ix] = -1;
  h->size--;
  if (nix == ix)
  {
#if fp20_DEBUG_HEAP > 0
    fp20_heapcheck (h);
#endif
#if fp20_DEBUG_HEAP > 1
    fp20_printheap (h);
#endif
    return;
  }

  h->entry[i] = nix;
  h->loc[nix] = i;

  i = fp20_siftup (h, i, nix);
  ILL_IFTRACE ("%s:%d:%d:%d:%d\n", __func__, ix, nix, pi, i);
  if (pi == i)
    fp20_siftdown (h, i, nix);

#if fp20_DEBUG_HEAP > 0
  fp20_heapcheck (h);
#endif
#if fp20_DEBUG_HEAP > 1
  fp20_printheap (h);
#endif
}

int fp20_ILLheap_findmin (
  fp20_heap * const h)
{
  if (h->hexist == 0 || h->size <= 0)
    return -1;
  return h->entry[0];
}

void fp20_ILLheap_init (
  fp20_heap * const h)
{
  h->entry = NULL;
  h->loc = NULL;
  h->key = NULL;
  h->hexist = 0;
}

int fp20_ILLheap_build (
  fp20_heap * const h,
  int const nelems,
  EGfp20_t * key)
{
  int rval = 0;
  int i, n = 0;

  ILL_IFTRACE ("%s:%d\n", __func__, nelems);

  h->hexist = 1;
  h->size = 0;
  h->maxsize = nelems;
  h->key = key;
  ILL_SAFE_MALLOC (h->entry, nelems, int);
  ILL_SAFE_MALLOC (h->loc, nelems, int);

  for (i = 0; i < nelems; i++)
  {
    if (fp20_EGlpNumIsGreatZero (key[i]))
    {
      h->entry[n] = i;
      h->loc[i] = n;
      n++;
    }
    else
      h->loc[i] = -1;
  }
  h->size = n;
  for (i = n - 1; i >= 0; i--)
  {
    ILL_IFTRACE2 ("insert %la\n", fp20_EGlpNumToLf (h->key[h->entry[i]]));
    fp20_siftdown (h, i, h->entry[i]);
  }

#if fp20_DEBUG_HEAP > 0
  fp20_heapcheck (h);
#endif
#if fp20_DEBUG_HEAP > 1
  fp20_printheap (h);
#endif

CLEANUP:
  if (rval)
    fp20_ILLheap_free (h);
  ILL_RETURN (rval, "fp20_ILLheap_init");
}

void fp20_ILLheap_free (
  fp20_heap * const h)
{
  if (h->hexist)
  {
    ILL_IFFREE (h->entry, int);
    ILL_IFFREE (h->loc, int);

    h->hexist = 0;
    h->maxsize = 0;
    h->size = 0;
  }
}


/****************************************************************************/
/*                                                                          */
/*                          matrix                                          */
/*                                                                          */
/*  Written by:  Applegate, Cook, Dash                                      */
/*  Date:                                                                   */
/*                                                                          */
/*    EXPORTED FUNCTIONS:                                                   */
/*                                                                          */
/****************************************************************************/

void fp20_ILLmatrix_init (
  fp20_ILLmatrix * A)
{
  if (A)
  {
    A->matval = 0;
    A->matcnt = 0;
    A->matbeg = 0;
    A->matind = 0;
    A->matcols = 0;
    A->matcolsize = 0;
    A->matrows = 0;
    A->matsize = 0;
    A->matfree = 0;
  }
}

void fp20_ILLmatrix_free (
  fp20_ILLmatrix * A)
{
  if (A)
  {
    fp20_EGlpNumFreeArray (A->matval);
    ILL_IFFREE (A->matcnt, int);
    ILL_IFFREE (A->matbeg, int);
    ILL_IFFREE (A->matind, int);

    fp20_ILLmatrix_init (A);
  }
}

void fp20_ILLmatrix_prt (
  EGioFile_t * fd,
  fp20_ILLmatrix * A)
{
  int j, k;

  if (A == NULL)
  {
    EGioPrintf (fd, "Matrix %p: empty\n", (void *) A);
  }
  else
  {
    EGioPrintf (fd, "Matrix %p: nrows = %d ncols = %d\n",
             (void *) A, A->matrows, A->matcols);
    for (j = 0; j < A->matcols; j++)
    {
      EGioPrintf (fd, "col %d: ", j);
      for (k = A->matbeg[j]; k < A->matbeg[j] + A->matcnt[j]; k++)
      {
        EGioPrintf (fd, "row %d=%.3f ", A->matind[k], fp20_EGlpNumToLf (A->matval[k]));
      }
      EGioPrintf (fd, "\n");
    }
  }
}

---