1/* $Id: CoinModelUseful.cpp 1543 2012-07-27 22:48:29Z unxusr $ */
2// Copyright (C) 2005, International Business Machines
3// Corporation and others. All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6#include "CoinPragma.hpp"
7
8#include <cstdlib>
9#include <cmath>
10#include <cassert>
11#include <cfloat>
12#include <string>
13#include <cstdio>
14#include <iostream>
15
16#include "CoinHelperFunctions.hpp"
17
18#include "CoinModelUseful.hpp"
19
20
21//#############################################################################
22// Constructors / Destructor / Assignment
23//#############################################################################
24
25//-------------------------------------------------------------------
26// Default Constructor
27//-------------------------------------------------------------------
28CoinModelLink::CoinModelLink ()
29 : row_(-1),
30 column_(-1),
31 value_(0.0),
32 position_(-1),
33 onRow_(true)
34{
35}
36
37//-------------------------------------------------------------------
38// Copy constructor
39//-------------------------------------------------------------------
40CoinModelLink::CoinModelLink (const CoinModelLink & rhs)
41 : row_(rhs.row_),
42 column_(rhs.column_),
43 value_(rhs.value_),
44 position_(rhs.position_),
45 onRow_(rhs.onRow_)
46{
47}
48
49//-------------------------------------------------------------------
50// Destructor
51//-------------------------------------------------------------------
52CoinModelLink::~CoinModelLink ()
53{
54}
55
56//----------------------------------------------------------------
57// Assignment operator
58//-------------------------------------------------------------------
59CoinModelLink &
60CoinModelLink::operator=(const CoinModelLink& rhs)
61{
62 if (this != &rhs) {
63 row_ = rhs.row_;
64 column_ = rhs.column_;
65 value_ = rhs.value_;
66 position_ = rhs.position_;
67 onRow_ = rhs.onRow_;
68 }
69 return *this;
70}
71
72namespace {
73 const int mmult[] = {
74 262139, 259459, 256889, 254291, 251701, 249133, 246709, 244247,
75 241667, 239179, 236609, 233983, 231289, 228859, 226357, 223829,
76 221281, 218849, 216319, 213721, 211093, 208673, 206263, 203773,
77 201233, 198637, 196159, 193603, 191161, 188701, 186149, 183761,
78 181303, 178873, 176389, 173897, 171469, 169049, 166471, 163871,
79 161387, 158941, 156437, 153949, 151531, 149159, 146749, 144299,
80 141709, 139369, 136889, 134591, 132169, 129641, 127343, 124853,
81 122477, 120163, 117757, 115361, 112979, 110567, 108179, 105727,
82 103387, 101021, 98639, 96179, 93911, 91583, 89317, 86939, 84521,
83 82183, 79939, 77587, 75307, 72959, 70793, 68447, 66103
84 };
85 const int lengthMult = static_cast<int> (sizeof(mmult) / sizeof(int));
86}
87
88//#############################################################################
89// Constructors / Destructor / Assignment
90//#############################################################################
91
92//-------------------------------------------------------------------
93// Default Constructor
94//-------------------------------------------------------------------
95CoinModelHash::CoinModelHash ()
96 : names_(NULL),
97 hash_(NULL),
98 numberItems_(0),
99 maximumItems_(0),
100 lastSlot_(-1)
101{
102}
103
104//-------------------------------------------------------------------
105// Copy constructor
106//-------------------------------------------------------------------
107CoinModelHash::CoinModelHash (const CoinModelHash & rhs)
108 : names_(NULL),
109 hash_(NULL),
110 numberItems_(rhs.numberItems_),
111 maximumItems_(rhs.maximumItems_),
112 lastSlot_(rhs.lastSlot_)
113{
114 if (maximumItems_) {
115 names_ = new char * [maximumItems_];
116 for (int i=0;i<maximumItems_;i++) {
117 names_[i]=CoinStrdup(rhs.names_[i]);
118 }
119 hash_ = CoinCopyOfArray(rhs.hash_,4*maximumItems_);
120 }
121}
122
123//-------------------------------------------------------------------
124// Destructor
125//-------------------------------------------------------------------
126CoinModelHash::~CoinModelHash ()
127{
128 for (int i=0;i<maximumItems_;i++)
129 free(names_[i]);
130 delete [] names_;
131 delete [] hash_;
132}
133
134//----------------------------------------------------------------
135// Assignment operator
136//-------------------------------------------------------------------
137CoinModelHash &
138CoinModelHash::operator=(const CoinModelHash& rhs)
139{
140 if (this != &rhs) {
141 for (int i=0;i<maximumItems_;i++)
142 free(names_[i]);
143 delete [] names_;
144 delete [] hash_;
145 numberItems_ = rhs.numberItems_;
146 maximumItems_ = rhs.maximumItems_;
147 lastSlot_ = rhs.lastSlot_;
148 if (maximumItems_) {
149 names_ = new char * [maximumItems_];
150 for (int i=0;i<maximumItems_;i++) {
151 names_[i]=CoinStrdup(rhs.names_[i]);
152 }
153 hash_ = CoinCopyOfArray(rhs.hash_,4*maximumItems_);
154 } else {
155 names_ = NULL;
156 hash_ = NULL;
157 }
158 }
159 return *this;
160}
161// Set number of items
162void
163CoinModelHash::setNumberItems(int number)
164{
165 assert (number>=0&&number<=numberItems_);
166 numberItems_=number;
167}
168// Resize hash (also re-hashs)
169void
170CoinModelHash::resize(int maxItems,bool forceReHash)
171{
172 assert (numberItems_<=maximumItems_);
173 if (maxItems<=maximumItems_&&!forceReHash)
174 return;
175 int n=maximumItems_;
176 maximumItems_=maxItems;
177 char ** names = new char * [maximumItems_];
178 int i;
179 for ( i=0;i<n;i++)
180 names[i]=names_[i];
181 for ( ;i<maximumItems_;i++)
182 names[i]=NULL;
183 delete [] names_;
184 names_ = names;
185 delete [] hash_;
186 int maxHash = 4 * maximumItems_;
187 hash_ = new CoinModelHashLink [maxHash];
188 int ipos;
189
190 for ( i = 0; i < maxHash; i++ ) {
191 hash_[i].index = -1;
192 hash_[i].next = -1;
193 }
194
195 /*
196 * Initialize the hash table. Only the index of the first name that
197 * hashes to a value is entered in the table; subsequent names that
198 * collide with it are not entered.
199 */
200 for ( i = 0; i < numberItems_; ++i ) {
201 if (names_[i]) {
202 ipos = hashValue ( names_[i]);
203 if ( hash_[ipos].index == -1 ) {
204 hash_[ipos].index = i;
205 }
206 }
207 }
208
209 /*
210 * Now take care of the names that collided in the preceding loop,
211 * by finding some other entry in the table for them.
212 * Since there are as many entries in the table as there are names,
213 * there must be room for them.
214 */
215 lastSlot_ = -1;
216 for ( i = 0; i < numberItems_; ++i ) {
217 if (!names_[i])
218 continue;
219 char *thisName = names[i];
220 ipos = hashValue ( thisName);
221
222 while ( true ) {
223 int j1 = hash_[ipos].index;
224
225 if ( j1 == i )
226 break;
227 else {
228 char *thisName2 = names[j1];
229
230 if ( strcmp ( thisName, thisName2 ) == 0 ) {
231 printf ( "** duplicate name %s\n", names[i] );
232 abort();
233 break;
234 } else {
235 int k = hash_[ipos].next;
236
237 if ( k == -1 ) {
238 while ( true ) {
239 ++lastSlot_;
240 if ( lastSlot_ > numberItems_ ) {
241 printf ( "** too many names\n" );
242 abort();
243 break;
244 }
245 if ( hash_[lastSlot_].index == -1 ) {
246 break;
247 }
248 }
249 hash_[ipos].next = lastSlot_;
250 hash_[lastSlot_].index = i;
251 break;
252 } else {
253 ipos = k;
254 /* nothing worked - try it again */
255 }
256 }
257 }
258 }
259 }
260
261}
262// validate
263void
264CoinModelHash::validateHash() const
265{
266 for (int i = 0; i < numberItems_; ++i ) {
267 if (names_[i]) {
268 assert (hash( names_[i])>=0);
269 }
270 }
271}
272// Returns index or -1
273int
274CoinModelHash::hash(const char * name) const
275{
276 int found = -1;
277
278 int ipos;
279
280 /* default if we don't find anything */
281 if ( !numberItems_ )
282 return -1;
283
284 ipos = hashValue ( name );
285 while ( true ) {
286 int j1 = hash_[ipos].index;
287
288 if ( j1 >= 0 ) {
289 char *thisName2 = names_[j1];
290
291 if ( strcmp ( name, thisName2 ) != 0 ) {
292 int k = hash_[ipos].next;
293
294 if ( k != -1 )
295 ipos = k;
296 else
297 break;
298 } else {
299 found = j1;
300 break;
301 }
302 } else {
303 int k = hash_[ipos].next;
304
305 if ( k != -1 )
306 ipos = k;
307 else
308 break;
309 }
310 }
311 return found;
312}
313// Adds to hash
314void
315CoinModelHash::addHash(int index, const char * name)
316{
317 // resize if necessary
318 if (numberItems_>=maximumItems_)
319 resize(1000+3*numberItems_/2);
320 assert (!names_[index]);
321 names_[index]=CoinStrdup(name);
322 int ipos = hashValue ( name);
323 numberItems_ = CoinMax(numberItems_,index+1);
324 if ( hash_[ipos].index <0 ) {
325 hash_[ipos].index = index;
326 } else {
327 while ( true ) {
328 int j1 = hash_[ipos].index;
329
330 if ( j1 == index )
331 break; // duplicate?
332 else {
333 if (j1>=0) {
334 char *thisName2 = names_[j1];
335 if ( strcmp ( name, thisName2 ) == 0 ) {
336 printf ( "** duplicate name %s\n", names_[index] );
337 abort();
338 break;
339 } else {
340 int k = hash_[ipos].next;
341
342 if ( k == -1 ) {
343 while ( true ) {
344 ++lastSlot_;
345 if ( lastSlot_ > numberItems_ ) {
346 printf ( "** too many names\n" );
347 abort();
348 break;
349 }
350 if ( hash_[lastSlot_].index <0 && hash_[lastSlot_].next<0) {
351 break;
352 }
353 }
354 hash_[ipos].next = lastSlot_;
355 hash_[lastSlot_].index = index;
356 hash_[lastSlot_].next=-1;
357 break;
358 } else {
359 ipos = k;
360 }
361 }
362 } else {
363 //slot available
364 hash_[ipos].index = index;
365 }
366 }
367 }
368 }
369}
370// Deletes from hash
371void
372CoinModelHash::deleteHash(int index)
373{
374 if (index<numberItems_&&names_[index]) {
375
376 int ipos = hashValue ( names_[index] );
377
378 while ( ipos>=0 ) {
379 int j1 = hash_[ipos].index;
380 if ( j1!=index) {
381 ipos = hash_[ipos].next;
382 } else {
383 hash_[ipos].index=-1; // available
384 break;
385 }
386 }
387 assert (ipos>=0);
388 free(names_[index]);
389 names_[index]=NULL;
390 }
391}
392// Returns name at position (or NULL)
393const char *
394CoinModelHash::name(int which) const
395{
396 if (which<numberItems_)
397 return names_[which];
398 else
399 return NULL;
400}
401// Returns non const name at position (or NULL)
402char *
403CoinModelHash::getName(int which) const
404{
405 if (which<numberItems_)
406 return names_[which];
407 else
408 return NULL;
409}
410// Sets name at position (does not create)
411void
412CoinModelHash::setName(int which,char * name )
413{
414 if (which<numberItems_)
415 names_[which]=name;
416}
417// Returns a hash value
418int
419CoinModelHash::hashValue(const char * name) const
420{
421
422 int n = 0;
423 int j;
424 int length = static_cast<int> (strlen(name));
425 // may get better spread with unsigned
426 const unsigned char * name2 = reinterpret_cast<const unsigned char *> (name);
427 while (length) {
428 int length2 = CoinMin( length,lengthMult);
429 for ( j = 0; j < length2; ++j ) {
430 n += mmult[j] * name2[j];
431 }
432 name+=length2;
433 length-=length2;
434 }
435 int maxHash = 4 * maximumItems_;
436 return ( abs ( n ) % maxHash ); /* integer abs */
437}
438//#############################################################################
439// Constructors / Destructor / Assignment
440//#############################################################################
441//-------------------------------------------------------------------
442// Default Constructor
443//-------------------------------------------------------------------
444CoinModelHash2::CoinModelHash2 ()
445 : hash_(NULL),
446 numberItems_(0),
447 maximumItems_(0),
448 lastSlot_(-1)
449{
450}
451
452//-------------------------------------------------------------------
453// Copy constructor
454//-------------------------------------------------------------------
455CoinModelHash2::CoinModelHash2 (const CoinModelHash2 & rhs)
456 : hash_(NULL),
457 numberItems_(rhs.numberItems_),
458 maximumItems_(rhs.maximumItems_),
459 lastSlot_(rhs.lastSlot_)
460{
461 if (maximumItems_) {
462 hash_ = CoinCopyOfArray(rhs.hash_,4*maximumItems_);
463 }
464}
465
466//-------------------------------------------------------------------
467// Destructor
468//-------------------------------------------------------------------
469CoinModelHash2::~CoinModelHash2 ()
470{
471 delete [] hash_;
472}
473
474//----------------------------------------------------------------
475// Assignment operator
476//-------------------------------------------------------------------
477CoinModelHash2 &
478CoinModelHash2::operator=(const CoinModelHash2& rhs)
479{
480 if (this != &rhs) {
481 delete [] hash_;
482 numberItems_ = rhs.numberItems_;
483 maximumItems_ = rhs.maximumItems_;
484 lastSlot_ = rhs.lastSlot_;
485 if (maximumItems_) {
486 hash_ = CoinCopyOfArray(rhs.hash_,4*maximumItems_);
487 } else {
488 hash_ = NULL;
489 }
490 }
491 return *this;
492}
493// Set number of items
494void
495CoinModelHash2::setNumberItems(int number)
496{
497 assert (number>=0&&(number<=numberItems_||!numberItems_));
498 numberItems_=number;
499}
500// Resize hash (also re-hashs)
501void
502CoinModelHash2::resize(int maxItems, const CoinModelTriple * triples,bool forceReHash)
503{
504 assert (numberItems_<=maximumItems_||!maximumItems_);
505 if (maxItems<=maximumItems_&&!forceReHash)
506 return;
507 if (maxItems>maximumItems_) {
508 maximumItems_=maxItems;
509 delete [] hash_;
510 hash_ = new CoinModelHashLink [4*maximumItems_];
511 }
512 int maxHash = 4 * maximumItems_;
513 int ipos;
514 int i;
515 for ( i = 0; i < maxHash; i++ ) {
516 hash_[i].index = -1;
517 hash_[i].next = -1;
518 }
519
520 /*
521 * Initialize the hash table. Only the index of the first name that
522 * hashes to a value is entered in the table; subsequent names that
523 * collide with it are not entered.
524 */
525 for ( i = 0; i < numberItems_; ++i ) {
526 int row = static_cast<int> (rowInTriple(triples[i]));
527 int column = triples[i].column;
528 if (column>=0) {
529 ipos = hashValue ( row, column);
530 if ( hash_[ipos].index == -1 ) {
531 hash_[ipos].index = i;
532 }
533 }
534 }
535
536 /*
537 * Now take care of the entries that collided in the preceding loop,
538 * by finding some other entry in the table for them.
539 * Since there are as many entries in the table as there are entries,
540 * there must be room for them.
541 */
542 lastSlot_ = -1;
543 for ( i = 0; i < numberItems_; ++i ) {
544 int row = static_cast<int> (rowInTriple(triples[i]));
545 int column = triples[i].column;
546 if (column>=0) {
547 ipos = hashValue ( row, column);
548
549 while ( true ) {
550 int j1 = hash_[ipos].index;
551
552 if ( j1 == i )
553 break;
554 else {
555 int row2 = static_cast<int> (rowInTriple(triples[j1]));
556 int column2 = triples[j1].column;
557 if ( row==row2&&column==column2 ) {
558 printf ( "** duplicate entry %d %d\n", row,column );
559 abort();
560 break;
561 } else {
562 int k = hash_[ipos].next;
563
564 if ( k == -1 ) {
565 while ( true ) {
566 ++lastSlot_;
567 if ( lastSlot_ > numberItems_ ) {
568 printf ( "** too many entries\n" );
569 abort();
570 break;
571 }
572 if ( hash_[lastSlot_].index == -1 ) {
573 break;
574 }
575 }
576 hash_[ipos].next = lastSlot_;
577 hash_[lastSlot_].index = i;
578 break;
579 } else {
580 ipos = k;
581 }
582 }
583 }
584 }
585 }
586 }
587
588}
589// Returns index or -1
590int
591CoinModelHash2::hash(int row, int column, const CoinModelTriple * triples) const
592{
593 int found = -1;
594
595 int ipos;
596
597 /* default if we don't find anything */
598 if ( !numberItems_ )
599 return -1;
600
601 ipos = hashValue ( row, column );
602 while ( true ) {
603 int j1 = hash_[ipos].index;
604
605 if ( j1 >= 0 ) {
606 int row2 = static_cast<int> (rowInTriple(triples[j1]));
607 int column2 = triples[j1].column;
608 if ( row!=row2||column!=column2 ) {
609 int k = hash_[ipos].next;
610
611 if ( k != -1 )
612 ipos = k;
613 else
614 break;
615 } else {
616 found = j1;
617 break;
618 }
619 } else {
620 int k = hash_[ipos].next;
621
622 if ( k != -1 )
623 ipos = k;
624 else
625 break;
626 }
627 }
628 return found;
629}
630// Adds to hash
631void
632CoinModelHash2::addHash(int index, int row, int column, const CoinModelTriple * triples)
633{
634 // resize if necessary
635 if (numberItems_>=maximumItems_||index+1>=maximumItems_)
636 resize(CoinMax(1000+3*numberItems_/2,index+1), triples);
637 int ipos = hashValue ( row, column);
638 numberItems_ = CoinMax(numberItems_,index+1);
639 assert (numberItems_<=maximumItems_);
640 if ( hash_[ipos].index <0 ) {
641 hash_[ipos].index = index;
642 } else {
643 while ( true ) {
644 int j1 = hash_[ipos].index;
645
646 if ( j1 == index ) {
647 break; // duplicate??
648 } else {
649 if (j1 >=0 ) {
650 int row2 = static_cast<int> (rowInTriple(triples[j1]));
651 int column2 = triples[j1].column;
652 if ( row==row2&&column==column2 ) {
653 printf ( "** duplicate entry %d %d\n", row, column );
654 abort();
655 break;
656 } else {
657 int k = hash_[ipos].next;
658
659 if ( k ==-1 ) {
660 while ( true ) {
661 ++lastSlot_;
662 if ( lastSlot_ > numberItems_ ) {
663 printf ( "** too many entrys\n" );
664 abort();
665 break;
666 }
667 if ( hash_[lastSlot_].index <0 ) {
668 break;
669 }
670 }
671 hash_[ipos].next = lastSlot_;
672 hash_[lastSlot_].index = index;
673 hash_[lastSlot_].next=-1;
674 break;
675 } else {
676 ipos = k;
677 }
678 }
679 } else {
680 // slot available
681 hash_[ipos].index = index;
682 }
683 }
684 }
685 }
686}
687// Deletes from hash
688void
689CoinModelHash2::deleteHash(int index,int row, int column)
690{
691 if (index<numberItems_) {
692
693 int ipos = hashValue ( row, column );
694
695 while ( ipos>=0 ) {
696 int j1 = hash_[ipos].index;
697 if ( j1!=index) {
698 ipos = hash_[ipos].next;
699 } else {
700 hash_[ipos].index=-1; // available
701 break;
702 }
703 }
704 }
705}
706namespace {
707 const int mmult2[] = {
708 262139, 259459, 256889, 254291, 251701, 249133, 246709, 244247,
709 241667, 239179, 236609, 233983, 231289, 228859, 226357, 223829
710 };
711}
712// Returns a hash value
713int
714CoinModelHash2::hashValue(int row, int column) const
715{
716
717 // Optimizer should take out one side of if
718 if (sizeof(int)==4*sizeof(char)) {
719 unsigned char tempChar[4];
720
721 unsigned int n = 0;
722 int * temp = reinterpret_cast<int *> (tempChar);
723 *temp=row;
724 n += mmult2[0] * tempChar[0];
725 n += mmult2[1] * tempChar[1];
726 n += mmult2[2] * tempChar[2];
727 n += mmult[3] * tempChar[3];
728 *temp=column;
729 n += mmult2[0+8] * tempChar[0];
730 n += mmult2[1+8] * tempChar[1];
731 n += mmult2[2+8] * tempChar[2];
732 n += mmult2[3+8] * tempChar[3];
733 return n % (maximumItems_<<1);
734 } else {
735 // ints are 8
736 unsigned char tempChar[8];
737
738 int n = 0;
739 unsigned int j;
740 int * temp = reinterpret_cast<int *> (tempChar);
741 *temp=row;
742 for ( j = 0; j < sizeof(int); ++j ) {
743 int itemp = tempChar[j];
744 n += mmult2[j] * itemp;
745 }
746 *temp=column;
747 for ( j = 0; j < sizeof(int); ++j ) {
748 int itemp = tempChar[j];
749 n += mmult2[j+8] * itemp;
750 }
751 int maxHash = 4 * maximumItems_;
752 int absN = abs(n);
753 int returnValue = absN % maxHash;
754 return returnValue;
755 }
756}
757//#############################################################################
758// Constructors / Destructor / Assignment
759//#############################################################################
760
761//-------------------------------------------------------------------
762// Default Constructor
763//-------------------------------------------------------------------
764CoinModelLinkedList::CoinModelLinkedList ()
765 : previous_(NULL),
766 next_(NULL),
767 first_(NULL),
768 last_(NULL),
769 numberMajor_(0),
770 maximumMajor_(0),
771 numberElements_(0),
772 maximumElements_(0),
773 type_(-1)
774{
775}
776
777//-------------------------------------------------------------------
778// Copy constructor
779//-------------------------------------------------------------------
780CoinModelLinkedList::CoinModelLinkedList (const CoinModelLinkedList & rhs)
781 : numberMajor_(rhs.numberMajor_),
782 maximumMajor_(rhs.maximumMajor_),
783 numberElements_(rhs.numberElements_),
784 maximumElements_(rhs.maximumElements_),
785 type_(rhs.type_)
786{
787 if (maximumMajor_) {
788 previous_ = CoinCopyOfArray(rhs.previous_,maximumElements_);
789 next_ = CoinCopyOfArray(rhs.next_,maximumElements_);
790 first_ = CoinCopyOfArray(rhs.first_,maximumMajor_+1);
791 last_ = CoinCopyOfArray(rhs.last_,maximumMajor_+1);
792 } else {
793 previous_ = NULL;
794 next_ = NULL;
795 first_ = NULL;
796 last_ = NULL;
797 }
798}
799
800//-------------------------------------------------------------------
801// Destructor
802//-------------------------------------------------------------------
803CoinModelLinkedList::~CoinModelLinkedList ()
804{
805 delete [] previous_;
806 delete [] next_;
807 delete [] first_;
808 delete [] last_;
809}
810
811//----------------------------------------------------------------
812// Assignment operator
813//-------------------------------------------------------------------
814CoinModelLinkedList &
815CoinModelLinkedList::operator=(const CoinModelLinkedList& rhs)
816{
817 if (this != &rhs) {
818 delete [] previous_;
819 delete [] next_;
820 delete [] first_;
821 delete [] last_;
822 numberMajor_ = rhs.numberMajor_;
823 maximumMajor_ = rhs.maximumMajor_;
824 numberElements_ = rhs.numberElements_;
825 maximumElements_ = rhs.maximumElements_;
826 type_ = rhs.type_;
827 if (maximumMajor_) {
828 previous_ = CoinCopyOfArray(rhs.previous_,maximumElements_);
829 next_ = CoinCopyOfArray(rhs.next_,maximumElements_);
830 first_ = CoinCopyOfArray(rhs.first_,maximumMajor_+1);
831 last_ = CoinCopyOfArray(rhs.last_,maximumMajor_+1);
832 } else {
833 previous_ = NULL;
834 next_ = NULL;
835 first_ = NULL;
836 last_ = NULL;
837 }
838 }
839 return *this;
840}
841// Resize list - for row list maxMajor is maximum rows
842void
843CoinModelLinkedList::resize(int maxMajor,int maxElements)
844{
845 maxMajor=CoinMax(maxMajor,maximumMajor_);
846 maxElements=CoinMax(maxElements,maximumElements_);
847 if (maxMajor>maximumMajor_) {
848 int * first = new int [maxMajor+1];
849 int free;
850 if (maximumMajor_) {
851 CoinMemcpyN(first_,maximumMajor_,first);
852# ifdef ZEROFAULT
853 memset(first+maximumMajor_,0,(maxMajor-maximumMajor_)*sizeof(int)) ;
854# endif
855 free = first_[maximumMajor_];
856 first[maximumMajor_]=-1;
857 } else {
858 free=-1;
859 }
860 first[maxMajor]=free;
861 delete [] first_;
862 first_=first;
863 int * last = new int [maxMajor+1];
864 if (maximumMajor_) {
865 CoinMemcpyN(last_,maximumMajor_,last);
866# ifdef ZEROFAULT
867 memset(last+maximumMajor_,0,(maxMajor-maximumMajor_)*sizeof(int)) ;
868# endif
869 free = last_[maximumMajor_];
870 last[maximumMajor_]=-1;
871 } else {
872 free=-1;
873 }
874 last[maxMajor]=free;
875 delete [] last_;
876 last_=last;
877 maximumMajor_ = maxMajor;
878 }
879 if ( maxElements>maximumElements_) {
880 int * previous = new int [maxElements];
881 CoinMemcpyN(previous_,numberElements_,previous);
882# ifdef ZEROFAULT
883 memset(previous+numberElements_,0,
884 (maxElements-numberElements_)*sizeof(int)) ;
885# endif
886 delete [] previous_;
887 previous_=previous;
888 int * next = new int [maxElements];
889 CoinMemcpyN(next_,numberElements_,next);
890# ifdef ZEROFAULT
891 memset(next+numberElements_,0,(maxElements-numberElements_)*sizeof(int)) ;
892# endif
893 delete [] next_;
894 next_=next;
895 maximumElements_=maxElements;
896 }
897}
898// Create list - for row list maxMajor is maximum rows
899void
900CoinModelLinkedList::create(int maxMajor,int maxElements,
901 int numberMajor,int /*numberMinor*/, int type,
902 int numberElements, const CoinModelTriple * triples)
903{
904 maxMajor=CoinMax(maxMajor,maximumMajor_);
905 maxMajor=CoinMax(maxMajor,numberMajor);
906 maxElements=CoinMax(maxElements,maximumElements_);
907 maxElements=CoinMax(maxElements,numberElements);
908 type_=type;
909 assert (!previous_);
910 previous_ = new int [maxElements];
911 next_ = new int [maxElements];
912 maximumElements_=maxElements;
913 assert (maxElements>=numberElements);
914 assert (maxMajor>0&&!maximumMajor_);
915 first_ = new int[maxMajor+1];
916 last_ = new int[maxMajor+1];
917# ifdef ZEROFAULT
918 memset(previous_,0,maxElements*sizeof(int)) ;
919 memset(next_,0,maxElements*sizeof(int)) ;
920 memset(first_,0,(maxMajor+1)*sizeof(int)) ;
921 memset(last_,0,(maxMajor+1)*sizeof(int)) ;
922# endif
923 assert (numberElements>=0);
924 numberElements_=numberElements;
925 maximumMajor_ = maxMajor;
926 // do lists
927 int i;
928 for (i=0;i<numberMajor;i++) {
929 first_[i]=-1;
930 last_[i]=-1;
931 }
932 first_[maximumMajor_]=-1;
933 last_[maximumMajor_]=-1;
934 int freeChain=-1;
935 for (i=0;i<numberElements;i++) {
936 if (triples[i].column>=0) {
937 int iMajor;
938 int iMinor;
939 if (!type_) {
940 // for rows
941 iMajor=static_cast<int> (rowInTriple(triples[i]));
942 iMinor=triples[i].column;
943 } else {
944 iMinor=static_cast<int> (rowInTriple(triples[i]));
945 iMajor=triples[i].column;
946 }
947 assert (iMajor<numberMajor);
948 if (first_[iMajor]>=0) {
949 // not first
950 int j=last_[iMajor];
951 next_[j]=i;
952 previous_[i]=j;
953 } else {
954 // first
955 first_[iMajor]=i;
956 previous_[i]=-1;
957 }
958 last_[iMajor]=i;
959 } else {
960 // on deleted list
961 if (freeChain>=0) {
962 next_[freeChain]=i;
963 previous_[i]=freeChain;
964 } else {
965 first_[maximumMajor_]=i;
966 previous_[i]=-1;
967 }
968 freeChain=i;
969 }
970 }
971 // Now clean up
972 if (freeChain>=0) {
973 next_[freeChain]=-1;
974 last_[maximumMajor_]=freeChain;
975 }
976 for (i=0;i<numberMajor;i++) {
977 int k=last_[i];
978 if (k>=0) {
979 next_[k]=-1;
980 last_[i]=k;
981 }
982 }
983 numberMajor_=numberMajor;
984}
985/* Adds to list - easy case i.e. add row to row list
986 Returns where chain starts
987*/
988int
989CoinModelLinkedList::addEasy(int majorIndex, int numberOfElements, const int * indices,
990 const double * elements, CoinModelTriple * triples,
991 CoinModelHash2 & hash)
992{
993 assert (majorIndex<maximumMajor_);
994 if (numberOfElements+numberElements_>maximumElements_) {
995 resize(maximumMajor_,(3*(numberElements_+numberOfElements))/2+1000);
996 }
997 int first=-1;
998 if (majorIndex>=numberMajor_) {
999 for (int i=numberMajor_;i<=majorIndex;i++) {
1000 first_[i]=-1;
1001 last_[i]=-1;
1002 }
1003 }
1004 if (numberOfElements) {
1005 bool doHash = hash.maximumItems()!=0;
1006 int lastFree=last_[maximumMajor_];
1007 int last=last_[majorIndex];
1008 for (int i=0;i<numberOfElements;i++) {
1009 int put;
1010 if (lastFree>=0) {
1011 put=lastFree;
1012 lastFree=previous_[lastFree];
1013 } else {
1014 put=numberElements_;
1015 assert (put<maximumElements_);
1016 numberElements_++;
1017 }
1018 if (type_==0) {
1019 // row
1020 setRowAndStringInTriple(triples[put],majorIndex,false);
1021 triples[put].column=indices[i];
1022 } else {
1023 // column
1024 setRowAndStringInTriple(triples[put],indices[i],false);
1025 triples[put].column=majorIndex;
1026 }
1027 triples[put].value=elements[i];
1028 if (doHash)
1029 hash.addHash(put,static_cast<int> (rowInTriple(triples[put])),triples[put].column,triples);
1030 if (last>=0) {
1031 next_[last]=put;
1032 } else {
1033 first_[majorIndex]=put;
1034 }
1035 previous_[put]=last;
1036 last=put;
1037 }
1038 next_[last]=-1;
1039 if (last_[majorIndex]<0) {
1040 // first in row
1041 first = first_[majorIndex];
1042 } else {
1043 first = next_[last_[majorIndex]];
1044 }
1045 last_[majorIndex]=last;
1046 if (lastFree>=0) {
1047 next_[lastFree]=-1;
1048 last_[maximumMajor_]=lastFree;
1049 } else {
1050 first_[maximumMajor_]=-1;
1051 last_[maximumMajor_]=-1;
1052 }
1053 }
1054 numberMajor_=CoinMax(numberMajor_,majorIndex+1);
1055 return first;
1056}
1057/* Adds to list - hard case i.e. add row to column list
1058 */
1059void
1060CoinModelLinkedList::addHard(int minorIndex, int numberOfElements, const int * indices,
1061 const double * elements, CoinModelTriple * triples,
1062 CoinModelHash2 & hash)
1063{
1064 int lastFree=last_[maximumMajor_];
1065 bool doHash = hash.maximumItems()!=0;
1066 for (int i=0;i<numberOfElements;i++) {
1067 int put;
1068 if (lastFree>=0) {
1069 put=lastFree;
1070 lastFree=previous_[lastFree];
1071 } else {
1072 put=numberElements_;
1073 assert (put<maximumElements_);
1074 numberElements_++;
1075 }
1076 int other=indices[i];
1077 if (type_==0) {
1078 // row
1079 setRowAndStringInTriple(triples[put],other,false);
1080 triples[put].column=minorIndex;
1081 } else {
1082 // column
1083 setRowAndStringInTriple(triples[put],minorIndex,false);
1084 triples[put].column=other;
1085 }
1086 triples[put].value=elements[i];
1087 if (doHash)
1088 hash.addHash(put,static_cast<int> (rowInTriple(triples[put])),triples[put].column,triples);
1089 if (other>=numberMajor_) {
1090 // Need to fill in null values
1091 fill(numberMajor_,other+1);
1092 numberMajor_=other+1;
1093 }
1094 int last=last_[other];
1095 if (last>=0) {
1096 next_[last]=put;
1097 } else {
1098 first_[other]=put;
1099 }
1100 previous_[put]=last;
1101 next_[put]=-1;
1102 last_[other]=put;
1103 }
1104 if (lastFree>=0) {
1105 next_[lastFree]=-1;
1106 last_[maximumMajor_]=lastFree;
1107 } else {
1108 first_[maximumMajor_]=-1;
1109 last_[maximumMajor_]=-1;
1110 }
1111}
1112/* Adds to list - hard case i.e. add row to column list
1113 This is when elements have been added to other copy
1114*/
1115void
1116CoinModelLinkedList::addHard(int first, const CoinModelTriple * triples,
1117 int firstFree, int lastFree,const int * next)
1118{
1119 first_[maximumMajor_]=firstFree;
1120 last_[maximumMajor_]=lastFree;
1121 int put=first;
1122 int minorIndex=-1;
1123 while (put>=0) {
1124 assert (put<maximumElements_);
1125 numberElements_=CoinMax(numberElements_,put+1);
1126 int other;
1127 if (type_==0) {
1128 // row
1129 other=rowInTriple(triples[put]);
1130 if (minorIndex>=0)
1131 assert(triples[put].column==minorIndex);
1132 else
1133 minorIndex=triples[put].column;
1134 } else {
1135 // column
1136 other=triples[put].column;
1137 if (minorIndex>=0)
1138 assert(static_cast<int> (rowInTriple(triples[put]))==minorIndex);
1139 else
1140 minorIndex=rowInTriple(triples[put]);
1141 }
1142 assert (other<maximumMajor_);
1143 if (other>=numberMajor_) {
1144 // Need to fill in null values
1145 fill (numberMajor_,other+1);
1146 numberMajor_=other+1;
1147 }
1148 int last=last_[other];
1149 if (last>=0) {
1150 next_[last]=put;
1151 } else {
1152 first_[other]=put;
1153 }
1154 previous_[put]=last;
1155 next_[put]=-1;
1156 last_[other]=put;
1157 put = next[put];
1158 }
1159}
1160/* Deletes from list - same case i.e. delete row from row list
1161*/
1162void
1163CoinModelLinkedList::deleteSame(int which, CoinModelTriple * triples,
1164 CoinModelHash2 & hash, bool zapTriples)
1165{
1166 assert (which>=0);
1167 if (which<numberMajor_) {
1168 int lastFree=last_[maximumMajor_];
1169 int put=first_[which];
1170 first_[which]=-1;
1171 while (put>=0) {
1172 if (hash.numberItems()) {
1173 // take out of hash
1174 hash.deleteHash(put, static_cast<int> (rowInTriple(triples[put])),triples[put].column);
1175 }
1176 if (zapTriples) {
1177 triples[put].column=-1;
1178 triples[put].value=0.0;
1179 }
1180 if (lastFree>=0) {
1181 next_[lastFree]=put;
1182 } else {
1183 first_[maximumMajor_]=put;
1184 }
1185 previous_[put]=lastFree;
1186 lastFree=put;
1187 put=next_[put];
1188 }
1189 if (lastFree>=0) {
1190 next_[lastFree]=-1;
1191 last_[maximumMajor_]=lastFree;
1192 } else {
1193 assert (last_[maximumMajor_]==-1);
1194 }
1195 last_[which]=-1;
1196 }
1197}
1198/* Deletes from list - other case i.e. delete row from column list
1199 This is when elements have been deleted from other copy
1200*/
1201void
1202CoinModelLinkedList::updateDeleted(int /*which*/, CoinModelTriple * triples,
1203 CoinModelLinkedList & otherList)
1204{
1205 int firstFree = otherList.firstFree();
1206 int lastFree = otherList.lastFree();
1207 const int * previousOther = otherList.previous();
1208 assert (maximumMajor_);
1209 if (lastFree>=0) {
1210 // First free should be same
1211 if (first_[maximumMajor_]>=0)
1212 assert (firstFree==first_[maximumMajor_]);
1213 int last = last_[maximumMajor_];
1214 first_[maximumMajor_]=firstFree;
1215 // Maybe nothing to do
1216 if (last_[maximumMajor_]==lastFree)
1217 return;
1218 last_[maximumMajor_]=lastFree;
1219 int iMajor;
1220 if (!type_) {
1221 // for rows
1222 iMajor=static_cast<int> (rowInTriple(triples[lastFree]));
1223 } else {
1224 iMajor=triples[lastFree].column;
1225 }
1226 if (first_[iMajor]>=0) {
1227 // take out
1228 int previousThis = previous_[lastFree];
1229 int nextThis = next_[lastFree];
1230 if (previousThis>=0&&previousThis!=last) {
1231 next_[previousThis]=nextThis;
1232 int iTest;
1233 if (!type_) {
1234 // for rows
1235 iTest=static_cast<int> (rowInTriple(triples[previousThis]));
1236 } else {
1237 iTest=triples[previousThis].column;
1238 }
1239 assert (triples[previousThis].column>=0);
1240 assert (iTest==iMajor);
1241 } else {
1242 first_[iMajor]=nextThis;
1243 }
1244 if (nextThis>=0) {
1245 previous_[nextThis]=previousThis;
1246 int iTest;
1247 if (!type_) {
1248 // for rows
1249 iTest=static_cast<int> (rowInTriple(triples[nextThis]));
1250 } else {
1251 iTest=triples[nextThis].column;
1252 }
1253 assert (triples[nextThis].column>=0);
1254 assert (iTest==iMajor);
1255 } else {
1256 last_[iMajor]=previousThis;
1257 }
1258 }
1259 triples[lastFree].column=-1;
1260 triples[lastFree].value=0.0;
1261 // Do first (by which I mean last)
1262 next_[lastFree]=-1;
1263 int previous = previousOther[lastFree];
1264 while (previous!=last) {
1265 if (previous>=0) {
1266 if (!type_) {
1267 // for rows
1268 iMajor=static_cast<int> (rowInTriple(triples[previous]));
1269 } else {
1270 iMajor=triples[previous].column;
1271 }
1272 if (first_[iMajor]>=0) {
1273 // take out
1274 int previousThis = previous_[previous];
1275 int nextThis = next_[previous];
1276 if (previousThis>=0&&previousThis!=last) {
1277 next_[previousThis]=nextThis;
1278 int iTest;
1279 if (!type_) {
1280 // for rows
1281 iTest=static_cast<int> (rowInTriple(triples[previousThis]));
1282 } else {
1283 iTest=triples[previousThis].column;
1284 }
1285 assert (triples[previousThis].column>=0);
1286 assert (iTest==iMajor);
1287 } else {
1288 first_[iMajor]=nextThis;
1289 }
1290 if (nextThis>=0) {
1291 previous_[nextThis]=previousThis;
1292 int iTest;
1293 if (!type_) {
1294 // for rows
1295 iTest=static_cast<int> (rowInTriple(triples[nextThis]));
1296 } else {
1297 iTest=triples[nextThis].column;
1298 }
1299 assert (triples[nextThis].column>=0);
1300 assert (iTest==iMajor);
1301 } else {
1302 last_[iMajor]=previousThis;
1303 }
1304 }
1305 triples[previous].column=-1;
1306 triples[previous].value=0.0;
1307 next_[previous]=lastFree;
1308 } else {
1309 assert (lastFree==firstFree);
1310 }
1311 previous_[lastFree]=previous;
1312 lastFree=previous;
1313 previous = previousOther[lastFree];
1314 }
1315 if (last>=0) {
1316 next_[previous]=lastFree;
1317 } else {
1318 assert (firstFree==lastFree);
1319 }
1320 previous_[lastFree]=previous;
1321 }
1322}
1323/* Deletes one element from Row list
1324 */
1325void
1326CoinModelLinkedList::deleteRowOne(int position, CoinModelTriple * triples,
1327 CoinModelHash2 & hash)
1328{
1329 int row=rowInTriple(triples[position]);
1330 assert (row<numberMajor_);
1331 if (hash.numberItems()) {
1332 // take out of hash
1333 hash.deleteHash(position, static_cast<int> (rowInTriple(triples[position])),triples[position].column);
1334 }
1335 int previous = previous_[position];
1336 int next = next_[position];
1337 // put on free list
1338 int lastFree=last_[maximumMajor_];
1339 if (lastFree>=0) {
1340 next_[lastFree]=position;
1341 } else {
1342 first_[maximumMajor_]=position;
1343 assert (last_[maximumMajor_]==-1);
1344 }
1345 last_[maximumMajor_]=position;
1346 previous_[position]=lastFree;
1347 next_[position]=-1;
1348 // Now take out of row
1349 if (previous>=0) {
1350 next_[previous]=next;
1351 } else {
1352 first_[row]=next;
1353 }
1354 if (next>=0) {
1355 previous_[next]=previous;
1356 } else {
1357 last_[row]=previous;
1358 }
1359}
1360/* Update column list for one element when
1361 one element deleted from row copy
1362*/
1363void
1364CoinModelLinkedList::updateDeletedOne(int position, const CoinModelTriple * triples)
1365{
1366 assert (maximumMajor_);
1367 int column=triples[position].column;
1368 assert (column>=0&&column<numberMajor_);
1369 int previous = previous_[position];
1370 int next = next_[position];
1371 // put on free list
1372 int lastFree=last_[maximumMajor_];
1373 if (lastFree>=0) {
1374 next_[lastFree]=position;
1375 } else {
1376 first_[maximumMajor_]=position;
1377 assert (last_[maximumMajor_]==-1);
1378 }
1379 last_[maximumMajor_]=position;
1380 previous_[position]=lastFree;
1381 next_[position]=-1;
1382 // Now take out of column
1383 if (previous>=0) {
1384 next_[previous]=next;
1385 } else {
1386 first_[column]=next;
1387 }
1388 if (next>=0) {
1389 previous_[next]=previous;
1390 } else {
1391 last_[column]=previous;
1392 }
1393}
1394// Fills first,last with -1
1395void
1396CoinModelLinkedList::fill(int first,int last)
1397{
1398 for (int i=first;i<last;i++) {
1399 first_[i]=-1;
1400 last_[i]=-1;
1401 }
1402}
1403/* Puts in free list from other list */
1404void
1405CoinModelLinkedList::synchronize(CoinModelLinkedList & other)
1406{
1407 int first = other.first_[other.maximumMajor_];
1408 first_[maximumMajor_]=first;
1409 int last = other.last_[other.maximumMajor_];
1410 last_[maximumMajor_]=last;
1411 int put=first;
1412 while (put>=0) {
1413 previous_[put]=other.previous_[put];
1414 next_[put]=other.next_[put];
1415 put = next_[put];
1416 }
1417}
1418// Checks that links are consistent
1419void
1420CoinModelLinkedList::validateLinks(const CoinModelTriple * triples) const
1421{
1422 char * mark = new char[maximumElements_];
1423 memset(mark,0,maximumElements_);
1424 int lastElement=-1;
1425 int i;
1426 for ( i=0;i<numberMajor_;i++) {
1427 int position = first_[i];
1428 int lastPosition=-1;
1429 while (position>=0) {
1430 int iMajor;
1431 if (position!=first_[i])
1432 assert (next_[previous_[position]]==position);
1433 if (!type_) {
1434 // for rows
1435 iMajor=static_cast<int> (rowInTriple(triples[position]));
1436 } else {
1437 iMajor=triples[position].column;
1438 }
1439 assert (triples[position].column>=0);
1440 mark[position]=1;
1441 lastElement = CoinMax(lastElement,position);
1442 assert (i==iMajor);
1443 lastPosition=position;
1444 position = next_[position];
1445 }
1446 assert (lastPosition==last_[i]);
1447 }
1448 for (i=0;i<=lastElement;i++) {
1449 if (!mark[i])
1450 assert(triples[i].column==-1);
1451 }
1452 delete [] mark;
1453}
1454