// This file is an example of a complete STL-like container.
// In particular, it demonstrates the relationship between
// the container and the iterator.
//
// Even though slink::iterator is a nested class, we define it
// separately, after class slink, to keep slink itself relatively small.

#ifndef SLINK_H_INCLUDED
#define SLINK_H_INCLUDED

#include <cassert>		// for assert
#include <cstddef>		// for size_t

template <typename T>
class slink {
    struct node {
	node(const T &what, node *follow) : datum(what), next(follow) {}
	T datum;
	struct node *next;
    };
    node *head = nullptr, *tail = nullptr;

  public:
    typedef std::size_t size_type;  // One typedef and one using,
    using value_type = T;	    //   just to be like that.

    class iterator {
	node *p;
      public:
	iterator(node *ptr) : p(ptr) { }
	iterator& operator++() {
	    assert(p);
	    p = p->next;
	    return *this;
	}
	// Postincrement is [[nodiscard]] to discourage unnecessary use.
	[[nodiscard]] iterator operator++(int) {	// Postincrement
	    const auto save = *this;
	    ++*this;			// Let preincrement do the work
	    return save;
	}
	// *iterator: Return a reference to the datum
	[[nodiscard]] T& operator*() const {
	    assert(p);
	    return p->datum;
	}
	// iterator->: Return the address of the datum
	[[nodiscard]] T* operator->() const {
	    assert(p);
	    return &p->datum;
	}
	[[nodiscard]] bool operator==(const iterator &rhs) const {
	    return p==rhs.p;
	}
	[[nodiscard]] bool operator!=(const iterator &rhs) const {
	    // return !operator==(rhs);	// 🤮
	    return !(*this == rhs);	// Let == do the work.
	}
    };

    ~slink() {
	clear();		    // easiest way to free memory
    }

    void clear() {
	while (!empty()) {
	    auto p = head->next;    // Get pointer to next node while we can.
	    delete head;
	    head = p;
	}
    }

    // An O(N) operation:
    [[nodiscard]] size_type size() const {
	size_type count=0;
	for (auto p = head; p; p=p->next)
	    count++;
	return count;
    }

    // An O(1) operation:
    [[nodiscard]] bool empty() const {
	return !head;
    }

    void push_front(const T &datum) {
	head = new node(datum, head);
	if (!tail)		    // A formerly-empty list?
	    tail = head;
    }

    void push_back(const T &datum) {
	auto p = new node(datum, nullptr);
	if (empty())		    // empty list?
	    head = p;
	else
	    tail->next = p;
	tail = p;
    }

    [[nodiscard]] iterator begin() const { return head; }
    [[nodiscard]] iterator end()   const { return nullptr; }
};
#endif /* SLINK_H_INCLUDED */