SmallList.h

Go to the documentation of this file.

#ifndef SmallList_HEADER
#define SmallList_HEADER

#ifdef HAVE_CONFIG_H
# include <config.h>
#endif

#include "SmallMemoryPool.h"
#include <boost/iterator/iterator_facade.hpp>

namespace hudson {

  template <class Item> class SmallList 
    : public SmallMemoryItem< SmallList<Item> > {
    struct Node : public SmallMemoryItem<Node> {
      Item item_;
      Node *next_;

      Node(Node *next): item_(), next_(next) { }

      template <class ItemCtorArg>
      Node(const ItemCtorArg& arg, Node *next): item_(arg), next_(next) { }
    };

    Node *head_;

    public:
    typedef Item                value_type;
    typedef Item&               reference;
    typedef const Item&         const_reference;

    SmallList() { head_ = NULL; }
    ~SmallList() { clear(); }

    private:
    void assumed_cleared_copy(const SmallList& other) {
      if (other.empty()) {
        head_ = NULL;
        return;
      }
      Node *tail = new Node(other.head_->item_, NULL);
      head_ = tail;
      for(const_iterator it = ++other.begin(); it != other.end(); ++it) {
        Node *newtail = new Node(*it, NULL);
        tail->next_ = newtail;
        tail = newtail;
      }
    }

    public:
    SmallList(const SmallList& other) {
      assumed_cleared_copy(other);
    }

    SmallList& operator = (const SmallList& other) {
      clear();
      assumed_cleared_copy(other);
    }

    bool empty() const { return head_ == NULL; }

    void clear() {
      Node *cur = head_;
      while (cur) {
        Node *next = cur->next_;
        delete cur;
        cur = next;
      }
      head_ = NULL;
    }

    template <class ItemCtorArg>
    void push_front(const ItemCtorArg& arg) {
      Node *n = new Node(arg, head_);
      head_ = n;
    }
    void push_front() {
      Node *n = new Node(head_);
      head_ = n;
    }

    void pop_front() {
      assert(head_);
      Node *next = head_->next_;
      delete head_;
      head_ = next;
    }

    const Item& front() const { assert(head_); return head_->item_; }
    Item& front() { assert(head_); return head_->item_; }

    class iterator;
    class const_iterator;

    class iterator : public boost::iterator_facade
                                < iterator
                                , Item
                                , boost::forward_traversal_tag >
    {
      Node *prev_;
      Node *cur_;
      friend class SmallList;
      friend class const_iterator; 

      public:
      explicit iterator(Node *p, Node *c): prev_(p), cur_(c) { }
      void increment() { prev_ = cur_; cur_ = cur_->next_; }
      bool equal(const iterator& other) const { return cur_ == other.cur_; }
      Item& dereference() const { return cur_->item_; }
    };

    iterator begin() { return iterator(NULL, head_); }
    iterator end() { return iterator(NULL, NULL); }

    private:
    iterator insertNode(iterator it, Node *n) {
      if (it.prev_) {
        it.prev_->next_ = n;
      } else {
        if (it.cur_ != NULL || empty()) {
          head_ = n;
        } else {
          // we're doing insert(end()); linear-time search
          it = begin();
          while (it.cur_) { ++it; }
          assert(it.prev_);
          it.prev_->next_ = n;
        }
      }
      return iterator(it.prev_, n);
    }
    public:

    template <class ItemCtorArg>
    iterator insert(iterator it, const ItemCtorArg& arg) {
      Node *n = new Node(arg, it.cur_);
      return insertNode(it, n);
    }

    iterator insert(iterator it) {
      Node *n = new Node(it.cur_);
      return insertNode(it, n);
    }

    iterator erase(iterator it) {
      Node *next = it.cur_->next_;
      assert(it.cur_);
      if (it.prev_) {
        it.prev_->next_ = next;
      } else {
        head_ = next;
      }
      delete it.cur_;
      return iterator(it.prev_, next);
    }


    class const_iterator : public boost::iterator_facade
                                < const_iterator
                                , Item
                                , boost::forward_traversal_tag >
    {
      Node *cur_;
      public:
      explicit const_iterator(Node *head): cur_(head) { }
      const_iterator(iterator it): cur_(it.cur_) { }
      void increment() { cur_ = cur_->next_; }
      bool equal(const const_iterator& other) const { return cur_ == other.cur_; }
      Item& dereference() const { return cur_->item_; }
    };

    const_iterator begin() const { return const_iterator(head_); }
    const_iterator end() const { return const_iterator(NULL); }


    void swap(SmallList& other) {
      Node *temp = head_;
      head_ = other.head_;
      other.head_ = temp;
    }

    void reverse() {
      Node *cur = head_;
      Node *prev = NULL;
      while(cur) {
        Node *next = cur->next_;
        cur->next_ = prev;
        prev = cur;
        cur = next;
      }
      head_ = prev;
    }

    void merge(SmallList& other) {
      if (empty()) {
        swap(other);
        return;
      }

      iterator here = begin();
      Node *there = other.head_;
      while (there) {
        while(*here < there->item_) {
          ++here;
        }
        Node *nextthere = there->next_;
        there->next_ = here.cur_;
        here = insertNode(here, there);
        there = nextthere;
      }
      other.head_ = 0;
    }

    void unique() {
      if (empty()) { return; }

      iterator here = ++begin();
      while (here != end()) {
        if (here.prev_->item_ == here.cur_->item_) {
          /* here = erase(here) -- but faster because we aren't at the head */
          Node *next = here.cur_->next_;
          delete here.cur_;
          here.cur_ = next;
          here.prev_->next_ = next;
        } else {
          ++here;
        }
      }
    }


  };
}

#endif

---