1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the class library                   */
4    	/*       SoPlex --- the Sequential object-oriented simPlex.                  */
5    	/*                                                                           */
6    	/*  Copyright (c) 1996-2023 Zuse Institute Berlin (ZIB)                      */
7    	/*                                                                           */
8    	/*  Licensed under the Apache License, Version 2.0 (the "License");          */
9    	/*  you may not use this file except in compliance with the License.         */
10   	/*  You may obtain a copy of the License at                                  */
11   	/*                                                                           */
12   	/*      http://www.apache.org/licenses/LICENSE-2.0                           */
13   	/*                                                                           */
14   	/*  Unless required by applicable law or agreed to in writing, software      */
15   	/*  distributed under the License is distributed on an "AS IS" BASIS,        */
16   	/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17   	/*  See the License for the specific language governing permissions and      */
18   	/*  limitations under the License.                                           */
19   	/*                                                                           */
20   	/*  You should have received a copy of the Apache-2.0 license                */
21   	/*  along with SoPlex; see the file LICENSE. If not email to soplex@zib.de.  */
22   	/*                                                                           */
23   	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24   	
25   	/**@file  dsvectorbase.h
26   	 * @brief Dynamic sparse vectors.
27   	 */
28   	#ifndef _DSVECTORBASE_H_
29   	#define _DSVECTORBASE_H_
30   	
31   	#include <assert.h>
32   	
33   	#include "soplex/svectorbase.h"
34   	
35   	namespace soplex
36   	{
37   	template < class R > class VectorBase;
38   	template < class S > class SSVectorBase;
39   	template < class R > class SLinSolver;
40   	
41   	/**@brief   Dynamic sparse vectors.
42   	 * @ingroup Algebra
43   	 *
44   	 *  Class DSVectorBase implements dynamic sparse vectors, i.e. #SVectorBase%s with an automatic memory management. This
45   	 *  allows the user to freely add() as many nonzeros to a DSVectorBase as desired, without any precautions.  For saving
46   	 *  memory method setMax() allows to reduce memory consumption to the amount really required.
47   	 *
48   	 *  @todo Both DSVectorBase and SVectorBase have a member variable that points to allocated memory. This does not seem to
49   	 *        make too much sense.  Why doesn't DSVectorBase use the element of its base class?
50   	 */
51   	template < class R >
52   	class DSVectorBase : public SVectorBase<R>
53   	{
54   	   friend class SLinSolver<R>;
55   	
56   	private:
57   	
58   	   // ------------------------------------------------------------------------------------------------------------------
59   	   /**@name Data */
60   	   ///@{
61   	
62   	   /// Memory.
63   	   Nonzero<R>* theelem;
64   	
65   	   ///@}
66   	
67   	   // ------------------------------------------------------------------------------------------------------------------
68   	   /**@name Private helpers */
69   	   ///@{
70   	
71   	   /// Allocate memory for \p n nonzeros.
72   	   void allocMem(int n)
73   	   {
74   	      spx_alloc(theelem, n);
75   	
76   	      for(int i = 0; i < n; i++)
77   	         new(&(theelem[i])) Nonzero<R>();
78   	
79   	      SVectorBase<R>::setMem(n, theelem);
80   	   }
81   	
82   	   /// Ensure there is room for \p n new nonzeros.
83   	   void makeMem(int n)
84   	   {
85   	      assert(n >= 0);
86   	
87   	      if(SVectorBase<R>::max() - SVectorBase<R>::size() < n)
88   	      {
89   	         assert(SVectorBase<R>::size() + n > 0);
90   	         setMax(SVectorBase<R>::size() + n);
91   	      }
92   	   }
93   	
94   	   ///@}
95   	
96   	public:
97   	
98   	   // ------------------------------------------------------------------------------------------------------------------
99   	   /**@name Construction, assignment, and destruction */
100  	   ///@{
101  	
102  	   /// Default constructor.
103  	   /** Creates a DSVectorBase ready to hold \p n nonzeros. However, the memory is automatically enlarged, if more
104  	    *  nonzeros are added to the DSVectorBase.
105  	    */
106  	   explicit DSVectorBase(int n = 8)
107  	      : theelem(0)
108  	   {
109  	      allocMem((n < 1) ? 2 : n);
110  	
111  	      assert(isConsistent());
112  	   }
113  	
114  	   /// Copy constructor.
115  	   template < class S >
116  	   explicit DSVectorBase(const SVectorBase<S>& old)
117  	      : theelem(0)
118  	   {
119  	      allocMem(old.size());
120  	      SVectorBase<R>::operator=(old);
121  	
122  	      assert(isConsistent());
123  	   }
124  	
125  	   /// Copy constructor.
126  	   /** The redundancy with the copy constructor below is necessary since otherwise the compiler doesn't realize that it
127  	    *  could use the more general one with S = R and generates a shallow copy constructor.
128  	    */
129  	   DSVectorBase(const DSVectorBase<R>& old)
130  	      : SVectorBase<R>()
131  	      , theelem(0)
132  	   {
133  	      allocMem(old.size());
134  	      SVectorBase<R>::operator=(old);
135  	
136  	      assert(isConsistent());
137  	   }
138  	
139  	   /// Copy constructor.
140  	   template < class S >
141  	   DSVectorBase(const DSVectorBase<S>& old)
142  	      : SVectorBase<R>()
143  	      , theelem(0)
144  	   {
145  	      allocMem(old.size());
146  	      SVectorBase<R>::operator=(old);
147  	
148  	      assert(isConsistent());
149  	   }
150  	
151  	   /// Copy constructor.
152  	   template < class S >
153  	   explicit DSVectorBase(const VectorBase<S>& vec);
154  	
155  	   /// Copy constructor.
156  	   template < class S >
157  	   explicit DSVectorBase(const SSVectorBase<S>& old);
158  	
159  	   /// Assignment operator.
160  	   template < class S >
161  	   DSVectorBase<R>& operator=(const SVectorBase<S>& vec)
162  	   {
163  	      if(this != &vec)
164  	      {
165  	         SVectorBase<R>::clear();
166  	         makeMem(vec.size());
167  	         SVectorBase<R>::operator=(vec);
168  	      }
169  	
170  	      return *this;
171  	   }
172  	
173  	   /// Assignment operator.
174  	   DSVectorBase<R>& operator=(const DSVectorBase<R>& vec)
175  	   {
176  	      if(this != &vec)
177  	      {
178  	         SVectorBase<R>::clear();
179  	         makeMem(vec.size());
180  	         SVectorBase<R>::operator=(vec);
181  	      }
182  	
183  	      return *this;
184  	   }
185  	
186  	   /// Assignment operator.
187  	   template < class S >
188  	   DSVectorBase<R>& operator=(const DSVectorBase<S>& vec)
189  	   {
190  	      if(this != (DSVectorBase<R>*)(&vec))
191  	      {
192  	         SVectorBase<R>::clear();
193  	         makeMem(vec.size());
194  	         SVectorBase<R>::operator=(vec);
195  	      }
196  	
197  	      return *this;
198  	   }
199  	
200  	   /// Assignment operator.
201  	   template < class S >
202  	   DSVectorBase<R>& operator=(const VectorBase<S>& vec);
203  	
204  	   /// Assignment operator.
205  	   template < class S >
206  	   DSVectorBase<R>& operator=(const SSVectorBase<S>& vec);
207  	
208  	   /// Destructor.
209  	   virtual ~DSVectorBase()
210  	   {
211  	      if(theelem)
212  	      {
213  	         for(int i = SVectorBase<R>::max() - 1; i >= 0; i--)
214  	            theelem[i].~Nonzero<R>();
215  	
216  	         spx_free(theelem);
217  	      }
218  	   }
219  	
220  	   ///@}
221  	
222  	   // ------------------------------------------------------------------------------------------------------------------
223  	   /**@name Modification */
224  	   ///@{
225  	
226  	   /// Append nonzeros of \p sv.
227  	   template < class S >
228  	   void add(const SVectorBase<S>& vec)
229  	   {
230  	      SVectorBase<R>::clear();
231  	      makeMem(vec.size());
232  	      SVectorBase<S>::add(vec);
233  	   }
234  	
235  	   /// Append one nonzero \p (i,v).
236  	   void add(int i, const R& v)
237  	   {
238  	      makeMem(1);
239  	      SVectorBase<R>::add(i, v);
240  	   }
241  	
242  	   /// Append one uninitialized nonzero.
243  	   void add(int i)
244  	   {
245  	      makeMem(1);
246  	      SVectorBase<R>::add(i);
247  	   }
248  	
249  	   /// Append \p n nonzeros.
250  	   void add(int n, const int i[], const R v[])
251  	   {
252  	      makeMem(n);
253  	      SVectorBase<R>::add(n, i, v);
254  	   }
255  	
256  	   /// Reset nonzero memory to >= \p newmax.
257  	   /** This methods resets the memory consumption to \p newmax. However, if \p newmax < size(), it is
258  	    *  reset to size() only.
259  	    */
260  	   void setMax(int newmax = 1)
261  	   {
262  	      int siz = SVectorBase<R>::size();
263  	      int len = (newmax < siz) ? siz : newmax;
264  	
265  	      if(len == SVectorBase<R>::max())
266  	         return;
267  	
268  	      Nonzero<R>* newmem = 0;
269  	
270  	      /* allocate new memory */
271  	      spx_alloc(newmem, len);
272  	
273  	      /* call copy constructor for first elements */
274  	      int i;
275  	
276  	      for(i = 0; i < siz; i++)
277  	         new((&newmem[i])) Nonzero<R>(theelem[i]);
278  	
279  	      /* call default constructor for remaining elements */
280  	      for(; i < len; i++)
281  	         new((&newmem[i])) Nonzero<R>();
282  	
283  	      /* free old memory */
284  	      for(i = SVectorBase<R>::max() - 1; i >= 0; i--)
285  	         theelem[i].~Nonzero<R>();
286  	
287  	      if(theelem != 0)
288  	         spx_free(theelem);
289  	
290  	      /* assign new memory */
291  	      theelem = newmem;
292  	      SVectorBase<R>::setMem(len, theelem);
293  	      SVectorBase<R>::set_size(siz);
294  	   }
295  	
296  	   ///@}
297  	
298  	   // ------------------------------------------------------------------------------------------------------------------
299  	   /**@name Utilities */
300  	   ///@{
301  	
302  	   /// Consistency check.
303  	   bool isConsistent() const
304  	   {
305  	#ifdef ENABLE_CONSISTENCY_CHECKS
306  	
307  	      if(theelem != 0 && SVectorBase<R>::mem() != theelem)
308  	         return SPX_MSG_INCONSISTENT("DSVectorBase");
309  	
310  	#endif
311  	
312  	      return true;
313  	   }
314  	
315  	   ///@}
316  	};
317  	
318  	
319  	
320  	/// Allocate memory for \p n nonzeros (specialization for Real).
321  	template<>
322  	inline
323  	void DSVectorBase<Real>::allocMem(int n)
324  	{
325  	   spx_alloc(theelem, n);
326  	   SVectorBase<Real>::setMem(n, theelem);
327  	}
328  	
329  	
330  	
331  	/// Destructor (specialization for Real).
332  	template<>
333  	inline
334  	DSVectorBase<Real>::~DSVectorBase()
335  	{
336  	   if(theelem)
337  	      spx_free(theelem);
338  	}
339  	
340  	
341  	
342  	/// Reset nonzero memory to >= \p newmax.
343  	/** This methods resets the memory consumption to \p newmax. However, if \p newmax < size(), it is
344  	 *  reset to size() only (specialization for Real).
345  	 */
346  	template<>
347  	inline
348  	void DSVectorBase<Real>::setMax(int newmax)
349  	{
350  	   int siz = size();
351  	   int len = (newmax < siz) ? siz : newmax;
352  	
353  	   spx_realloc(theelem, len);
354  	   setMem(len, theelem);
355  	   // reset 'size' to old size since the above call to setMem() sets 'size' to 0
356  	   set_size(siz);
357  	}
358  	} // namespace soplex
359  	#endif // _DSVECTORBASE_H_
360