1868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Copyright (c) 2013 The Chromium Authors. All rights reserved.
2868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be
3868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// found in the LICENSE file.
4868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
5868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#ifndef CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_
6868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#define CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_
7868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
8868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include <algorithm>
9868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include <iterator>
10868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include <list>
11868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include <set>
12868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "base/logging.h"
13868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "base/memory/scoped_ptr.h"
14868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
15868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)//
16868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// A container class that provides fast containment test (like a set)
17868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// but maintains insertion order for iteration (like list).
18868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)//
19868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Member types of value (primitives and objects by value), raw pointers
20868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// and scoped_refptr<> are supported.
21868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)//
22868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)template <typename T>
23868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)class list_set {
24868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) public:
25868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  list_set() {}
26868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  list_set(const list_set<T>& other) : list_(other.list_), set_(other.set_) {}
27868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  list_set& operator=(const list_set<T>& other) {
28868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    list_ = other.list_;
29868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    set_ = other.set_;
30868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    return *this;
31868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  }
32868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
33868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  void insert(const T& elem) {
34868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    if (set_.find(elem) != set_.end())
35868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      return;
36868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    set_.insert(elem);
37868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    list_.push_back(elem);
38868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  }
39868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
40868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  void erase(const T& elem) {
41868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    if (set_.find(elem) == set_.end())
42868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      return;
43868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    set_.erase(elem);
44868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    typename std::list<T>::iterator it =
45868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)        std::find(list_.begin(), list_.end(), elem);
46868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    DCHECK(it != list_.end());
47868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    list_.erase(it);
48868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  }
49868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
508bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)  size_t count(const T& elem) const {
518bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)    return set_.find(elem) == set_.end() ? 0 : 1;
528bcbed890bc3ce4d7a057a8f32cab53fa534672eTorne (Richard Coles)  }
53868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
54868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  size_t size() const {
55868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    DCHECK_EQ(list_.size(), set_.size());
56868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    return set_.size();
57868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  }
58868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
59868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  bool empty() const {
60868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    DCHECK_EQ(list_.empty(), set_.empty());
61868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    return set_.empty();
62868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  }
63868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
64868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  class const_iterator;
65868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
66868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  class iterator {
67868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)   public:
68868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    typedef iterator self_type;
69868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    typedef T value_type;
70868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    typedef T& reference;
71868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    typedef T* pointer;
72868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    typedef std::bidirectional_iterator_tag iterator_category;
73868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    typedef std::ptrdiff_t difference_type;
74868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
75868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    explicit inline iterator(typename std::list<T>::iterator it) : it_(it) {}
76868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline self_type& operator++() {
77868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      ++it_;
78868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      return *this;
79868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    }
80868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline self_type operator++(int /*ignored*/) {
81868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      self_type result(*this);
82868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      ++(*this);
83868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      return result;
84868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    }
85868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline self_type& operator--() {
86868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      --it_;
87868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      return *this;
88868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    }
89868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline self_type operator--(int /*ignored*/) {
90868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      self_type result(*this);
91868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      --(*this);
92868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      return result;
93868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    }
94868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline value_type& operator*() { return *it_; }
95868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline value_type* operator->() { return &(*it_); }
96868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline bool operator==(const iterator& rhs) const { return it_ == rhs.it_; }
97868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline bool operator!=(const iterator& rhs) const { return it_ != rhs.it_; }
98868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
99868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline operator const_iterator() const { return const_iterator(it_); }
100868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
101868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)   private:
102868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    typename std::list<T>::iterator it_;
103868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  };
104868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
105868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  class const_iterator {
106868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)   public:
107868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    typedef const_iterator self_type;
108868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    typedef T value_type;
109868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    typedef T& reference;
110868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    typedef T* pointer;
111868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    typedef std::bidirectional_iterator_tag iterator_category;
112868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    typedef std::ptrdiff_t difference_type;
113868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
114868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    explicit inline const_iterator(typename std::list<T>::const_iterator it)
115868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)        : it_(it) {}
116868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline self_type& operator++() {
117868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      ++it_;
118868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      return *this;
119868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    }
120868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline self_type operator++(int ignored) {
121868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      self_type result(*this);
122868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      ++(*this);
123868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      return result;
124868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    }
125868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline self_type& operator--() {
126868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      --it_;
127868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      return *this;
128868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    }
129868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline self_type operator--(int ignored) {
130868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      self_type result(*this);
131868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      --(*this);
132868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      return result;
133868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    }
134868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline const value_type& operator*() { return *it_; }
135868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline const value_type* operator->() { return &(*it_); }
136868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline bool operator==(const const_iterator& rhs) const {
137868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      return it_ == rhs.it_;
138868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    }
139868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    inline bool operator!=(const const_iterator& rhs) const {
140868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)      return it_ != rhs.it_;
141868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    }
142868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
143868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)   private:
144868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)    typename std::list<T>::const_iterator it_;
145868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  };
146868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
147868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  iterator begin() { return iterator(list_.begin()); }
148868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  iterator end() { return iterator(list_.end()); }
149868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  const_iterator begin() const { return const_iterator(list_.begin()); }
150868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  const_iterator end() const { return const_iterator(list_.end()); }
151868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
152868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) private:
153868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  std::list<T> list_;
154868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)  std::set<T> set_;
155868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)};
156868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
157868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Prevent instantiation of list_set<scoped_ptr<T>> as the current
158868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// implementation would fail.
159868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// TODO(jsbell): Support scoped_ptr through specialization.
160868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)template <typename T>
161868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)class list_set<scoped_ptr<T> >;
162868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)
163868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#endif  // CONTENT_BROWSER_INDEXED_DB_LIST_SET_H_
164