third_party/rust_crates/vendor/lru-cache/src/lib.rs - fuchsia - Git at Google

 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
 // file at the top-level directory of this distribution and at
 // http://rust-lang.org/COPYRIGHT.
 //
 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.

 //! A cache that holds a limited number of key-value pairs. When the
 //! capacity of the cache is exceeded, the least-recently-used
 //! (where "used" means a look-up or putting the pair into the cache)
 //! pair is automatically removed.
 //!
 //! # Examples
 //!
 //! ```
 //! use lru_cache::LruCache;
 //!
 //! let mut cache = LruCache::new(2);
 //!
 //! cache.insert(1, 10);
 //! cache.insert(2, 20);
 //! cache.insert(3, 30);
 //! assert!(cache.get_mut(&1).is_none());
 //! assert_eq!(*cache.get_mut(&2).unwrap(), 20);
 //! assert_eq!(*cache.get_mut(&3).unwrap(), 30);
 //!
 //! cache.insert(2, 22);
 //! assert_eq!(*cache.get_mut(&2).unwrap(), 22);
 //!
 //! cache.insert(6, 60);
 //! assert!(cache.get_mut(&3).is_none());
 //!
 //! cache.set_capacity(1);
 //! assert!(cache.get_mut(&2).is_none());
 //! ```

 extern crate linked_hash_map;

 use std::borrow::Borrow;
 use std::collections::hash_map::RandomState;
 use std::fmt;
 use std::hash::{Hash, BuildHasher};

 use linked_hash_map::LinkedHashMap;

 #[cfg(feature = "heapsize_impl")]
 mod heapsize;

 // FIXME(conventions): implement indexing?

 /// An LRU cache.
 #[derive(Clone)]
 pub struct LruCache<K: Eq + Hash, V, S: BuildHasher = RandomState> {
     map: LinkedHashMap<K, V, S>,
     max_size: usize,
 }

 impl<K: Eq + Hash, V> LruCache<K, V> {
     /// Creates an empty cache that can hold at most `capacity` items.
     ///
     /// # Examples
     ///
     /// ```
     /// use lru_cache::LruCache;
     /// let mut cache: LruCache<i32, &str> = LruCache::new(10);
     /// ```
     pub fn new(capacity: usize) -> Self {
         LruCache {
             map: LinkedHashMap::new(),
             max_size: capacity,
         }
     }
 }

 impl<K: Eq + Hash, V, S: BuildHasher> LruCache<K, V, S> {
     /// Creates an empty cache that can hold at most `capacity` items with the given hash builder.
     pub fn with_hasher(capacity: usize, hash_builder: S) -> Self {
         LruCache { map: LinkedHashMap::with_hasher(hash_builder), max_size: capacity }
     }

     /// Checks if the map contains the given key.
     ///
     /// # Examples
     ///
     /// ```
     /// use lru_cache::LruCache;
     ///
     /// let mut cache = LruCache::new(1);
     ///
     /// cache.insert(1, "a");
     /// assert_eq!(cache.contains_key(&1), true);
     /// ```
     pub fn contains_key<Q: ?Sized>(&mut self, key: &Q) -> bool
         where K: Borrow<Q>,
               Q: Hash + Eq
     {
         self.get_mut(key).is_some()
     }

     /// Inserts a key-value pair into the cache. If the key already existed, the old value is
     /// returned.
     ///
     /// # Examples
     ///
     /// ```
     /// use lru_cache::LruCache;
     ///
     /// let mut cache = LruCache::new(2);
     ///
     /// cache.insert(1, "a");
     /// cache.insert(2, "b");
     /// assert_eq!(cache.get_mut(&1), Some(&mut "a"));
     /// assert_eq!(cache.get_mut(&2), Some(&mut "b"));
     /// ```
     pub fn insert(&mut self, k: K, v: V) -> Option<V> {
         let old_val = self.map.insert(k, v);
         if self.len() > self.capacity() {
             self.remove_lru();
         }
         old_val
     }

     /// Returns a mutable reference to the value corresponding to the given key in the cache, if
     /// any.
     ///
     /// # Examples
     ///
     /// ```
     /// use lru_cache::LruCache;
     ///
     /// let mut cache = LruCache::new(2);
     ///
     /// cache.insert(1, "a");
     /// cache.insert(2, "b");
     /// cache.insert(2, "c");
     /// cache.insert(3, "d");
     ///
     /// assert_eq!(cache.get_mut(&1), None);
     /// assert_eq!(cache.get_mut(&2), Some(&mut "c"));
     /// ```
     pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
         where K: Borrow<Q>,
               Q: Hash + Eq
     {
         self.map.get_refresh(k)
     }

     /// Removes the given key from the cache and returns its corresponding value.
     ///
     /// # Examples
     ///
     /// ```
     /// use lru_cache::LruCache;
     ///
     /// let mut cache = LruCache::new(2);
     ///
     /// cache.insert(2, "a");
     ///
     /// assert_eq!(cache.remove(&1), None);
     /// assert_eq!(cache.remove(&2), Some("a"));
     /// assert_eq!(cache.remove(&2), None);
     /// assert_eq!(cache.len(), 0);
     /// ```
     pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
         where K: Borrow<Q>,
               Q: Hash + Eq
     {
         self.map.remove(k)
     }

     /// Returns the maximum number of key-value pairs the cache can hold.
     ///
     /// # Examples
     ///
     /// ```
     /// use lru_cache::LruCache;
     /// let mut cache: LruCache<i32, &str> = LruCache::new(2);
     /// assert_eq!(cache.capacity(), 2);
     /// ```
     pub fn capacity(&self) -> usize {
         self.max_size
     }

     /// Sets the number of key-value pairs the cache can hold. Removes
     /// least-recently-used key-value pairs if necessary.
     ///
     /// # Examples
     ///
     /// ```
     /// use lru_cache::LruCache;
     ///
     /// let mut cache = LruCache::new(2);
     ///
     /// cache.insert(1, "a");
     /// cache.insert(2, "b");
     /// cache.insert(3, "c");
     ///
     /// assert_eq!(cache.get_mut(&1), None);
     /// assert_eq!(cache.get_mut(&2), Some(&mut "b"));
     /// assert_eq!(cache.get_mut(&3), Some(&mut "c"));
     ///
     /// cache.set_capacity(3);
     /// cache.insert(1, "a");
     /// cache.insert(2, "b");
     ///
     /// assert_eq!(cache.get_mut(&1), Some(&mut "a"));
     /// assert_eq!(cache.get_mut(&2), Some(&mut "b"));
     /// assert_eq!(cache.get_mut(&3), Some(&mut "c"));
     ///
     /// cache.set_capacity(1);
     ///
     /// assert_eq!(cache.get_mut(&1), None);
     /// assert_eq!(cache.get_mut(&2), None);
     /// assert_eq!(cache.get_mut(&3), Some(&mut "c"));
     /// ```
     pub fn set_capacity(&mut self, capacity: usize) {
         for _ in capacity..self.len() {
             self.remove_lru();
         }
         self.max_size = capacity;
     }

     /// Removes and returns the least recently used key-value pair as a tuple.
     ///
     /// # Examples
     ///
     /// ```
     /// use lru_cache::LruCache;
     ///
     /// let mut cache = LruCache::new(2);
     ///
     /// cache.insert(1, "a");
     /// cache.insert(2, "b");
     ///
     /// assert_eq!(cache.remove_lru(), Some((1, "a")));
     /// assert_eq!(cache.len(), 1);
     /// ```
     #[inline]
     pub fn remove_lru(&mut self) -> Option<(K, V)> {
         self.map.pop_front()
     }

     /// Returns the number of key-value pairs in the cache.
     pub fn len(&self) -> usize { self.map.len() }

     /// Returns `true` if the cache contains no key-value pairs.
     pub fn is_empty(&self) -> bool { self.map.is_empty() }

     /// Removes all key-value pairs from the cache.
     pub fn clear(&mut self) { self.map.clear(); }

     /// Returns an iterator over the cache's key-value pairs in least- to most-recently-used order.
     ///
     /// Accessing the cache through the iterator does _not_ affect the cache's LRU state.
     ///
     /// # Examples
     ///
     /// ```
     /// use lru_cache::LruCache;
     ///
     /// let mut cache = LruCache::new(2);
     ///
     /// cache.insert(1, 10);
     /// cache.insert(2, 20);
     /// cache.insert(3, 30);
     ///
     /// let kvs: Vec<_> = cache.iter().collect();
     /// assert_eq!(kvs, [(&2, &20), (&3, &30)]);
     /// ```
     pub fn iter(&self) -> Iter<K, V> { Iter(self.map.iter()) }

     /// Returns an iterator over the cache's key-value pairs in least- to most-recently-used order,
     /// with mutable references to the values.
     ///
     /// Accessing the cache through the iterator does _not_ affect the cache's LRU state.
     ///
     /// # Examples
     ///
     /// ```
     /// use lru_cache::LruCache;
     ///
     /// let mut cache = LruCache::new(2);
     ///
     /// cache.insert(1, 10);
     /// cache.insert(2, 20);
     /// cache.insert(3, 30);
     ///
     /// let mut n = 2;
     ///
     /// for (k, v) in cache.iter_mut() {
     ///     assert_eq!(*k, n);
     ///     assert_eq!(*v, n * 10);
     ///     *v *= 10;
     ///     n += 1;
     /// }
     ///
     /// assert_eq!(n, 4);
     /// assert_eq!(cache.get_mut(&2), Some(&mut 200));
     /// assert_eq!(cache.get_mut(&3), Some(&mut 300));
     /// ```
     pub fn iter_mut(&mut self) -> IterMut<K, V> { IterMut(self.map.iter_mut()) }
 }

 impl<K: Eq + Hash, V, S: BuildHasher> Extend<(K, V)> for LruCache<K, V, S> {
     fn extend<I: IntoIterator<Item=(K, V)>>(&mut self, iter: I) {
         for (k, v) in iter {
             self.insert(k, v);
         }
     }
 }

 impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug for LruCache<K, V, S> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         f.debug_map().entries(self.iter().rev()).finish()
     }
 }

 impl<K: Eq + Hash, V, S: BuildHasher> IntoIterator for LruCache<K, V, S> {
     type Item = (K, V);
     type IntoIter = IntoIter<K, V>;

     fn into_iter(self) -> IntoIter<K, V> {
         IntoIter(self.map.into_iter())
     }
 }

 impl<'a, K: Eq + Hash, V, S: BuildHasher> IntoIterator for &'a LruCache<K, V, S> {
     type Item = (&'a K, &'a V);
     type IntoIter = Iter<'a, K, V>;
     fn into_iter(self) -> Iter<'a, K, V> { self.iter() }
 }

 impl<'a, K: Eq + Hash, V, S: BuildHasher> IntoIterator for &'a mut LruCache<K, V, S> {
     type Item = (&'a K, &'a mut V);
     type IntoIter = IterMut<'a, K, V>;
     fn into_iter(self) -> IterMut<'a, K, V> { self.iter_mut() }
 }

 /// An iterator over a cache's key-value pairs in least- to most-recently-used order.
 ///
 /// # Examples
 ///
 /// ```
 /// use lru_cache::LruCache;
 ///
 /// let mut cache = LruCache::new(2);
 ///
 /// cache.insert(1, 10);
 /// cache.insert(2, 20);
 /// cache.insert(3, 30);
 ///
 /// let mut n = 2;
 ///
 /// for (k, v) in cache {
 ///     assert_eq!(k, n);
 ///     assert_eq!(v, n * 10);
 ///     n += 1;
 /// }
 ///
 /// assert_eq!(n, 4);
 /// ```
 #[derive(Clone)]
 pub struct IntoIter<K, V>(linked_hash_map::IntoIter<K, V>);

 impl<K, V> Iterator for IntoIter<K, V> {
     type Item = (K, V);

     fn next(&mut self) -> Option<(K, V)> {
         self.0.next()
     }

     fn size_hint(&self) -> (usize, Option<usize>) {
         self.0.size_hint()
     }
 }

 impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
     fn next_back(&mut self) -> Option<(K, V)> {
         self.0.next_back()
     }
 }

 impl<K, V> ExactSizeIterator for IntoIter<K, V> {
     fn len(&self) -> usize {
         self.0.len()
     }
 }

 /// An iterator over a cache's key-value pairs in least- to most-recently-used order.
 ///
 /// Accessing a cache through the iterator does _not_ affect the cache's LRU state.
 pub struct Iter<'a, K: 'a, V: 'a>(linked_hash_map::Iter<'a, K, V>);

 impl<'a, K, V> Clone for Iter<'a, K, V> {
     fn clone(&self) -> Iter<'a, K, V> { Iter(self.0.clone()) }
 }

 impl<'a, K, V> Iterator for Iter<'a, K, V> {
     type Item = (&'a K, &'a V);
     fn next(&mut self) -> Option<(&'a K, &'a V)> { self.0.next() }
     fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
 }

 impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
     fn next_back(&mut self) -> Option<(&'a K, &'a V)> { self.0.next_back() }
 }

 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
     fn len(&self) -> usize { self.0.len() }
 }

 /// An iterator over a cache's key-value pairs in least- to most-recently-used order with mutable
 /// references to the values.
 ///
 /// Accessing a cache through the iterator does _not_ affect the cache's LRU state.
 pub struct IterMut<'a, K: 'a, V: 'a>(linked_hash_map::IterMut<'a, K, V>);

 impl<'a, K, V> Iterator for IterMut<'a, K, V> {
     type Item = (&'a K, &'a mut V);
     fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.0.next() }
     fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
 }

 impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
     fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { self.0.next_back() }
 }

 impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
     fn len(&self) -> usize { self.0.len() }
 }

 #[cfg(test)]
 mod tests {
     use super::LruCache;

     #[test]
     fn test_put_and_get() {
         let mut cache = LruCache::new(2);
         cache.insert(1, 10);
         cache.insert(2, 20);
         assert_eq!(cache.get_mut(&1), Some(&mut 10));
         assert_eq!(cache.get_mut(&2), Some(&mut 20));
         assert_eq!(cache.len(), 2);
     }

     #[test]
     fn test_put_update() {
         let mut cache = LruCache::new(1);
         cache.insert("1", 10);
         cache.insert("1", 19);
         assert_eq!(cache.get_mut("1"), Some(&mut 19));
         assert_eq!(cache.len(), 1);
     }

     #[test]
     fn test_contains_key() {
         let mut cache = LruCache::new(1);
         cache.insert("1", 10);
         assert_eq!(cache.contains_key("1"), true);
     }

     #[test]
     fn test_expire_lru() {
         let mut cache = LruCache::new(2);
         cache.insert("foo1", "bar1");
         cache.insert("foo2", "bar2");
         cache.insert("foo3", "bar3");
         assert!(cache.get_mut("foo1").is_none());
         cache.insert("foo2", "bar2update");
         cache.insert("foo4", "bar4");
         assert!(cache.get_mut("foo3").is_none());
     }

     #[test]
     fn test_pop() {
         let mut cache = LruCache::new(2);
         cache.insert(1, 10);
         cache.insert(2, 20);
         assert_eq!(cache.len(), 2);
         let opt1 = cache.remove(&1);
         assert!(opt1.is_some());
         assert_eq!(opt1.unwrap(), 10);
         assert!(cache.get_mut(&1).is_none());
         assert_eq!(cache.len(), 1);
     }

     #[test]
     fn test_change_capacity() {
         let mut cache = LruCache::new(2);
         assert_eq!(cache.capacity(), 2);
         cache.insert(1, 10);
         cache.insert(2, 20);
         cache.set_capacity(1);
         assert!(cache.get_mut(&1).is_none());
         assert_eq!(cache.capacity(), 1);
     }

     #[test]
     fn test_debug() {
         let mut cache = LruCache::new(3);
         cache.insert(1, 10);
         cache.insert(2, 20);
         cache.insert(3, 30);
         assert_eq!(format!("{:?}", cache), "{3: 30, 2: 20, 1: 10}");
         cache.insert(2, 22);
         assert_eq!(format!("{:?}", cache), "{2: 22, 3: 30, 1: 10}");
         cache.insert(6, 60);
         assert_eq!(format!("{:?}", cache), "{6: 60, 2: 22, 3: 30}");
         cache.get_mut(&3);
         assert_eq!(format!("{:?}", cache), "{3: 30, 6: 60, 2: 22}");
         cache.set_capacity(2);
         assert_eq!(format!("{:?}", cache), "{3: 30, 6: 60}");
     }

     #[test]
     fn test_remove() {
         let mut cache = LruCache::new(3);
         cache.insert(1, 10);
         cache.insert(2, 20);
         cache.insert(3, 30);
         cache.insert(4, 40);
         cache.insert(5, 50);
         cache.remove(&3);
         cache.remove(&4);
         assert!(cache.get_mut(&3).is_none());
         assert!(cache.get_mut(&4).is_none());
         cache.insert(6, 60);
         cache.insert(7, 70);
         cache.insert(8, 80);
         assert!(cache.get_mut(&5).is_none());
         assert_eq!(cache.get_mut(&6), Some(&mut 60));
         assert_eq!(cache.get_mut(&7), Some(&mut 70));
         assert_eq!(cache.get_mut(&8), Some(&mut 80));
     }

     #[test]
     fn test_clear() {
         let mut cache = LruCache::new(2);
         cache.insert(1, 10);
         cache.insert(2, 20);
         cache.clear();
         assert!(cache.get_mut(&1).is_none());
         assert!(cache.get_mut(&2).is_none());
         assert_eq!(format!("{:?}", cache), "{}");
     }

     #[test]
     fn test_iter() {
         let mut cache = LruCache::new(3);
         cache.insert(1, 10);
         cache.insert(2, 20);
         cache.insert(3, 30);
         cache.insert(4, 40);
         cache.insert(5, 50);
         assert_eq!(cache.iter().collect::<Vec<_>>(),
                    [(&3, &30), (&4, &40), (&5, &50)]);
         assert_eq!(cache.iter_mut().collect::<Vec<_>>(),
                    [(&3, &mut 30), (&4, &mut 40), (&5, &mut 50)]);
         assert_eq!(cache.iter().rev().collect::<Vec<_>>(),
                    [(&5, &50), (&4, &40), (&3, &30)]);
         assert_eq!(cache.iter_mut().rev().collect::<Vec<_>>(),
                    [(&5, &mut 50), (&4, &mut 40), (&3, &mut 30)]);
     }
 }
	// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
	// file at the top-level directory of this distribution and at
	// http://rust-lang.org/COPYRIGHT.
	//
	// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
	// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
	// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
	// option. This file may not be copied, modified, or distributed
	// except according to those terms.

	//! A cache that holds a limited number of key-value pairs. When the
	//! capacity of the cache is exceeded, the least-recently-used
	//! (where "used" means a look-up or putting the pair into the cache)
	//! pair is automatically removed.
	//!
	//! # Examples
	//!
	//! ```
	//! use lru_cache::LruCache;
	//!
	//! let mut cache = LruCache::new(2);
	//!
	//! cache.insert(1, 10);
	//! cache.insert(2, 20);
	//! cache.insert(3, 30);
	//! assert!(cache.get_mut(&1).is_none());
	//! assert_eq!(*cache.get_mut(&2).unwrap(), 20);
	//! assert_eq!(*cache.get_mut(&3).unwrap(), 30);
	//!
	//! cache.insert(2, 22);
	//! assert_eq!(*cache.get_mut(&2).unwrap(), 22);
	//!
	//! cache.insert(6, 60);
	//! assert!(cache.get_mut(&3).is_none());
	//!
	//! cache.set_capacity(1);
	//! assert!(cache.get_mut(&2).is_none());
	//! ```

	extern crate linked_hash_map;

	use std::borrow::Borrow;
	use std::collections::hash_map::RandomState;
	use std::fmt;
	use std::hash::{Hash, BuildHasher};

	use linked_hash_map::LinkedHashMap;

	#[cfg(feature = "heapsize_impl")]
	mod heapsize;

	// FIXME(conventions): implement indexing?

	/// An LRU cache.
	#[derive(Clone)]
	pub struct LruCache<K: Eq + Hash, V, S: BuildHasher = RandomState> {
	map: LinkedHashMap<K, V, S>,
	max_size: usize,
	}

	impl<K: Eq + Hash, V> LruCache<K, V> {
	/// Creates an empty cache that can hold at most `capacity` items.
	///
	/// # Examples
	///
	/// ```
	/// use lru_cache::LruCache;
	/// let mut cache: LruCache<i32, &str> = LruCache::new(10);
	/// ```
	pub fn new(capacity: usize) -> Self {
	LruCache {
	map: LinkedHashMap::new(),
	max_size: capacity,
	}
	}
	}

	impl<K: Eq + Hash, V, S: BuildHasher> LruCache<K, V, S> {
	/// Creates an empty cache that can hold at most `capacity` items with the given hash builder.
	pub fn with_hasher(capacity: usize, hash_builder: S) -> Self {
	LruCache { map: LinkedHashMap::with_hasher(hash_builder), max_size: capacity }
	}

	/// Checks if the map contains the given key.
	///
	/// # Examples
	///
	/// ```
	/// use lru_cache::LruCache;
	///
	/// let mut cache = LruCache::new(1);
	///
	/// cache.insert(1, "a");
	/// assert_eq!(cache.contains_key(&1), true);
	/// ```
	pub fn contains_key<Q: ?Sized>(&mut self, key: &Q) -> bool
	where K: Borrow<Q>,
	Q: Hash + Eq
	{
	self.get_mut(key).is_some()
	}

	/// Inserts a key-value pair into the cache. If the key already existed, the old value is
	/// returned.
	///
	/// # Examples
	///
	/// ```
	/// use lru_cache::LruCache;
	///
	/// let mut cache = LruCache::new(2);
	///
	/// cache.insert(1, "a");
	/// cache.insert(2, "b");
	/// assert_eq!(cache.get_mut(&1), Some(&mut "a"));
	/// assert_eq!(cache.get_mut(&2), Some(&mut "b"));
	/// ```
	pub fn insert(&mut self, k: K, v: V) -> Option<V> {
	let old_val = self.map.insert(k, v);
	if self.len() > self.capacity() {
	self.remove_lru();
	}
	old_val
	}

	/// Returns a mutable reference to the value corresponding to the given key in the cache, if
	/// any.
	///
	/// # Examples
	///
	/// ```
	/// use lru_cache::LruCache;
	///
	/// let mut cache = LruCache::new(2);
	///
	/// cache.insert(1, "a");
	/// cache.insert(2, "b");
	/// cache.insert(2, "c");
	/// cache.insert(3, "d");
	///
	/// assert_eq!(cache.get_mut(&1), None);
	/// assert_eq!(cache.get_mut(&2), Some(&mut "c"));
	/// ```
	pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
	where K: Borrow<Q>,
	Q: Hash + Eq
	{
	self.map.get_refresh(k)
	}

	/// Removes the given key from the cache and returns its corresponding value.
	///
	/// # Examples
	///
	/// ```
	/// use lru_cache::LruCache;
	///
	/// let mut cache = LruCache::new(2);
	///
	/// cache.insert(2, "a");
	///
	/// assert_eq!(cache.remove(&1), None);
	/// assert_eq!(cache.remove(&2), Some("a"));
	/// assert_eq!(cache.remove(&2), None);
	/// assert_eq!(cache.len(), 0);
	/// ```
	pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
	where K: Borrow<Q>,
	Q: Hash + Eq
	{
	self.map.remove(k)
	}

	/// Returns the maximum number of key-value pairs the cache can hold.
	///
	/// # Examples
	///
	/// ```
	/// use lru_cache::LruCache;
	/// let mut cache: LruCache<i32, &str> = LruCache::new(2);
	/// assert_eq!(cache.capacity(), 2);
	/// ```
	pub fn capacity(&self) -> usize {
	self.max_size
	}

	/// Sets the number of key-value pairs the cache can hold. Removes
	/// least-recently-used key-value pairs if necessary.
	///
	/// # Examples
	///
	/// ```
	/// use lru_cache::LruCache;
	///
	/// let mut cache = LruCache::new(2);
	///
	/// cache.insert(1, "a");
	/// cache.insert(2, "b");
	/// cache.insert(3, "c");
	///
	/// assert_eq!(cache.get_mut(&1), None);
	/// assert_eq!(cache.get_mut(&2), Some(&mut "b"));
	/// assert_eq!(cache.get_mut(&3), Some(&mut "c"));
	///
	/// cache.set_capacity(3);
	/// cache.insert(1, "a");
	/// cache.insert(2, "b");
	///
	/// assert_eq!(cache.get_mut(&1), Some(&mut "a"));
	/// assert_eq!(cache.get_mut(&2), Some(&mut "b"));
	/// assert_eq!(cache.get_mut(&3), Some(&mut "c"));
	///
	/// cache.set_capacity(1);
	///
	/// assert_eq!(cache.get_mut(&1), None);
	/// assert_eq!(cache.get_mut(&2), None);
	/// assert_eq!(cache.get_mut(&3), Some(&mut "c"));
	/// ```
	pub fn set_capacity(&mut self, capacity: usize) {
	for _ in capacity..self.len() {
	self.remove_lru();
	}
	self.max_size = capacity;
	}

	/// Removes and returns the least recently used key-value pair as a tuple.
	///
	/// # Examples
	///
	/// ```
	/// use lru_cache::LruCache;
	///
	/// let mut cache = LruCache::new(2);
	///
	/// cache.insert(1, "a");
	/// cache.insert(2, "b");
	///
	/// assert_eq!(cache.remove_lru(), Some((1, "a")));
	/// assert_eq!(cache.len(), 1);
	/// ```
	#[inline]
	pub fn remove_lru(&mut self) -> Option<(K, V)> {
	self.map.pop_front()
	}

	/// Returns the number of key-value pairs in the cache.
	pub fn len(&self) -> usize { self.map.len() }

	/// Returns `true` if the cache contains no key-value pairs.
	pub fn is_empty(&self) -> bool { self.map.is_empty() }

	/// Removes all key-value pairs from the cache.
	pub fn clear(&mut self) { self.map.clear(); }

	/// Returns an iterator over the cache's key-value pairs in least- to most-recently-used order.
	///
	/// Accessing the cache through the iterator does _not_ affect the cache's LRU state.
	///
	/// # Examples
	///
	/// ```
	/// use lru_cache::LruCache;
	///
	/// let mut cache = LruCache::new(2);
	///
	/// cache.insert(1, 10);
	/// cache.insert(2, 20);
	/// cache.insert(3, 30);
	///
	/// let kvs: Vec<_> = cache.iter().collect();
	/// assert_eq!(kvs, [(&2, &20), (&3, &30)]);
	/// ```
	pub fn iter(&self) -> Iter<K, V> { Iter(self.map.iter()) }

	/// Returns an iterator over the cache's key-value pairs in least- to most-recently-used order,
	/// with mutable references to the values.
	///
	/// Accessing the cache through the iterator does _not_ affect the cache's LRU state.
	///
	/// # Examples
	///
	/// ```
	/// use lru_cache::LruCache;
	///
	/// let mut cache = LruCache::new(2);
	///
	/// cache.insert(1, 10);
	/// cache.insert(2, 20);
	/// cache.insert(3, 30);
	///
	/// let mut n = 2;
	///
	/// for (k, v) in cache.iter_mut() {
	/// assert_eq!(*k, n);
	/// assert_eq!(v, n 10);
	/// v = 10;
	/// n += 1;
	/// }
	///
	/// assert_eq!(n, 4);
	/// assert_eq!(cache.get_mut(&2), Some(&mut 200));
	/// assert_eq!(cache.get_mut(&3), Some(&mut 300));
	/// ```
	pub fn iter_mut(&mut self) -> IterMut<K, V> { IterMut(self.map.iter_mut()) }
	}

	impl<K: Eq + Hash, V, S: BuildHasher> Extend<(K, V)> for LruCache<K, V, S> {
	fn extend<I: IntoIterator<Item=(K, V)>>(&mut self, iter: I) {
	for (k, v) in iter {
	self.insert(k, v);
	}
	}
	}

	impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug for LruCache<K, V, S> {
	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
	f.debug_map().entries(self.iter().rev()).finish()
	}
	}

	impl<K: Eq + Hash, V, S: BuildHasher> IntoIterator for LruCache<K, V, S> {
	type Item = (K, V);
	type IntoIter = IntoIter<K, V>;

	fn into_iter(self) -> IntoIter<K, V> {
	IntoIter(self.map.into_iter())
	}
	}

	impl<'a, K: Eq + Hash, V, S: BuildHasher> IntoIterator for &'a LruCache<K, V, S> {
	type Item = (&'a K, &'a V);
	type IntoIter = Iter<'a, K, V>;
	fn into_iter(self) -> Iter<'a, K, V> { self.iter() }
	}

	impl<'a, K: Eq + Hash, V, S: BuildHasher> IntoIterator for &'a mut LruCache<K, V, S> {
	type Item = (&'a K, &'a mut V);
	type IntoIter = IterMut<'a, K, V>;
	fn into_iter(self) -> IterMut<'a, K, V> { self.iter_mut() }
	}

	/// An iterator over a cache's key-value pairs in least- to most-recently-used order.
	///
	/// # Examples
	///
	/// ```
	/// use lru_cache::LruCache;
	///
	/// let mut cache = LruCache::new(2);
	///
	/// cache.insert(1, 10);
	/// cache.insert(2, 20);
	/// cache.insert(3, 30);
	///
	/// let mut n = 2;
	///
	/// for (k, v) in cache {
	/// assert_eq!(k, n);
	/// assert_eq!(v, n * 10);
	/// n += 1;
	/// }
	///
	/// assert_eq!(n, 4);
	/// ```
	#[derive(Clone)]
	pub struct IntoIter<K, V>(linked_hash_map::IntoIter<K, V>);

	impl<K, V> Iterator for IntoIter<K, V> {
	type Item = (K, V);

	fn next(&mut self) -> Option<(K, V)> {
	self.0.next()
	}

	fn size_hint(&self) -> (usize, Option<usize>) {
	self.0.size_hint()
	}
	}

	impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
	fn next_back(&mut self) -> Option<(K, V)> {
	self.0.next_back()
	}
	}

	impl<K, V> ExactSizeIterator for IntoIter<K, V> {
	fn len(&self) -> usize {
	self.0.len()
	}
	}

	/// An iterator over a cache's key-value pairs in least- to most-recently-used order.
	///
	/// Accessing a cache through the iterator does _not_ affect the cache's LRU state.
	pub struct Iter<'a, K: 'a, V: 'a>(linked_hash_map::Iter<'a, K, V>);

	impl<'a, K, V> Clone for Iter<'a, K, V> {
	fn clone(&self) -> Iter<'a, K, V> { Iter(self.0.clone()) }
	}

	impl<'a, K, V> Iterator for Iter<'a, K, V> {
	type Item = (&'a K, &'a V);
	fn next(&mut self) -> Option<(&'a K, &'a V)> { self.0.next() }
	fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
	}

	impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
	fn next_back(&mut self) -> Option<(&'a K, &'a V)> { self.0.next_back() }
	}

	impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
	fn len(&self) -> usize { self.0.len() }
	}

	/// An iterator over a cache's key-value pairs in least- to most-recently-used order with mutable
	/// references to the values.
	///
	/// Accessing a cache through the iterator does _not_ affect the cache's LRU state.
	pub struct IterMut<'a, K: 'a, V: 'a>(linked_hash_map::IterMut<'a, K, V>);

	impl<'a, K, V> Iterator for IterMut<'a, K, V> {
	type Item = (&'a K, &'a mut V);
	fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.0.next() }
	fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() }
	}

	impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
	fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { self.0.next_back() }
	}

	impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
	fn len(&self) -> usize { self.0.len() }
	}

	#[cfg(test)]
	mod tests {
	use super::LruCache;

	#[test]
	fn test_put_and_get() {
	let mut cache = LruCache::new(2);
	cache.insert(1, 10);
	cache.insert(2, 20);
	assert_eq!(cache.get_mut(&1), Some(&mut 10));
	assert_eq!(cache.get_mut(&2), Some(&mut 20));
	assert_eq!(cache.len(), 2);
	}

	#[test]
	fn test_put_update() {
	let mut cache = LruCache::new(1);
	cache.insert("1", 10);
	cache.insert("1", 19);
	assert_eq!(cache.get_mut("1"), Some(&mut 19));
	assert_eq!(cache.len(), 1);
	}

	#[test]
	fn test_contains_key() {
	let mut cache = LruCache::new(1);
	cache.insert("1", 10);
	assert_eq!(cache.contains_key("1"), true);
	}

	#[test]
	fn test_expire_lru() {
	let mut cache = LruCache::new(2);
	cache.insert("foo1", "bar1");
	cache.insert("foo2", "bar2");
	cache.insert("foo3", "bar3");
	assert!(cache.get_mut("foo1").is_none());
	cache.insert("foo2", "bar2update");
	cache.insert("foo4", "bar4");
	assert!(cache.get_mut("foo3").is_none());
	}

	#[test]
	fn test_pop() {
	let mut cache = LruCache::new(2);
	cache.insert(1, 10);
	cache.insert(2, 20);
	assert_eq!(cache.len(), 2);
	let opt1 = cache.remove(&1);
	assert!(opt1.is_some());
	assert_eq!(opt1.unwrap(), 10);
	assert!(cache.get_mut(&1).is_none());
	assert_eq!(cache.len(), 1);
	}

	#[test]
	fn test_change_capacity() {
	let mut cache = LruCache::new(2);
	assert_eq!(cache.capacity(), 2);
	cache.insert(1, 10);
	cache.insert(2, 20);
	cache.set_capacity(1);
	assert!(cache.get_mut(&1).is_none());
	assert_eq!(cache.capacity(), 1);
	}

	#[test]
	fn test_debug() {
	let mut cache = LruCache::new(3);
	cache.insert(1, 10);
	cache.insert(2, 20);
	cache.insert(3, 30);
	assert_eq!(format!("{:?}", cache), "{3: 30, 2: 20, 1: 10}");
	cache.insert(2, 22);
	assert_eq!(format!("{:?}", cache), "{2: 22, 3: 30, 1: 10}");
	cache.insert(6, 60);
	assert_eq!(format!("{:?}", cache), "{6: 60, 2: 22, 3: 30}");
	cache.get_mut(&3);
	assert_eq!(format!("{:?}", cache), "{3: 30, 6: 60, 2: 22}");
	cache.set_capacity(2);
	assert_eq!(format!("{:?}", cache), "{3: 30, 6: 60}");
	}

	#[test]
	fn test_remove() {
	let mut cache = LruCache::new(3);
	cache.insert(1, 10);
	cache.insert(2, 20);
	cache.insert(3, 30);
	cache.insert(4, 40);
	cache.insert(5, 50);
	cache.remove(&3);
	cache.remove(&4);
	assert!(cache.get_mut(&3).is_none());
	assert!(cache.get_mut(&4).is_none());
	cache.insert(6, 60);
	cache.insert(7, 70);
	cache.insert(8, 80);
	assert!(cache.get_mut(&5).is_none());
	assert_eq!(cache.get_mut(&6), Some(&mut 60));
	assert_eq!(cache.get_mut(&7), Some(&mut 70));
	assert_eq!(cache.get_mut(&8), Some(&mut 80));
	}

	#[test]
	fn test_clear() {
	let mut cache = LruCache::new(2);
	cache.insert(1, 10);
	cache.insert(2, 20);
	cache.clear();
	assert!(cache.get_mut(&1).is_none());
	assert!(cache.get_mut(&2).is_none());
	assert_eq!(format!("{:?}", cache), "{}");
	}

	#[test]
	fn test_iter() {
	let mut cache = LruCache::new(3);
	cache.insert(1, 10);
	cache.insert(2, 20);
	cache.insert(3, 30);
	cache.insert(4, 40);
	cache.insert(5, 50);
	assert_eq!(cache.iter().collect::<Vec<_>>(),
	[(&3, &30), (&4, &40), (&5, &50)]);
	assert_eq!(cache.iter_mut().collect::<Vec<_>>(),
	[(&3, &mut 30), (&4, &mut 40), (&5, &mut 50)]);
	assert_eq!(cache.iter().rev().collect::<Vec<_>>(),
	[(&5, &50), (&4, &40), (&3, &30)]);
	assert_eq!(cache.iter_mut().rev().collect::<Vec<_>>(),
	[(&5, &mut 50), (&4, &mut 40), (&3, &mut 30)]);
	}
	}