list_set.h revision 868fa2fe829687343ffae624259930155e16dbd8 
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  bool has(const T& elem) { return set_.find(elem) != set_.end(); }
51
52  size_t size() const {
53    DCHECK_EQ(list_.size(), set_.size());
54    return set_.size();
55  }
56
57  bool empty() const {
58    DCHECK_EQ(list_.empty(), set_.empty());
59    return set_.empty();
60  }
61
62  class const_iterator;
63
64  class iterator {
65   public:
66    typedef iterator self_type;
67    typedef T value_type;
68    typedef T& reference;
69    typedef T* pointer;
70    typedef std::bidirectional_iterator_tag iterator_category;
71    typedef std::ptrdiff_t difference_type;
72
73    explicit inline iterator(typename std::list<T>::iterator it) : it_(it) {}
74    inline self_type& operator++() {
75      ++it_;
76      return *this;
77    }
78    inline self_type operator++(int /*ignored*/) {
79      self_type result(*this);
80      ++(*this);
81      return result;
82    }
83    inline self_type& operator--() {
84      --it_;
85      return *this;
86    }
87    inline self_type operator--(int /*ignored*/) {
88      self_type result(*this);
89      --(*this);
90      return result;
91    }
92    inline value_type& operator*() { return *it_; }
93    inline value_type* operator->() { return &(*it_); }
94    inline bool operator==(const iterator& rhs) const { return it_ == rhs.it_; }
95    inline bool operator!=(const iterator& rhs) const { return it_ != rhs.it_; }
96
97    inline operator const_iterator() const { return const_iterator(it_); }
98
99   private:
100    typename std::list<T>::iterator it_;
101  };
102
103  class const_iterator {
104   public:
105    typedef const_iterator self_type;
106    typedef T value_type;
107    typedef T& reference;
108    typedef T* pointer;
109    typedef std::bidirectional_iterator_tag iterator_category;
110    typedef std::ptrdiff_t difference_type;
111
112    explicit inline const_iterator(typename std::list<T>::const_iterator it)
113        : it_(it) {}
114    inline self_type& operator++() {
115      ++it_;
116      return *this;
117    }
118    inline self_type operator++(int ignored) {
119      self_type result(*this);
120      ++(*this);
121      return result;
122    }
123    inline self_type& operator--() {
124      --it_;
125      return *this;
126    }
127    inline self_type operator--(int ignored) {
128      self_type result(*this);
129      --(*this);
130      return result;
131    }
132    inline const value_type& operator*() { return *it_; }
133    inline const value_type* operator->() { return &(*it_); }
134    inline bool operator==(const const_iterator& rhs) const {
135      return it_ == rhs.it_;
136    }
137    inline bool operator!=(const const_iterator& rhs) const {
138      return it_ != rhs.it_;
139    }
140
141   private:
142    typename std::list<T>::const_iterator it_;
143  };
144
145  iterator begin() { return iterator(list_.begin()); }
146  iterator end() { return iterator(list_.end()); }
147  const_iterator begin() const { return const_iterator(list_.begin()); }
148  const_iterator end() const { return const_iterator(list_.end()); }
149
150 private:
151  std::list<T> list_;
152  std::set<T> set_;
153};
154
155// Prevent instantiation of list_set<scoped_ptr<T>> as the current
156// implementation would fail.
157// TODO(jsbell): Support scoped_ptr through specialization.
158template <typename T>
159class list_set<scoped_ptr<T> >;
160
161#endif  // CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_
162