I created a pop_back function and rebalancing for this deque I am making, but when it rebalances, I wanted it to become a b c after the 3rd pop back so that the c can be popped off, therefore, passing the test case.
Would this be a rebalance issue or a pop back issue as my rebalance is working and passing previous test cases (any advice appreciated)?
Front: a Back: e
c b a d
Deque size after pop_back: 4
Front: a Back: d
c b a
Deque size after pop_back: 3
Front: a Back: c
a c b
Deque size after pop_back: 3
Front: a Back: b
a c
Deque size after pop_back: 2
Front: a Back: c
main.cpp:167: Failure
Expected equality of these values:
deque.back()
Which is: 'c' (99, 0x63)
'a'
Which is: 'a' (97, 0x61)
a
TEST(MyDequeTest, PopBackAndBackChar) {
MyDeque<char> deque {'a', 'b', 'c', 'd', 'e'};
EXPECT_EQ(deque.back(), 'e');
deque.pop_back();
EXPECT_EQ(deque.back(), 'd');
deque.pop_back();
EXPECT_EQ(deque.back(), 'c');
deque.pop_back();
EXPECT_EQ(deque.back(), 'b');
deque.pop_back();
EXPECT_EQ(deque.back(), 'a');
deque.pop_back();
EXPECT_TRUE(deque.empty());
}
my pop back function is looking like this
template <typename T>
void MyDeque<T>::pop_back() {
if (backVector.empty()) {
if (frontVector.size() > 1) {
rebalance(true);
backVector.swap(frontVector);
} else if (frontVector.size() == 1) {
frontVector.pop_back();
}
} else {
backVector.pop_back();
}
rebalance(false);
and my rebalance function is looking like this
template <typename T>
void MyDeque<T>::rebalance(bool front) {
if (front) {
// Rebalance frontVector
while (frontVector.size() > (backVector.size() + 1)) {
// Move an element from frontVector to backVector
T temp = frontVector.back();
frontVector.pop_back();
// Find the correct position to insert the element in backVector
typename std::vector<T>::iterator it = backVector.begin();
while (it != backVector.end() && *it < temp) {
++it;
}
// Insert the element at the correct position in backVector
backVector.insert(it, temp);
}
} else {
// Rebalance backVector
while (backVector.size() > (frontVector.size() + 1)) {
// Move an element from backVector to frontVector
T temp = backVector.front();
backVector.erase(backVector.begin());
// Find the correct position to insert the element in frontVector
typename std::vector<T>::reverse_iterator rit = frontVector.rbegin();
while (rit != frontVector.rend() && *rit > temp) {
++rit;
}
// Insert the element at the correct position in frontVector
frontVector.insert(rit.base(), temp);
}
}
}