CoinIndexedVector.hpp

Go to the documentation of this file.

/* $Id: CoinIndexedVector.hpp 1767 2015-01-05 12:36:13Z forrest $ */
// Copyright (C) 2000, International Business Machines
// Corporation and others.  All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).

#ifndef CoinIndexedVector_H
#define CoinIndexedVector_H

#if defined(_MSC_VER)
// Turn off compiler warning about long names
#  pragma warning(disable:4786)
#endif

#include <map>
#include "CoinFinite.hpp"
#ifndef CLP_NO_VECTOR
#include "CoinPackedVectorBase.hpp"
#endif
#include "CoinSort.hpp"
#include "CoinHelperFunctions.hpp"
#include <cassert>

#ifndef COIN_FLOAT
#define COIN_INDEXED_TINY_ELEMENT 1.0e-50
#define COIN_INDEXED_REALLY_TINY_ELEMENT 1.0e-100
#else
#define COIN_INDEXED_TINY_ELEMENT 1.0e-35
#define COIN_INDEXED_REALLY_TINY_ELEMENT 1.0e-39
#endif

class CoinIndexedVector {
   friend void CoinIndexedVectorUnitTest();
  
public:
   inline int getNumElements() const { return nElements_; }
   inline const int * getIndices() const { return indices_; }
   // ** No longer supported virtual const double * getElements() const ;
   inline int * getIndices() { return indices_; }
   inline double * denseVector() const { return elements_; }
  inline void setDenseVector(double * array)
  { elements_ = array;}
  inline void setIndexVector(int * array)
  { indices_ = array;}
   double & operator[](int i) const; 

 
   //-------------------------------------------------------------------
   // Set indices and elements
   //------------------------------------------------------------------- 
   inline void setNumElements(int value) { nElements_ = value;
   if (!nElements_) packedMode_=false;}
   void clear();
   void empty();
   CoinIndexedVector & operator=(const CoinIndexedVector &);
#ifndef CLP_NO_VECTOR

   CoinIndexedVector & operator=(const CoinPackedVectorBase & rhs);
#endif

   void copy(const CoinIndexedVector & rhs, double multiplier=1.0);

  void borrowVector(int size, int numberIndices, int* inds, double* elems);

   void returnVector();

  void setVector(int numberIndices, const int * inds, const double * elems);
  
   void setVector(int size, int numberIndices, const int * inds, const double * elems);
  
  void setConstant(int size, const int * inds, double elems);
  
  void setFull(int size, const double * elems);

   void setElement(int index, double element);

   void insert(int index, double element);
   inline void quickInsert(int index, double element)
               {
                 assert (!elements_[index]);
                 indices_[nElements_++] = index;
                 assert (nElements_<=capacity_);
                 elements_[index] = element;
               }
   void add(int index, double element);
   inline void quickAdd(int index, double element)
               {
                 if (elements_[index]) {
                   element += elements_[index];
                   if ((element > 0 ? element : -element) >= COIN_INDEXED_TINY_ELEMENT) {
                     elements_[index] = element;
                   } else {
                     elements_[index] = 1.0e-100;
                   }
                 } else if ((element > 0 ? element : -element) >= COIN_INDEXED_TINY_ELEMENT) {
                   indices_[nElements_++] = index;
                   assert (nElements_<=capacity_);
                   elements_[index] = element;
                 }
               }
   inline void quickAddNonZero(int index, double element)
               {
                 assert (element);
                 if (elements_[index]) {
                   element += elements_[index];
                   if ((element > 0 ? element : -element) >= COIN_INDEXED_TINY_ELEMENT) {
                     elements_[index] = element;
                   } else {
                     elements_[index] = COIN_DBL_MIN;
                   }
                 } else {
                   indices_[nElements_++] = index;
                   assert (nElements_<=capacity_);
                   elements_[index] = element;
                 }
               }
   inline void zero(int index)
               {
                 if (elements_[index]) 
                   elements_[index] = COIN_DBL_MIN;
               }
   int clean(double tolerance);
   int cleanAndPack(double tolerance);
   int cleanAndPackSafe(double tolerance);
  inline void setPacked()
  { packedMode_ = true;}
#ifndef NDEBUG
   void checkClear();
   void checkClean();
#else
  inline void checkClear() {};
  inline void checkClean() {};
#endif
   int scan();
   int scan(int start, int end);
   int scan(double tolerance);
   int scan(int start, int end, double tolerance);
   int scanAndPack();
   int scanAndPack(int start, int end);
   int scanAndPack(double tolerance);
   int scanAndPack(int start, int end, double tolerance);
   void createPacked(int number, const int * indices, 
                    const double * elements);
   void createUnpacked(int number, const int * indices, 
                    const double * elements);
   void createOneUnpackedElement(int index, double element);
   void expand();
#ifndef CLP_NO_VECTOR
   void append(const CoinPackedVectorBase & caboose);
#endif
   void append(const CoinIndexedVector & caboose);
  void append(CoinIndexedVector & other,int adjustIndex,bool zapElements=false);

   void swap(int i, int j); 

   void truncate(int newSize); 
   void print() const;

   void operator+=(double value);
   void operator-=(double value);
   void operator*=(double value);
   void operator/=(double value);

#ifndef CLP_NO_VECTOR

   bool operator==(const CoinPackedVectorBase & rhs) const;
   bool operator!=(const CoinPackedVectorBase & rhs) const;
#endif

   bool operator==(const CoinIndexedVector & rhs) const;
   bool operator!=(const CoinIndexedVector & rhs) const;
   int isApproximatelyEqual(const CoinIndexedVector & rhs, double tolerance=1.0e-8) const;

   int getMaxIndex() const;
   int getMinIndex() const;


   void sort()
   { std::sort(indices_,indices_+nElements_); }

   void sortIncrIndex()
   { std::sort(indices_,indices_+nElements_); }

   void sortDecrIndex();
  
   void sortIncrElement();

   void sortDecrElement();
   void sortPacked();


  //#############################################################################

CoinIndexedVector operator+(
                           const CoinIndexedVector& op2);

CoinIndexedVector operator-(
                           const CoinIndexedVector& op2);

CoinIndexedVector operator*(
                           const CoinIndexedVector& op2);

CoinIndexedVector operator/(
                           const CoinIndexedVector& op2);
void operator+=(const CoinIndexedVector& op2);

void operator-=( const CoinIndexedVector& op2);

void operator*=(const CoinIndexedVector& op2);

void operator/=(const CoinIndexedVector& op2);

   void reserve(int n);
   inline int capacity() const { return capacity_; }
   inline void setCapacity(int value)
   { capacity_ = value; }
   inline void setPackedMode(bool yesNo)
   { packedMode_=yesNo;}
   inline bool packedMode() const
   { return packedMode_;}

   CoinIndexedVector();
  CoinIndexedVector(int size, const int * inds, const double * elems);
  CoinIndexedVector(int size, const int * inds, double element);
  CoinIndexedVector(int size, const double * elements);
  CoinIndexedVector(int size);
   CoinIndexedVector(const CoinIndexedVector &);
   CoinIndexedVector(const CoinIndexedVector *);
#ifndef CLP_NO_VECTOR

   CoinIndexedVector(const CoinPackedVectorBase & rhs);
#endif

   ~CoinIndexedVector ();
    
private:
   void gutsOfSetVector(int size,
                        const int * inds, const double * elems);
   void gutsOfSetVector(int size, int numberIndices,
                        const int * inds, const double * elems);
   void gutsOfSetPackedVector(int size, int numberIndices,
                        const int * inds, const double * elems);
   void gutsOfSetConstant(int size,
                          const int * inds, double value);

protected:
   int * indices_;
   double * elements_;
   int nElements_;
   int capacity_;
   int offset_;
   bool packedMode_;
};

//#############################################################################
void
CoinIndexedVectorUnitTest();
class CoinArrayWithLength {
  
public:
  inline int getSize() const 
  { return size_; }
  inline int rawSize() const 
  { return size_; }
  inline bool switchedOn() const 
  { return size_!=-1; }
  inline int capacity() const 
  { return (size_>-2) ? size_ : (-size_)-2; }
  inline void setCapacity() 
  { if (size_<=-2) size_ = (-size_)-2; }
  inline const char * array() const 
  { return (size_>-2) ? array_ : NULL; }
  
  inline void setSize(int value) 
  { size_ = value; }
  inline void switchOff() 
  { size_ = -1; }
  inline void switchOn(int alignment=3) 
  { size_ = -2; alignment_=alignment;}
  void setPersistence(int flag,int currentLength);
  void clear();
  void swap(CoinArrayWithLength & other);
  void extend(int newSize);
  
  char * conditionalNew(long sizeWanted); 
  void conditionalDelete();
  
  inline CoinArrayWithLength()
    : array_(NULL),size_(-1),offset_(0),alignment_(0)
  { }
  inline CoinArrayWithLength(int size)
    : size_(-1),offset_(0),alignment_(0)
  { array_=new char [size];}
  CoinArrayWithLength(int size, int mode);
  CoinArrayWithLength(const CoinArrayWithLength & rhs);
  CoinArrayWithLength(const CoinArrayWithLength * rhs);
  CoinArrayWithLength& operator=(const CoinArrayWithLength & rhs);
  void copy(const CoinArrayWithLength & rhs, int numberBytes=-1);
  void allocate(const CoinArrayWithLength & rhs, int numberBytes);
  ~CoinArrayWithLength ();
  void getArray(int size);
  void reallyFreeArray();
  void getCapacity(int numberBytes,int numberIfNeeded=-1);
  
protected:
  char * array_;
  CoinBigIndex size_;
  int offset_;
  int alignment_;
};

class CoinDoubleArrayWithLength : public CoinArrayWithLength {
  
public:
  inline int getSize() const 
  { return size_/CoinSizeofAsInt(double); }
  inline double * array() const 
  { return reinterpret_cast<double *> ((size_>-2) ? array_ : NULL); }
  
  inline void setSize(int value) 
  { size_ = value*CoinSizeofAsInt(double); }
  
  inline double * conditionalNew(int sizeWanted)
  { return reinterpret_cast<double *> ( CoinArrayWithLength::conditionalNew(sizeWanted>=0 ? static_cast<long> ((sizeWanted)*CoinSizeofAsInt(double)) : -1)); }
  
  inline CoinDoubleArrayWithLength()
  { array_=NULL; size_=-1;}
  inline CoinDoubleArrayWithLength(int size)
  { array_=new char [size*CoinSizeofAsInt(double)]; size_=-1;}
  inline CoinDoubleArrayWithLength(int size, int mode)
    : CoinArrayWithLength(size*CoinSizeofAsInt(double),mode) {}
  inline CoinDoubleArrayWithLength(const CoinDoubleArrayWithLength & rhs)
    : CoinArrayWithLength(rhs) {}
  inline CoinDoubleArrayWithLength(const CoinDoubleArrayWithLength * rhs)
    : CoinArrayWithLength(rhs) {}
  inline CoinDoubleArrayWithLength& operator=(const CoinDoubleArrayWithLength & rhs)
  { CoinArrayWithLength::operator=(rhs);  return *this;}
};

class CoinFactorizationDoubleArrayWithLength : public CoinArrayWithLength {
  
public:
  inline int getSize() const 
  { return size_/CoinSizeofAsInt(CoinFactorizationDouble); }
  inline CoinFactorizationDouble * array() const 
  { return reinterpret_cast<CoinFactorizationDouble *> ((size_>-2) ? array_ : NULL); }
  
  inline void setSize(int value) 
  { size_ = value*CoinSizeofAsInt(CoinFactorizationDouble); }
  
  inline CoinFactorizationDouble * conditionalNew(int sizeWanted)
  { return reinterpret_cast<CoinFactorizationDouble *> (CoinArrayWithLength::conditionalNew(sizeWanted>=0 ? static_cast<long> (( sizeWanted)*CoinSizeofAsInt(CoinFactorizationDouble)) : -1)); }
  
  inline CoinFactorizationDoubleArrayWithLength()
  { array_=NULL; size_=-1;}
  inline CoinFactorizationDoubleArrayWithLength(int size)
  { array_=new char [size*CoinSizeofAsInt(CoinFactorizationDouble)]; size_=-1;}
  inline CoinFactorizationDoubleArrayWithLength(int size, int mode)
    : CoinArrayWithLength(size*CoinSizeofAsInt(CoinFactorizationDouble),mode) {}
  inline CoinFactorizationDoubleArrayWithLength(const CoinFactorizationDoubleArrayWithLength & rhs)
    : CoinArrayWithLength(rhs) {}
  inline CoinFactorizationDoubleArrayWithLength(const CoinFactorizationDoubleArrayWithLength * rhs)
    : CoinArrayWithLength(rhs) {}
  inline CoinFactorizationDoubleArrayWithLength& operator=(const CoinFactorizationDoubleArrayWithLength & rhs)
  { CoinArrayWithLength::operator=(rhs);  return *this;}
};

class CoinFactorizationLongDoubleArrayWithLength : public CoinArrayWithLength {
  
public:
  inline int getSize() const 
  { return size_/CoinSizeofAsInt(long double); }
  inline long double * array() const 
  { return reinterpret_cast<long double *> ((size_>-2) ? array_ : NULL); }
  
  inline void setSize(int value) 
  { size_ = value*CoinSizeofAsInt(long double); }
  
  inline long double * conditionalNew(int sizeWanted)
  { return reinterpret_cast<long double *> (CoinArrayWithLength::conditionalNew(sizeWanted>=0 ? static_cast<long> (( sizeWanted)*CoinSizeofAsInt(long double)) : -1)); }
  
  inline CoinFactorizationLongDoubleArrayWithLength()
  { array_=NULL; size_=-1;}
  inline CoinFactorizationLongDoubleArrayWithLength(int size)
  { array_=new char [size*CoinSizeofAsInt(long double)]; size_=-1;}
  inline CoinFactorizationLongDoubleArrayWithLength(int size, int mode)
    : CoinArrayWithLength(size*CoinSizeofAsInt(long double),mode) {}
  inline CoinFactorizationLongDoubleArrayWithLength(const CoinFactorizationLongDoubleArrayWithLength & rhs)
    : CoinArrayWithLength(rhs) {}
  inline CoinFactorizationLongDoubleArrayWithLength(const CoinFactorizationLongDoubleArrayWithLength * rhs)
    : CoinArrayWithLength(rhs) {}
  inline CoinFactorizationLongDoubleArrayWithLength& operator=(const CoinFactorizationLongDoubleArrayWithLength & rhs)
  { CoinArrayWithLength::operator=(rhs);  return *this;}
};

class CoinIntArrayWithLength : public CoinArrayWithLength {
  
public:
  inline int getSize() const 
  { return size_/CoinSizeofAsInt(int); }
  inline int * array() const 
  { return reinterpret_cast<int *> ((size_>-2) ? array_ : NULL); }
  
  inline void setSize(int value) 
  { size_ = value*CoinSizeofAsInt(int); }
  
  inline int * conditionalNew(int sizeWanted)
  { return reinterpret_cast<int *> (CoinArrayWithLength::conditionalNew(sizeWanted>=0 ? static_cast<long> (( sizeWanted)*CoinSizeofAsInt(int)) : -1)); }
  
  inline CoinIntArrayWithLength()
  { array_=NULL; size_=-1;}
  inline CoinIntArrayWithLength(int size)
  { array_=new char [size*CoinSizeofAsInt(int)]; size_=-1;}
  inline CoinIntArrayWithLength(int size, int mode)
    : CoinArrayWithLength(size*CoinSizeofAsInt(int),mode) {}
  inline CoinIntArrayWithLength(const CoinIntArrayWithLength & rhs)
    : CoinArrayWithLength(rhs) {}
  inline CoinIntArrayWithLength(const CoinIntArrayWithLength * rhs)
    : CoinArrayWithLength(rhs) {}
  inline CoinIntArrayWithLength& operator=(const CoinIntArrayWithLength & rhs)
  { CoinArrayWithLength::operator=(rhs);  return *this;}
};

class CoinBigIndexArrayWithLength : public CoinArrayWithLength {
  
public:
  inline int getSize() const 
  { return size_/CoinSizeofAsInt(CoinBigIndex); }
  inline CoinBigIndex * array() const 
  { return reinterpret_cast<CoinBigIndex *> ((size_>-2) ? array_ : NULL); }
  
  inline void setSize(int value) 
  { size_ = value*CoinSizeofAsInt(CoinBigIndex); }
  
  inline CoinBigIndex * conditionalNew(int sizeWanted)
  { return reinterpret_cast<CoinBigIndex *> (CoinArrayWithLength::conditionalNew(sizeWanted>=0 ? static_cast<long> (( sizeWanted)*CoinSizeofAsInt(CoinBigIndex)) : -1)); }
  
  inline CoinBigIndexArrayWithLength()
  { array_=NULL; size_=-1;}
  inline CoinBigIndexArrayWithLength(int size)
  { array_=new char [size*CoinSizeofAsInt(CoinBigIndex)]; size_=-1;}
  inline CoinBigIndexArrayWithLength(int size, int mode)
    : CoinArrayWithLength(size*CoinSizeofAsInt(CoinBigIndex),mode) {}
  inline CoinBigIndexArrayWithLength(const CoinBigIndexArrayWithLength & rhs)
    : CoinArrayWithLength(rhs) {}
  inline CoinBigIndexArrayWithLength(const CoinBigIndexArrayWithLength * rhs)
    : CoinArrayWithLength(rhs) {}
  inline CoinBigIndexArrayWithLength& operator=(const CoinBigIndexArrayWithLength & rhs)
  { CoinArrayWithLength::operator=(rhs);  return *this;}
};

class CoinUnsignedIntArrayWithLength : public CoinArrayWithLength {
  
public:
  inline int getSize() const 
  { return size_/CoinSizeofAsInt(unsigned int); }
  inline unsigned int * array() const 
  { return reinterpret_cast<unsigned int *> ((size_>-2) ? array_ : NULL); }
  
  inline void setSize(int value) 
  { size_ = value*CoinSizeofAsInt(unsigned int); }
  
  inline unsigned int * conditionalNew(int sizeWanted)
  { return reinterpret_cast<unsigned int *> (CoinArrayWithLength::conditionalNew(sizeWanted>=0 ? static_cast<long> (( sizeWanted)*CoinSizeofAsInt(unsigned int)) : -1)); }
  
  inline CoinUnsignedIntArrayWithLength()
  { array_=NULL; size_=-1;}
  inline CoinUnsignedIntArrayWithLength(int size)
  { array_=new char [size*CoinSizeofAsInt(unsigned int)]; size_=-1;}
  inline CoinUnsignedIntArrayWithLength(int size, int mode)
    : CoinArrayWithLength(size*CoinSizeofAsInt(unsigned int),mode) {}
  inline CoinUnsignedIntArrayWithLength(const CoinUnsignedIntArrayWithLength & rhs)
    : CoinArrayWithLength(rhs) {}
  inline CoinUnsignedIntArrayWithLength(const CoinUnsignedIntArrayWithLength * rhs)
    : CoinArrayWithLength(rhs) {}
  inline CoinUnsignedIntArrayWithLength& operator=(const CoinUnsignedIntArrayWithLength & rhs)
  { CoinArrayWithLength::operator=(rhs);  return *this;}
};

class CoinVoidStarArrayWithLength : public CoinArrayWithLength {
  
public:
  inline int getSize() const 
  { return size_/CoinSizeofAsInt(void *); }
  inline void ** array() const 
  { return reinterpret_cast<void **> ((size_>-2) ? array_ : NULL); }
  
  inline void setSize(int value) 
  { size_ = value*CoinSizeofAsInt(void *); }
  
  inline void ** conditionalNew(int sizeWanted)
  { return reinterpret_cast<void **> ( CoinArrayWithLength::conditionalNew(sizeWanted>=0 ? static_cast<long> ((sizeWanted)*CoinSizeofAsInt(void *)) : -1)); }
  
  inline CoinVoidStarArrayWithLength()
  { array_=NULL; size_=-1;}
  inline CoinVoidStarArrayWithLength(int size)
  { array_=new char [size*CoinSizeofAsInt(void *)]; size_=-1;}
  inline CoinVoidStarArrayWithLength(int size, int mode)
    : CoinArrayWithLength(size*CoinSizeofAsInt(void *),mode) {}
  inline CoinVoidStarArrayWithLength(const CoinVoidStarArrayWithLength & rhs)
    : CoinArrayWithLength(rhs) {}
  inline CoinVoidStarArrayWithLength(const CoinVoidStarArrayWithLength * rhs)
    : CoinArrayWithLength(rhs) {}
  inline CoinVoidStarArrayWithLength& operator=(const CoinVoidStarArrayWithLength & rhs)
  { CoinArrayWithLength::operator=(rhs);  return *this;}
};

class CoinArbitraryArrayWithLength : public CoinArrayWithLength {
  
public:
  inline int getSize() const 
  { return size_/lengthInBytes_; }
  inline void ** array() const 
  { return reinterpret_cast<void **> ((size_>-2) ? array_ : NULL); }
  
  inline void setSize(int value) 
  { size_ = value*lengthInBytes_; }
  
  inline char * conditionalNew(int length, int sizeWanted)
  { lengthInBytes_=length;return reinterpret_cast<char *> ( CoinArrayWithLength::conditionalNew(sizeWanted>=0 ? static_cast<long> 
                                                                          ((sizeWanted)*lengthInBytes_) : -1)); }
  
  inline CoinArbitraryArrayWithLength(int length=1)
  { array_=NULL; size_=-1;lengthInBytes_=length;}
  inline CoinArbitraryArrayWithLength(int length, int size)
  { array_=new char [size*length]; size_=-1; lengthInBytes_=length;}
  inline CoinArbitraryArrayWithLength(int length, int size, int mode)
    : CoinArrayWithLength(size*length,mode) {lengthInBytes_=length;}
  inline CoinArbitraryArrayWithLength(const CoinArbitraryArrayWithLength & rhs)
    : CoinArrayWithLength(rhs) {}
  inline CoinArbitraryArrayWithLength(const CoinArbitraryArrayWithLength * rhs)
    : CoinArrayWithLength(rhs) {}
  inline CoinArbitraryArrayWithLength& operator=(const CoinArbitraryArrayWithLength & rhs)
  { CoinArrayWithLength::operator=(rhs);  return *this;}

protected:
  int lengthInBytes_;
};
class CoinPartitionedVector : public CoinIndexedVector {
  
public:
#ifndef COIN_PARTITIONS
#define COIN_PARTITIONS 8
#endif

   inline int getNumElements(int partition) const { assert (partition<COIN_PARTITIONS);
     return numberElementsPartition_[partition]; }
   inline int getNumPartitions() const
  { return numberPartitions_; }
   inline int getNumElements() const { return nElements_; }
  inline int startPartition(int partition) const  { assert (partition<=COIN_PARTITIONS);
    return startPartition_[partition]; }
  inline const int * startPartitions() const
  { return startPartition_; }
 
   //-------------------------------------------------------------------
   // Set indices and elements
   //------------------------------------------------------------------- 
  inline void setNumElementsPartition(int partition, int value) { assert (partition<COIN_PARTITIONS);
    if (numberPartitions_) numberElementsPartition_[partition]=value; }
  inline void setTempNumElementsPartition(int partition, int value) { assert (partition<COIN_PARTITIONS);
    numberElementsPartition_[partition]=value; }
  void computeNumberElements();
  void compact();
   void reserve(int n);
  void setPartitions(int number,const int * starts);
   void clearAndReset();
   void clearAndKeep();
   void clearPartition(int partition);
#ifndef NDEBUG
   void checkClear();
   void checkClean();
#else
  inline void checkClear() {};
  inline void checkClean() {};
#endif
  int scan(int partition, double tolerance=0.0);
   void print() const;
 
  void sort();

   CoinPartitionedVector();
  CoinPartitionedVector(int size, const int * inds, const double * elems);
  CoinPartitionedVector(int size, const int * inds, double element);
  CoinPartitionedVector(int size, const double * elements);
  CoinPartitionedVector(int size);
   CoinPartitionedVector(const CoinPartitionedVector &);
   CoinPartitionedVector(const CoinPartitionedVector *);
   CoinPartitionedVector & operator=(const CoinPartitionedVector &);
   ~CoinPartitionedVector ();
protected:
   int startPartition_[COIN_PARTITIONS+1];
   int numberElementsPartition_[COIN_PARTITIONS];
  int numberPartitions_;
};
#endif