Git Product home page Git Product logo

ap_exam_2021's Introduction

Advanced Programming Exam 2021-22

Deadline

The deadline for this project is January 7, 2022, at midnight.

How to submit

Fork the repository, populate the file list_pool.hpp then push on the master branch of the fork. I will not accept any other form (e.g., you send me a tar.gz). I will check just the master branch. You can write additional tests, but your code is required to be compliant to the given ones. You can run the test suite by typing make check.

A pool of blazingly fast linked lists

In this project, you must write a pool for fast linked lists. The pool stores each node in a std::vector<node_t>. The "address" of a node is 1+idx, where idx is the index where the node is stored in the vector. This trick allows us to use address 0 as end, so we can use unsigned integers type. The first node stored in the vector will be put at idx == 0, but it will be referenced as 1.

  list_pool<int, std::size_t> pool{};
  auto l = pool.new_list();
  // l == pool.end() == std::size_t(0)
  l = pool.push_front(42,l);
  // l == std::size_t(1)

The pool maintains a list of free nodes, i.e., available positions in the vector. The free_node_list is empty at the beginning.

  list_pool<int, std::size_t> pool{};
  auto l = pool.new_list();
  l = pool.push_front(10,l); // l == std::size_t(1)
  l = pool.push_front(11,l); // l == std::size_t(2) <-- later, this node will be deleted
  
  auto l2 = pool.new_list();
  l2 = pool.push_front(20,l2); // l2 == std::size_t(3)
  
  l = pool.free(l); // that node is deleted, so it is added to free_node_list
  
  l2 = pool.push_front(21,l2); // l2 == std::size_t(2)

Here is the class template (without the noexcepts, remember to use them). The following functions must be implemented, and you don't have to change the names. Of course, you are free to implement more private and public methods. Remember to write a good class for iterators to avoid code duplication for iterator and const_iterator.

template <typename T, typename N = std::size_t>
class list_pool{
  struct node_t{
    T value;
    N next;
  };
  std::vector<node_t> pool;
  using list_type = N;
  using value_type = T;
  using size_type = typename std::vector<node_t>::size_type;
  list_type free_node_list; // at the beginning, it is empty
  
  node_t& node(list_type x) noexcept { return pool[x-1]; }
  const node_t& node(list_type x) const noexcept { return pool[x-1]; }

  public:
  list_pool();
  explicit list_pool(size_type n); // reserve n nodes in the pool
    
  using iterator = ...;
  using const_iterator = ...;

  iterator begin(list_type x);
  iterator end(list_type ); // this is not a typo
    
  const_iterator begin(list_type x) const;
  const_iterator end(list_type ) const; 
  
    const_iterator cbegin(list_type x) const;
  const_iterator cend(list_type ) const;
    
  list_type new_list(); // return an empty list

  void reserve(size_type n); // reserve n nodes in the pool
  size_type capacity() const; // the capacity of the pool

  bool is_empty(list_type x) const;

  list_type end() const noexcept { return list_type(0); }

  T& value(list_type x);
  const T& value(list_type x);

  list_type& next(list_type x);
  const list_type& next(list_type x) const;

  list_type push_front(const T& val, list_type head);
  list_type push_front(T&& val, list_type head);

  list_type push_back(const T& val, list_type head);
  list_type push_back(T&& val, list_type head);
  
  list_type free(list_type x); // delete first node

  list_type free_list(list_type x); // free entire list
};

Finally, there is an example of the usage of the iterators.

#include <cassert>
#include <algorithm> max_element, min_element

list_pool<int> pool{22};
auto l1 = pool.new_list();
// credits: pi as random number generator :)
l1 = pool.push_front(3, l1);
l1 = pool.push_front(1, l1);
l1 = pool.push_front(4, l1);
l1 = pool.push_front(1, l1);
l1 = pool.push_front(5, l1);
l1 = pool.push_front(9, l1);
l1 = pool.push_front(2, l1);
l1 = pool.push_front(6, l1);
l1 = pool.push_front(5, l1);
l1 = pool.push_front(3, l1);
l1 = pool.push_front(5, l1);
    
auto l2 = pool.new_list();
l2 = pool.push_front(8, l2);
l2 = pool.push_front(9, l2);
l2 = pool.push_front(7, l2);
l2 = pool.push_front(9, l2);
l2 = pool.push_front(3, l2);
l2 = pool.push_front(1, l2);
l2 = pool.push_front(1, l2);
l2 = pool.push_front(5, l2);
l2 = pool.push_front(9, l2);
l2 = pool.push_front(9, l2);
l2 = pool.push_front(7, l2);

auto M = std::max_element(pool.begin(l1), pool.end(l1));
assert(*M == 9);

auto m = std::min_element(pool.begin(l2), pool.end(l2));
assert(*m == 1);

ap_exam_2021's People

Contributors

asartori86 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.