UML Diagram: Class Attributes: Node: A private, embedded struct. Members: value

Question

UML Diagram:

Class Attributes:

Node:

A private, embedded struct.

Members:

value - stores the integer being stored in the MyVector object.

next - stores the memory address of the next node of the linked list.

Variables:

head - a Node pointer that stores the memory address of the first node in the linked list.

tail - a Node pointer that stores the memory address of the last node in the linked list.

Methods:

constructor - initializes head and tail to nullptr.

destructor - frees all memory used by the list.

push_back - Creates a new node, stores it's argument in the node, and appends it to the list.

pop_back - if the list isn't empty (head == nullptr), removes the last node from memory. Throws an exception otherwise. The exception is a c-string: "EMPTY VECTOR".

at - uses it's argument as a subscript for the MyVector. Returns the value from that corresponding node. It's return type is an integer reference (int&). Throws an exception if the argument is an invalid index. The exception is a c-string: "OUT OF BOUNDS". If the MyVector object is empty, throws "EMPTY VECTOR" exception.

clear - removes all nodes from memory, and sets head and tail back to nullptr.

size - counts and returns the number of nodes in the list.

insert - inserts new value i before position pos in the MyVector list. So, if the list contained the values :
8 6 7
and the method was invoked as:
v.insert(2, 9)
then the list would be updated to:
8 6 9 7
Throws an exception "OUT OF BOUNDS" if an invalid position is specified.

None of the above methods interacts with the user in any way. You are not writing a program, just a class in it's own header file.

Place the class declaration in it's own header file named MyVector.h. Place the method definitions in it's own file named MyVector.cpp.

MyVector Node value: int next Node -head: Node -tail: Node* +MyVector): +-MyVector): +push_back(i: int): void +pop_back(): void +at(i: int): int& +clear: void +size(): int tinsert (pos: int, i: int): void

Explanation / Answer

MyVector.h

#ifndef __COMMON_VECTOR_H
#define __COMMON_VECTOR_H

#include "Defs.h"

class CBaseRecordVector
{
void MoveItems(int destIndex, int srcIndex);
protected:
int _capacity;
int _size;
void *_items;
size_t _itemSize;
  
void ReserveOnePosition();
void InsertOneItem(int index);
void TestIndexAndCorrectNum(int index, int &num) const
{ if (index + num > _size) num = _size - index; }
public:
CBaseRecordVector(size_t itemSize): _capacity(0), _size(0), _items(0), _itemSize(itemSize) {}
virtual ~CBaseRecordVector();
void ClearAndFree();
int Size() const { return _size; }
bool IsEmpty() const { return (_size == 0); }
void Reserve(int newCapacity);
void ReserveDown();
virtual void Delete(int index, int num = 1);
void Clear();
void DeleteFrom(int index);
void DeleteBack();
};

template <class T>
class CRecordVector: public CBaseRecordVector
{
public:
CRecordVector(): CBaseRecordVector(sizeof(T)){};
CRecordVector(const CRecordVector &v): CBaseRecordVector(sizeof(T)) { *this = v; }
CRecordVector& operator=(const CRecordVector &v)
{
Clear();
return (*this += v);
}
CRecordVector& operator+=(const CRecordVector &v)
{
int size = v.Size();
Reserve(Size() + size);
for (int i = 0; i < size; i++)
Add(v[i]);
return *this;
}
int Add(T item)
{
ReserveOnePosition();
((T *)_items)[_size] = item;
return _size++;
}
void Insert(int index, T item)
{
InsertOneItem(index);
((T *)_items)[index] = item;
}
// T* GetPointer() const { return (T*)_items; }
// operator const T *() const { return _items; };
const T& operator[](int index) const { return ((T *)_items)[index]; }
T& operator[](int index) { return ((T *)_items)[index]; }
const T& Front() const { return operator[](0); }
T& Front() { return operator[](0); }
const T& Back() const { return operator[](_size - 1); }
T& Back() { return operator[](_size - 1); }

void Swap(int i, int j)
{
T temp = operator[](i);
operator[](i) = operator[](j);
operator[](j) = temp;
}

int FindInSorted(const T& item, int left, int right) const
{
while (left != right)
{
int mid = (left + right) / 2;
const T& midValue = (*this)[mid];
if (item == midValue)
return mid;
if (item < midValue)
right = mid;
else
left = mid + 1;
}
return -1;
}

int FindInSorted(const T& item) const
{
int left = 0, right = Size();
while (left != right)
{
int mid = (left + right) / 2;
const T& midValue = (*this)[mid];
if (item == midValue)
return mid;
if (item < midValue)
right = mid;
else
left = mid + 1;
}
return -1;
}

int AddToUniqueSorted(const T& item)
{
int left = 0, right = Size();
while (left != right)
{
int mid = (left + right) / 2;
const T& midValue = (*this)[mid];
if (item == midValue)
return mid;
if (item < midValue)
right = mid;
else
left = mid + 1;
}
Insert(right, item);
return right;
}

static void SortRefDown(T* p, int k, int size, int (*compare)(const T*, const T*, void *), void *param)
{
T temp = p[k];
for (;;)
{
int s = (k << 1);
if (s > size)
break;
if (s < size && compare(p + s + 1, p + s, param) > 0)
s++;
if (compare(&temp, p + s, param) >= 0)
break;
p[k] = p[s];
k = s;
}
p[k] = temp;
}

void Sort(int (*compare)(const T*, const T*, void *), void *param)
{
int size = _size;
if (size <= 1)
return;
T* p = (&Front()) - 1;
{
int i = size / 2;
do
SortRefDown(p, i, size, compare, param);
while (--i != 0);
}
do
{
T temp = p[size];
p[size--] = p[1];
p[1] = temp;
SortRefDown(p, 1, size, compare, param);
}
while (size > 1);
}
};

typedef CRecordVector<int> CIntVector;
typedef CRecordVector<unsigned int> CUIntVector;
typedef CRecordVector<bool> CBoolVector;
typedef CRecordVector<unsigned char> CByteVector;
typedef CRecordVector<void *> CPointerVector;

template <class T>
class CObjectVector: public CPointerVector
{
public:
CObjectVector() {};
~CObjectVector() { Clear(); };
CObjectVector(const CObjectVector &v): CPointerVector() { *this = v; }
CObjectVector& operator=(const CObjectVector &v)
{
Clear();
return (*this += v);
}
CObjectVector& operator+=(const CObjectVector &v)
{
int size = v.Size();
Reserve(Size() + size);
for (int i = 0; i < size; i++)
Add(v[i]);
return *this;
}
const T& operator[](int index) const { return *((T *)CPointerVector::operator[](index)); }
T& operator[](int index) { return *((T *)CPointerVector::operator[](index)); }
T& Front() { return operator[](0); }
const T& Front() const { return operator[](0); }
T& Back() { return operator[](_size - 1); }
const T& Back() const { return operator[](_size - 1); }
int Add(const T& item) { return CPointerVector::Add(new T(item)); }
void Insert(int index, const T& item) { CPointerVector::Insert(index, new T(item)); }
virtual void Delete(int index, int num = 1)
{
TestIndexAndCorrectNum(index, num);
for (int i = 0; i < num; i++)
delete (T *)(((void **)_items)[index + i]);
CPointerVector::Delete(index, num);
}
int Find(const T& item) const
{
for (int i = 0; i < Size(); i++)
if (item == (*this)[i])
return i;
return -1;
}
int FindInSorted(const T& item) const
{
int left = 0, right = Size();
while (left != right)
{
int mid = (left + right) / 2;
const T& midValue = (*this)[mid];
if (item == midValue)
return mid;
if (item < midValue)
right = mid;
else
left = mid + 1;
}
return -1;
}
int AddToSorted(const T& item)
{
int left = 0, right = Size();
while (left != right)
{
int mid = (left + right) / 2;
const T& midValue = (*this)[mid];
if (item == midValue)
{
right = mid + 1;
break;
}
if (item < midValue)
right = mid;
else
left = mid + 1;
}
Insert(right, item);
return right;
}

void Sort(int (*compare)(void *const *, void *const *, void *), void *param)
{ CPointerVector::Sort(compare, param); }

static int CompareObjectItems(void *const *a1, void *const *a2, void * /* param */)
{ return MyCompare(*(*((const T **)a1)), *(*((const T **)a2))); }
void Sort() { CPointerVector::Sort(CompareObjectItems, 0); }
};

#endif

MyVector.cpp

#include "StdAfx.h"

#include <string.h>

#include "MyVector.h"

CBaseRecordVector::~CBaseRecordVector() { ClearAndFree(); }

void CBaseRecordVector::ClearAndFree()
{
Clear();
delete []((unsigned char *)_items);
_capacity = 0;
_size = 0;
_items = 0;
}

void CBaseRecordVector::Clear() { DeleteFrom(0); }
void CBaseRecordVector::DeleteBack() { Delete(_size - 1); }
void CBaseRecordVector::DeleteFrom(int index) { Delete(index, _size - index); }

void CBaseRecordVector::ReserveOnePosition()
{
if (_size != _capacity)
return;
unsigned delta = 1;
if (_capacity >= 64)
delta = (unsigned)_capacity / 4;
else if (_capacity >= 8)
delta = 8;
Reserve(_capacity + (int)delta);
}

void CBaseRecordVector::Reserve(int newCapacity)
{
// if (newCapacity <= _capacity)
if (newCapacity == _capacity)
return;
if ((unsigned)newCapacity >= ((unsigned)1 << (sizeof(unsigned) * 8 - 1)))
throw 1052353;
size_t newSize = (size_t)(unsigned)newCapacity * _itemSize;
if (newSize / _itemSize != (size_t)(unsigned)newCapacity)
throw 1052354;
unsigned char *p = NULL;
if (newSize > 0)
{
p = new unsigned char[newSize];
if (p == 0)
throw 1052355;
int numRecordsToMove = (_size < newCapacity ? _size : newCapacity);
memcpy(p, _items, _itemSize * numRecordsToMove);
}
delete [](unsigned char *)_items;
_items = p;
_capacity = newCapacity;
}

void CBaseRecordVector::ReserveDown()
{
Reserve(_size);
}

void CBaseRecordVector::MoveItems(int destIndex, int srcIndex)
{
memmove(((unsigned char *)_items) + destIndex * _itemSize,
((unsigned char *)_items) + srcIndex * _itemSize,
_itemSize * (_size - srcIndex));
}

void CBaseRecordVector::InsertOneItem(int index)
{
ReserveOnePosition();
MoveItems(index + 1, index);
_size++;
}

void CBaseRecordVector::Delete(int index, int num)
{
TestIndexAndCorrectNum(index, num);
if (num > 0)
{
MoveItems(index, index + num);
_size -= num;
}
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.