1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135
|
#ifndef VECTORUTILS_H
#define VECTORUTILS_H
#include <vector>
// Add value into vectr[index], shifting all elements already in positions
// index..size-1 up one, to make room.
template <typename T>
void addElement (std::vector<T>& vectr, int& size, int index, T value)
{
// Make room for the insertion
int toBeMoved = vectr.size() - 1;
vectr.push_back(value);
// Shift elements up to make room
while (toBeMoved >= index) {
vectr[toBeMoved+1] = vectr[toBeMoved];
--toBeMoved;
}
// Insert the new value
vectr[index] = value;
}
// Assume the elements of the vector are already in order
// Find the position where value could be added to keep
// everything in order, and insert it there.
// Return the position where it was inserted
template <typename T>
int addInOrder (std::vector<T>& vectr, T value)
{
// Make room for the insertion
int toBeMoved = vectr.size() - 1;
vectr.push_back(value);
// Shift elements up to make room
while (toBeMoved >= 0 && value < vectr[toBeMoved]) {
vectr[toBeMoved+1] = vectr[toBeMoved];
--toBeMoved;
}
// Insert the new value
vectr[toBeMoved+1] = value;
return toBeMoved+1;
}
// Search a vector for a given value, returning the index where
// found or -1 if not found.
template <typename T>
int seqSearch(const std::vector<T>& list, T searchItem)
{
int loc;
for (loc = 0; loc < list.size(); loc++)
if (list[loc] == searchItem)
return loc;
return -1;
}
// Search an ordered vector for a given value, returning the index where
// found or -1 if not found.
template <typename T>
int seqOrderedSearch(const std::vector<T> list, T searchItem)
{
int loc = 0;
while (loc < list.size() && list[loc] < searchItem)
{
++loc;
}
if (loc < list.size() && list[loc] == searchItem)
return loc;
else
return -1;
}
// Removes an element from the indicated position in the vector, moving
// all elements in higher positions down one to fill in the gap.
template <typename T>
void removeElement (T* vectr, int& size, int index)
{
int toBeMoved = index + 1;
while (toBeMoved < size) {
vectr[toBeMoved] = vectr[toBeMoved+1];
++toBeMoved;
}
--size;
}
// Search an ordered vector for a given value, returning the index where
// found or -1 if not found.
template <typename T>
int binarySearch(const std::vector<T> list, T searchItem)
{
int first = 0;
int last = list.size() - 1;
int mid;
bool found = false;
while (first <= last && !found)
{
mid = (first + last) / 2;
if (list[mid] == searchItem)
found = true;
else
if (searchItem < list[mid])
last = mid - 1;
else
first = mid + 1;
}
if (found)
return mid;
else
return -1;
}
#endif
|