The rebalance function is rebalancing incorrectly so the pop back function cant pop the correct value off

61 Views Asked by At

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);
        }
    }
}
0

There are 0 best solutions below