Constructor

Cvoid Vector_InitVector (struct Vector *vector, size_t capacity, CopyFunc cfunc, DelFunc dfunc, void *ptr);

C++Vector::Vector (size_t capacity, CopyFunc cfunc, DelFunc dfunc, void *ptr);

Description: Init new vector instance.

Access type: RW

Parameters:

• vector - pointer to the vector
• capacity - initial count of elements that the vector can hold. Vector capacity is auto extended if required.
• cfunc - pointer to copy function for element fields: key and data, or NULL. Copy function should follow this prototype.
• dfunc - pointer to delete function to call for removing elements, or NULL. Delete function should follow this prototype.
• ptr - pointer to user's data, required by element copy and delete functions, or NULL.

Return value: None.

Copy constructor

Cvoid Vector_CopyVector (struct Vector *vector, const struct Vector *source);

C++Vector::Vector (const Vector &source);

Description: Init new instance of the vector and copy all elements from the source vector inside the new one. New vector has its own data space and doesn't share any memory blocks with the source vector. Source vector stay unchanged and accessed in read only mode.

Access type: RW

Parameters:

• vector - pointer to target vector
• source - pointer to source vector

Return value: None.

Destructor

Cvoid Vector_FreeVector (struct Vector *vector);

C++Vector::~Vector (void);

Description: Reset the vector instance and release all memory blocks are used by the object.

Access type: RW

Parameters:

• vector - pointer to the vector

Return value: None.

Access predicates

Access predicates is an easy and efficient way to write multithreaded highly concurrent code. Vector functions may change container elements, add new values and remove the existing ones. This can result to data inconsistency among different threads. To solve this possible issue, you have to separate read and write operations to the vector. Write operation can not be invoked in the same time with other write or read operations, and should get exclusive access to the container. Read operations can be processed simultaneously with each other, but not with write operation (because of possible dirty reads).

Access predicates solve these problems and support lock methods for exclusive writes and concurrent reads from different threads. Lock functions return TRUE state only when you get appropriate access to the vector. They support wait and no wait behaviors. If wait flag is set, then lock functions wait until the lock is taken. In no wait mode they try to get lock for some short period of time (spinlock cycle). And if no success, then return FALSE. Your code may check the return status and do something else instead of just waiting.

Lock operations

Lock operations give you appropriate access type to the vector and return TRUE, if you get such access, or FALSE, if lock is taken by other thread, and you chose no wait behavior (wait flag is set to FALSE). You can check lock status and run some code while other threads hold the lock. If the thread get the lock, then you can be sure that other threads do not process unsafe operations on the container. To guarantee this other threads also should use lock functions and check returned lock result. When you complete the operations, then release the lock by calling release functions, described below. This will wake up waiting threads for further data processing.

Exclusive access

Cbool Vector_LockReadings (struct Vector *vector, bool wait);

C++bool Vector::LockReadings (bool wait);

Description: Lock read and write operations from other threads and provide exclusive access for vector modifications. All other threads are waiting until the lock is released by AllowReadings procedure. To guarantee that the thread has exclusive access, all concurrent threads also should use either of lock functions like LockReadings or LockWritings to wait.

Wait flag, is used by the functions, can change their behavior from always wait, until the lock is taken, to no wait behavior. No wait variant tries to get the lock in spinlock cycle, and if no success, then return FALSE state. User's code can check the functions status, and if exclusive lock is taken, then process the vector modifications, or do something else if lock is not taken.

Access type: RW

Parameters:

• vector - pointer to the vector
• wait - wait flag. If set, then functions wait until lock is taken and always return TRUE.

Return value:

• TRUE (1) if you have exclusive access to the vector.
• FALSE (0) if the wait flag was not set and exclusive lock is not taken.

Warning:Exclusive lock operation is not recursive. It should be called only once and then released. Thread can do it many times but not in recursive mode.

Note:Do not forget to release exclusive lock when you finished. Use the AllowReadings procedure.

Read only access

Cbool Vector_LockWritings (struct Vector *vector, bool wait);

C++bool Vector::LockWritings (bool wait);

Description: Lock write operations from all threads and provide read only access to the vector. All write threads, are waiting until the lock is released by AllowWritings procedure. All reading threads continue to work. To guarantee that the thread has read only access, all concurrent threads also should use either of lock functions like LockReadings or LockWritings to wait.

Wait flag, is used by the functions, can change their behavior from always wait, until the lock is taken, to no wait behavior. No wait variant tries to get the lock in spinlock cycle, and if no success, then return FALSE state. User's code can check the functions status, and if read only lock is taken, then process the vector readings, or do something else if lock is not taken.

Access type: RW

Parameters:

• vector - pointer to the vector
• wait - wait flag. If set, then functions wait until lock is taken and always return TRUE.

Return value:

• TRUE (1) if you have read only access to the vector.
• FALSE (0) if the wait flag was not set and read only lock is not taken.

Warning:Vector built in futex collects count of concurrent reading threads. So each succeed read lock should always have appropriate release call.

Note:Do not forget to release read only lock when you finished. Use the AllowWritings procedure.

Release operations

Release operations unlock the built in futex and wake up waiters for further data processing. AllowReadings procedure release exclusive lock and wake all writing and reading threads. AllowWritings procedure wake anyone of writing threads if the vector have any of them. Each lock function should always call release function to prevent dead locks.

Releasing of exclusive lock

Cvoid Vector_AllowReadings (struct Vector *vector);

C++void Vector::AllowReadings (void);

Description: Release exclusive lock and allow vector readings and writings from other threads.

Access type: RW

Parameters:

• vector - pointer to the vector

Return value: None.

Releasing of read only lock

Cvoid Vector_AllowWritings (struct Vector *vector);

C++void Vector::AllowWritings (void);

Description: Release read only lock and allow vector writings from other threads. If you have multiple reading threads, then only the last reading thread really release the lock and wake up the writing thread.

Access type: RW

Parameters:

• vector - pointer to the vector

Return value: None.

Warning:Vector built in futex collects count of concurrent reading threads. So each succeed read lock should always have appropriate release call.

Copying elements

Csize_t Vector_Copy (struct Vector *vector, size_t tpos, const struct Vector *source, size_t spos, size_t count);

C++size_t Vector::Copy (size_t tpos, const Vector *source, size_t spos, size_t count);

Description: Copy "count" elements from source vector into target vector. Functions copy data starting from "spos" element in source vector, until all "count" elements are inserted into target vector after "tpos" position. Source vector stay unchanged and accessed in read only mode.

Access type: RW

Parameters:

• vector - pointer to target vector
• tpos - insert position into the target vector
• source - pointer to source vector
• spos - starting position in the source vector
• count - number of elements to copy (-1 means all available elements)

Return value:

• Real count of elements, which were copied from source vector.
• -1 if target vector was not able to extend its capacity for new elements, or starting position is greater than or equal to target/source vector size, or functions are called from read only section, started by LockWritings access predicate.

Moving elements

Csize_t Vector_Move (struct Vector *vector, size_t tpos, struct Vector *source, size_t spos, size_t count);

C++size_t Vector::Move (size_t tpos, Vector *source, size_t spos, size_t count);

Description: Move "count" elements from source vector into target vector. Functions move data starting from "spos" element in source vector, until all "count" elements are inserted into target vector after "tpos" position.

Access type: RW

Parameters:

• vector - pointer to target vector
• tpos - insert position into the target vector
• source - pointer to source vector
• spos - starting position in the source vector
• count - number of elements to move (-1 means all available elements)

Return value:

• Real count of elements, which were moved from source vector.
• -1 if target vector was not able to extend its capacity for new elements, or starting position is greater than or equal to target/source vector size, or functions are called from read only section, started by LockWritings access predicate.

Addition of element

Cbool Vector_Push (struct Vector *vector, const struct pair_t *data);

C++bool Vector::Push (const pair_t *data);

Description: Push new element at the end of the the vector.

Access type: RW

Parameters:

• vector - pointer to the vector
• data - pointer to the new element

Return value:

• TRUE (1) if element was successfully inserted into the vector.
• FALSE (0) if the vector was not able to extend its capacity for the new element, or functions are called from read only section, started by LockWritings access predicate.

Removal of element

Cbool Vector_Pop (struct Vector *vector);

C++bool Vector::Pop (void);

Description: Pop last element from the vector.

Access type: RW

Parameters:

• vector - pointer to the vector

Return value:

• TRUE (1) if vector is not empty.
• FALSE (0) if vector is empty, or functions are called from read only section, started by LockWritings access predicate.

Insertion of element

Cbool Vector_Insert (struct Vector *vector, const struct pair_t *data, size_t pos);

C++bool Vector::Insert (const pair_t *data, size_t pos);

Description: Insert new element into the selected position in the vector.

Access type: RW

Parameters:

• vector - pointer to the vector
• data - pointer to the new element
• pos - element position in the vector

Return value:

• TRUE (1) if element was successfully inserted into the vector.
• FALSE (0) if the vector was not able to extend its capacity, or element position is incorrect, or functions are called from read only section, started by LockWritings access predicate.

Extraction of element

Cbool Vector_Extract (struct Vector *vector, size_t pos);

C++bool Vector::Extract (size_t pos);

Description: Delete the element in the selected position in the vector.

Access type: RW

Parameters:

• vector - pointer to the vector
• pos - element position in the vector

Return value:

• TRUE (1) if element position is less than the vector size.
• FALSE (0) if element position is incorrect, or functions are called from read only section, started by LockWritings access predicate.

Setting element value

Cbool Vector_Set (struct Vector *vector, const struct pair_t *data, size_t pos);

C++bool Vector::Set (const pair_t *data, size_t pos);

Description: Set value of the element in selected position in the vector.

Access type: RW

Parameters:

• vector - pointer to the vector
• data - pointer to the new value of the element
• pos - element position in the vector

Return value:

• TRUE (1) if element position is less than the vector size.
• FALSE (0) if element with target position does not exist, or functions are called from read only section, started by LockWritings access predicate.

Getting element value

Cbool Vector_Get (const struct Vector *vector, struct pair_t *data, size_t pos);

C++bool Vector::Get (pair_t *data, size_t pos) const;

Description: Get value of the element in selected position in the vector. The vector stay unchanged.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the element
• pos - element position in the vector

Return value:

• TRUE (1) if element position is less than the vector size.
• FALSE (0) if element with target position does not exist.

Changing elements order

These functions allow to change elements order in the vector and swap the elements.

Reversing elements order

Csize_t Vector_Reverse (struct Vector *vector, size_t pos, size_t count);

C++size_t Vector::Reverse (size_t pos, size_t count);

Description: Reverse order of "count" elements in the vector starting from the "pos" position, and store them in the same place in new order. Other elements are not modified.

Access type: RW

Parameters:

• vector - pointer to the vector
• pos - starting position in the vector
• count - number of elements to reverse (-1 means all available elements)

Return value:

• Real count of elements, which were reversed.
• -1 if starting position is greater than or equal to the vector size, or functions are called from read only section, started by LockWritings access predicate.

Swapping elements

Cbool Vector_Swap (struct Vector *vector, size_t pos1, size_t pos2);

C++bool Vector::Swap (size_t pos1, size_t pos2);

Description: Swap selected elements in the vector.

Access type: RW

Parameters:

• vector - pointer to the vector
• pos1 - first element position in the vector
• pos2 - second element position in the vector

Return value:

• TRUE (1) if element positions are less than the vector size.
• FALSE (0) if elements with target positions do not exist, or functions are called from read only section, started by LockWritings access predicate.

Minimum and maximum value

Next functions scan "count" elements in the vector from first element to last element and from last element to first element, starting from "pos" position, and return position of the first/last element, which has minimum/maximum key value.

Minimum value

Csize_t Vector_MinFwd (const struct Vector *vector, struct pair_t *data, size_t pos, size_t count);
size_t Vector_MinBwd (const struct Vector *vector, struct pair_t *data, size_t pos, size_t count);

C++size_t Vector::MinFwd (pair_t *data, size_t pos, size_t count) const;
size_t Vector::MinBwd (pair_t *data, size_t pos, size_t count) const;

Description: Scan "count" elements in the vector from first/last element to last/first element, starting from "pos" position. Then return position of the first/last element, which has minimum value of the key, and store its value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the found element
• pos - starting position in the vector
• count - number of elements to check (-1 means all available elements)

Return value:

• Index of the first/last element, having minimum value, in the vector.
• -1 if position is greater than or equal to the vector size.

Maximum value

Csize_t Vector_MaxFwd (const struct Vector *vector, struct pair_t *data, size_t pos, size_t count);
size_t Vector_MaxBwd (const struct Vector *vector, struct pair_t *data, size_t pos, size_t count);

C++size_t Vector::MaxFwd (pair_t *data, size_t pos, size_t count) const;
size_t Vector::MaxBwd (pair_t *data, size_t pos, size_t count) const;

Description: Scan "count" elements in the vector from first/last element to last/first element, starting from "pos" position. Then return position of the first/last element, which has maximum value of the key, and store its value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the found element
• pos - starting position in the vector
• count - number of elements to check (-1 means all available elements)

Return value:

• Index of the first/last element, having maximum value, in the vector.
• -1 if position is greater than or equal to the vector size.

Key searching

Following functions check vector elements for first/last element, which match the key or the set of keys, then return position to that object. If required element is found, then they store its value into the data structure is pointed by "data" pointer. If target value was not found, then functions return -1 and "data" structure stay unchanged.

Linear search

Following functions scan "count" elements in the vector from first element to last element and from last element to first element, starting from "pos" position, and return position of the first/last element, which is equal to the specified key or to the set of keys. If beginning position is greater than or equal to vector size, then -1 is returned.

Single key searching

Csize_t Vector_FindKeyFwd (const struct Vector *vector, struct pair_t *data, union adt_t key, size_t pos, size_t count);
size_t Vector_FindKeyBwd (const struct Vector *vector, struct pair_t *data, union adt_t key, size_t pos, size_t count);

C++size_t Vector::FindKeyFwd (pair_t *data, adt_t key, size_t pos, size_t count) const;
size_t Vector::FindKeyBwd (pair_t *data, adt_t key, size_t pos, size_t count) const;

Description: Scan "count" elements in the vector from first/last element to last/first element, starting from "pos" position. Then return position of the first/last element, which is equal to the specified key, and store its value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the found element
• key - key value to find in the vector
• pos - starting position in the vector
• count - number of elements to check (-1 means all available elements)

Return value:

• Index of the first/last found element in the vector.
• -1 if no matches were met, or position is greater than or equal to the vector size.

Keys set searching

Csize_t Vector_FindKeysFwd (const struct Vector *vector, struct pair_t *data, const union adt_t keys[], size_t size, size_t pos, size_t count);
size_t Vector_FindKeysBwd (const struct Vector *vector, struct pair_t *data, const union adt_t keys[], size_t size, size_t pos, size_t count);

C++size_t Vector::FindKeysFwd (pair_t *data, const adt_t keys[], size_t size, size_t pos, size_t count) const;
size_t Vector::FindKeysBwd (pair_t *data, const adt_t keys[], size_t size, size_t pos, size_t count) const;

Description: Scan "count" elements in the vector from first/last element to last/first element, starting from "pos" position. Then return position of the first/last element, which is equal to any key in the set of keys, and store its value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the found element
• keys - array of keys to find in the vector
• size - size of array of keys
• pos - starting position in the vector
• count - number of elements to check (-1 means all available elements)

Return value:

• Index of the first/last found element in the vector.
• -1 if no matches were met, or position is greater than or equal to the vector size.

Binary search

Binary search algorithms find position of a specified value within a sorted vector. Vectors may be sorted in ascending or descending order. Functions can be used to find elements, which conform to special conditions like equal, less, great etc. They return index of first/last position of element, which met the condition and its value.

Ascending sort order

Searching for first equal keytop

Csize_t Vector_FindFirstEqualAsc (const struct Vector *vector, struct pair_t *data, union adt_t key);

C++size_t Vector::FindFirstEqualAsc (pair_t *data, adt_t key) const;

Description: Search the vector, which is sorted in ascending order, for the first element, which is equal to the specified key. Then store element value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the found element
• key - key value to process

Return value:

• An index of first element, which is equal to the key.
• -1 if key was not found, or vector is empty.

Note:These functions work only with sorted vectors. To use them with regular vectors they should be sorted first.

Searching for last equal keytop

Csize_t Vector_FindLastEqualAsc (const struct Vector *vector, struct pair_t *data, union adt_t key);

C++size_t Vector::FindLastEqualAsc (pair_t *data, adt_t key) const;

Description: Search the vector, which is sorted in ascending order, for the last element, which is equal to the specified key. Then store element value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the found element
• key - key value to process

Return value:

• An index of last element, which is equal to the key.
• -1 if key was not found, or vector is empty.

Note:These functions work only with sorted vectors. To use them with regular vectors they should be sorted first.

Searching for greater keytop

Csize_t Vector_FindGreatAsc (const struct Vector *vector, struct pair_t *data, union adt_t key);

C++size_t Vector::FindGreatAsc (pair_t *data, adt_t key) const;

Description: Search the vector, which is sorted in ascending order, for the first element, which is greater than the specified key. Then store element value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the found element
• key - key value to process

Return value:

• An index of first element, which is greater than the key.
• -1 if key was not found, or vector is empty.

Note:These functions work only with sorted vectors. To use them with regular vectors they should be sorted first.

Searching for greater or equal keytop

Csize_t Vector_FindGreatOrEqualAsc (const struct Vector *vector, struct pair_t *data, union adt_t key);

C++size_t Vector::FindGreatOrEqualAsc (pair_t *data, adt_t key) const;

Description: Search the vector, which is sorted in ascending order, for the first element, which is greater than or equal to the specified key. Then store element value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the found element
• key - key value to process

Return value:

• An index of first element, which is greater than or equal to the key.
• -1 if key was not found, or vector is empty.

Note:These functions work only with sorted vectors. To use them with regular vectors they should be sorted first.

Searching for less keytop

Csize_t Vector_FindLessAsc (const struct Vector *vector, struct pair_t *data, union adt_t key);

C++size_t Vector::FindLessAsc (pair_t *data, adt_t key) const;

Description: Search the vector, which is sorted in ascending order, for the last element, which is less than the specified key. Then store element value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the found element
• key - key value to process

Return value:

• An index of last element, which is less than the key.
• -1 if key was not found, or vector is empty.

Note:These functions work only with sorted vectors. To use them with regular vectors they should be sorted first.

Searching for less or equal keytop

Csize_t Vector_FindLessOrEqualAsc (const struct Vector *vector, struct pair_t *data, union adt_t key);

C++size_t Vector::FindLessOrEqualAsc (pair_t *data, adt_t key) const;

Description: Search the vector, which is sorted in ascending order, for the last element, which is less than or equal to the specified key. Then store element value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the found element
• key - key value to process

Return value:

• An index of last element, which is less than or equal to the key.
• -1 if key was not found, or vector is empty.

Note:These functions work only with sorted vectors. To use them with regular vectors they should be sorted first.

Descending sort order

Searching for first equal keytop

Csize_t Vector_FindFirstEqualDsc (const struct Vector *vector, struct pair_t *data, union adt_t key);

C++size_t Vector::FindFirstEqualDsc (pair_t *data, adt_t key) const;

Description: Search the vector, which is sorted in descending order, for the first element, which is equal to the specified key. Then store element value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the found element
• key - key value to process

Return value:

• An index of first element, which is equal to the key.
• -1 if key was not found, or vector is empty.

Note:These functions work only with sorted vectors. To use them with regular vectors they should be sorted first.

Searching for last equal keytop

Csize_t Vector_FindLastEqualDsc (const struct Vector *vector, struct pair_t *data, union adt_t key);

C++size_t Vector::FindLastEqualDsc (pair_t *data, adt_t key) const;

Description: Search the vector, which is sorted in descending order, for the last element, which is equal to the specified key. Then store element value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the found element
• key - key value to process

Return value:

• An index of last element, which is equal to the key.
• -1 if key was not found, or vector is empty.

Note:These functions work only with sorted vectors. To use them with regular vectors they should be sorted first.

Searching for less keytop

Csize_t Vector_FindLessDsc (const struct Vector *vector, struct pair_t *data, union adt_t key);

C++size_t Vector::FindLessDsc (pair_t *data, adt_t key) const;

Description: Search the vector, which is sorted in descending order, for the first element, which is less than the specified key. Then store element value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the found element
• key - key value to process

Return value:

• An index of first element, which is less than the key.
• -1 if key was not found, or vector is empty.

Note:These functions work only with sorted vectors. To use them with regular vectors they should be sorted first.

Searching for less or equal keytop

Csize_t Vector_FindLessOrEqualDsc (const struct Vector *vector, struct pair_t *data, union adt_t key);

C++size_t Vector::FindLessOrEqualDsc (pair_t *data, adt_t key) const;

Description: Search the vector, which is sorted in descending order, for the first element, which is less than or equal to the specified key. Then store element value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the found element
• key - key value to process

Return value:

• An index of first element, which is less than or equal to the key.
• -1 if key was not found, or vector is empty.

Note:These functions work only with sorted vectors. To use them with regular vectors they should be sorted first.

Searching for greater keytop

Csize_t Vector_FindGreatDsc (const struct Vector *vector, struct pair_t *data, union adt_t key);

C++size_t Vector::FindGreatDsc (pair_t *data, adt_t key) const;

Description: Search the vector, which is sorted in descending order, for the last element, which is greater than the specified key. Then store element value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the found element
• key - key value to process

Return value:

• An index of last element, which is greater than the key.
• -1 if key was not found, or vector is empty.

Note:These functions work only with sorted vectors. To use them with regular vectors they should be sorted first.

Searching for greater or equal keytop

Csize_t Vector_FindGreatOrEqualDsc (const struct Vector *vector, struct pair_t *data, union adt_t key);

C++size_t Vector::FindGreatOrEqualDsc (pair_t *data, adt_t key) const;

Description: Search the vector, which is sorted in descending order, for the last element, which is greater than or equal to the specified key. Then store element value into the data structure is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of the found element
• key - key value to process

Return value:

• An index of last element, which is greater than or equal to the key.
• -1 if key was not found, or vector is empty.

Note:These functions work only with sorted vectors. To use them with regular vectors they should be sorted first.

Duplicates searching

Csize_t Vector_FindDupFwd (const struct Vector *vector, struct pair_t *data, size_t pos, size_t count);
size_t Vector_FindDupBwd (const struct Vector *vector, struct pair_t *data, size_t pos, size_t count);

C++size_t Vector::FindDupFwd (pair_t *data, size_t pos, size_t count) const;
size_t Vector::FindDupBwd (pair_t *data, size_t pos, size_t count) const;

Description: Scan "count" elements of the vector in forward/backward direction from "pos" position, and return position of first non unique element, then return value of that element. If no duplicates were found, then functions return -1 and do not change data structure, which is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of non unique element
• pos - starting position in the vector
• count - number of elements to check (-1 means all available elements)

Return value:

• Fisrt/last position of duplicated element.
• -1 if all elements are unique, or starting position is greater than or equal to vector size.

Note:These functions work only with sorted vectors, regardless of sort order. To use them with regular vectors they should be sorted first.

Unordered elements searching

Following functions check vectors for required sort order, and return value and position of the first element, which did not pass the sort condition.

Ascending sort order

Csize_t Vector_FindNonAscFwd (const struct Vector *vector, struct pair_t *data, size_t pos, size_t count);
size_t Vector_FindNonAscBwd (const struct Vector *vector, struct pair_t *data, size_t pos, size_t count);

C++size_t Vector::FindNonAscFwd (pair_t *data, size_t pos, size_t count) const;
size_t Vector::FindNonAscBwd (pair_t *data, size_t pos, size_t count) const;

Description: Scan "count" elements of the vector in forward/backward direction from "pos" position, and return position of first non ascending element, then return value of that element. If all elements are correctly ordered, then functions return -1, and do not change data structure, which is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of non ordered element
• pos - starting position in the vector
• count - number of elements to check (-1 means all available elements)

Return value:

• Fisrt/last position of non ordered element.
• -1 if all elements have correct order, or starting position is greater than or equal to vector size.

Descending sort order

Csize_t Vector_FindNonDscFwd (const struct Vector *vector, struct pair_t *data, size_t pos, size_t count);
size_t Vector_FindNonDscBwd (const struct Vector *vector, struct pair_t *data, size_t pos, size_t count);

C++size_t Vector::FindNonDscFwd (pair_t *data, size_t pos, size_t count) const;
size_t Vector::FindNonDscBwd (pair_t *data, size_t pos, size_t count) const;

Description: Scan "count" elements of the vector in forward/backward direction from "pos" position, and return position of first non descending element, then return value of that element. If all elements are correctly ordered, then functions return -1, and do not change data structure, which is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to the vector
• data - address where to return the value of non ordered element
• pos - starting position in the vector
• count - number of elements to check (-1 means all available elements)

Return value:

• Fisrt/last position of non ordered element.
• -1 if all elements have correct order, or starting position is greater than or equal to vector size.

Searching for differences

Csize_t Vector_FindDiffFwd (const struct Vector *vector, struct pair_t *data, size_t tpos, const struct Vector *source, size_t spos, size_t count);
size_t Vector_FindDiffBwd (const struct Vector *vector, struct pair_t *data, size_t tpos, const struct Vector *source, size_t spos, size_t count);

C++size_t Vector::FindDiffFwd (pair_t *data, size_t tpos, const Vector *source, size_t spos, size_t count) const;
size_t Vector::FindDiffBwd (pair_t *data, size_t tpos, const Vector *source, size_t spos, size_t count) const;

Description: Compare "count" elements of two vector objects (key by key) from first element to last element and from last element to first element, then return position and value of the first/last non equal element in target vector. Target vector is scanned from "tpos" position. And source vector is scanned from "spos" position. These functions do not compare assigned data fields, but only the keys. If no different keys were found during "count" elements, then functions return -1 and do not change data structure, which is pointed by "data" pointer.

Access type: RO

Parameters:

• vector - pointer to target vector
• data - address where to return the value of non equal element
• tpos - starting position in the target vector
• source - pointer to source vector
• spos - starting position in the source vector
• count - number of elements to check (-1 means all available elements)

Return value:

• Index of the first/last non equal element in target vector.
• -1 if no different keys were found during "count" elements, or position is greater than or equal to target/source vector size.

Key counting

Key counting algorithms return a number of pattern matches were met in the vector. Linear counting algorithms always check all "count" elements even if pattern was not found. Binary count algorithms assume that the vector is sorted in ascending or descending order, and take log(N) compare operations to find a number of pattern matches.

Linear counting

Following functions scan "count" elements in the vector from first element to last element and from last element to first element, starting from "pos" position, and return count of matches to the key or to the set of keys.

Single key counting

Csize_t Vector_CountKeyFwd (const struct Vector *vector, union adt_t key, size_t pos, size_t count);
size_t Vector_CountKeyBwd (const struct Vector *vector, union adt_t key, size_t pos, size_t count);

C++size_t Vector::CountKeyFwd (adt_t key, size_t pos, size_t count) const;
size_t Vector::CountKeyBwd (adt_t key, size_t pos, size_t count) const;

Description: Scan "count" elements in the vector from first/last element to last/first element, starting from "pos" position. Then return count of the elements, which are equal to the specified key.

Access type: RO

Parameters:

• vector - pointer to the vector
• key - key value to find in the vector
• pos - starting position in the vector
• count - number of elements to check (-1 means all available elements)

Return value: Count of the elements, which are equal to the specified key.

Keys set counting

Csize_t Vector_CountKeysFwd (const struct Vector *vector, const union adt_t keys[], size_t size, size_t pos, size_t count);
size_t Vector_CountKeysBwd (const struct Vector *vector, const union adt_t keys[], size_t size, size_t pos, size_t count);

C++size_t Vector::CountKeysFwd (const adt_t keys[], size_t size, size_t pos, size_t count) const;
size_t Vector::CountKeysBwd (const adt_t keys[], size_t size, size_t pos, size_t count) const;

Description: Scan "count" elements in the vector from first/last element to last/first element, starting from "pos" position. Then return count of the elements, which are equal to any key in the set of keys.

Access type: RO

Parameters:

• vector - pointer to the vector
• keys - array of keys to find in the vector
• size - size of array of keys
• pos - starting position in the vector
• count - number of elements to check (-1 means all available elements)

Return value: Count of the elements, which are equal to any key in the set of keys.

Binary counting

Binary counting is very efficient way to count pattern matches in sorted vector. It takes log(N) compare operations to find a number of pattern matches and works only with sorted is ascending or descending order vectors. Use appropriate function for each sort order.

Ascending sort order

Csize_t Vector_CountAsc (const struct Vector *vector, union adt_t key);

C++size_t Vector::CountAsc (adt_t key) const;

Description: Search the vector, which is sorted in ascending order, for specified value and return the count of pattern matches were met.

Access type: RO

Parameters:

• vector - pointer to the vector
• key - key value to find in the vector

Return value: Count of the elements, which are equal to the specified key.

Note:These functions work only with sorted vectors. To use them with regular vectors they should be sorted first.

Descending sort order

Csize_t Vector_CountDsc (const struct Vector *vector, union adt_t key);

C++size_t Vector::CountDsc (adt_t key) const;

Description: Search the vector, which is sorted in descending order, for specified value and return the count of pattern matches were met.

Access type: RO

Parameters:

• vector - pointer to the vector
• key - key value to find in the vector

Return value: Count of the elements, which are equal to the specified key.

Note:These functions work only with sorted vectors. To use them with regular vectors they should be sorted first.

Insertion sort

Insertion sort is a simple sorting algorithm that builds the final sorted vector one item at a time. It is much less efficient on large vectors than more advanced algorithms such as quicksort or merge sort, but it is stable. Stable sorting algorithms maintain the relative order of elements with equal keys.

Ascending sort order

Csize_t Vector_InsertSortAsc (struct Vector *vector);

C++size_t Vector::InsertSortAsc (void);

Description: Sort vector in ascending order using Insert sort algorithm.

Access type: RW

Parameters:

• vector - pointer to the vector

Return value:

• Count of the elements, which were sorted.
• -1 if functions are called from read only section, started by LockWritings access predicate.

Tip:Insert sort preserve the relative order of elements with equal keys. And should be used for small vectors (32 elements or less) where this option is necessary.

Descending sort order

Csize_t Vector_InsertSortDsc (struct Vector *vector);

C++size_t Vector::InsertSortDsc (void);

Description: Sort vector in descending order using Insert sort algorithm.

Access type: RW

Parameters:

• vector - pointer to the vector

Return value:

• Count of the elements, which were sorted.
• -1 if functions are called from read only section, started by LockWritings access predicate.

Tip:Insert sort preserve the relative order of elements with equal keys. And should be used for small vectors (32 elements or less) where this option is necessary.

Quick sort

Quick sort is a sorting algorithm developed by Tony Hoare that, on average, makes N*log(N) comparisons to sort N items. In the worst case, it makes O(N²) comparisons, though this behavior is rare. Quick sort sequential and localized memory references work well with a cache. This algorithm is implemented as an in-place partitioning algorithm, and doesn't require any additional place for sorting.

Ascending sort order

Csize_t Vector_QuickSortAsc (struct Vector *vector);

C++size_t Vector::QuickSortAsc (void);

Description: Sort vector in ascending order using Quick sort algorithm.

Access type: RW

Parameters:

• vector - pointer to the vector

Return value:

• Count of the elements, which were sorted.
• -1 if functions are called from read only section, started by LockWritings access predicate.

Descending sort order

Csize_t Vector_QuickSortDsc (struct Vector *vector);

C++size_t Vector::QuickSortDsc (void);

Description: Sort vector in descending order using Quick sort algorithm.

Access type: RW

Parameters:

• vector - pointer to the vector

Return value:

• Count of the elements, which were sorted.
• -1 if functions are called from read only section, started by LockWritings access predicate.

Merge sort

Merge sort is an N*log(N) comparison-based sorting algorithm. It produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.

Ascending sort order

Csize_t Vector_MergeSortAsc (struct Vector *vector);

C++size_t Vector::MergeSortAsc (void);

Description: Sort vector in ascending order using Merge sort algorithm.

Access type: RW

Parameters:

• vector - pointer to the vector

Return value:

• Count of the elements, which were sorted.
• -1 if sort functions were not able to allocate new memory blocks for internal use, or functions are called from read only section, started by LockWritings access predicate.

Tip:Merge sort preserve the relative order of elements with equal keys. And should be used for big vectors (more than 32 elements) where this option is necessary.

Descending sort order

Csize_t Vector_MergeSortDsc (struct Vector *vector);

C++size_t Vector::MergeSortDsc (void);

Description: Sort vector in descending order using Merge sort algorithm.

Access type: RW

Parameters:

• vector - pointer to the vector

Return value:

• Count of the elements, which were sorted.
• -1 if sort functions were not able to allocate new memory blocks for internal use, or functions are called from read only section, started by LockWritings access predicate.

Tip:Merge sort preserve the relative order of elements with equal keys. And should be used for big vectors (more than 32 elements) where this option is necessary.

Merging of sorted vectors

Merge functions take two sorted vectors and merge them into one sorted vector. These functions just add content of source vector into target vector, according to the sort order.

Ascending sort order

Csize_t Vector_MergeAsc (struct Vector *vector, struct Vector *source);

C++size_t Vector::MergeAsc (Vector *source);

Description: Merge two sorted in ascending order vectors into one sorted vector (target vector). All elements from source vector are moved to target vector and source vector remains empty after merge operation.

Access type: RW

Parameters:

• vector - pointer to target vector
• source - pointer to source vector

Return value:

• Count of the elements, which were copied from source vector.
• -1 if merge functions were not able to extend capacity of the vector object for the new elements, or functions are called from read only section, started by LockWritings access predicate.

Warning:Merge operation moves all elements from source vector into target vector.

Note:These functions work only with sorted in correct order vectors. If you try to merge unsorted vectors, then result is undefined.

Descending sort order

Csize_t Vector_MergeDsc (struct Vector *vector, struct Vector *source);

C++size_t Vector::MergeDsc (Vector *source);

Description: Merge two sorted in descending order vectors into one sorted vector (target vector). All elements from source vector are moved to target vector and source vector remains empty after merge operation.

Access type: RW

Parameters:

• vector - pointer to target vector
• source - pointer to source vector

Return value:

• Count of the elements, which were copied from source vector.
• -1 if merge functions were not able to extend capacity of the vector object for the new elements, or functions are called from read only section, started by LockWritings access predicate.

Warning:Merge operation moves all elements from source vector into target vector.

Note:These functions work only with sorted in correct order vectors. If you try to merge unsorted vectors, then result is undefined.

Unique values

Csize_t Vector_Unique (struct Vector *vector, const struct Vector *source);

C++size_t Vector::Unique (const Vector *source);

Description: Extract only unique keys from source vector, and store them into target vector. When this operation is done, target vector will have only unique keys and count of duplicates that each key had in source vector. Number of duplicates is stored into data field of the elements.

Access type: RW

Parameters:

• vector - pointer to target vector
• source - pointer to source vector

Return value:

• Count of unique elements were found in source vector.
• -1 if target vector was not able to extend its capacity for new elements, or it was not empty, or functions are called from read only section, started by LockWritings access predicate.

Warning:These functions assume that target vector is empty. If it already has any elements, then operations will fail.

Warning:Unique functions do not make deep copy of keys from source vector, but use only reference to original objects from source vector. Do not delete objects from source vector until you finish all operations with unique keys. In other case you may have broken pointers or undefined behavior of your program.

Note:These functions work only with sorted vectors, regardless of sort order. To use them with regular vectors they should be sorted first.

Comparison of vectors

Csint64_t Vector_Compare (const struct Vector *vector, const struct Vector *source);

C++sint64_t Vector::Compare (const Vector *source) const;

Description: Compare two vector objects (key by key) starting from first element to last element, using provided key compare function, and return relations between them (less, equal or greater). These functions do not compare assigned data fields, but only the keys.

Access type: RO

Parameters:

• vector - pointer to target vector
• source - pointer to source vector

Return value:

• -1 if first vector is less than second vector.
• 0 if first vector is equal to second vector.
• +1 if first vector is greater than second vector.

Checks

Check for sort order

Following functions check vectors for required sort order, and return status of this check as boolean value. TRUE (1) if elements are correctly sorted and FALSE (0) if not.

Check for ascending sort order

Cbool Vector_CheckSortAsc (const struct Vector *vector);

C++bool Vector::CheckSortAsc (void) const;

Description: Check if vector is sorted in ascending sort order.

Access type: RO

Parameters:

• vector - pointer to target vector

Return value:

• TRUE (1) if elements are sorted in ascending order.
• FALSE (0) if at least one element does not conform with correct order.

Check for descending sort order

Cbool Vector_CheckSortDsc (const struct Vector *vector);

C++bool Vector::CheckSortDsc (void) const;

Description: Check if vector is sorted in descending sort order.

Access type: RO

Parameters:

• vector - pointer to target vector

Return value:

• TRUE (1) if elements are sorted in descending order.
• FALSE (0) if at least one element does not conform with correct order.

Check for duplicate values

Cbool Vector_CheckDup (const struct Vector *vector);

C++bool Vector::CheckDup (void) const;

Description: Check vector for non unique values (duplicates).

Access type: RO

Parameters:

• vector - pointer to target vector

Return value:

• TRUE (1) if duplicates were found.
• FALSE (0) if vector has no duplicated values.

Note:These functions work only with sorted vectors, regardless of sort order. To use them with regular vectors they should be sorted first.

Check for equality

Cbool Vector_IsEqual (const struct Vector *vector, const struct Vector *source);

C++bool Vector::IsEqual (const Vector *source) const;

Description: Check if both vectors have the same size, key order and key values, using provided key compare function. These functions do not compare assigned data fields, but only the keys.

Access type: RO

Parameters:

• vector - pointer to target vector
• source - pointer to source vector

Return value:

• TRUE (1) if vectors are equal.
• FALSE (0) if vectors are not equal.

Vector properties

Vector built-in key type

Csize_t Vector_KeyType (const struct Vector *vector);

C++size_t Vector::KeyType (void) const;

Description: Return built-in key type and built-in key compare function, is assigned to this type, which internally used by the vector.

Access type: RO

Parameters:

• vector - pointer to the vector

Return value: Built-in key type and corresponding built-in key compare function. Full list of such types is defined in built-in key types table.

Vector key compare function

CKeyCmp Vector_CompareFunction (const struct Vector *vector);

C++KeyCmp Vector::CompareFunction (void) const;

Description: Return pointer to key compare function is used by the vector.

Access type: RO

Parameters:

• vector - pointer to the vector

Return value: Pointer to key compare function, which conforms to this prototype.

Vector pair copy function

CCopyFunc Vector_CopyFunction (const struct Vector *vector);

C++CopyFunc Vector::CopyFunction (void) const;

Description: Return pointer to copy function for element fields: key and data, is used by the vector.

Access type: RO

Parameters:

• vector - pointer to the vector

Return value: Pointer to copy function for element fields, which conforms to this prototype.

Vector pair delete function

CDelFunc Vector_DeleteFunction (const struct Vector *vector);

C++DelFunc Vector::DeleteFunction (void) const;

Description: Return pointer to delete function to call for removing elements, which is used by the vector.

Access type: RO

Parameters:

• vector - pointer to the vector

Return value: Pointer to delete function to call for removing elements, which conforms to this prototype.

Vector user's data

Cvoid* Vector_UserData (const struct Vector *vector);

C++void* Vector::UserData (void) const;

Description: Return pointer to user's data, required by element copy and delete functions, are used by the vector.

Access type: RO

Parameters:

• vector - pointer to the vector

Return value: Pointer to user's data, required by element copy and delete functions.

Vector capacity

Csize_t Vector_Capacity (const struct Vector *vector);

C++size_t Vector::Capacity (void) const;

Description: Return the vector capacity.

Access type: RO

Parameters:

• vector - pointer to the vector

Return value: Max count of objects that vector can hold.

Vector size

Csize_t Vector_Size (const struct Vector *vector);

C++size_t Vector::Size (void) const;

Description: Return current size of the vector (count of allocated objects).

Access type: RO

Parameters:

• vector - pointer to the vector

Return value: Count of allocated objects inside the vector.

Check if vector is empty

Cbool Vector_IsEmpty (const struct Vector *vector);

C++bool Vector::IsEmpty (void) const;

Description: Check if the vector is empty.

Access type: RO

Parameters:

• vector - pointer to the vector

Return value:

• TRUE (1) if vector is empty.
• FALSE (0) if vector is not empty.

Check if vector is initialized

Cbool Vector_IsInit (const struct Vector *vector);

C++bool Vector::IsInit (void) const;

Description: Check if the vector is initialized.

Access type: RO

Parameters:

• vector - pointer to the vector

Return value:

• TRUE (1) if vector is initialized.
• FALSE (0) if vector is not initialized.