61: Simple Templates

In this we make a tiny Double Linked List, but we write an automated test for it to get into how testing works. Next exercise we'll also recreate fuc2 to learn more about how testing works.

The main purpose of this exercise though is to understand the basics of template and how it's used in creating generic data structures.

The Code

This is the simple double linked list (dlist) implemented with a template. It's done in an old-school style with individual nodes and lots of pointers.

View Source file ex61_dlist.hpp Only

#include <functional>

void my_assert(bool test, const std::string& message) {
  if(!test) throw std::runtime_error(message);
}

template<typename T>
struct DListNode {
  T data;
  DListNode<T> *next = nullptr;
  DListNode<T> *prev = nullptr;
};

template<typename T>
class DList {
  DListNode<T> *head = nullptr;
  DListNode<T> *tail = nullptr;

public:
  DListNode<T>* first() {
    return head;
  }

  DListNode<T>* last() {
    return tail;
  }

  void push_back(const T& data) {
    auto* temp = new DListNode<T>{.data = data};

    if(tail == nullptr) {
      // empty list
      head = temp;
      tail = temp;
    } else {
      // has elements
      tail->next = temp;
      temp->prev = tail;
      tail = temp;
    }
  }

  void push_front(const T& data) {
    auto* temp = new DListNode<T>{.data = data};

    if(head == nullptr) {
      // empty list
      head = temp;
      tail = temp;
    } else {
      // has elements
      head->prev = temp;
      temp->next = head;
      head = temp;
    }
  }

  T pop_front() {
    my_assert(head != nullptr, "empty list!");

    auto result = head->data;

    if(head->next == nullptr) {
      // one
      delete head;
      head = nullptr;
      tail = nullptr;
    } else {
      // many, shuffle head down
      head = head->next; // move down one
      delete head->prev; // delete the old head
      head->prev = nullptr; // close it off
    }

    return result;
  }

  T pop_back() {
    // zero, abort
    my_assert(tail != nullptr, "empty list!");

    // has either one or many, aways return result
    auto result = tail->data;

    // different operation for one vs many
    if(tail->prev == nullptr) {
      // one, delete tail and clear head/tail
      delete tail;
      head = nullptr;
      tail = nullptr;
    } else {
      // many, shuffle tail around
      tail = tail->prev; // move back one
      delete tail->next; // delete old tail
      tail->next = nullptr; // close it off
    }

    return result;
  }

  void for_each(std::function<void(const T&)> cb) {
    for(auto* cur = head; cur != nullptr; cur = cur->next) {
      cb(cur->data);
    }
  }

  int count() {
    int res = 0;

    for_each([&](const auto& val) { res++; });

    return res;
  }
};

Then the ex61.cpp file is a test using fuc2 that tests the DList. I may do it where they get the test and have to make the DList but I could also go the other way.

View Source file ex61.cpp Only

#include <fmt/core.h>
#include <chrono>
#include <thread>
#include <string>
#include <cassert>
#include <functional>
#include <fuc2/testing.hpp>
#include <fuc2/run.hpp>
#include "ex61_dlist.hpp"

using namespace fuc2;

void test_push_pop_back() {
  DList<int> ages;

  for(int i = 0; i < 5; i++) {
    ages.push_back(i * 34);
  }

  CHECK(ages.count() == 5, "wrong count");

  for(int i = 0; i < 5; i++) {
    auto res = ages.pop_back();
    fmt::println("pop_back: {}, count: {}", res, ages.count());
  }

  EQUAL(ages.count(), 0, "wrong count");
  NOT_EQUAL(ages.count(), 5, "wrong count");
}

void test_push_pop_front() {
  DList<float> ages;

  for(int i = 0; i < 5; i++) {
    ages.push_front(i * 34);
  }

  CHECK(ages.count() == 5, "should have 5");

  for(int i = 0; i < 5; i++) {
    auto res = ages.pop_front();
    fmt::println("pop_front: {}, count: {}", res, ages.count());
  }

  EQUAL(ages.count(), 0, "should be empty");
}

void test_push_blows_up() {
  DList<float> ages;

  auto runner = [&]() {
      ages.pop_front();
  };

  BLOWS_UP(runner, "pop_front empty should crash");
}

int main(int argc, char* argv[]) {
  return run({
    .name="DList basic operations",
    .options={ .fail_fast=false },
    .tests={
      TEST(test_push_pop_back),
      TEST(test_push_pop_front),
      TEST(test_push_blows_up),
    }
  }, {}, false);
}

The Breakdown

line of code

Description.

The Discussion

Blah blah.

Further Study

• Do this next.