// -*- mode: c++; c-basic-offset: 2; -*-

#ifndef OBSERVERS_HH
#define OBSERVERS_HH

template<typename T>
class Observers {
private:
  struct Entry {
    T const item_;
    unsigned int ref_;
    bool deleted_;
    Entry* next_;

    Entry(T const& item, Entry* next)
      : item_(item), ref_(0), deleted_(false), next_(next) {
    }
  };

public:
  class Iterator {
  public:
    Iterator(Observers* observers)
      : observers_(observers), cur_(nullptr) {
    }
    Iterator(Iterator const& iter)
      : observers_(iter.observers_), cur_(iter.cur_) {
      if (cur_) observers_->ref(cur_);
    }
    ~Iterator() {
      if (cur_) observers_->unref(cur_);
    }

    Iterator& operator=(Iterator const& iter) {
      if (cur_) observers_->unref(cur_);
      observers_ = iter.observers_;
      cur_ = iter.cur_;
      if (cur_) observers_->ref(cur_);
      return *this;
    }

    bool operator==(Iterator const& iter) const {
      return observers_ == iter.observers_ && cur_ == iter.cur_;
    }
    bool operator!=(Iterator const& iter) const {
      return observers_ != iter.observers_ || cur_ != iter.cur_;
    }

    bool has_next() const {
      auto n = cur_ ? cur_->next_ : observers_->first_;
      while (n && n->deleted_) n = n->next_;
      return n;
    }

    T const& next() {
      if (cur_) {
        assert(cur_->next_);
        auto last = cur_;
        cur_ = cur_->next_;
        observers_->unref(last);
      } else {
        assert(observers_->first_);
        cur_ = observers_->first_;
      }
      while (cur_ && cur_->deleted_) cur_ = cur_->next_;
      assert(cur_);
      observers_->ref(cur_);
      return cur_->item_;
    }

  private:
    Observers* observers_;
    Entry* cur_;
  };

  Observers()
    : first_(nullptr) {
  }

  ~Observers() {
    auto c = first_;
    while (c) {
      auto n = c->next_;
      delete c;
      c = n;
    }
  }

  void insert(T const& item) {
    first_ = new Entry(item, first_);
  }

  void erase(T const& item) {
    if (!first_) return;
    auto c = first_;
    if (c->item_ == item) {
      if (c->ref_ == 0) {
        first_ = c->next_;
        delete c;
      } else {
        c->deleted_ = true;
      }
      return;
    }
    while (c->next_) {
      if (c->next_->item_ == item) {
        if (c->next_->ref_ == 0) {
          auto del = c->next_;
          c->next_ = del->next_;
          delete del;
        } else {
          c->next_->deleted_ = true;
        }
        return;
      }
      c = c->next_;
    }
  }

  Iterator notify() {
    return Iterator(this);
  }

private:
  void ref(Entry* entry) {
    assert(entry->ref_ > 0 || !entry->deleted_);
    entry->ref_++;
  }

  void unref(Entry* entry) {
    assert(entry->ref_ > 0);
    if (--entry->ref_ == 0 && entry->deleted_) {
      if (entry == first_) {
        first_ = entry->next_;
      } else {
        auto c = first_;
        while (c->next_ != entry) c = c->next_;
        c->next_ = entry->next_;
      }
      delete entry;
    }
  }

  Entry* first_;
};

#endif  // OBSERVERS_HH