CoinUtils/src/CoinModelUseful.cpp

/* $Id: CoinModelUseful.cpp 2083 2019-01-06 19:38:09Z unxusr $ */
// Copyright (C) 2005, International Business Machines
// Corporation and others.  All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).

#include "CoinPragma.hpp"

#include <cstdlib>
#include <cmath>
#include <cassert>
#include <cfloat>
#include <string>
#include <cstdio>
#include <iostream>

#include "CoinHelperFunctions.hpp"

#include "CoinModelUseful.hpp"

//#############################################################################
// Constructors / Destructor / Assignment
//#############################################################################

//-------------------------------------------------------------------
// Default Constructor
//-------------------------------------------------------------------
CoinModelLink::CoinModelLink()
  : row_(-1)
  , column_(-1)
  , value_(0.0)
  , position_(-1)
  , onRow_(true)
{
}

//-------------------------------------------------------------------
// Copy constructor
//-------------------------------------------------------------------
CoinModelLink::CoinModelLink(const CoinModelLink &rhs)
  : row_(rhs.row_)
  , column_(rhs.column_)
  , value_(rhs.value_)
  , position_(rhs.position_)
  , onRow_(rhs.onRow_)
{
}

//-------------------------------------------------------------------
// Destructor
//-------------------------------------------------------------------
CoinModelLink::~CoinModelLink()
{
}

//----------------------------------------------------------------
// Assignment operator
//-------------------------------------------------------------------
CoinModelLink &
CoinModelLink::operator=(const CoinModelLink &rhs)
{
  if (this != &rhs) {
    row_ = rhs.row_;
    column_ = rhs.column_;
    value_ = rhs.value_;
    position_ = rhs.position_;
    onRow_ = rhs.onRow_;
  }
  return *this;
}

namespace {
const int mmult[] = {
  262139, 259459, 256889, 254291, 251701, 249133, 246709, 244247,
  241667, 239179, 236609, 233983, 231289, 228859, 226357, 223829,
  221281, 218849, 216319, 213721, 211093, 208673, 206263, 203773,
  201233, 198637, 196159, 193603, 191161, 188701, 186149, 183761,
  181303, 178873, 176389, 173897, 171469, 169049, 166471, 163871,
  161387, 158941, 156437, 153949, 151531, 149159, 146749, 144299,
  141709, 139369, 136889, 134591, 132169, 129641, 127343, 124853,
  122477, 120163, 117757, 115361, 112979, 110567, 108179, 105727,
  103387, 101021, 98639, 96179, 93911, 91583, 89317, 86939, 84521,
  82183, 79939, 77587, 75307, 72959, 70793, 68447, 66103
};
const int lengthMult = static_cast< int >(sizeof(mmult) / sizeof(int));
}

//#############################################################################
// Constructors / Destructor / Assignment
//#############################################################################

//-------------------------------------------------------------------
// Default Constructor
//-------------------------------------------------------------------
CoinModelHash::CoinModelHash()
  : names_(NULL)
  , hash_(NULL)
  , numberItems_(0)
  , maximumItems_(0)
  , lastSlot_(-1)
{
}

//-------------------------------------------------------------------
// Copy constructor
//-------------------------------------------------------------------
CoinModelHash::CoinModelHash(const CoinModelHash &rhs)
  : names_(NULL)
  , hash_(NULL)
  , numberItems_(rhs.numberItems_)
  , maximumItems_(rhs.maximumItems_)
  , lastSlot_(rhs.lastSlot_)
{
  if (maximumItems_) {
    names_ = new char *[maximumItems_];
    for (int i = 0; i < maximumItems_; i++) {
      names_[i] = CoinStrdup(rhs.names_[i]);
    }
    hash_ = CoinCopyOfArray(rhs.hash_, 4 * maximumItems_);
  }
}

//-------------------------------------------------------------------
// Destructor
//-------------------------------------------------------------------
CoinModelHash::~CoinModelHash()
{
  for (int i = 0; i < maximumItems_; i++)
    free(names_[i]);
  delete[] names_;
  delete[] hash_;
}

//----------------------------------------------------------------
// Assignment operator
//-------------------------------------------------------------------
CoinModelHash &
CoinModelHash::operator=(const CoinModelHash &rhs)
{
  if (this != &rhs) {
    for (int i = 0; i < maximumItems_; i++)
      free(names_[i]);
    delete[] names_;
    delete[] hash_;
    numberItems_ = rhs.numberItems_;
    maximumItems_ = rhs.maximumItems_;
    lastSlot_ = rhs.lastSlot_;
    if (maximumItems_) {
      names_ = new char *[maximumItems_];
      for (int i = 0; i < maximumItems_; i++) {
        names_[i] = CoinStrdup(rhs.names_[i]);
      }
      hash_ = CoinCopyOfArray(rhs.hash_, 4 * maximumItems_);
    } else {
      names_ = NULL;
      hash_ = NULL;
    }
  }
  return *this;
}
// Set number of items
void CoinModelHash::setNumberItems(int number)
{
  assert(number >= 0 && number <= numberItems_);
  numberItems_ = number;
}
// Resize hash (also re-hashs)
void CoinModelHash::resize(int maxItems, bool forceReHash)
{
  assert(numberItems_ <= maximumItems_);
  if (maxItems <= maximumItems_ && !forceReHash)
    return;
  int n = maximumItems_;
  maximumItems_ = maxItems;
  char **names = new char *[maximumItems_];
  int i;
  for (i = 0; i < n; i++)
    names[i] = names_[i];
  for (; i < maximumItems_; i++)
    names[i] = NULL;
  delete[] names_;
  names_ = names;
  delete[] hash_;
  int maxHash = 4 * maximumItems_;
  hash_ = new CoinModelHashLink[maxHash];
  int ipos;

  for (i = 0; i < maxHash; i++) {
    hash_[i].index = -1;
    hash_[i].next = -1;
  }

  /*
   * Initialize the hash table.  Only the index of the first name that
   * hashes to a value is entered in the table; subsequent names that
   * collide with it are not entered.
   */
  for (i = 0; i < numberItems_; ++i) {
    if (names_[i]) {
      ipos = hashValue(names_[i]);
      if (hash_[ipos].index == -1) {
        hash_[ipos].index = i;
      }
    }
  }

  /*
   * Now take care of the names that collided in the preceding loop,
   * by finding some other entry in the table for them.
   * Since there are as many entries in the table as there are names,
   * there must be room for them.
   */
  lastSlot_ = -1;
  for (i = 0; i < numberItems_; ++i) {
    if (!names_[i])
      continue;
    char *thisName = names[i];
    ipos = hashValue(thisName);

    while (true) {
      int j1 = hash_[ipos].index;

      if (j1 == i)
        break;
      else {
        char *thisName2 = names[j1];

        if (strcmp(thisName, thisName2) == 0) {
          printf("** duplicate name %s\n", names[i]);
          abort();
          break;
        } else {
          int k = hash_[ipos].next;

          if (k == -1) {
            while (true) {
              ++lastSlot_;
              if (lastSlot_ > numberItems_) {
                printf("** too many names\n");
                abort();
                break;
              }
              if (hash_[lastSlot_].index == -1) {
                break;
              }
            }
            hash_[ipos].next = lastSlot_;
            hash_[lastSlot_].index = i;
            break;
          } else {
            ipos = k;
            /* nothing worked - try it again */
          }
        }
      }
    }
  }
}
// validate
void CoinModelHash::validateHash() const
{
  for (int i = 0; i < numberItems_; ++i) {
    if (names_[i]) {
      assert(hash(names_[i]) >= 0);
    }
  }
}
// Returns index or -1
int CoinModelHash::hash(const char *name) const
{
  int found = -1;

  int ipos;

  /* default if we don't find anything */
  if (!numberItems_)
    return -1;

  ipos = hashValue(name);
  while (true) {
    int j1 = hash_[ipos].index;

    if (j1 >= 0) {
      char *thisName2 = names_[j1];

      if (strcmp(name, thisName2) != 0) {
        int k = hash_[ipos].next;

        if (k != -1)
          ipos = k;
        else
          break;
      } else {
        found = j1;
        break;
      }
    } else {
      int k = hash_[ipos].next;

      if (k != -1)
        ipos = k;
      else
        break;
    }
  }
  return found;
}
// Adds to hash
void CoinModelHash::addHash(int index, const char *name)
{
  // resize if necessary
  if (numberItems_ >= maximumItems_)
    resize(1000 + 3 * numberItems_ / 2);
  assert(!names_[index]);
  names_[index] = CoinStrdup(name);
  int ipos = hashValue(name);
  numberItems_ = CoinMax(numberItems_, index + 1);
  if (hash_[ipos].index < 0) {
    hash_[ipos].index = index;
  } else {
    while (true) {
      int j1 = hash_[ipos].index;

      if (j1 == index)
        break; // duplicate?
      else {
        if (j1 >= 0) {
          char *thisName2 = names_[j1];
          if (strcmp(name, thisName2) == 0) {
            printf("** duplicate name %s\n", names_[index]);
            abort();
            break;
          } else {
            int k = hash_[ipos].next;

            if (k == -1) {
              while (true) {
                ++lastSlot_;
                if (lastSlot_ > numberItems_) {
                  printf("** too many names\n");
                  abort();
                  break;
                }
                if (hash_[lastSlot_].index < 0 && hash_[lastSlot_].next < 0) {
                  break;
                }
              }
              hash_[ipos].next = lastSlot_;
              hash_[lastSlot_].index = index;
              hash_[lastSlot_].next = -1;
              break;
            } else {
              ipos = k;
            }
          }
        } else {
          //slot available
          hash_[ipos].index = index;
        }
      }
    }
  }
}
// Deletes from hash
void CoinModelHash::deleteHash(int index)
{
  if (index < numberItems_ && names_[index]) {

    int ipos = hashValue(names_[index]);

    while (ipos >= 0) {
      int j1 = hash_[ipos].index;
      if (j1 != index) {
        ipos = hash_[ipos].next;
      } else {
        hash_[ipos].index = -1; // available
        break;
      }
    }
    assert(ipos >= 0);
    free(names_[index]);
    names_[index] = NULL;
  }
}
// Returns name at position (or NULL)
const char *
CoinModelHash::name(int which) const
{
  if (which < numberItems_)
    return names_[which];
  else
    return NULL;
}
// Returns non const name at position (or NULL)
char *
CoinModelHash::getName(int which) const
{
  if (which < numberItems_)
    return names_[which];
  else
    return NULL;
}
// Sets name at position (does not create)
void CoinModelHash::setName(int which, char *name)
{
  if (which < numberItems_)
    names_[which] = name;
}
// Returns a hash value
int CoinModelHash::hashValue(const char *name) const
{

  int n = 0;
  int j;
  int length = static_cast< int >(strlen(name));
  // may get better spread with unsigned
  const unsigned char *name2 = reinterpret_cast< const unsigned char * >(name);
  while (length) {
    int length2 = CoinMin(length, lengthMult);
    for (j = 0; j < length2; ++j) {
      n += mmult[j] * name2[j];
    }
    name += length2;
    length -= length2;
  }
  int maxHash = 4 * maximumItems_;
  return (abs(n) % maxHash); /* integer abs */
}
//#############################################################################
// Constructors / Destructor / Assignment
//#############################################################################
//-------------------------------------------------------------------
// Default Constructor
//-------------------------------------------------------------------
CoinModelHash2::CoinModelHash2()
  : hash_(NULL)
  , numberItems_(0)
  , maximumItems_(0)
  , lastSlot_(-1)
{
}

//-------------------------------------------------------------------
// Copy constructor
//-------------------------------------------------------------------
CoinModelHash2::CoinModelHash2(const CoinModelHash2 &rhs)
  : hash_(NULL)
  , numberItems_(rhs.numberItems_)
  , maximumItems_(rhs.maximumItems_)
  , lastSlot_(rhs.lastSlot_)
{
  if (maximumItems_) {
    hash_ = CoinCopyOfArray(rhs.hash_, 4 * maximumItems_);
  }
}

//-------------------------------------------------------------------
// Destructor
//-------------------------------------------------------------------
CoinModelHash2::~CoinModelHash2()
{
  delete[] hash_;
}

//----------------------------------------------------------------
// Assignment operator
//-------------------------------------------------------------------
CoinModelHash2 &
CoinModelHash2::operator=(const CoinModelHash2 &rhs)
{
  if (this != &rhs) {
    delete[] hash_;
    numberItems_ = rhs.numberItems_;
    maximumItems_ = rhs.maximumItems_;
    lastSlot_ = rhs.lastSlot_;
    if (maximumItems_) {
      hash_ = CoinCopyOfArray(rhs.hash_, 4 * maximumItems_);
    } else {
      hash_ = NULL;
    }
  }
  return *this;
}
// Set number of items
void CoinModelHash2::setNumberItems(CoinBigIndex number)
{
  assert(number >= 0 && (number <= numberItems_ || !numberItems_));
  numberItems_ = number;
}
// Resize hash (also re-hashs)
void CoinModelHash2::resize(CoinBigIndex maxItems, const CoinModelTriple *triples, bool forceReHash)
{
  assert(numberItems_ <= maximumItems_ || !maximumItems_);
  if (maxItems <= maximumItems_ && !forceReHash)
    return;
  if (maxItems > maximumItems_) {
    maximumItems_ = maxItems;
    delete[] hash_;
    hash_ = new CoinModelHashLink2[4 * maximumItems_];
  }
  CoinBigIndex maxHash = 4 * maximumItems_;
  CoinBigIndex ipos;
  CoinBigIndex i;
  for (i = 0; i < maxHash; i++) {
    hash_[i].index = -1;
    hash_[i].next = -1;
  }

  /*
   * Initialize the hash table.  Only the index of the first name that
   * hashes to a value is entered in the table; subsequent names that
   * collide with it are not entered.
   */
  for (i = 0; i < numberItems_; ++i) {
    int row = static_cast< int >(rowInTriple(triples[i]));
    int column = triples[i].column;
    if (column >= 0) {
      ipos = hashValue(row, column);
      if (hash_[ipos].index == -1) {
        hash_[ipos].index = i;
      }
    }
  }

  /*
   * Now take care of the entries that collided in the preceding loop,
   * by finding some other entry in the table for them.
   * Since there are as many entries in the table as there are entries,
   * there must be room for them.
   */
  lastSlot_ = -1;
  for (i = 0; i < numberItems_; ++i) {
    int row = static_cast< int >(rowInTriple(triples[i]));
    int column = triples[i].column;
    if (column >= 0) {
      ipos = hashValue(row, column);

      while (true) {
        CoinBigIndex j1 = hash_[ipos].index;

        if (j1 == i)
          break;
        else {
          int row2 = static_cast< int >(rowInTriple(triples[j1]));
          int column2 = triples[j1].column;
          if (row == row2 && column == column2) {
            printf("** duplicate entry %d %d\n", row, column);
            abort();
            break;
          } else {
            CoinBigIndex k = hash_[ipos].next;

            if (k == -1) {
              while (true) {
                ++lastSlot_;
                if (lastSlot_ > numberItems_) {
                  printf("** too many entries\n");
                  abort();
                  break;
                }
                if (hash_[lastSlot_].index == -1) {
                  break;
                }
              }
              hash_[ipos].next = lastSlot_;
              hash_[lastSlot_].index = i;
              break;
            } else {
              ipos = k;
            }
          }
        }
      }
    }
  }
}
// Returns index or -1
CoinBigIndex
CoinModelHash2::hash(int row, int column, const CoinModelTriple *triples) const
{
  CoinBigIndex found = -1;

  CoinBigIndex ipos;

  /* default if we don't find anything */
  if (!numberItems_)
    return -1;

  ipos = hashValue(row, column);
  while (true) {
    CoinBigIndex j1 = hash_[ipos].index;

    if (j1 >= 0) {
      int row2 = static_cast< int >(rowInTriple(triples[j1]));
      int column2 = triples[j1].column;
      if (row != row2 || column != column2) {
        CoinBigIndex k = hash_[ipos].next;

        if (k != -1)
          ipos = k;
        else
          break;
      } else {
        found = j1;
        break;
      }
    } else {
      CoinBigIndex k = hash_[ipos].next;

      if (k != -1)
        ipos = k;
      else
        break;
    }
  }
  return found;
}
// Adds to hash
void CoinModelHash2::addHash(CoinBigIndex index, int row, int column, const CoinModelTriple *triples)
{
  // resize if necessary
  if (numberItems_ >= maximumItems_ || index + 1 >= maximumItems_)
    resize(CoinMax(1000 + 3 * numberItems_ / 2, index + 1), triples);
  CoinBigIndex ipos = hashValue(row, column);
  numberItems_ = CoinMax(numberItems_, index + 1);
  assert(numberItems_ <= maximumItems_);
  if (hash_[ipos].index < 0) {
    hash_[ipos].index = index;
  } else {
    while (true) {
      CoinBigIndex j1 = hash_[ipos].index;

      if (j1 == index) {
        break; // duplicate??
      } else {
        if (j1 >= 0) {
          int row2 = static_cast< int >(rowInTriple(triples[j1]));
          int column2 = triples[j1].column;
          if (row == row2 && column == column2) {
            printf("** duplicate entry %d %d\n", row, column);
            abort();
            break;
          } else {
            CoinBigIndex k = hash_[ipos].next;

            if (k == -1) {
              while (true) {
                ++lastSlot_;
                if (lastSlot_ > numberItems_) {
                  printf("** too many entrys\n");
                  abort();
                  break;
                }
                if (hash_[lastSlot_].index < 0) {
                  break;
                }
              }
              hash_[ipos].next = lastSlot_;
              hash_[lastSlot_].index = index;
              hash_[lastSlot_].next = -1;
              break;
            } else {
              ipos = k;
            }
          }
        } else {
          // slot available
          hash_[ipos].index = index;
        }
      }
    }
  }
}
// Deletes from hash
void CoinModelHash2::deleteHash(CoinBigIndex index, int row, int column)
{
  if (index < numberItems_) {

    CoinBigIndex ipos = hashValue(row, column);

    while (ipos >= 0) {
      CoinBigIndex j1 = hash_[ipos].index;
      if (j1 != index) {
        ipos = hash_[ipos].next;
      } else {
        hash_[ipos].index = -1; // available
        break;
      }
    }
  }
}
namespace {
const int mmult2[] = {
  262139, 259459, 256889, 254291, 251701, 249133, 246709, 244247,
  241667, 239179, 236609, 233983, 231289, 228859, 226357, 223829
};
}
// Returns a hash value
CoinBigIndex
CoinModelHash2::hashValue(int row, int column) const
{

  // Optimizer should take out one side of if
  if (sizeof(int) == 4 * sizeof(char)) {
    unsigned char tempChar[4];

    unsigned int n = 0;
    int *temp = reinterpret_cast< int * >(tempChar);
    *temp = row;
    n += mmult2[0] * tempChar[0];
    n += mmult2[1] * tempChar[1];
    n += mmult2[2] * tempChar[2];
    n += mmult[3] * tempChar[3];
    *temp = column;
    n += mmult2[0 + 8] * tempChar[0];
    n += mmult2[1 + 8] * tempChar[1];
    n += mmult2[2 + 8] * tempChar[2];
    n += mmult2[3 + 8] * tempChar[3];
    return n % (maximumItems_ << 1);
  } else {
    // ints are 8
    unsigned char tempChar[8];

    int n = 0;
    unsigned int j;
    int *temp = reinterpret_cast< int * >(tempChar);
    *temp = row;
    for (j = 0; j < sizeof(int); ++j) {
      int itemp = tempChar[j];
      n += mmult2[j] * itemp;
    }
    *temp = column;
    for (j = 0; j < sizeof(int); ++j) {
      int itemp = tempChar[j];
      n += mmult2[j + 8] * itemp;
    }
    CoinBigIndex maxHash = 4 * maximumItems_;
    CoinBigIndex absN = abs(n);
    CoinBigIndex returnValue = absN % maxHash;
    return returnValue;
  }
}
//#############################################################################
// Constructors / Destructor / Assignment
//#############################################################################

//-------------------------------------------------------------------
// Default Constructor
//-------------------------------------------------------------------
CoinModelLinkedList::CoinModelLinkedList()
  : previous_(NULL)
  , next_(NULL)
  , first_(NULL)
  , last_(NULL)
  , numberMajor_(0)
  , maximumMajor_(0)
  , numberElements_(0)
  , maximumElements_(0)
  , type_(-1)
{
}

//-------------------------------------------------------------------
// Copy constructor
//-------------------------------------------------------------------
CoinModelLinkedList::CoinModelLinkedList(const CoinModelLinkedList &rhs)
  : numberMajor_(rhs.numberMajor_)
  , maximumMajor_(rhs.maximumMajor_)
  , numberElements_(rhs.numberElements_)
  , maximumElements_(rhs.maximumElements_)
  , type_(rhs.type_)
{
  if (maximumMajor_) {
    previous_ = CoinCopyOfArray(rhs.previous_, maximumElements_);
    next_ = CoinCopyOfArray(rhs.next_, maximumElements_);
    first_ = CoinCopyOfArray(rhs.first_, maximumMajor_ + 1);
    last_ = CoinCopyOfArray(rhs.last_, maximumMajor_ + 1);
  } else {
    previous_ = NULL;
    next_ = NULL;
    first_ = NULL;
    last_ = NULL;
  }
}

//-------------------------------------------------------------------
// Destructor
//-------------------------------------------------------------------
CoinModelLinkedList::~CoinModelLinkedList()
{
  delete[] previous_;
  delete[] next_;
  delete[] first_;
  delete[] last_;
}

//----------------------------------------------------------------
// Assignment operator
//-------------------------------------------------------------------
CoinModelLinkedList &
CoinModelLinkedList::operator=(const CoinModelLinkedList &rhs)
{
  if (this != &rhs) {
    delete[] previous_;
    delete[] next_;
    delete[] first_;
    delete[] last_;
    numberMajor_ = rhs.numberMajor_;
    maximumMajor_ = rhs.maximumMajor_;
    numberElements_ = rhs.numberElements_;
    maximumElements_ = rhs.maximumElements_;
    type_ = rhs.type_;
    if (maximumMajor_) {
      previous_ = CoinCopyOfArray(rhs.previous_, maximumElements_);
      next_ = CoinCopyOfArray(rhs.next_, maximumElements_);
      first_ = CoinCopyOfArray(rhs.first_, maximumMajor_ + 1);
      last_ = CoinCopyOfArray(rhs.last_, maximumMajor_ + 1);
    } else {
      previous_ = NULL;
      next_ = NULL;
      first_ = NULL;
      last_ = NULL;
    }
  }
  return *this;
}
// Resize list - for row list maxMajor is maximum rows
void CoinModelLinkedList::resize(int maxMajor, CoinBigIndex maxElements)
{
  maxMajor = CoinMax(maxMajor, maximumMajor_);
  maxElements = CoinMax(maxElements, maximumElements_);
  if (maxMajor > maximumMajor_) {
    CoinBigIndex *first = new CoinBigIndex[maxMajor + 1];
    CoinBigIndex free;
    if (maximumMajor_) {
      CoinMemcpyN(first_, maximumMajor_, first);
#ifdef ZEROFAULT
      memset(first + maximumMajor_, 0, (maxMajor - maximumMajor_) * sizeof(CoinBigIndex));
#endif
      free = first_[maximumMajor_];
      first[maximumMajor_] = -1;
    } else {
      free = -1;
    }
    first[maxMajor] = free;
    delete[] first_;
    first_ = first;
    CoinBigIndex *last = new CoinBigIndex[maxMajor + 1];
    if (maximumMajor_) {
      CoinMemcpyN(last_, maximumMajor_, last);
#ifdef ZEROFAULT
      memset(last + maximumMajor_, 0, (maxMajor - maximumMajor_) * sizeof(CoinBigIndex));
#endif
      free = last_[maximumMajor_];
      last[maximumMajor_] = -1;
    } else {
      free = -1;
    }
    last[maxMajor] = free;
    delete[] last_;
    last_ = last;
    maximumMajor_ = maxMajor;
  }
  if (maxElements > maximumElements_) {
    CoinBigIndex *previous = new CoinBigIndex[maxElements];
    CoinMemcpyN(previous_, numberElements_, previous);
#ifdef ZEROFAULT
    memset(previous + numberElements_, 0,
      (maxElements - numberElements_) * sizeof(CoinBigIndex));
#endif
    delete[] previous_;
    previous_ = previous;
    CoinBigIndex *next = new CoinBigIndex[maxElements];
    CoinMemcpyN(next_, numberElements_, next);
#ifdef ZEROFAULT
    memset(next + numberElements_, 0, (maxElements - numberElements_) * sizeof(CoinBigIndex));
#endif
    delete[] next_;
    next_ = next;
    maximumElements_ = maxElements;
  }
}
// Create list - for row list maxMajor is maximum rows
void CoinModelLinkedList::create(int maxMajor, CoinBigIndex maxElements,
  int numberMajor, int /*numberMinor*/, int type,
  CoinBigIndex numberElements, const CoinModelTriple *triples)
{
  maxMajor = CoinMax(maxMajor, maximumMajor_);
  maxMajor = CoinMax(maxMajor, numberMajor);
  maxElements = CoinMax(maxElements, maximumElements_);
  maxElements = CoinMax(maxElements, numberElements);
  type_ = type;
  assert(!previous_);
  previous_ = new CoinBigIndex[maxElements];
  next_ = new CoinBigIndex[maxElements];
  maximumElements_ = maxElements;
  assert(maxElements >= numberElements);
  assert(maxMajor > 0 && !maximumMajor_);
  first_ = new CoinBigIndex[maxMajor + 1];
  last_ = new CoinBigIndex[maxMajor + 1];
#ifdef ZEROFAULT
  memset(previous_, 0, maxElements * sizeof(CoinBigIndex));
  memset(next_, 0, maxElements * sizeof(CoinBigIndex));
  memset(first_, 0, (maxMajor + 1) * sizeof(CoinBigIndex));
  memset(last_, 0, (maxMajor + 1) * sizeof(CoinBigIndex));
#endif
  assert(numberElements >= 0);
  numberElements_ = numberElements;
  maximumMajor_ = maxMajor;
  // do lists
  int i;
  for (i = 0; i < numberMajor; i++) {
    first_[i] = -1;
    last_[i] = -1;
  }
  first_[maximumMajor_] = -1;
  last_[maximumMajor_] = -1;
  int freeChain = -1;
  for (i = 0; i < numberElements; i++) {
    if (triples[i].column >= 0) {
      int iMajor;
      if (!type_) {
        // for rows
        iMajor = static_cast< int >(rowInTriple(triples[i]));
      } else {
        iMajor = triples[i].column;
      }
      assert(iMajor < numberMajor);
      if (first_[iMajor] >= 0) {
        // not first
        CoinBigIndex j = last_[iMajor];
        next_[j] = i;
        previous_[i] = j;
      } else {
        // first
        first_[iMajor] = i;
        previous_[i] = -1;
      }
      last_[iMajor] = i;
    } else {
      // on deleted list
      if (freeChain >= 0) {
        next_[freeChain] = i;
        previous_[i] = freeChain;
      } else {
        first_[maximumMajor_] = i;
        previous_[i] = -1;
      }
      freeChain = i;
    }
  }
  // Now clean up
  if (freeChain >= 0) {
    next_[freeChain] = -1;
    last_[maximumMajor_] = freeChain;
  }
  for (i = 0; i < numberMajor; i++) {
    CoinBigIndex k = last_[i];
    if (k >= 0) {
      next_[k] = -1;
      last_[i] = k;
    }
  }
  numberMajor_ = numberMajor;
}
/* Adds to list - easy case i.e. add row to row list
   Returns where chain starts
*/
CoinBigIndex
CoinModelLinkedList::addEasy(int majorIndex, CoinBigIndex numberOfElements, const int *indices,
  const double *elements, CoinModelTriple *triples,
  CoinModelHash2 &hash)
{
  assert(majorIndex < maximumMajor_);
  if (numberOfElements + numberElements_ > maximumElements_) {
    resize(maximumMajor_, (3 * (numberElements_ + numberOfElements)) / 2 + 1000);
  }
  CoinBigIndex first = -1;
  if (majorIndex >= numberMajor_) {
    for (int i = numberMajor_; i <= majorIndex; i++) {
      first_[i] = -1;
      last_[i] = -1;
    }
  }
  if (numberOfElements) {
    bool doHash = hash.maximumItems() != 0;
    CoinBigIndex lastFree = last_[maximumMajor_];
    CoinBigIndex last = last_[majorIndex];
    for (int i = 0; i < numberOfElements; i++) {
      CoinBigIndex put;
      if (lastFree >= 0) {
        put = lastFree;
        lastFree = previous_[lastFree];
      } else {
        put = numberElements_;
        assert(put < maximumElements_);
        numberElements_++;
      }
      if (type_ == 0) {
        // row
        setRowAndStringInTriple(triples[put], majorIndex, false);
        triples[put].column = indices[i];
      } else {
        // column
        setRowAndStringInTriple(triples[put], indices[i], false);
        triples[put].column = majorIndex;
      }
      triples[put].value = elements[i];
      if (doHash)
        hash.addHash(put, static_cast< int >(rowInTriple(triples[put])), triples[put].column, triples);
      if (last >= 0) {
        next_[last] = put;
      } else {
        first_[majorIndex] = put;
      }
      previous_[put] = last;
      last = put;
    }
    next_[last] = -1;
    if (last_[majorIndex] < 0) {
      // first in row
      first = first_[majorIndex];
    } else {
      first = next_[last_[majorIndex]];
    }
    last_[majorIndex] = last;
    if (lastFree >= 0) {
      next_[lastFree] = -1;
      last_[maximumMajor_] = lastFree;
    } else {
      first_[maximumMajor_] = -1;
      last_[maximumMajor_] = -1;
    }
  }
  numberMajor_ = CoinMax(numberMajor_, majorIndex + 1);
  return first;
}
/* Adds to list - hard case i.e. add row to column list
 */
void CoinModelLinkedList::addHard(int minorIndex, CoinBigIndex numberOfElements, const int *indices,
  const double *elements, CoinModelTriple *triples,
  CoinModelHash2 &hash)
{
  CoinBigIndex lastFree = last_[maximumMajor_];
  bool doHash = hash.maximumItems() != 0;
  for (int i = 0; i < numberOfElements; i++) {
    CoinBigIndex put;
    if (lastFree >= 0) {
      put = lastFree;
      lastFree = previous_[lastFree];
    } else {
      put = numberElements_;
      assert(put < maximumElements_);
      numberElements_++;
    }
    int other = indices[i];
    if (type_ == 0) {
      // row
      setRowAndStringInTriple(triples[put], other, false);
      triples[put].column = minorIndex;
    } else {
      // column
      setRowAndStringInTriple(triples[put], minorIndex, false);
      triples[put].column = other;
    }
    triples[put].value = elements[i];
    if (doHash)
      hash.addHash(put, static_cast< int >(rowInTriple(triples[put])), triples[put].column, triples);
    if (other >= numberMajor_) {
      // Need to fill in null values
      fill(numberMajor_, other + 1);
      numberMajor_ = other + 1;
    }
    CoinBigIndex last = last_[other];
    if (last >= 0) {
      next_[last] = put;
    } else {
      first_[other] = put;
    }
    previous_[put] = last;
    next_[put] = -1;
    last_[other] = put;
  }
  if (lastFree >= 0) {
    next_[lastFree] = -1;
    last_[maximumMajor_] = lastFree;
  } else {
    first_[maximumMajor_] = -1;
    last_[maximumMajor_] = -1;
  }
}
/* Adds to list - hard case i.e. add row to column list
   This is when elements have been added to other copy
*/
void CoinModelLinkedList::addHard(CoinBigIndex first, const CoinModelTriple *triples,
  CoinBigIndex firstFree, CoinBigIndex lastFree, const CoinBigIndex *next)
{
  first_[maximumMajor_] = firstFree;
  last_[maximumMajor_] = lastFree;
  CoinBigIndex put = first;
  int minorIndex = -1;
  while (put >= 0) {
    assert(put < maximumElements_);
    numberElements_ = CoinMax(numberElements_, put + 1);
    int other;
    if (type_ == 0) {
      // row
      other = rowInTriple(triples[put]);
      if (minorIndex >= 0)
        assert(triples[put].column == minorIndex);
      else
        minorIndex = triples[put].column;
    } else {
      // column
      other = triples[put].column;
      if (minorIndex >= 0)
        assert(static_cast< int >(rowInTriple(triples[put])) == minorIndex);
      else
        minorIndex = rowInTriple(triples[put]);
    }
    assert(other < maximumMajor_);
    if (other >= numberMajor_) {
      // Need to fill in null values
      fill(numberMajor_, other + 1);
      numberMajor_ = other + 1;
    }
    CoinBigIndex last = last_[other];
    if (last >= 0) {
      next_[last] = put;
    } else {
      first_[other] = put;
    }
    previous_[put] = last;
    next_[put] = -1;
    last_[other] = put;
    put = next[put];
  }
}
/* Deletes from list - same case i.e. delete row from row list
*/
void CoinModelLinkedList::deleteSame(int which, CoinModelTriple *triples,
  CoinModelHash2 &hash, bool zapTriples)
{
  assert(which >= 0);
  if (which < numberMajor_) {
    CoinBigIndex lastFree = last_[maximumMajor_];
    CoinBigIndex put = first_[which];
    first_[which] = -1;
    while (put >= 0) {
      if (hash.numberItems()) {
        // take out of hash
        hash.deleteHash(put, static_cast< int >(rowInTriple(triples[put])), triples[put].column);
      }
      if (zapTriples) {
        triples[put].column = -1;
        triples[put].value = 0.0;
      }
      if (lastFree >= 0) {
        next_[lastFree] = put;
      } else {
        first_[maximumMajor_] = put;
      }
      previous_[put] = lastFree;
      lastFree = put;
      put = next_[put];
    }
    if (lastFree >= 0) {
      next_[lastFree] = -1;
      last_[maximumMajor_] = lastFree;
    } else {
      assert(last_[maximumMajor_] == -1);
    }
    last_[which] = -1;
  }
}
/* Deletes from list - other case i.e. delete row from column list
   This is when elements have been deleted from other copy
*/
void CoinModelLinkedList::updateDeleted(int /*which*/, CoinModelTriple *triples,
  CoinModelLinkedList &otherList)
{
  CoinBigIndex firstFree = otherList.firstFree();
  CoinBigIndex lastFree = otherList.lastFree();
  const CoinBigIndex *previousOther = otherList.previous();
  assert(maximumMajor_);
  if (lastFree >= 0) {
    // First free should be same
    if (first_[maximumMajor_] >= 0)
      assert(firstFree == first_[maximumMajor_]);
    CoinBigIndex last = last_[maximumMajor_];
    first_[maximumMajor_] = firstFree;
    // Maybe nothing to do
    if (last_[maximumMajor_] == lastFree)
      return;
    last_[maximumMajor_] = lastFree;
    int iMajor;
    if (!type_) {
      // for rows
      iMajor = static_cast< int >(rowInTriple(triples[lastFree]));
    } else {
      iMajor = triples[lastFree].column;
    }
    if (first_[iMajor] >= 0) {
      // take out
      CoinBigIndex previousThis = previous_[lastFree];
      CoinBigIndex nextThis = next_[lastFree];
      if (previousThis >= 0 && previousThis != last) {
        next_[previousThis] = nextThis;
#ifndef NDEBUG
        int iTest;
        if (!type_) {
          // for rows
          iTest = static_cast< int >(rowInTriple(triples[previousThis]));
        } else {
          iTest = triples[previousThis].column;
        }
        assert(triples[previousThis].column >= 0);
        assert(iTest == iMajor);
#endif
      } else {
        first_[iMajor] = nextThis;
      }
      if (nextThis >= 0) {
        previous_[nextThis] = previousThis;
#ifndef NDEBUG
        int iTest;
        if (!type_) {
          // for rows
          iTest = static_cast< int >(rowInTriple(triples[nextThis]));
        } else {
          iTest = triples[nextThis].column;
        }
        assert(triples[nextThis].column >= 0);
        assert(iTest == iMajor);
#endif
      } else {
        last_[iMajor] = previousThis;
      }
    }
    triples[lastFree].column = -1;
    triples[lastFree].value = 0.0;
    // Do first (by which I mean last)
    next_[lastFree] = -1;
    CoinBigIndex previous = previousOther[lastFree];
    while (previous != last) {
      if (previous >= 0) {
        if (!type_) {
          // for rows
          iMajor = static_cast< int >(rowInTriple(triples[previous]));
        } else {
          iMajor = triples[previous].column;
        }
        if (first_[iMajor] >= 0) {
          // take out
          CoinBigIndex previousThis = previous_[previous];
          CoinBigIndex nextThis = next_[previous];
          if (previousThis >= 0 && previousThis != last) {
            next_[previousThis] = nextThis;
#ifndef NDEBUG
            int iTest;
            if (!type_) {
              // for rows
              iTest = static_cast< int >(rowInTriple(triples[previousThis]));
            } else {
              iTest = triples[previousThis].column;
            }
            assert(triples[previousThis].column >= 0);
            assert(iTest == iMajor);
#endif
          } else {
            first_[iMajor] = nextThis;
          }
          if (nextThis >= 0) {
            previous_[nextThis] = previousThis;
#ifndef NDEBUG
            int iTest;
            if (!type_) {
              // for rows
              iTest = static_cast< int >(rowInTriple(triples[nextThis]));
            } else {
              iTest = triples[nextThis].column;
            }
            assert(triples[nextThis].column >= 0);
            assert(iTest == iMajor);
#endif
          } else {
            last_[iMajor] = previousThis;
          }
        }
        triples[previous].column = -1;
        triples[previous].value = 0.0;
        next_[previous] = lastFree;
      } else {
        assert(lastFree == firstFree);
      }
      previous_[lastFree] = previous;
      lastFree = previous;
      previous = previousOther[lastFree];
    }
    if (last >= 0) {
      next_[previous] = lastFree;
    } else {
      assert(firstFree == lastFree);
    }
    previous_[lastFree] = previous;
  }
}
/* Deletes one element from Row list
 */
void CoinModelLinkedList::deleteRowOne(CoinBigIndex position, CoinModelTriple *triples,
  CoinModelHash2 &hash)
{
  int row = rowInTriple(triples[position]);
  assert(row < numberMajor_);
  if (hash.numberItems()) {
    // take out of hash
    hash.deleteHash(position, static_cast< int >(rowInTriple(triples[position])), triples[position].column);
  }
  CoinBigIndex previous = previous_[position];
  CoinBigIndex next = next_[position];
  // put on free list
  CoinBigIndex lastFree = last_[maximumMajor_];
  if (lastFree >= 0) {
    next_[lastFree] = position;
  } else {
    first_[maximumMajor_] = position;
    assert(last_[maximumMajor_] == -1);
  }
  last_[maximumMajor_] = position;
  previous_[position] = lastFree;
  next_[position] = -1;
  // Now take out of row
  if (previous >= 0) {
    next_[previous] = next;
  } else {
    first_[row] = next;
  }
  if (next >= 0) {
    previous_[next] = previous;
  } else {
    last_[row] = previous;
  }
}
/* Update column list for one element when
   one element deleted from row copy
*/
void CoinModelLinkedList::updateDeletedOne(CoinBigIndex position, const CoinModelTriple *triples)
{
  assert(maximumMajor_);
  int column = triples[position].column;
  assert(column >= 0 && column < numberMajor_);
  CoinBigIndex previous = previous_[position];
  CoinBigIndex next = next_[position];
  // put on free list
  CoinBigIndex lastFree = last_[maximumMajor_];
  if (lastFree >= 0) {
    next_[lastFree] = position;
  } else {
    first_[maximumMajor_] = position;
    assert(last_[maximumMajor_] == -1);
  }
  last_[maximumMajor_] = position;
  previous_[position] = lastFree;
  next_[position] = -1;
  // Now take out of column
  if (previous >= 0) {
    next_[previous] = next;
  } else {
    first_[column] = next;
  }
  if (next >= 0) {
    previous_[next] = previous;
  } else {
    last_[column] = previous;
  }
}
// Fills first,last with -1
void CoinModelLinkedList::fill(int first, int last)
{
  for (int i = first; i < last; i++) {
    first_[i] = -1;
    last_[i] = -1;
  }
}
/* Puts in free list from other list */
void CoinModelLinkedList::synchronize(CoinModelLinkedList &other)
{
  CoinBigIndex first = other.first_[other.maximumMajor_];
  first_[maximumMajor_] = first;
  CoinBigIndex last = other.last_[other.maximumMajor_];
  last_[maximumMajor_] = last;
  CoinBigIndex put = first;
  while (put >= 0) {
    previous_[put] = other.previous_[put];
    next_[put] = other.next_[put];
    put = next_[put];
  }
}
// Checks that links are consistent
void CoinModelLinkedList::validateLinks(const CoinModelTriple *triples) const
{
  char *mark = new char[maximumElements_];
  memset(mark, 0, maximumElements_);
  CoinBigIndex lastElement = -1;
  int i;
  for (i = 0; i < numberMajor_; i++) {
    CoinBigIndex position = first_[i];
#ifndef NDEBUG
    CoinBigIndex lastPosition = -1;
#endif
    while (position >= 0) {
      assert(position == first_[i] || next_[previous_[position]] == position);
      assert(type_ || i == static_cast< int >(rowInTriple(triples[position]))); // i == iMajor for rows
      assert(!type_ || i == triples[position].column); // i == iMajor
      assert(triples[position].column >= 0);
      mark[position] = 1;
      lastElement = CoinMax(lastElement, position);
#ifndef NDEBUG
      lastPosition = position;
#endif
      position = next_[position];
    }
    assert(lastPosition == last_[i]);
  }
  for (i = 0; i <= lastElement; i++) {
    if (!mark[i])
      assert(triples[i].column == -1);
  }
  delete[] mark;
}

/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
*/