Merge branch 'main' of feistymeow.org:feisty_meow
[feisty_meow.git] / structures / amorph.h
1 #ifndef AMORPH_CLASS
2 #define AMORPH_CLASS
3
4 /*****************************************************************************\
5 *                                                                             *
6 *  Name   : amorph                                                            *
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 "object_packers.h"
19
20 #include <basis/astring.h>
21 #include <basis/functions.h>
22 #include <basis/contracts.h>
23 #include <basis/guards.h>
24
25 //! A dynamic container class that holds any kind of object via pointers.
26 /*!
27   The object is considered owned by the amorph unless re-acquired from it,
28   and will be deleted when the amorph is destroyed.
29
30   An amorph has a specified number of fields at any one time, but the number
31   can be changed with "zap", "insert" and "adjust".  Fields in the amorph
32   are either full or empty, where an empty field in the amorph has NULL_POINTER as
33   its content.  "put" adds a new field to the amorph.  "get" retrieves the
34   contents of a field as a constant.  "acquire" is used to check a field
35   out of the amorph, meaning that the amorph no longer possesses that field.
36   The legal range of indices in an amorph is from 0 through
37   "elements() - 1".  In general, a range violation for an index is
38   treated as an invalid request and is ignored (although BAD_INDEX is
39   returned by functions with compatible return values).
40
41   Model:
42
43   The policy followed in amorph is that once an object is checked in with
44   "put" or "append", then the amorph owns that object.  The object must not
45   be destroyed externally, because the amorph will automatically destroy
46   the object when either: 1) the amorph itself is destroyed, or 2) another
47   object is entered into the same field.  If the stored object must be
48   destroyed externally, then it should be checked out of the amorph with
49   "acquire"; after that, the pointer may be deleted.  "get" and "borrow"
50   return a pointer to the stored item while leaving it checked in to the
51   amorph.  it is safe to modify what was "borrow"ed or to look at what one
52   "get"s, but do not destroy the pointers returned from either method.
53 */
54
55 namespace structures {
56
57 template <class contents>
58 class amorph : protected basis::array<contents *>
59 {
60 public:
61   amorph(int elements = 0);
62     //!< constructs an amorph capable of holding "elements" pointers.
63
64   ~amorph();
65
66   int elements() const { return this->length(); }
67     //!< the maximum number of elements currently allowed in this amorph.
68
69   int valid_fields() const { return _fields_used; }
70     //!< Returns the number of fields that have non-null contents.
71     /*!< This might be different from the number of total elements. */
72
73   void adjust(int new_max);
74     //!< Changes the maximum number of elements for this amorph.
75     /*!< If the new number is smaller than the original, then the fields at
76     index "new_maximum" and upwards are thrown away.  existing fields are
77     kept. */
78
79   void resize(int new_maximum = 0);
80     //!< like adjust but doesn't keep existing contents.
81
82   void reset() { this->resize(0); }
83         //!< cleans out all of the contents.
84
85   basis::outcome put(int field, const contents *data);
86     //!< Enters an object into the field at index "field" in the amorph.
87     /*!< If "data" is NULL_POINTER, then the field is cleared.  The amorph considers the
88     pointer "data" to be its own property after put is invoked; "data"
89     should not be destructed since the amorph will automatically do so.
90     This restriction does not hold if the object is checked back out of
91     the amorph with acquire(). */
92
93   basis::outcome append(const contents *data);
94     //!< puts "data" on the end of this amorph.
95     /*!< adds an element to the end of the amorph by increasing the amorph size
96     (with "adjust") and putting the element into the new spot (with "put"). */
97
98   basis::outcome operator += (const contents *data) { return append(data); }
99     //!< a synonym for append.
100
101   //! Returns a constant pointer to the information at the index "field".
102   /*! If no information is stored or the field is out range, then NULL_POINTER is
103   returned. */
104   const contents *get(int field) const;
105   //! Returns a pointer to the information at the index "field".
106   /*! Also returns NULL_POINTER for invalid indexes.  DO NOT destroy the returned
107   pointer; it is still owned by the amorph. */
108   contents *borrow(int field);
109
110   //! synonym for get.
111   const contents *operator [] (int field) const { return get(field); }
112   //! synonym for borrow.
113   contents *operator [] (int field) { return borrow(field); }
114
115   contents *acquire(int field);
116     //!< Retrieves a "field" from the amorph, taking responsibility for it back.
117     /*!< This function is similar to get, except that the contents are pulled
118     out of the amorph.  The contents will no longer be destroyed when the
119     amorph is destroyed.  To store the modified contents again, use put,
120     and then the amorph will take over management of the contents again.
121     Note that the index is not zapped with this function; the acquired
122     "field" will simply hold a null pointer. */
123
124   basis::outcome clear(int field);
125     //!< Clears the contents of the field specified.
126     /*!< Clearing an empty field has no effect.  Clearing an invalid field has
127     no effect.  NOTE: clearing the contents means that the contents are
128     destroyed, not just disconnected. */
129
130   void clear_all();
131     //!< Clears every field in the amorph.
132
133   basis::outcome zap(int start, int end);
134     //!< Removes a range of indices from the amorph.
135     /*!< This does not just clear the field associated with the specified index
136     as "clear" does, it actually changes the number of total elements by
137     removing the indices from the amorph.  The new amorph contains the old
138     elements up to just before the "start" and from the "end" + 1 through the
139     end of the amorph.  AMORPH_BAD_INDEX is returned if either index is out of
140     range.  If the zap succeeds, then AMORPH_OKAY is returned, even if the
141     "end" is less than the "start". */
142
143   basis::outcome insert(int position, int lines_to_add);
144     //!< Adds "lines_to_add" indices to the amorph at the index "position".
145     /*!< If "lines_to_add" is non-positive, the request is ignored.  Inserting
146     at a position beyond the bounds of the array is ignored, but a position AT
147     elements() is allowed (it is an append...). */
148
149   int find_empty(basis::outcome &o) const;
150     //!< Returns the index of a free field if there are any.
151     /*!< The returned index is invalid if the "o" is IS_FULL. */
152
153   const contents *next_valid(int &field) const;
154     //!< Returns the contents of the next valid element at or after "field".
155     /*!< "field" is set to the location where an entry was found, if one was
156     actually found.  If none exists at "field" or after it, then NULL_POINTER is
157     returned. */
158
159   int find(const contents *to_locate, basis::outcome &o);
160     //!< Searches the amorph for the contents specified.
161     /*!< Since only pointers to the contents are maintained, the search is
162     based on finding a pointer in the amorph that is identical to "to_locate".
163     if "o" is OKAY, then the index of the entry is returned.  If
164     "o" is NOT_FOUND, then the contents are not present. */
165
166   void swap_contents(amorph<contents> &other);
167     //!< Exchanges the contents of "this" and "other".
168     /*!< No validation is performed but this should always succeed given
169     amorphs that are constructed properly. */
170
171 private:
172   int _fields_used;  //!< The number of fields currently full of info.
173
174   void check_fields(const char *where) const;
175     //!< Crashes out if the field count is wrong.
176     /*!< This is only used for the debugging version. */
177
178   void set_nil(int start, int end);
179     // Puts NULL_POINTER in the indices between start and end.
180     /*!< Does not delete whatever used to reside there; it just sets the
181     pointers to NULL_POINTER. */
182
183   // not to be used: amorphs should not be copied because it is intended that
184   // they support storing heavyweight objects that either have no copy
185   // constructors or have high-cost copy constructors.
186   amorph(const amorph &to_copy) {_fields_used = 0;}  //!< not to be used.
187   amorph &operator = (const amorph &to_copy) { return *this; }
188     //!< not to be used.
189 };
190
191 //////////////
192
193 // these extensions are phrased as macros to avoid including the headers
194 // necessary for compiling them.  to use them, just put the macro name in
195 // the file where the template is needed.
196
197 //////////////
198
199 //! This can be used when the templated object has a copy constructor.
200 /*! this makes the "to_assign" into a copy of the "to_copy" amorph. */
201 template <class contents>
202 void amorph_assign(amorph<contents> &to_assign,
203     const amorph<contents> &to_copy);
204
205 //////////////
206
207 //! support for packing an amorph into an array of bytes.
208 /*!
209   this can be used when the underlying object is based on packable or
210   supports the same pack/unpack methods.  note that if there are empty spots in
211   the amorph, they are not packed.  when the packed form is unpacked again, it will
212   have only the first N elements set, where N is the number of non-empty items.
213 */
214 template <class contents>
215 void amorph_pack(basis::byte_array &packed_form, const amorph<contents> &to_pack);
216
217 //! unpacks the amorph from an array of bytes.
218 template <class contents>
219 bool amorph_unpack(basis::byte_array &packed_form, amorph<contents> &to_unpack);
220
221 //! reports how large the packed form will be.
222 template <class contents>
223 int amorph_packed_size(const amorph<contents> &to_pack);
224
225 // implementation for longer methods...
226
227 //#define DEBUG_AMORPH
228   // uncomment to enable more testing, as well as complaints on errors.
229
230 #undef static_class_name
231 #define static_class_name() "amorph"
232   // used in bounds_halt macro.
233
234 #undef AMO_ALERT
235 #ifdef DEBUG_AMORPH
236   #include <basis/astring.h>
237   #define AMO_ALERT(a, b, c) basis::throw_error(basis::astring(a), basis::astring(func), basis::astring(b) + " -- " + c)
238   #define CHECK_FIELDS check_fields(func)
239 #else
240   #define AMO_ALERT(a1, a2, a3) {}
241   #define CHECK_FIELDS { if (!func) {} }
242 #endif
243
244 //////////////
245
246 template <class contents>
247 amorph<contents>::amorph(int elements)
248 : basis::array<contents *>(elements, NULL_POINTER, basis::array<contents *>::SIMPLE_COPY
249       | basis::array<contents *>::EXPONE | basis::array<contents *>::FLUSH_INVISIBLE),
250   _fields_used(0)
251 {
252   FUNCDEF("constructor");
253   set_nil(0, elements - 1);
254   CHECK_FIELDS;
255 }
256
257 template <class contents>
258 amorph<contents>::~amorph()
259 {
260   FUNCDEF("destructor");
261   CHECK_FIELDS;
262   clear_all();
263 }
264
265 template <class contents>
266 void amorph<contents>::set_nil(int start, int end)
267 {
268   for (int i = start; i <= end; i++)
269     basis::array<contents *>::put(i, (contents *)NULL_POINTER);
270 }
271
272 template <class contents>
273 void amorph<contents>::check_fields(const char *where) const
274 {
275   FUNCDEF("check_fields");
276   int counter = 0;
277   for (int i = 0; i < elements(); i++)
278     if (basis::array<contents *>::get(i)) counter++;
279   if (_fields_used != counter) {
280     AMO_ALERT("amorph", basis::a_sprintf("check_fields for %s", where),
281         "error in _fields_used count");
282   }
283 }
284
285 template <class contents>
286 void amorph<contents>::resize(int new_maximum)
287 {
288   FUNCDEF("reset");
289   CHECK_FIELDS;
290   adjust(new_maximum);
291   clear_all();
292 }
293
294 template <class contents>
295 void amorph<contents>::clear_all()
296 {
297   FUNCDEF("clear_all");
298   CHECK_FIELDS;
299   for (int i = 0; i < elements(); i++) clear(i);
300 }
301
302 template <class contents>
303 basis::outcome amorph<contents>::append(const contents *data)
304 {
305   FUNCDEF("append");
306   CHECK_FIELDS;
307   adjust(elements() + 1);
308   return put(elements() - 1, (contents *)data);
309 }
310
311 template <class contents>
312 const contents *amorph<contents>::get(int field) const
313 {
314   FUNCDEF("get");
315   CHECK_FIELDS;
316   bounds_return(field, 0, elements() - 1, NULL_POINTER);
317   return basis::array<contents *>::observe()[field];
318 }
319
320 template <class contents>
321 void amorph<contents>::adjust(int new_maximum)
322 {
323   FUNCDEF("adjust");
324   CHECK_FIELDS;
325   if (new_maximum < 0) return;  // bad input here.
326   int old_max = elements();
327   if (new_maximum == old_max) return;  // nothing to do.
328   if (new_maximum < old_max) {
329     // removes the elements beyond the new size of the amorph.
330     zap(new_maximum, old_max - 1);
331     // we're done tuning it.
332     return;
333   }
334
335   // we get to here if we need more space than we used to.
336   int new_fields = new_maximum - old_max;
337
338   basis::array<contents *>::insert(old_max, new_fields);
339   for (int i = old_max; i < new_maximum; i++) {
340     basis::array<contents *>::put(i, NULL_POINTER);
341   }
342 }
343
344 template <class contents>
345 basis::outcome amorph<contents>::insert(int position, int lines_to_add)
346 {
347   FUNCDEF("insert");
348   CHECK_FIELDS;
349   bounds_return(position, 0, elements(), basis::common::OUT_OF_RANGE);
350   basis::outcome o = basis::array<contents *>::insert(position, lines_to_add);
351   if (o != basis::common::OKAY) return basis::common::OUT_OF_RANGE;
352   set_nil(position, position + lines_to_add - 1);
353   return basis::common::OKAY;
354 }
355
356 template <class contents>
357 basis::outcome amorph<contents>::zap(int start_index, int end_index)
358 {
359   FUNCDEF("zap");
360   CHECK_FIELDS;
361   bounds_return(start_index, 0, elements() - 1, basis::common::OUT_OF_RANGE);
362   bounds_return(end_index, 0, elements() - 1, basis::common::OUT_OF_RANGE);
363   if (end_index < start_index) return basis::common::OKAY;
364   for (int i = start_index; i <= end_index;  i++) clear(i);
365   basis::outcome o = basis::array<contents *>::zap(start_index, end_index);
366   return (o == basis::common::OKAY? basis::common::OKAY : basis::common::OUT_OF_RANGE);
367 }
368
369 template <class contents>
370 basis::outcome amorph<contents>::put(int field, const contents *data)
371 {
372   FUNCDEF("put");
373   CHECK_FIELDS;
374   bounds_return(field, 0, elements() - 1, basis::common::OUT_OF_RANGE);
375   contents *to_whack = acquire(field);
376   delete to_whack;
377   if (data) {
378     basis::array<contents *>::access()[field] = (contents *)data;
379     _fields_used++; 
380   }
381   return basis::common::OKAY;
382 }
383
384 template <class contents>
385 int amorph<contents>::find_empty(basis::outcome &o) const
386 {
387   FUNCDEF("find_empty");
388   CHECK_FIELDS;
389   if (_fields_used == elements()) { o = basis::common::IS_FULL; return 0; }
390   for (int i = 0; i < elements(); i++)
391     if (!basis::array<contents *>::get(i)) { o = basis::common::OKAY; return i; }
392   AMO_ALERT("amorph", "empty", "_fields_used is incorrect");
393   return basis::common::IS_FULL;
394 }
395
396 template <class contents>
397 const contents *amorph<contents>::next_valid(int &field) const
398 {
399   FUNCDEF("next_valid");
400   CHECK_FIELDS;
401   bounds_return(field, 0, elements() - 1, NULL_POINTER);
402   for (int i = field; i < elements(); i++)
403     if (basis::array<contents *>::get(i)) {
404       field = i;
405       return basis::array<contents *>::get(i);
406     }
407   return NULL_POINTER;
408 }
409
410 template <class contents>
411 basis::outcome amorph<contents>::clear(int field)
412 {
413   FUNCDEF("clear");
414   CHECK_FIELDS;
415   return this->put(field, NULL_POINTER);
416 }
417
418 template <class contents>
419 contents *amorph<contents>::acquire(int field)
420 {
421   FUNCDEF("acquire");
422   CHECK_FIELDS;
423   contents *to_return = borrow(field);
424   if (to_return) {
425     _fields_used--;
426     basis::array<contents *>::access()[field] = NULL_POINTER;
427   }
428   return to_return;
429 }
430
431 template <class contents>
432 int amorph<contents>::find(const contents *to_locate, basis::outcome &o)
433 {
434   FUNCDEF("find");
435   CHECK_FIELDS;
436   if (!_fields_used) { o = basis::common::NOT_FOUND; return 0; }
437   for (int i = 0; i < elements(); i++) {
438     if (basis::array<contents *>::get(i) == to_locate) {
439       o = basis::common::OKAY;
440       return i; 
441     }
442   }
443   o = basis::common::NOT_FOUND;
444   return 0;
445 }
446
447 template <class contents>
448 contents *amorph<contents>::borrow(int field)
449 {
450   FUNCDEF("borrow");
451   CHECK_FIELDS;
452   bounds_return(field, 0, elements() - 1, NULL_POINTER);
453   return basis::array<contents *>::access()[field];
454 }
455
456 template <class contents>
457 void amorph<contents>::swap_contents(amorph<contents> &other)
458 {
459   FUNCDEF("swap_contents");
460   CHECK_FIELDS;
461   int hold_fields = _fields_used;
462   _fields_used = other._fields_used;
463   other._fields_used = hold_fields;
464   this->basis::array<contents *>::swap_contents(other);
465 }
466
467 template <class contents>
468 int amorph_packed_size(const amorph<contents> &to_pack)
469 {
470   int parts_size = 0;
471   for (int i = 0; i < to_pack.elements(); i++) {
472     const contents *current = to_pack.get(i);
473     if (current) parts_size += current->packed_size();
474   }
475   return PACKED_SIZE_INT32 + parts_size;
476 }
477
478 template <class contents>
479 void amorph_pack(basis::byte_array &packed_form, const amorph<contents> &to_pack)
480 {
481   structures::attach(packed_form, to_pack.elements());
482   for (int i = 0; i < to_pack.elements(); i++) {
483     const contents *current = to_pack.get(i);
484     if (current) current->pack(packed_form);
485   }
486 }
487
488 template <class contents>
489 bool amorph_unpack(basis::byte_array &packed_form, amorph<contents> &to_unpack)
490 {
491   to_unpack.reset();
492   int elem = 0;
493   if (!structures::detach(packed_form, elem)) return false;
494   for (int i = 0; i < elem; i++) {
495     contents *to_add = new contents;
496     if (!to_add->unpack(packed_form)) { delete to_add; return false; }
497     to_unpack.append(to_add);
498   }
499   return true;
500 }
501
502 template <class contents>
503 void amorph_assign(amorph<contents> &to_assign,
504     const amorph<contents> &to_copy)
505 {
506   if (&to_assign == &to_copy) return;
507   to_assign.clear_all();
508   if (to_assign.elements() != to_copy.elements()) {
509     to_assign.zap(0, to_assign.elements() - 1);
510     to_assign.insert(0, to_copy.elements());
511   }
512   for (int i = 0; i < to_assign.elements(); i++) {
513     if (to_copy.get(i)) to_assign.put(i, new contents(*to_copy.get(i)));
514     else to_assign.put(i, (contents *)NULL_POINTER);
515   }
516 }
517
518 #undef static_class_name
519
520 } //namespace.
521
522 #endif
523