list_set.h revision 8bcbed890bc3ce4d7a057a8f32cab53fa534672e 
1// Copyright (c) 2013 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_
6#define CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_
7
8#include <algorithm>
9#include <iterator>
10#include <list>
11#include <set>
12#include "base/logging.h"
13#include "base/memory/scoped_ptr.h"
14
15//
16// A container class that provides fast containment test (like a set)
17// but maintains insertion order for iteration (like list).
18//
19// Member types of value (primitives and objects by value), raw pointers
20// and scoped_refptr<> are supported.
21//
22template <typename T>
23class list_set {
24 public:
25  list_set() {}
26  list_set(const list_set<T>& other) : list_(other.list_), set_(other.set_) {}
27  list_set& operator=(const list_set<T>& other) {
28    list_ = other.list_;
29    set_ = other.set_;
30    return *this;
31  }
32
33  void insert(const T& elem) {
34    if (set_.find(elem) != set_.end())
35      return;
36    set_.insert(elem);
37    list_.push_back(elem);
38  }
39
40  void erase(const T& elem) {
41    if (set_.find(elem) == set_.end())
42      return;
43    set_.erase(elem);
44    typename std::list<T>::iterator it =
45        std::find(list_.begin(), list_.end(), elem);
46    DCHECK(it != list_.end());
47    list_.erase(it);
48  }
49
50  size_t count(const T& elem) const {
51    return set_.find(elem) == set_.end() ? 0 : 1;
52  }
53
54  size_t size() const {
55    DCHECK_EQ(list_.size(), set_.size());
56    return set_.size();
57  }
58
59  bool empty() const {
60    DCHECK_EQ(list_.empty(), set_.empty());
61    return set_.empty();
62  }
63
64  class const_iterator;
65
66  class iterator {
67   public:
68    typedef iterator self_type;
69    typedef T value_type;
70    typedef T& reference;
71    typedef T* pointer;
72    typedef std::bidirectional_iterator_tag iterator_category;
73    typedef std::ptrdiff_t difference_type;
74
75    explicit inline iterator(typename std::list<T>::iterator it) : it_(it) {}
76    inline self_type& operator++() {
77      ++it_;
78      return *this;
79    }
80    inline self_type operator++(int /*ignored*/) {
81      self_type result(*this);
82      ++(*this);
83      return result;
84    }
85    inline self_type& operator--() {
86      --it_;
87      return *this;
88    }
89    inline self_type operator--(int /*ignored*/) {
90      self_type result(*this);
91      --(*this);
92      return result;
93    }
94    inline value_type& operator*() { return *it_; }
95    inline value_type* operator->() { return &(*it_); }
96    inline bool operator==(const iterator& rhs) const { return it_ == rhs.it_; }
97    inline bool operator!=(const iterator& rhs) const { return it_ != rhs.it_; }
98
99    inline operator const_iterator() const { return const_iterator(it_); }
100
101   private:
102    typename std::list<T>::iterator it_;
103  };
104
105  class const_iterator {
106   public:
107    typedef const_iterator self_type;
108    typedef T value_type;
109    typedef T& reference;
110    typedef T* pointer;
111    typedef std::bidirectional_iterator_tag iterator_category;
112    typedef std::ptrdiff_t difference_type;
113
114    explicit inline const_iterator(typename std::list<T>::const_iterator it)
115        : it_(it) {}
116    inline self_type& operator++() {
117      ++it_;
118      return *this;
119    }
120    inline self_type operator++(int ignored) {
121      self_type result(*this);
122      ++(*this);
123      return result;
124    }
125    inline self_type& operator--() {
126      --it_;
127      return *this;
128    }
129    inline self_type operator--(int ignored) {
130      self_type result(*this);
131      --(*this);
132      return result;
133    }
134    inline const value_type& operator*() { return *it_; }
135    inline const value_type* operator->() { return &(*it_); }
136    inline bool operator==(const const_iterator& rhs) const {
137      return it_ == rhs.it_;
138    }
139    inline bool operator!=(const const_iterator& rhs) const {
140      return it_ != rhs.it_;
141    }
142
143   private:
144    typename std::list<T>::const_iterator it_;
145  };
146
147  iterator begin() { return iterator(list_.begin()); }
148  iterator end() { return iterator(list_.end()); }
149  const_iterator begin() const { return const_iterator(list_.begin()); }
150  const_iterator end() const { return const_iterator(list_.end()); }
151
152 private:
153  std::list<T> list_;
154  std::set<T> set_;
155};
156
157// Prevent instantiation of list_set<scoped_ptr<T>> as the current
158// implementation would fail.
159// TODO(jsbell): Support scoped_ptr through specialization.
160template <typename T>
161class list_set<scoped_ptr<T> >;
162
163#endif  // CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_
164