ProteoWizard
mru_list.hpp
Go to the documentation of this file.
1/* $Id$
2 *
3 * Boost.MultiIndex example of serialization of a MRU list.
4 *
5 * Copyright 2003-2008 Joaquin M Lopez Munoz.
6 * Distributed under the Boost Software License, Version 1.0.
7 * (See accompanying file LICENSE_1_0.txt or copy at
8 * http://www.boost.org/LICENSE_1_0.txt)
9 *
10 * See http://www.boost.org/libs/multi_index for library home page.
11 */
12
13#ifndef _MRU_LIST_HPP_
14#define _MRU_LIST_HPP_
15
16
17#if !defined(NDEBUG)
18#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
19#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
20#endif
21
22
23#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
24#include <algorithm>
25#include <boost/multi_index_container.hpp>
26#include <boost/multi_index/hashed_index.hpp>
27#include <boost/multi_index/identity.hpp>
28#include <boost/multi_index/member.hpp>
29#include <boost/multi_index/mem_fun.hpp>
30#include <boost/multi_index/sequenced_index.hpp>
31#include <fstream>
32#include <iostream>
33#include <iterator>
34#include <sstream>
35#include <string>
36
37
38namespace pwiz {
39namespace util {
40
41
42/* An MRU (most recently used) list keeps record of the last n
43 * inserted items, listing first the newer ones. Care has to be
44 * taken when a duplicate item is inserted: instead of letting it
45 * appear twice, the MRU list relocates it to the first position.
46 */
47
48template <typename Item, typename KeyExtractor = boost::multi_index::identity<Item> >
50{
51 typedef boost::multi_index::multi_index_container
52 <
53 Item,
54 boost::multi_index::indexed_by
55 <
56 boost::multi_index::sequenced<>,
57 boost::multi_index::hashed_unique<KeyExtractor>
58 >
60
61public:
62 typedef Item item_type;
63 typedef typename item_list::iterator iterator;
64 typedef typename item_list::reverse_iterator reverse_iterator;
65 typedef typename item_list::const_iterator const_iterator;
66 typedef typename item_list::const_reverse_iterator const_reverse_iterator;
67 typedef typename item_list::value_type value_type;
68
69 mru_list(std::size_t max_num_items_) : max_num_items(max_num_items_){}
70
71 bool insert(const item_type& item)
72 {
73 std::pair<iterator,bool> p=il.push_front(item);
74
75 if(!p.second){ /* duplicate item */
76 il.relocate(il.begin(),p.first); /* put in front */
77 return false; /* item not inserted */
78 }
79 else if(il.size()>max_num_items){ /* keep the length <= max_num_items */
80 il.pop_back();
81 }
82 return true; /* new item inserted */
83 }
84
85 template<typename Modifier>
86 bool modify(iterator position, Modifier modifier)
87 {
88 return il.modify(position, modifier);
89 }
90
91 bool empty() const {return il.empty();}
92 std::size_t size() const {return il.size();}
93 std::size_t max_size() const {return std::min(max_num_items, il.max_size());}
94 void clear() {il.clear();}
95
96 const item_type& mru() const {return *il.begin();}
97 const item_type& lru() const {return *il.rbegin();}
98
99 iterator begin() {return il.begin();}
100 iterator end() {return il.end();}
101
102 reverse_iterator rbegin() {return il.rbegin();}
103 reverse_iterator rend() {return il.rend();}
104
105 const_iterator begin() const {return il.begin();}
106 const_iterator end() const {return il.end();}
107
108 const_reverse_iterator rbegin() const {return il.rbegin();}
109 const_reverse_iterator rend() const {return il.rend();}
110
111private:
113 std::size_t max_num_items;
114};
115
116
117} // namespace util
118} // namespace pwiz
119
120
121#endif // _MRU_LIST_HPP_
reverse_iterator rbegin()
Definition mru_list.hpp:102
bool empty() const
Definition mru_list.hpp:91
std::size_t max_size() const
Definition mru_list.hpp:93
item_list::reverse_iterator reverse_iterator
Definition mru_list.hpp:64
bool modify(iterator position, Modifier modifier)
Definition mru_list.hpp:86
const item_type & mru() const
Definition mru_list.hpp:96
reverse_iterator rend()
Definition mru_list.hpp:103
item_list::value_type value_type
Definition mru_list.hpp:67
std::size_t max_num_items
Definition mru_list.hpp:113
const_reverse_iterator rend() const
Definition mru_list.hpp:109
const_reverse_iterator rbegin() const
Definition mru_list.hpp:108
boost::multi_index::multi_index_container< Item, boost::multi_index::indexed_by< boost::multi_index::sequenced<>, boost::multi_index::hashed_unique< KeyExtractor > > > item_list
Definition mru_list.hpp:59
item_list::const_reverse_iterator const_reverse_iterator
Definition mru_list.hpp:66
const_iterator begin() const
Definition mru_list.hpp:105
item_list::const_iterator const_iterator
Definition mru_list.hpp:65
std::size_t size() const
Definition mru_list.hpp:92
const item_type & lru() const
Definition mru_list.hpp:97
item_list::iterator iterator
Definition mru_list.hpp:63
mru_list(std::size_t max_num_items_)
Definition mru_list.hpp:69
const_iterator end() const
Definition mru_list.hpp:106
bool insert(const item_type &item)
Definition mru_list.hpp:71