This class implements dynamically resizable arrays.
Throughout the documentation, the following prefixes will be used:
Global_
The library prefix: for applications, this is typically
empty, for an xyz-Library, this is either XYZ_, xyz_ or
Xyz, depending on the identifier in occurs in.
Template
Instantiation
Global_VECTOR_OK
XYZ_VECTOR_OK
Global_vector_new
xyz_vector_new
Vector_
This is equivalent to Global_vector_oType, or the name
that was set with -name=... for this data structure.
The case and underbar convention is adjusted, too.
Assuming a library prefix xyz and oType == char, you get:
It was tried to keep the argument order consistent, with some rules:
for functions returning multiple values into pointer arguments, these
are always before input arguments. (e.g. Vector_locate (output, self, ...)).
(Mnemonic: like memcpy, strcpy, assignment statement etc.)
if Vector_errno is not interesting, either because it is not
set or because only memory overflow or assertion failures may be
a possible sources of an error, the C functions return void:
The C++ functions still return the object reference.
Status Codes
These are undef'ed first because there is only one error code for all
the arrays in your program.
All the functions returing error codes will both return this error
and write it into Global_vector_errno.
Condition
Description
Macro to use
= Global_VECTOR_OK
Ok.
Global_VECTOR_IS_OK(X)
< Global_VECTOR_OK
Error: operation did
not succeed.
Global_VECTOR_IS_ERROR(X)
> Global_VECTOR_OK
Warning: operation
succeeded but not
perfectly. (e.g. rehash
failed)
Global_VECTOR_IS_WARNING(X)
In all cases, the consistency of the data structure is guaranteed.
Warnings are only visible in Global_vector_errno; the functions still return
VECTOR_OK.
This might be strange: it makes a new vector from the contents of the other
vector and then detaches the data from the other vector. Its purpose is
mainly useful in C++ where you can clone vectors from a static vector
by this means. E.g.:
Clears the vector by initialising a new completely empty
table not consuming any memory. The effect is mainly that
you can use the value of Vector_as_array and Vector_as_open_array
independently from the vector. The old function
delete_flat is now a sequence of detach() and delete().
Note
This function should be used when the vector is not
needed anymore after a cast to a raw array (e.g. by
Vector_as_array).
Compare this function with Vector_detach_as_is(). These functions
are important to distinguish if you defined Global_oType_UPDATE_POS.
Returns the found element or the zero element on failure.
If index is out of range, a message is also output to
stderr if you defined Global_ERWIN_VERBOSE.
Returns a pointer to the element at index or an signals an error if
the index is out of range. (This is the same behaviour towards errors
as Vector_nth has)
Does not output anything to stderr even if you define Global_ERWIN_VERBOSE.
Returns a pointer to the element at index if it is in range.
If is is one too large, returns a pointer to the element after the end,
mimicking string behaviour. That element is guaranteed to be allocated,
of couse. If you write to that element, it only is guarateed to have
any effect up to the next change to the vector size. Don't change that
element, though.
Because this function is so similar to adding an integer to a 'char const *',
i.e., to get a suffix string, this function always zero-terminates the
vector like Vector_as_array() does. So Vector_nth_ptr_char(self,0) is
equivalent to Vector_as_array().
Note
This behaves a bit strange together with ALLOW_OUTOFRANGE:
Accesses to any element starting from a[nentries()] make the vector
larger for the non-const version! This includes the nentries()th
element, which, even if only read with this function, enlarges the
vector due to the potential threat of the user writing to it.
In case ALLOW_OUTOFRANGE is off, this never makes the vector larger,
but does allow access to nentries()th element. That element is always
ensured to be ZERO, however, so you cannot write to it.
This signals an error if the index is out of range.
(This is the some behaviour towards errors as Vector_nth_char has.)
Does not output anything to stderr even if you define Global_ERWIN_VERBOSE.
Returns a pointer to the element at index or an signals an error if
the index is out of range. (This is the same behaviour towards errors
as Vector_nth has)
Does not output anything to stderr even if you define Global_ERWIN_VERBOSE.
Returns a pointer to the element at index if it is in range.
If is is one too large, returns a pointer to the element after the end,
mimicking string behaviour. That element is guaranteed to be allocated,
of couse. If you write to that element, it only is guarateed to have
any effect up to the next change to the vector size. Don't change that
element, though.
Because this function is so similar to adding an integer to a 'char const *',
i.e., to get a suffix string, this function always zero-terminates the
vector like Vector_as_array() does. So Vector_nth_ptr_char(self,0) is
equivalent to Vector_as_array().
Note
This behaves a bit strange together with ALLOW_OUTOFRANGE:
Accesses to any element starting from a[nentries()] make the vector
larger for the non-const version! This includes the nentries()th
element, which, even if only read with this function, enlarges the
vector due to the potential threat of the user writing to it.
In case ALLOW_OUTOFRANGE is off, this never makes the vector larger,
but does allow access to nentries()th element. That element is always
ensured to be ZERO, however, so you cannot write to it.
This signals an error if the index is out of range.
(This is the some behaviour towards errors as Vector_nth_char has.)
Does not output anything to stderr even if you define Global_ERWIN_VERBOSE.
int Vector_swap_erase (Vector_t * self, int index, int number_of_elements)
This is similar to Vector_erase, but instead of shifting all elements after
the ones erased, this functions copies elements from the end of the vector
into the gap. This is faster if number_of_elements is small.
The order of the copied elements is reversed.
int Vector_erase (Vector_t * self, int index, int number_of_elements)
The values erased from the the vector are freed. If number_of_elements
is negative, the end of the vector is cut off. If index or
number_of_elements are out of range, they are adjusted appropriately.
E.g.:
if index == -2 and count == 5
then elements 0,1,2 are erased,
if index >= nentries
nothing is erased,
if index + count >= nentries
only the tail of the vector is erased.
However, all this is only done if Vector_ALLOW_OUTOFRANGE is true.
Otherwise, you'll get an assertion failure in all these cases,
because index or count are out of range.
if count < 0
then count is adjusted to nelements - index, e.g.
index == 2, count = -1 will cut off the last two elements of
the vector.
(The absolute value of count is not considered here, only the fact
that it is < 0). This adjustment always happens, i.e., even if
Vector_ALLOW_OUTOFRANGE is false.
Erases the second of two adjacent elements that is equal (wrt. the
given function) to the first. This is repeated recursively so that
groups of adjacent equal elements are reduced to one element.
Before erasing, the function calls back combine to let the user
adjust things (e.g. copy something from the moribund entry to
the surviving one).
The default cmp function, used if cmp is NULL, is Global_oType_CMP.
In a sorted vector, this procedure erases all equal elements.
The values erased from the vector are freed using oType_OFREE.
int Vector_swap_erase (Vector_t * self, int index, int number_of_elements)
This is similar to Vector_erase, but instead of shifting all elements after
the ones erased, this functions copies elements from the end of the vector
into the gap. This is faster if number_of_elements is small.
The order of the copied elements is reversed.
This functions generates an assertion failure if the number of
elements to chop is greater than the number of elements in the
vector. However, if Vector_ALLOW_OUTOFRANGE is true, then
this operation simply clears the vector without assertion failure
in this case.
Due to the fact that the equivalent using Vector_swap_erase is
very trivial: Vector_swap_erase (self, 0, 1), there is no
Vector_swap_chop() in C (but in C++, we still have it).
Tries to finds an entry equal to needle. Returns the index of the first element >= start
or -1 of nothing was found. The search is performed from the beginning to the end.
If start is negativ, search is started at the last but start-th position. So to search
the whole vector, start should be 0.
Note
This function is not called `Vector_search', because it does not only
perform the search, but also returns the result of that search.
Tries to finds an entry equal to needle. Returns the index of the first element >= start
or -1 of nothing was found. The search is performed from the beginning to the end.
If start is negativ, search is started at the last but start-th position. So to search
the whole vector, start should be 0.
Note
This function is not called `Vector_search', because it does not only
perform the search, but also returns the result of that search.
Tries to finds an entry equal to needle. Returns the index of the first element <= start
or -1 of nothing was found. The search is performed from the end to the beginning.
If start is negativ, search is started at the last but start-th position. So to search
the whole vector, start should be -1.
Return the position of `needle' or -1 if it is not found.
Note that it is no problem to search for the zero element Global_oType_ZERO.
These all use the Vector_EQUAL macro.
Negative values for start will count from the end of the vector.
Return the position of `needle' or -1 if it is not found.
Note that it is no problem to search for the zero element Global_oType_ZERO.
These all use the Vector_EQUAL macro.
Negative values for start will count from the end of the vector.
Return the position of `needle' or -1 if it is not found.
Note that it is no problem to search for the zero element Global_oType_ZERO.
These all use the Vector_EQUAL macro.
Negative values for start will count from the end of the vector.
Return the position of `needle' or -1 if it is not found.
Note that it is no problem to search for the zero element Global_oType_ZERO.
These all use the Vector_EQUAL macro.
Negative values for start will count from the end of the vector.
Return the position of `needle' or -1 if it is not found.
Note that it is no problem to search for the zero element Global_oType_ZERO.
These all use the Vector_EQUAL macro.
Negative values for start will count from the end of the vector.
Return the position of `needle' or -1 if it is not found.
Note that it is no problem to search for the zero element Global_oType_ZERO.
These all use the Vector_EQUAL macro.
Negative values for start will count from the end of the vector.
Return the position of `needle' or -1 if it is not found.
Note that it is no problem to search for the zero element Global_oType_ZERO.
These all use the Vector_EQUAL macro.
Negative values for start will count from the end of the vector.
Return the position of `needle' or -1 if it is not found.
Note that it is no problem to search for the zero element Global_oType_ZERO.
These all use the Vector_EQUAL macro.
Negative values for start will count from the end of the vector.
Tries to finds an entry equal to needle. Returns the index of the first element <= start
or -1 of nothing was found. The search is performed from the end to the beginning.
If start is negativ, search is started at the last but start-th position. So to search
the whole vector, start should be -1.
Return the position of `needle' or -1 if it is not found.
Note that it is no problem to search for the zero element Global_oType_ZERO.
These all use the Vector_EQUAL macro.
Negative values for start will count from the end of the vector.
Return the position of `needle' or -1 if it is not found.
Note that it is no problem to search for the zero element Global_oType_ZERO.
These all use the Vector_EQUAL macro.
Negative values for start will count from the end of the vector.
Return the position of `needle' or -1 if it is not found.
Note that it is no problem to search for the zero element Global_oType_ZERO.
These all use the Vector_EQUAL macro.
Negative values for start will count from the end of the vector.
Return the position of `needle' or -1 if it is not found.
Note that it is no problem to search for the zero element Global_oType_ZERO.
These all use the Vector_EQUAL macro.
Negative values for start will count from the end of the vector.
Return the position of `needle' or -1 if it is not found.
Note that it is no problem to search for the zero element Global_oType_ZERO.
These all use the Vector_EQUAL macro.
Negative values for start will count from the end of the vector.
Return the position of `needle' or -1 if it is not found.
Note that it is no problem to search for the zero element Global_oType_ZERO.
These all use the Vector_EQUAL macro.
Negative values for start will count from the end of the vector.
Return the position of `needle' or -1 if it is not found.
Note that it is no problem to search for the zero element Global_oType_ZERO.
These all use the Vector_EQUAL macro.
Negative values for start will count from the end of the vector.
Return the position of `needle' or -1 if it is not found.
Note that it is no problem to search for the zero element Global_oType_ZERO.
These all use the Vector_EQUAL macro.
Negative values for start will count from the end of the vector.
Tries to find an entry with a certain feature. Returns the index of the first element >= start
or -1 of nothing was found. The search is performed from the beginning to the end.
If start is negativ, search is started at the last but start-th position. So to search
the whole vector, start should be 0.
Tries to find an entry with a certain feature. Returns the index of the first element >= start
or -1 of nothing was found. The search is performed from the beginning to the end.
If start is negativ, search is started at the last but start-th position. So to search
the whole vector, start should be 0.
Tries to find an entry with a certain feature. Returns the index of the first element <= start
or -1 of nothing was found. The search is performed from the end to the beginning.
If start is negativ, search is started at the last but start-th position. So to search
the whole vector, start should be -1.
Tries to find an entry with a certain feature. Returns the index of the first element <= start
or -1 of nothing was found. The search is performed from the end to the beginning.
If start is negativ, search is started at the last but start-th position. So to search
the whole vector, start should be -1.
Tries to find an entry with a certain feature. Returns the index of the first element >= start
or -1 of nothing was found. The search is performed from the beginning to the end.
If start is negativ, search is started at the last but start-th position. So to search
the whole vector, start should be 0.
Tries to find an entry with a certain feature. Returns the index of the first element >= start
or -1 of nothing was found. The search is performed from the beginning to the end.
If start is negativ, search is started at the last but start-th position. So to search
the whole vector, start should be 0.
Tries to find an entry with a certain feature. Returns the index of the first element <= start
or -1 of nothing was found. The search is performed from the end to the beginning.
If start is negativ, search is started at the last but start-th position. So to search
the whole vector, start should be -1.
Tries to find an entry with a certain feature. Returns the index of the first element <= start
or -1 of nothing was found. The search is performed from the end to the beginning.
If start is negativ, search is started at the last but start-th position. So to search
the whole vector, start should be -1.
Like the Vector_trim_if family with an isspace feature. The special isspace used
here defines '\0' to be a space. This is useful for pre-allocating space
by inserting \0, then using standard clib functions to fill the buffer,
and then trimming it.
int fread (FILE * fileptr, Vector_cnt_t max_count = -1)
C++:
int Vector_t::fread (FILE * fileptr, int max_count = -1)
C:
int Vector_fread (Vector_t * self, FILE * f, int max_count)
Read the whole file or a prefix into the vector.
If you pass -1 for max_count, there is no maximal count.
This function returns the number of elements read or -1 in case of
an error. If vector_errno is VECTOR_ERR_IO, you can use ferror(f)
to query the error.
int Vector_fgets (Vector_t * self, FILE * f, int max_count)
Read one line into the vector. You can bound the number of elements stored
in the vector. However, a line is always read completely to the end.
This function returns the error code. VECTOR_OK means no error.
If no char could be read, this returns VECTOR_WARN_EMPTY. Otherwise,
VECTOR_OK is returned if not file error occured, VECTOR_ERR_IO
otherwise. Then you can query the error on the file using ferror (f).
Like the clib function, the trailing \n is appended if it was there.
Returns the index of the first and last characters that belongs to the basename
of a file name. The algorithm depends on the operating system this runs on.
This is an extended version of Vector_basename_index, which does not return
the last index. E.g. under Unix, for "tmp/test" this function returns:
*first= 5,
*length= 4
first and length may be NULL in which case nothing is returned for the
respective value.
Append the default configuration file name (either global or local one) to the vector.
The default global name under Unix is
/etc/progname.conf
under Windos it is
C:\etc\progname.ini
The default local name under Unix is
$HOME/.prognamerc
under Windos
%HOME%\progname.ini
Returns Global_vector_errno. Note that if $HOME is not defined (which is typical under DOS),
VECTOR_ERR_OUTOFRANGE is returned and nothing appended if local != 0.
Returns the zero element of this vector. This need not be the same
for all vectors (you can specify it with Vector_new_with_zero) unless
you defined Vector_CONSTANT_ZERO.
int Vector_overwrite (Vector_t * self, int start_index_in_self, Vector_t const * newdata, int start_index_in_initial, int max_count)
Each element is copied using Global_oType_OCOPY, the old contents are deleted
with Global_oType_OFREE. This overwrites maximally max_count elements from
initial to self starting at position start_index_in* in the two
vectors.
int Vector_overwrite (Vector_t * self, int start_index_in_self, Vector_t const * newdata, int start_index_in_initial, int max_count)
Each element is copied using Global_oType_OCOPY, the old contents are deleted
with Global_oType_OFREE. This overwrites maximally max_count elements from
initial to self starting at position start_index_in* in the two
vectors.
int Vector_overwrite_raw (Vector_t * self, int start_index_in_self, oType const * newdata, int count)
Overwrites portions of the vector from a normal array.
The overwritten data is freed using oType_OFREE in the old vector and
the new data copied from the new data array using oType_OCOPY.
int Vector_overwrite_raw (Vector_t * self, int start_index_in_self, oType const * newdata, int count)
Overwrites portions of the vector from a normal array.
The overwritten data is freed using oType_OFREE in the old vector and
the new data copied from the new data array using oType_OCOPY.
int Vector_insert_subvector (Vector_t * self, int start_index_self, Vector_t const * other, int start_index_other, int size, Global_ERWIN_BOOL docopy)
Inserts a portion of a vector into another one. If size is < 0, it defines
the last element to enter. -1 therefore means: the rest of the vector starting
at start_index
int Vector_insert_subvector (Vector_t * self, int start_index_self, Vector_t const * other, int start_index_other, int size, Global_ERWIN_BOOL docopy)
Inserts a portion of a vector into another one. If size is < 0, it defines
the last element to enter. -1 therefore means: the rest of the vector starting
at start_index
Find out the string length of the given zero-terminated string.
The zero element is taken from the vector. This does not modify
the vector at all, nor does it look at the vector's elements. It
only gets the zero element from the vector.
int Vector_ensure_table_size (Vector_t * self, int size)
Pre-allocates vector elements. To be used when you know some good
upper approximation to the expected number of elements which will be
inserted in the future. Does not change the contents of the vector.
To set a minimal size for the vector by appending zero elements,
use Vector_ensure_size.
When Vector_LOW_MEM is active, this functions has no operation, since the
table size cannot be changed independently from the size.
returns a pointer to the string the vector is stored in. The string
is terminated with a zero element (usually Global_oType_ZERO, but this
can be changed by using Vector_new_with_zero).
Note
For convenience, this takes a const pointer although the
representation (but not the contained data) might be changed. It only
changes things outside the user view (behind the end of the vector).
Further note that NULL is ok, NULL is returned, regardless of Vector_ALLOW_NULL.
When Vector_INLINE_STORE is active, the returned pointer may become
invalid when you invoke Vector_detach or Vector_detach_as_is. Use
Vector_as_array_detach() in that case (you cannot split that operation
in this case).
Developer's Note: this functions is not _pure_: it may change the
internal structure, and thus the result of table_size() and
has_heap_storage() etc.
Same as Vector_as_array, but without the guaranteed zero element.
This is sometimes faster and never resizes the vector.
Note
If Vector_MINIMAL_SIZE is 0 and the vector has size 0, this
function might return NULL instead of an allocated array!
This is because the function will never try to reallocate.
When Vector_INLINE_STORE is active, the returned pointer may become
invalid when you invoke Vector_detach or Vector_detach_as_is. Use
Vector_as_array_detach() in that case (you cannot split that operation
in this case).
Ensure that the contents are stored on the heap so that _detach
does not destroy the vector. Used by Vector_as_array_detach(), but
may also be used manually before as_array() or Vector_nth_ptr() to
ensure that the pointer is on the heap.
This function actually does something only when Vector_INLINE_STORE
is used or Vector_MINIMAL_SIZE is 0. Otherwise, this function does
nothing. This includes not doing any harm.
Note
With both LOW_MEM and INLINE_STORE active, this functions may
append ZERO elements to the vector, because resizing the table
may mean to resize the vector.
Note
With Vector_MINIMAL_SIZE == 0, vectors of size 0 are still not
resized to size 1.
Functions returning pointers to the table (e.g. Vector_as_open_array)
will return NULL in this special case, which is ususally no problem
in handling.
This function is for handling the more complex cases that occur with
the Vector_INLINE_STORE option.
Returns whether the storage on the heap is allocated or not.
This is interesting only when Vector_MINIMIAL_SIZE == 0 or
Vector_INLINE_STORE is activated.
Returns the number of elements the inline store has.
This is 0 unless Vector_INLINE_STORE is activated, in which case other
values are possible. The result is a constant, therefore there is no
argument to this function.
This makes a heap. The first element of the vector will then
be the maximum (according to the given compare function).
The others will have the Heap Property:
Returns the index of the left child of i in a heap structure.
The index i must be a valid index of the vector.
Returns something < 0 if there is no such child of i.
The left index is guaranteed to be < than the right index.
Returns the index of the left child of i in a heap structure.
The index i must be a valid index of the vector.
Returns something < 0 if there is no such child of i.
The right index is guaranteed to be > than the left index.
Returns the index of the left child of i in a heap structure.
The index i must be a valid index of the vector.
Returns something < 0 if i does not have a father, i.e., if i == 0.
This extracts the maximum from the heap, returns it, shrinks the
vector, and re-heapifies it. See Vector_make_heap()
and Vector_heap_sink(). You may only invoke this for vectors that
have the heap property and have at least one element.
The operation takes O(log n) time, since it reinvokes Vector_heap_sink.
The default cmp function, used if cmp is NULL, is Global_oType_PRIORITY_CMP.
This function checks the input and itself when in debug mode, causing
assertion failures if the heap property is violated.
Note that this check takes O(n) time, so the function is significantly
slower during debugging. If you don't want this, you may
#define Vector_DEBUG_EXPENSIVE_CHECKS 0
or (for all vectors)
#define Global_VECTOR_DEBUG_EXPENSIVE_CHECKS 0
Note
this returns oTypeVar instead of oTypeResult (if these are different),
because the element is removed, so no reference can be returned.
The operation checks for element i whether its priority has increased.
it so, the heap property is re-established.
The operation takes O(log n) time.
The default cmp function, used if cmp is NULL, is Global_oType_PRIORITY_CMP.
This function checks itself when in debug mode, causing
assertion failures if the heap property is violated after operation.
Such an assertion failure may also mean that the vector was no
heap (apart from the element i) before this operation.
Note that this check takes O(n) time, so the function is significantly
slower during debugging. If you don't want this, you may
Note that this function does not do debug checks of the heap property,
because it may be used to construct a heap, so one of its purposes is to
be invoked on heaps. We might add a check for a partial heap property
later, though.
The default cmp function, used if cmp is NULL, is Global_oType_PRIORITY_CMP.
The success is returned.
This function checks the input (and itself indirectly via Vector_heap_raise) when
in debug mode, causing assertion failures if the heap property is violated.
Note that this check takes O(n) time, so the function is significantly
slower during debugging. If you don't want this, you may
The default cmp function, used if cmp is NULL, is Global_oType_PRIORITY_CMP.
The success is returned.
This function checks the input (and itself indirectly via Vector_heap_raise) when
in debug mode, causing assertion failures if the heap property is violated.
Note that this check takes O(n) time, so the function is significantly
slower during debugging. If you don't want this, you may
Uses the order function to sort the vector. The compare function may be NULL
if Global_oType_CMP is defined. In this case that default compare function
is used. See Vector_u.h for definition.
For a guaranteed O(n log n) runtime and O(1) space, see Vector_heap_sort.
The default cmp function, used if cmp is NULL, is Global_oType_CMP.
This function the CLib function qsort(3). Note that qsort(3) need not
use Quicksort internally, e.g. if the glibc under Linux finds that there
is enough memory, it uses merge sort instead. So you have good chances
that this function is stable in many cases under Linux. However, if you
need stability, this function does not guarantee that. Especially, when
running your programm under Windows, its qsort(3) implementation is not
stable. That's perfectly ok. For stability, simply always use
Vector_sort().
Uses Global_erwin_merge_sort, which implements a stable sorting algorithm.
Uses the order function. order may be NULL (see Vector_qsort and
Vector_heap_sort) if Global_oType_CMP is defined, which will then be used.
The default cmp function, used if cmp is NULL, is Global_oType_CMP.
Uses Erwin's erwin_merge_sort function which is stable but needs O(n) space.
Needs a sorted vector. Then searches with binary search. Uses the cmp function.
cmp may be NULL (see above)
-1 means: not found.
Uses the system function bsearch().
This operation takes O(log n) time.
The default cmp function, used if cmp is NULL, is Global_oType_CMP.
This function checks the input when in debug mode, causing assertion
failures if input is not sorted.the heap property is violated after operation.
Note that this check takes O(n) time, so the function is significantly
slower during debugging. If you don't want this, you may
#define Vector_DEBUG_EXPENSIVE_CHECKS 0
or #define Global_VECTOR_DEBUG_EXPENSIVE_CHECKS 0 (for all vectors)
Returns a hash value, which is derived from hash values for oType.
This is traditionally called hash_raw although the hash value is
good enough for a normal HASH nowadays.
Note
Usually you want hash values if you work with maps. So you
should define the hash value in such a way that both the map
header as well as the vector header find them.
Further Note
This will only be implemented if Global_oType_HASH_RAW
is defined.
Perform a table shrink operation if necessary. Mostly useful
if Vector_NO_AUTO_SHRINK is set, otherwise, this function is
automatically invoked whenever the vector shrinks.
If tight is not Global_ERWIN_FALSE, the vector is reallocated to the
absolute minimum that is necessary to store the data. Otherwise,
the standard algorithm of halving chunks is used.
Note that the function will never resize the vector smaller
than Vector_MINIMAL_SIZE (actually, no function will do that).
If Vector_MINIMAL_SIZE == 0, and if you invoke this function
on an empty vector, the vector will not use any allocated
internal structure anymore until you insert anything.
When Vector_LOW_MEM is active, this functions has no operation, since the
table size cannot be changed independently from the size.
Note that calling Vector_as_array() on a shrinked
vector is not wise since the vector will have to resize for
the padded zero element.
Note
This function is always successful. Even if realloc
failed, the vector is still consistent. Therefore, no
error code is returned. However, the error code is
set up correctly.
Further Note
If you defined memory overflow errors to be
fatal (by #define Global_ERWIN_NOMEM_IS_FATAL), they are also
fatal in this function.
If you extract the vector contents e.g. with Vector_as_array(), then
detach a vector to free its contents later, use this function for
freeing. If the memory management is left with its default settings,
this is a simple free() (or delete[] if you compiled for C++ only).
But to be sure to use the right deallocator in more complex cases,
please prefer to use this function.
Like Vector_clear you can specify whether a realloc will be performed and
whether the elements will be freed.
The former is useful if you want to clear the vector but expect new data of
around the same length to be inserted afterwards.
This function is only available of oType == oTypeVar.
This is not called `Vector_size' in order to prevent confusion
about the unit of the result. `size' might refer to bytes. `nentries', however,
is clearer.
Returns a comparison value for lexical sort order, or by length order,
depending on Vector_COMPARE_LEXICOGRAPHICALLY, which defaults to 1 for
non-character types, and to 0 for all others. The difference is that
the length order checks the length of the vector first, which is expected
to yield a quicker distinction for most vectors.
This function is NULL safe. NULL is smaller than any
other vector. By this you can easily sort a vector in reverse order and then
rtrim_if(is_NULL) to get rid of NULL elements.
If cmp is NULL, Global_oType_CMP will be used. If that is not defined, an error
will occur.
void Vector_swap (Vector_t * self, int index1, int index2)
Because using set or modify to implement swapping of two elements involves
freeing and copying elements, this functions provides a way to swap
elements without that overhead.
Needs a sorted vector. Then searches with binary search. Uses the cmp function.
cmp may be NULL (see above)
In contrast to Vector_bfind you are provided with a possible
insertion position that will keep the vector's order.
The function returns Global_ERWIN_TRUE if the element was found and Global_ERWIN_FALSE if not.
This operation takes O(log n) time.
The default cmp function, used if cmp is NULL, is Global_oType_CMP.
This function checks the input when in debug mode, causing assertion
failures if input is not sorted.the heap property is violated after operation.
Chis check takes O(n) time, so the function is significantly slower
during debugging. If you don't want this, you may
#define Vector_DEBUG_EXPENSIVE_CHECKS 0
or #define Global_VECTOR_DEBUG_EXPENSIVE_CHECKS 0 (for all vectors)
The how argument defines what value to return for the *index. The following table
give an explanation of the value written into *index:
how
if found (result ==
Global_ERWIN_TRUE)
if not found (result
== Global_ERWIN_FALSE
usage
1
the smallest index
of equal elements
insertion position
to find an element or
to insert an element
at the smallest
possible position
0
some index of an equal
element
insertion position
to find and insert
without caring about
order of equal
elements
1
the largest index of
equal elements
insertion position - 1
to find an element or
to insert an element
at the largest
possible position.
At first sight, for how==1 the value of index seems strange. But from the point of
view of inserting even in case of equality, you can simply insert at (*index+1) to
insert at the right most possible position keeping the vector's order without looking at
the function's return value. However, in case of finding the element, *index always
points to an equal element. Note that because of this, index may be -1 (for how=1
if you want to insert at the beginning).
Note
for how==0 and how==-1, the functions will set *index to
Vector_nentries(self) if the searched element is larger than any in the vector,
because that is the correct value for Vector_insert.
Summarized constraints that always hold:
for how==0 and how==-1
*index always is the correct
insertion position.
for how==1
(*index + 1) always is the correct
insert position.
Needs a sorted vector. Then searches with binary search. Uses the cmp function.
cmp may be NULL (see above)
In contrast to Vector_bfind you are provided with a possible
insertion position that will keep the vector's order.
The function returns Global_ERWIN_TRUE if the element was found and Global_ERWIN_FALSE if not.
This operation takes O(log n) time.
The default cmp function, used if cmp is NULL, is Global_oType_CMP.
This function checks the input when in debug mode, causing assertion
failures if input is not sorted.the heap property is violated after operation.
Chis check takes O(n) time, so the function is significantly slower
during debugging. If you don't want this, you may
#define Vector_DEBUG_EXPENSIVE_CHECKS 0
or #define Global_VECTOR_DEBUG_EXPENSIVE_CHECKS 0 (for all vectors)
The how argument defines what value to return for the *index. The following table
give an explanation of the value written into *index:
how
if found (result ==
Global_ERWIN_TRUE)
if not found (result
== Global_ERWIN_FALSE
usage
1
the smallest index
of equal elements
insertion position
to find an element or
to insert an element
at the smallest
possible position
0
some index of an equal
element
insertion position
to find and insert
without caring about
order of equal
elements
1
the largest index of
equal elements
insertion position - 1
to find an element or
to insert an element
at the largest
possible position.
At first sight, for how==1 the value of index seems strange. But from the point of
view of inserting even in case of equality, you can simply insert at (*index+1) to
insert at the right most possible position keeping the vector's order without looking at
the function's return value. However, in case of finding the element, *index always
points to an equal element. Note that because of this, index may be -1 (for how=1
if you want to insert at the beginning).
Note
for how==0 and how==-1, the functions will set *index to
Vector_nentries(self) if the searched element is larger than any in the vector,
because that is the correct value for Vector_insert.
Summarized constraints that always hold:
for how==0 and how==-1
*index always is the correct
insertion position.
for how==1
(*index + 1) always is the correct
insert position.
