Merge branch 'main' of feistymeow.org:feisty_meow
[feisty_meow.git] / basis / array.h
1 #ifndef ARRAY_CLASS
2 #define ARRAY_CLASS
3
4 /*****************************************************************************\
5 *                                                                             *
6 *  Name   : array                                                             *
7 *  Author : Chris Koeritz                                                     *
8 *                                                                             *
9 *******************************************************************************
10 * Copyright (c) 1989-$now By Author.  This program is free software; you can  *
11 * redistribute it and/or modify it under the terms of the GNU General Public  *
12 * License as published by the Free Software Foundation; either version 2 of   *
13 * the License or (at your option) any later version.  This is online at:      *
14 *     http://www.fsf.org/copyleft/gpl.html                                    *
15 * Please send any updates to: fred@gruntose.com                               *
16 \*****************************************************************************/
17
18 #include "common_outcomes.h"
19 #include "definitions.h"
20 #include "enhance_cpp.h"
21 #include "functions.h"
22 #include "guards.h"
23 #include "outcome.h"
24
25 #include <string.h>
26
27 #define DEBUG_ARRAY
28   // uncomment for the noisier debugging version.
29
30 namespace basis {
31
32 //! Represents a sequential, ordered, contiguous collection of objects.
33 /*!
34   This object manages a contiguous array of memory to hold the objects it
35   contains.  The objects to be stored must have a constructor with zero
36   parameters, since the objects are stored in a C-style array (and array
37   constructors cannot be given arguments to be passed to the objects).
38   The objects must also either be flat (containing no pointers) or have an
39   assignment operator (=) that correctly copies the deep contents.
40     This class also provides an exponential growth mode for memory to reduce
41   thrashing; this allows the size pre-allocated to double every time a new
42   allocation is required during a resize. This causes the allocation to grow
43   very swiftly, speeding up usage of frequently growing arrays, but this may
44   not be desired for every array.
45   terms used here...
46     blank array: a array with some number of elements, but where those
47        elements are objects that have been constructed using their default
48        parameterless constructor.
49     empty array: a array of zero elements.
50 */
51
52 template <class contents>
53 class array : public virtual root_object
54 {
55 public:
56   //! the flags specify how the array treats its contents and its length.
57   enum specialc_flags {
58     NO_SPECIAL_MODES = 0x0,  //!< do nothing extra; only valid by itself.
59     SIMPLE_COPY = 0x1,  //!< the contents can be memcpy'd and are not deep.
60     EXPONENTIAL_GROWTH = 0x2,  //!< length is doubled when reallocation happens.
61     EXPONE = EXPONENTIAL_GROWTH,  //!< synonym for EXPONENTIAL_GROWTH.
62     FLUSH_INVISIBLE = 0x4  //!< blanks out allocated but inaccessible elements.
63   };
64
65   DEFINE_CLASS_NAME("array");
66
67   enum how_to_copy { NEW_AT_END, NEW_AT_BEGINNING, DONT_COPY }; 
68     //!< An enumeration of ways to shift existing contents in an array.
69     /*!< In the context of dynamically resizing an array of data, a range of
70     new elements can be added (or removed for that matter) at the end of the
71     existing space (NEW_AT_END), at the beginning of the existing space
72     (NEW_AT_BEGINNING), or we might not care about the existing data when
73     we perform the resize (DONT_COPY).  These methods impose a particular
74     shift on the existing contents if we actually already have enough space
75     for the new contents.  If there is space before the part of the array
76     that's in use and we want NEW_AT_END, then the existing contents are
77     jammed up into the front end of the array. */
78
79   array(int number = 0, const contents *init = NULL_POINTER,
80           int flags = EXPONENTIAL_GROWTH | FLUSH_INVISIBLE);
81     //!< Constructs an array with room for "number" objects.
82     /*!< The initial contents are copied from "init" unless NULL_POINTER is passed in
83     instead.  If "init" is not NULL_POINTER, then it must point to an array of objects
84     that contains at least "number".  The "flags" are a value based on the
85     special flags being added bit-wise.  If "flags" contains SIMPLE_COPY, then
86     memmove() is used rather than using the C++ object's assignment operator.
87     Note that SIMPLE_COPY will NOT work if the templated object has a regular
88     constructor or assignment operator, since those methods will not be
89     called on copying.  If the "flags" contain EXPONENTIAL_GROWTH, then the
90     true allocation size will be doubled every time a new allocation is
91     required.  when the FLUSH_INVISIBLE flag is included, then the array
92     elements that go out of scope are returned to the state provided by
93     the content's default constructor.  this ensures that if they ever come
94     back into scope, they do not yet have any contents.  further, if the
95     elements had any deep contents, those resources should be released. */
96
97   array(const array<contents> &copy_from);
98     //!< copies the contents & sizing information from "copy_from".
99
100   virtual ~array();  //!< destroys the memory allocated for the objects.
101
102   void reset(int number = 0, const contents *initial_contents = NULL_POINTER);
103     //!< Resizes this array and sets the contents from an array of contents.
104     /*< If "initial_contents" is not NULL_POINTER, then it must contain an array of
105     "contents" with at least "number" objects in it.  If it is NULL_POINTER, then
106     the size of the array is changed but the contents are not.  note that
107     any pre-existing elements that were previously out of range might still
108     have their prior contents; the newly available elements are not necessarily
109     "blank".  thus, before using them, ensure you store appropriate elements
110     in those positions. */
111
112   array &operator = (const array<contents> &copy_from);
113     //!< Copies the array in "copy_from" into this.
114
115   int length() const { return c_active_length; }
116     //!< Returns the current reported length of the allocated C array.
117
118   int last() const { return c_active_length - 1; }
119     //!< Returns the last valid element in the array.
120
121   int flags() const { return c_flags; }
122     //!< Provides the raw flags value, without interpreting what it means.
123
124   bool exponential() const { return c_flags & EXPONENTIAL_GROWTH; }
125     //!< Returns true if this allocator will grow exponentially on resize.
126
127   bool simple() const { return c_flags & SIMPLE_COPY; }
128     //!< Reports whether the templated object is a simple type or not.
129
130   const contents &get(int index) const;
131     //!< Accesses individual objects stored in "this" at the "index" position.
132     /*!< If the index is out of range, then a bogus reference (to internally
133     held garbage) is returned. */
134   contents &use(int index);
135     //!< A non-constant version of get(); the returned object can be modified.
136
137   const contents &operator [] (int index) const { return get(index); }
138     //!< Synonym for get that provides the expected array indexing syntax.
139   contents &operator [] (int index) { return use(index); }
140     //!< Synonym for use that provides the expected array indexing syntax.
141
142   outcome put(int index, const contents &to_put);
143     //!< Stores an object at the index "index" in the array.
144     /*!< The outcome is "OUT_OF_RANGE" if the index does not exist. */
145
146   array concatenation(const array &to_concatenate) const;
147     //!< Returns the concatenation of "this" and the array "to_concatenate".
148   array concatenation(const contents &to_concatenate) const;
149     //!< Returns the concatenation of "this" and the object "to_concatenate".
150
151   array &concatenate(const array &to_concatenate);
152     //!< Appends the array "to_concatenate" onto "this" and returns "this".
153   array &concatenate(const contents &to_concatenate);
154     //!< Appends the object "to_concatenate" onto "this" and returns "this".
155   array &concatenate(const contents *to_concatenate, int length);
156     //!< Concatenates a C-array "to_concatenate" onto "this" and returns "this".
157     /*!< There must be at least "length" elements in "to_concatenate". */
158
159   array operator + (const array &to_cat) const
160           { return concatenation(to_cat); }
161     //!< Synonym for concatenation.
162   array operator + (const contents &to_concatenate) const
163           { return concatenation(to_concatenate); }
164     //!< Synonym for concatenation.
165   array &operator += (const array &to_concatenate)
166           { return concatenate(to_concatenate); }
167     //!< Synonym for concatenate that modifies "this".
168   array &operator += (const contents &to_concatenate)
169           { return concatenate(to_concatenate); }
170     //!< Synonym for concatenate that modifies "this".
171
172   const contents *observe() const { return c_offset; }
173     //!< Returns a pointer to the underlying C array of data.
174     /*!< The array contains "length()" number of objects in it.  BE CAREFUL.
175     This version is a constant peek at that pointer. */
176   contents *access() { return c_offset; }
177     //!< A non-constant access of the underlying C-array.  BE REALLY CAREFUL.
178
179   void swap_contents(array<contents> &other);
180     //!< Exchanges the contents of "this" and "other".
181     /*!< No validation is performed but this should always succeed given
182     arrays constructed properly. */
183
184   void snarf(array &new_contents);
185     //!< Drops "this" array's contents into the dustbin and uses "new_contents".
186     /*!< Afterwards, "new_contents" is an empty array and what used to be
187     stored there is now in "this" instead. */
188
189   array subarray(int start, int end) const;
190     //!< Returns the array segment between the indices "start" and "end".
191     /*!< This is all characters from "start" to "end" inclusively, as long as
192     those values are valid for this array.   Even then, an intelligent default
193     is usually assumed if the indices are out of range. */
194
195   outcome insert(int index, int new_indices);
196     //!< Adds "new_indices" new positions for objects into the array at "index".
197
198   outcome overwrite(int index, const array &write_with, int count = -1);
199     //!< Stores the array "write_with" into the current array at the "index".
200     /*!< The current contents are overwritten with "write_with".  If the
201     index is invalid, then OUT_OF_RANGE is returned.  If the "write_with"
202     array cannot fit due to the boundaries of "this" array, then only the
203     portion that can fit is used.  If "count" is negative, the whole
204     "write_with" array is used; otherwise, only "count" elements are used. */
205
206   outcome stuff(int length, contents *to_stuff) const;
207     //!< Copies at most "length" elements from this into the array "to_stuff".
208     /*!< This call will fail disastrously if "length" is larger than the
209     array "to_stuff"'s allocated length. */
210
211   outcome resize(int new_size, how_to_copy way = NEW_AT_END);
212     //!< Changes the size of the C array to "new_size".
213     /*!< If "way" is NEW_AT_END and the array grows, then new space is added
214     at the end and the prefix of the array is the same as the old array.  If
215     the "way" is NEW_AT_END, but the array shrinks, then the new array is a
216     prefix of the old array.  If "way" is NEW_AT_BEGINNING and the array
217     grows, then the suffix of the array is the same as the old one and the
218     space is added at the beginning.  if the "way" is NEW_AT_BEGINNING but the
219     array shrinks, then the new array is a suffix of the old array.  if "way"
220     is DONT_COPY, then the old contents are not copied.  keep in mind that
221     any newly visible elements can be in an arbitrary state and will not
222     necessarily be freshly constructed. */
223
224   outcome zap(int start, int end);
225     //!< Deletes from "this" the objects inclusively between "start" and "end".
226     /*!< C-array conventions are used (0 through length()-1 are valid if
227     length() > 0).  If either index is out of range, then a default is
228     assumed. */
229
230   outcome shrink();
231     //!< Cuts loose any allocated space that is beyond the real length.
232
233   outcome retrain(int new_size, const contents *to_copy);
234     //!< Resizes the C array and stuffs it with the contents in "to_copy".
235
236   enum shift_directions { TO_LEFT, TO_RIGHT };
237     //!< All the real contents can be shifted to either the left or right.
238
239   void shift_data(shift_directions where);
240     //!< The valid portion of the array is moved to the left or right.
241     /*!< This means that the unused space (dictated by the offset where the
242     data starts) will be adjusted.  This may involve copying the data. */
243
244   // These are gritty internal information methods and should not be used
245   // except by appropriately careful code.
246   int internal_real_length() const { return c_real_length; }
247     //!< Gritty Internal: the real allocated length.
248   int internal_offset() const { return int(c_offset - c_mem_block); }
249     //!< Gritty Internal: the offset from real start to stored data.
250   const contents *internal_block_start() const { return c_mem_block; }
251     //!< Gritty Internal: constant peek at the real allocated pointer.
252   contents *internal_block_start() { return c_mem_block; }
253     //!< Gritty Internal: the real allocated pointer made accessible.
254   contents * const *internal_offset_mem() const { return &c_offset; }
255     //!< Gritty Internal: the start of the actual stored data.
256
257 private:
258   int c_active_length; //!< the number of objects reported to be in the array.
259   int c_real_length;  // the real number of objects that can be stored.
260   contents *c_mem_block;  //!< a pointer to the objects held for this array.
261   contents *c_offset;  //!< the beginning of the useful part of the memory block.
262   int c_flags;  //!< records the special characteristics of this array.
263
264   outcome allocator_reset(int initial_elements, int blocking);
265     //!< Allocates space for the "initial_elements" plus the "blocking" factor.
266     /*!< This resets the C-array to have "initial_elements" indices, plus an
267     extra pre-allocation of "blocking" that leaves room for expansion.  Any
268     prior contents are whacked. */
269 };
270
271 //////////////
272
273 //! A simple object that wraps a templated array of ints.
274 class int_array : public array<int>
275 {
276 public:
277   int_array(int number = 0, const int *initial_contents = 0)
278       : root_object(),
279         array<int>(number, initial_contents, SIMPLE_COPY | EXPONE) {}
280     //!< Constructs an array of "number" integers.
281     /*!< creates a list of ints based on an initial "number" of entries and
282     some "initial_contents", which should be a regular C array of ints
283     with at least as many entries as "number". */
284 };
285
286 //////////////
287
288 //! An array of double floating point numbers.
289 class double_array : public array<double>
290 {
291 public:
292   double_array(int len = 0, double *data = NULL_POINTER)
293       : root_object(),
294         array<double>(len, data, SIMPLE_COPY | EXPONE) {}
295   double_array(const array<double> &to_copy) : array<double>(to_copy) {}
296 };
297
298 //////////////
299
300 // implementation code, much longer methods below...
301
302 // GOALS:
303 //
304 // 1) provide a slightly smarter allocation method for C arrays and other
305 //    contiguous-storage container classes with better speed and reduced memory
306 //    fragmentation through pre-allocation.  this can reduce memory thrashing
307 //    when doing appends and inserts that can be granted with previously
308 //    allocated, but unused, space.
309 // 2) clean-up bounds failure cases in functions that return a reference by
310 //    always having at least one bogus element in the array for returns.  this
311 //    really just requires that we never allow our hidden real length of the
312 //    array to be zero.
313
314 template <class contents>
315 array<contents>::array(int num, const contents *init, int flags)
316 : root_object(), c_active_length(0), c_real_length(0), c_mem_block(NULL_POINTER), c_offset(NULL_POINTER), c_flags(flags)
317 {
318   if (c_flags > 7) {
319 #ifdef DEBUG_ARRAY
320     throw "error: array::constructor: error in parameters!  still passing a block size?";
321 #endif
322     c_flags = EXPONE | FLUSH_INVISIBLE;
323       // drop simple copy, since the caller doesn't know what they're doing.
324   }
325
326   allocator_reset(num, 1);  // get some space.
327   retrain(num, init);  // plug in their contents.
328 }
329
330 template <class contents>
331 array<contents>::array(const array<contents> &cf)
332 : root_object(), c_active_length(0), c_real_length(0), c_mem_block(NULL_POINTER), c_offset(NULL_POINTER), c_flags(cf.c_flags)
333 {
334   allocator_reset(cf.c_active_length, 1);  // get some space.
335   operator = (cf);  // assignment operator does the rest.
336 }
337
338 template <class contents>
339 array<contents>::~array()
340 {
341   c_offset = NULL_POINTER;
342   if (c_mem_block) delete [] c_mem_block;
343   c_mem_block = NULL_POINTER;
344   c_active_length = 0;
345   c_real_length = 0;
346 }
347
348 template <class contents>
349 void array<contents>::reset(int num, const contents *init)
350 { retrain(num, init); }
351
352 template <class contents>
353 array<contents> &array<contents>::operator =(const array &cf)
354 {
355   if (this == &cf) return *this;
356   c_flags = cf.c_flags;  // copy the flags coming in from the other object.
357   // prepare the array for retraining...
358   c_offset = c_mem_block;  // slide the offset back to the start.
359   c_active_length = 0;  // the length gets reset also.
360   retrain(cf.c_active_length, cf.observe());
361   return *this;
362 }
363
364 template <class contents>
365 contents &array<contents>::use(int index)
366 {
367   bounds_return(index, 0, this->last(), bogonic<contents>());
368   return this->access()[index];
369 }
370
371 template <class contents>
372 const contents &array<contents>::get(int index) const
373 {
374   bounds_return(index, 0, this->last(), bogonic<contents>());
375   return this->observe()[index];
376 }
377
378 template <class contents>
379 array<contents> &array<contents>::concatenate(const array &s1)
380 {
381   // check whether there's anything to concatenate.
382   if (!s1.length()) return *this;
383   if (this == &s1) {
384     // make sure they don't concatenate this array to itself.
385     return concatenate(array<contents>(*this)); 
386   }
387   int old_len = this->length();
388   resize(this->length() + s1.length(), NEW_AT_END);
389   overwrite(old_len, s1);
390   return *this;
391 }
392
393 template <class contents>
394 array<contents> &array<contents>::concatenate(const contents &to_concatenate)
395 {
396   resize(this->length() + 1, NEW_AT_END);
397   if (!this->simple())
398     this->access()[this->last()] = to_concatenate;
399   else
400     memcpy(&(this->access()[this->last()]), &to_concatenate, sizeof(contents));
401   return *this;
402 }
403
404 template <class contents>
405 array<contents> &array<contents>::concatenate(const contents *to_concatenate,
406     int length)
407 {
408   if (!length) return *this;  // nothing to do.
409   const int old_len = this->length();
410   resize(this->length() + length, NEW_AT_END);
411   if (!this->simple())
412     for (int i = 0; i < length; i++)
413       this->access()[old_len + i] = to_concatenate[i];
414   else
415     memcpy(&(this->access()[old_len]), to_concatenate,
416         length * sizeof(contents));
417   return *this;
418 }
419
420 template <class contents>
421 array<contents> array<contents>::concatenation(const array &s1) const
422 {
423   // tailor the return array to the new size needed.
424   array<contents> to_return(this->length() + s1.length(), NULL_POINTER, s1.c_flags);
425   to_return.overwrite(0, *this);  // put the first part into the new array.
426   to_return.overwrite(this->length(), s1);  // add the second segment.
427   return to_return;
428 }
429
430 template <class contents>
431 array<contents> array<contents>::concatenation(const contents &s1) const
432 {
433   array<contents> to_return(this->length() + 1, NULL_POINTER, c_flags);
434   to_return.overwrite(0, *this);
435   if (!this->simple())
436     to_return.access()[to_return.last()] = s1;
437   else
438     memcpy(&(to_return.access()[to_return.last()]), &s1, sizeof(contents));
439   return to_return;
440 }
441
442 template <class contents>
443 array<contents> array<contents>::subarray(int start, int end) const
444 {
445   bounds_return(start, 0, this->last(), array<contents>(0, NULL_POINTER, c_flags));
446   bounds_return(end, 0, this->last(), array<contents>(0, NULL_POINTER, c_flags));
447   if (start > end) return array<contents>(0, NULL_POINTER, c_flags);
448   return array<contents>(end - start + 1, &(this->observe()[start]), c_flags);
449 }
450
451 template <class contents>
452 void array<contents>::swap_contents(array &other)
453 {
454   if (this == &other) return;  // already swapped then, i suppose.
455   swap_values(this->c_active_length, other.c_active_length);
456   swap_values(this->c_real_length, other.c_real_length);
457   swap_values(this->c_offset, other.c_offset);
458   swap_values(this->c_mem_block, other.c_mem_block);
459   swap_values(this->c_flags, other.c_flags);
460 }
461
462 template <class contents>
463 outcome array<contents>::shrink()
464 {
465   if (!c_mem_block) return common::OUT_OF_MEMORY;
466   if (c_active_length == c_real_length) return common::OKAY;  // already just right.
467   array new_holder(*this);
468     // create a copy of this object that is just the size needed.
469   swap_contents(new_holder);
470     // swap this object with the copy, leaving the enlarged version behind
471     // for destruction.
472   return common::OKAY;
473 }
474
475 template <class contents>
476 outcome array<contents>::stuff(int lengthx, contents *to_stuff) const
477 {
478   if (!lengthx || !this->length()) return common::OKAY;
479   int copy_len = minimum(lengthx, this->length());
480   if (!this->simple()) {
481     for (int i = 0; i < copy_len; i++)
482       to_stuff[i] = this->observe()[i];
483   } else {
484     memcpy(to_stuff, this->observe(), copy_len * sizeof(contents));
485   }
486   return common::OKAY;
487 }
488
489 template <class contents>
490 outcome array<contents>::overwrite(int position,
491     const array<contents> &write_with, int count)
492 {
493   if (!count) return common::OKAY;
494   if ( (this == &write_with) || !this->length() || !write_with.length())
495     return common::BAD_INPUT;
496   bounds_return(position, 0, this->last(), common::OUT_OF_RANGE);
497   if ( negative(count) || (count > write_with.length()) )
498     count = write_with.length();
499   if (position > this->length() - count)
500     count = this->length() - position;
501   if (!this->simple()) {
502     for (int i = position; i < position + count; i++)
503       this->access()[i] = write_with.observe()[i - position];
504   } else {
505     memcpy(&(this->access()[position]), write_with.observe(), 
506         count * sizeof(contents));
507   }
508   return common::OKAY;
509 }
510
511 template <class contents>
512 outcome array<contents>::allocator_reset(int initial, int blocking)
513 {
514 //  FUNCDEF("allocator_reset")
515   if (blocking < 1) {
516 #ifdef DEBUG_ARRAY
517     throw "error: array::allocator_reset: has bad block size";
518 #endif
519     blocking = 1;
520   }
521   if (initial < 0) initial = 0;  // no antimatter arrays.
522   if (c_mem_block) {
523     // remove old contents.
524     delete [] c_mem_block;
525     c_mem_block = NULL_POINTER;
526     c_offset = NULL_POINTER;
527   }
528   c_active_length = initial;  // reset the length to the reporting size.
529   c_real_length = initial + blocking;  // compute the real length.
530   if (c_real_length) {
531     c_mem_block = new contents[c_real_length];
532     if (!c_mem_block) {
533       // this is an odd situation; memory allocation didn't blow out an
534       // exception, but the memory block is empty.  let's consider that
535       // a fatal error; we can't issue empty objects.
536       throw common::OUT_OF_MEMORY;
537     }
538     c_offset = c_mem_block;  // reset offset to start of array.
539   }
540   return common::OKAY;
541 }
542
543 template <class contents>
544 void array<contents>::shift_data(shift_directions where)
545 {
546   if (where == TO_LEFT) {
547     // we want to end up with the data jammed up against the left edge.  thus
548     // we need the offset to be zero bytes from start.
549     if (c_offset == c_mem_block)
550       return;  // offset already at start, we're done.
551     // well, we need to move the data.
552     if (simple()) {
553       memmove(c_mem_block, c_offset, c_active_length * sizeof(contents));
554     } else {
555       for (contents *ptr = c_offset; ptr < c_offset + c_active_length; ptr++)
556         c_mem_block[ptr - c_offset] = *ptr;
557     }
558     c_offset = c_mem_block;  // we've ensured that this is correct.
559     if (c_flags & FLUSH_INVISIBLE) {
560       // we need to clean up what might have had contents previously.
561 //      for (contents *p = c_mem_block + c_active_length; p < c_mem_block + c_real_length; p++)
562 //        *p = contents();
563     }
564   } else {
565     // we want to move the data to the right, so the offset should be the
566     // difference between the real length and the length.
567     if (c_offset == c_mem_block + c_real_length - c_active_length)
568       return;  // the offset is already the right size.
569     if (simple()) {
570       memmove(&c_mem_block[c_real_length - c_active_length], c_offset, c_active_length * sizeof(contents));
571     } else {
572       for (int i = c_real_length - 1; i >= c_real_length - c_active_length; i--)
573         c_mem_block[i] = c_offset[i - c_real_length + c_active_length];
574     }
575     c_offset = c_mem_block + c_real_length - c_active_length;  // we've now ensured this.
576     if (c_flags & FLUSH_INVISIBLE) {
577       // we need to clean up the space on the left where old contents might be.
578 //      for (contents *p = c_mem_block; p < c_offset; p++)
579 //        *p = contents();
580     }
581   }
582 }
583
584 template <class contents>
585 outcome array<contents>::resize(int new_size, how_to_copy way)
586 {
587 ///  FUNCDEF("resize");
588   if (new_size < 0) new_size = 0;  // we stifle this.
589   if (new_size == c_active_length) {
590     // nothing much to do.
591     return common::OKAY;
592   }
593   // okay, now we at least know that the sizes are different.  we save all the
594   // old information about the array prior to this resizing.
595   contents *old_s = c_mem_block;  // save the old contents...
596   const int old_len = c_active_length;  // and length.
597   contents *old_off = c_offset;  // and offset.
598   bool delete_old = false;  // if true, old memory is whacked once it's copied.
599
600 //hmmm: wasn't there a nice realization that we could bail out early in
601 //      the case where the size is already suffcient?  there seems to be
602 //      an extraneous copy case here.
603 //      also it would be nice to have better, more descriptive names for the
604 //      variables here since they are not lending themselves to understanding
605 //      the algorithm.
606
607   // we check whether there's easily enough space in the array already.
608   // if not, then we have some more decisions to make.
609   if (c_real_length - (old_off - old_s) < new_size) {
610     // well, there's not enough space with the current space and offset.
611     if (c_real_length < new_size) {
612       // there's really not enough space overall, no fooling.  we now will
613       // create a new block.
614       c_mem_block = NULL_POINTER;  // zero out the pointer so reset doesn't delete it.
615       delete_old = true;
616       int blocking = 1;
617       if (exponential()) blocking = new_size + 1;
618       outcome ret = allocator_reset(new_size, blocking);
619       if (ret != common::OKAY) {
620         // failure, but don't forget to whack the old glob.
621 #ifdef DEBUG_ARRAY
622         throw "error: array::resize: saw array reset failure";
623 #endif
624         delete [] old_s;
625         return ret;
626       }
627       // fall out to the copying phase, now that we have some fresh memory.
628     } else {
629       // there is enough space if we shift some things around.
630       const int size_difference = new_size - c_active_length;
631         // we compute how much space has to be found in the array somewhere
632         // to support the new larger size.
633       if (way == DONT_COPY) {
634         // simplest case; just reset the offset appropriately so the new_size
635         // will fit.
636         c_offset = c_mem_block;
637         c_active_length = new_size;
638       } else if (way == NEW_AT_BEGINNING) {
639         // if the new space is at the beginning, there are two cases.  either
640         // the new size can be accomodated by the current position of the
641         // data or the data must be shifted to the right.
642         if (c_offset - c_mem_block < size_difference) {
643           // we need to shift the data over to the right since the offset isn't
644           // big enough for the size increase.
645           shift_data(TO_RIGHT);  // resets the offset appropriately.
646         }
647         // now we know that the amount of space prior to the real data
648         // is sufficient to hold what new space is needed.  we just need to
649         // shift the offset back somewhat.
650         c_offset -= size_difference;
651         c_active_length = new_size;
652       } else {
653         // better only be three ways to do this; we're now assuming the new
654         // space should be at the end (NEW_AT_END).
655         // now that we're here, we know there will be enough space if we shift
656         // the block to the left, but we DO NEED to do this.  if we didn't need
657         // to shift the data, then we would find that:
658         //     c_real_length - old_off >= new_size
659         // which is disallowed by the guardian conditional around this area.
660         shift_data(TO_LEFT);  // resets the offset for us.
661         c_active_length = new_size;
662       }
663       // we have ensured that we had enough space and we have already shifted
664       // the data around appropriately.  we no longer need to enter the next
665       // block where we would copy data around if we had to.  it has become
666       // primarily for cases where either we have to copy data because we
667       // have new storage to fill or where we are shrinking the array.
668       return common::OKAY;
669     }
670   }
671
672   // the blob of code below is offset invariant.  by the time we reach here,
673   // the array should be big enough and the offset should be okay.
674   c_active_length = new_size;  // set length to the new reporting size.
675   if (way != DONT_COPY) {
676     int where = 0;  // offset for storing into new array.
677     bool do_copy = false;  // if true, then we need to move the data around.
678     contents *loopc_offset_old = old_off;  // offset into original object.
679     // we should only have to copy the memory in one other case besides our
680     // inhabiting new memory--when we are asked to resize with the new stuff
681     // at the beginning of the array.  if the new space is at the end, we're
682     // already looking proper, but if the new stuff is at the beginning, we
683     // need to shift existing stuff downwards.
684     if (way == NEW_AT_BEGINNING) {
685       where = new_size - old_len;  // move up existing junk.
686       if (where) do_copy = true;  // do copy, since it's not immobile.
687       if (where < 0) {
688         // array shrank; we need to do the loop differently for starting
689         // from the beginning.  we skip to the point in the array that our
690         // suffix needs to start at.
691         loopc_offset_old -= where;
692         where = 0;  // reset where so we don't have negative offsets.
693       }
694     }
695     const int size_now = minimum(old_len, c_active_length);
696     if (delete_old || do_copy) {
697       contents *offset_in_new = c_offset + where;
698       contents *posn_in_old = loopc_offset_old;
699       if (simple()) {
700         // memmove should take care of intersections.
701         memmove(offset_in_new, posn_in_old, size_now * sizeof(contents));
702       } else {
703         // we need to do the copies using the object's assignment operator.
704         if (new_size >= old_len) {
705           for (int i = size_now - 1; i >= 0; i--)
706             offset_in_new[i] = posn_in_old[i];
707         } else {
708           for (int i = 0; i < size_now; i++)
709             offset_in_new[i] = posn_in_old[i];
710         }
711       }
712
713       // we only want to flush the obscured elements when we aren't already
714       // inhabiting new space.
715       if ( (c_flags & FLUSH_INVISIBLE) && !delete_old) {
716         // clear out the space that just went out of scope.  we only do this
717         // for the flushing mode and when we aren't starting from a fresh
718         // pointer (i.e., delete_old isn't true).
719         if (new_size < old_len) {
720 //          for (contents *p = posn_in_old; p < offset_in_new; p++)
721 //            *p = contents();
722         }
723       }
724     }
725   }
726   if (delete_old) delete [] old_s;
727   return common::OKAY;
728 }
729
730 template <class contents>
731 outcome array<contents>::retrain(int new_len, const contents *to_set)
732 {
733 ///  FUNCDEF("retrain")
734   if (new_len < 0) new_len = 0;  // stifle that bad length.
735 #ifdef DEBUG_ARRAY
736   if (to_set && (c_mem_block >= to_set) && (c_mem_block < to_set + new_len) ) {
737     throw "error: array::retrain: ranges overlap in retrain!";
738   }
739 #endif
740   outcome ret = resize(new_len, DONT_COPY);
741   if (ret != common::OKAY) return ret;
742 #ifdef DEBUG_ARRAY
743   if (new_len != c_active_length) {
744     throw "error: array resize set the wrong length";
745   }
746 #endif
747   if (to_set) {
748     if (simple()) 
749       memcpy(c_offset, to_set, c_active_length * sizeof(contents));
750     else
751       for (int i = 0; i < c_active_length; i++)
752         c_offset[i] = to_set[i];
753   } else {
754     if (c_flags & FLUSH_INVISIBLE) {
755       // no contents provided, so stuff the space with blanks.
756 //      for (int i = 0; i < c_active_length; i++) c_offset[i] = contents();
757     }
758   }
759   if (c_flags & FLUSH_INVISIBLE) {
760 //    for (contents *ptr = c_mem_block; ptr < c_offset; ptr++)
761 //      *ptr = contents();
762 //    for (contents *ptr = c_offset + c_active_length; ptr < c_mem_block + c_real_length; ptr++)
763 //      *ptr = contents();
764   }
765   return common::OKAY;
766 }
767
768 template <class contents>
769 outcome array<contents>::zap(int position1, int position2)
770 {
771   if (position1 > position2) return common::OKAY;
772   bounds_return(position1, 0, c_active_length - 1, common::OUT_OF_RANGE);
773   bounds_return(position2, 0, c_active_length - 1, common::OUT_OF_RANGE);
774   if (!position1) {
775     // if they're whacking from the beginning, we just reset the offset.
776     c_offset += position2 + 1;
777     c_active_length -= position2 + 1;
778     return common::OKAY;
779   }
780   const int difference = position2 - position1 + 1;
781   // copy from just above position2 down into position1.
782   if (simple()) {
783     if (c_active_length - difference - position1 > 0)
784       memmove(&c_offset[position1], &c_offset[position1 + difference],
785           (c_active_length - difference - position1) * sizeof(contents));
786   } else {
787     for (int i = position1; i < c_active_length - difference; i++)
788       c_offset[i] = c_offset[i + difference];
789   }
790
791   outcome ret = resize(c_active_length - difference, NEW_AT_END);
792     // chop down to new size.
793 #ifdef DEBUG_ARRAY
794   if (ret != common::OKAY) {
795     throw "error: array::zap: resize failure";
796     return ret;
797   }
798 #endif
799   return ret;
800 }
801
802 template <class contents>
803 outcome array<contents>::insert(int position, int elem_to_add)
804 {
805   if (position < 0) return common::OUT_OF_RANGE;
806   if (position > this->length())
807     position = this->length();
808   if (elem_to_add < 0) return common::OUT_OF_RANGE;
809   how_to_copy how = NEW_AT_END;
810   if (position == 0) how = NEW_AT_BEGINNING;
811   resize(this->length() + elem_to_add, how);
812
813   // if the insert wasn't at the front, we have to copy stuff into the new
814   // locations.
815   if (how == NEW_AT_END) {
816     const contents simple_default_object = contents();
817     if (!this->simple()) {
818       for (int i = this->last(); i >= position + elem_to_add; i--)
819         this->access()[i] = this->observe()[i - elem_to_add];
820       for (int j = position; j < position + elem_to_add; j++)
821         this->access()[j] = simple_default_object;
822     } else {
823       memmove(&(this->access()[position + elem_to_add]),
824           &(this->observe()[position]), (this->length() - position
825           - elem_to_add) * sizeof(contents));
826       for (int j = position; j < position + elem_to_add; j++)
827         memcpy(&this->access()[j], &simple_default_object, sizeof(contents));
828     }
829   }
830   return common::OKAY;
831 }
832
833 template <class contents>
834 outcome array<contents>::put(int index, const contents &to_put)
835 {
836   bounds_return(index, 0, this->last(), common::OUT_OF_RANGE);
837   if (!this->simple())
838     this->access()[index] = to_put;
839   else
840     memcpy(&(this->access()[index]), &to_put, sizeof(contents));
841   return common::OKAY;
842 }
843
844 template <class contents>
845 void array<contents>::snarf(array<contents> &new_contents)
846 {
847   if (this == &new_contents) return;  // no blasting own feet off.
848   reset();  // trash our current storage.
849   swap_contents(new_contents);
850 }
851
852 /*
853 //! a simple wrapper of an array of char *, used by portable::break_line().
854 class char_star_array : public array<char *>
855 {
856 public:
857   char_star_array() : array<char *>(0, NULL_POINTER, SIMPLE_COPY | EXPONE
858       | FLUSH_INVISIBLE) {}
859   ~char_star_array() {
860     // clean up all the memory we're holding.
861     for (int i = 0; i < length(); i++) {
862       delete [] (use(i));
863     }
864   }
865 };
866 */
867
868 } //namespace
869
870 #undef static_class_name
871
872 #endif
873