content/browser/indexed_db/list_set.h

// Copyright (c) 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_
#define CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_

#include <algorithm>
#include <iterator>
#include <list>
#include <set>
#include "base/logging.h"
#include "base/memory/scoped_ptr.h"

//
// A container class that provides fast containment test (like a set)
// but maintains insertion order for iteration (like list).
//
// Member types of value (primitives and objects by value), raw pointers
// and scoped_refptr<> are supported.
//
template <typename T>
class list_set {
 public:
  list_set() {}
  list_set(const list_set<T>& other) : list_(other.list_), set_(other.set_) {}
  list_set& operator=(const list_set<T>& other) {
    list_ = other.list_;
    set_ = other.set_;
    return *this;
  }

  void insert(const T& elem) {
    if (set_.find(elem) != set_.end())
      return;
    set_.insert(elem);
    list_.push_back(elem);
  }

  void erase(const T& elem) {
    if (set_.find(elem) == set_.end())
      return;
    set_.erase(elem);
    typename std::list<T>::iterator it =
        std::find(list_.begin(), list_.end(), elem);
    DCHECK(it != list_.end());
    list_.erase(it);
  }

  size_t count(const T& elem) const {
    return set_.find(elem) == set_.end() ? 0 : 1;
  }

  size_t size() const {
    DCHECK_EQ(list_.size(), set_.size());
    return set_.size();
  }

  bool empty() const {
    DCHECK_EQ(list_.empty(), set_.empty());
    return set_.empty();
  }

  class const_iterator;

  class iterator {
   public:
    typedef iterator self_type;
    typedef T value_type;
    typedef T& reference;
    typedef T* pointer;
    typedef std::bidirectional_iterator_tag iterator_category;
    typedef std::ptrdiff_t difference_type;

    explicit inline iterator(typename std::list<T>::iterator it) : it_(it) {}
    inline self_type& operator++() {
      ++it_;
      return *this;
    }
    inline self_type operator++(int /*ignored*/) {
      self_type result(*this);
      ++(*this);
      return result;
    }
    inline self_type& operator--() {
      --it_;
      return *this;
    }
    inline self_type operator--(int /*ignored*/) {
      self_type result(*this);
      --(*this);
      return result;
    }
    inline value_type& operator*() { return *it_; }
    inline value_type* operator->() { return &(*it_); }
    inline bool operator==(const iterator& rhs) const { return it_ == rhs.it_; }
    inline bool operator!=(const iterator& rhs) const { return it_ != rhs.it_; }

    inline operator const_iterator() const { return const_iterator(it_); }

   private:
    typename std::list<T>::iterator it_;
  };

  class const_iterator {
   public:
    typedef const_iterator self_type;
    typedef T value_type;
    typedef T& reference;
    typedef T* pointer;
    typedef std::bidirectional_iterator_tag iterator_category;
    typedef std::ptrdiff_t difference_type;

    explicit inline const_iterator(typename std::list<T>::const_iterator it)
        : it_(it) {}
    inline self_type& operator++() {
      ++it_;
      return *this;
    }
    inline self_type operator++(int ignored) {
      self_type result(*this);
      ++(*this);
      return result;
    }
    inline self_type& operator--() {
      --it_;
      return *this;
    }
    inline self_type operator--(int ignored) {
      self_type result(*this);
      --(*this);
      return result;
    }
    inline const value_type& operator*() { return *it_; }
    inline const value_type* operator->() { return &(*it_); }
    inline bool operator==(const const_iterator& rhs) const {
      return it_ == rhs.it_;
    }
    inline bool operator!=(const const_iterator& rhs) const {
      return it_ != rhs.it_;
    }

   private:
    typename std::list<T>::const_iterator it_;
  };

  iterator begin() { return iterator(list_.begin()); }
  iterator end() { return iterator(list_.end()); }
  const_iterator begin() const { return const_iterator(list_.begin()); }
  const_iterator end() const { return const_iterator(list_.end()); }

 private:
  std::list<T> list_;
  std::set<T> set_;
};

// Prevent instantiation of list_set<scoped_ptr<T>> as the current
// implementation would fail.
// TODO(jsbell): Support scoped_ptr through specialization.
template <typename T>
class list_set<scoped_ptr<T> >;

#endif  // CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_