17bdc3750454efe59617b7df945eadd7e59bee954Andy Huang/* 27bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * Copyright (C) 2012 Google Inc. 37bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * Licensed to The Android Open Source Project. 47bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * 57bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * Licensed under the Apache License, Version 2.0 (the "License"); 67bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * you may not use this file except in compliance with the License. 77bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * You may obtain a copy of the License at 87bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * 97bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * http://www.apache.org/licenses/LICENSE-2.0 107bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * 117bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * Unless required by applicable law or agreed to in writing, software 127bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * distributed under the License is distributed on an "AS IS" BASIS, 137bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 147bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * See the License for the specific language governing permissions and 157bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * limitations under the License. 167bdc3750454efe59617b7df945eadd7e59bee954Andy Huang */ 177bdc3750454efe59617b7df945eadd7e59bee954Andy Huang 187bdc3750454efe59617b7df945eadd7e59bee954Andy Huangpackage com.android.mail.utils; 197bdc3750454efe59617b7df945eadd7e59bee954Andy Huang 207bdc3750454efe59617b7df945eadd7e59bee954Andy Huangimport com.google.common.collect.Lists; 217bdc3750454efe59617b7df945eadd7e59bee954Andy Huangimport com.google.common.collect.Maps; 227bdc3750454efe59617b7df945eadd7e59bee954Andy Huang 237bdc3750454efe59617b7df945eadd7e59bee954Andy Huangimport java.util.Deque; 247bdc3750454efe59617b7df945eadd7e59bee954Andy Huangimport java.util.Map; 257bdc3750454efe59617b7df945eadd7e59bee954Andy Huang 267bdc3750454efe59617b7df945eadd7e59bee954Andy Huang/** 277bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * A Map of Deques. Each entry at key K has a deque of values V. 287bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * 297bdc3750454efe59617b7df945eadd7e59bee954Andy Huang */ 307bdc3750454efe59617b7df945eadd7e59bee954Andy Huangpublic class DequeMap<K, V> { 317bdc3750454efe59617b7df945eadd7e59bee954Andy Huang 327bdc3750454efe59617b7df945eadd7e59bee954Andy Huang public interface Visitor<V> { 337bdc3750454efe59617b7df945eadd7e59bee954Andy Huang void visit(V item); 347bdc3750454efe59617b7df945eadd7e59bee954Andy Huang } 357bdc3750454efe59617b7df945eadd7e59bee954Andy Huang 367bdc3750454efe59617b7df945eadd7e59bee954Andy Huang private final Map<K, Deque<V>> mMap = Maps.newHashMap(); 377bdc3750454efe59617b7df945eadd7e59bee954Andy Huang 387bdc3750454efe59617b7df945eadd7e59bee954Andy Huang /** 397bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * Add a value V to the deque stored under key K. 407bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * 417bdc3750454efe59617b7df945eadd7e59bee954Andy Huang */ 427bdc3750454efe59617b7df945eadd7e59bee954Andy Huang public void add(K key, V item) { 437bdc3750454efe59617b7df945eadd7e59bee954Andy Huang Deque<V> pile = mMap.get(key); 447bdc3750454efe59617b7df945eadd7e59bee954Andy Huang if (pile == null) { 457bdc3750454efe59617b7df945eadd7e59bee954Andy Huang pile = Lists.newLinkedList(); 467bdc3750454efe59617b7df945eadd7e59bee954Andy Huang mMap.put(key, pile); 477bdc3750454efe59617b7df945eadd7e59bee954Andy Huang } 487bdc3750454efe59617b7df945eadd7e59bee954Andy Huang pile.add(item); 497bdc3750454efe59617b7df945eadd7e59bee954Andy Huang } 507bdc3750454efe59617b7df945eadd7e59bee954Andy Huang 517bdc3750454efe59617b7df945eadd7e59bee954Andy Huang /** 527bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * Removes and returns the first value V from the deque of Vs for key K, or null if no such Vs 537bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * exist. 547bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * 557bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * @see Deque#poll() 567bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * 577bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * @param key 587bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * @return a V, or null 597bdc3750454efe59617b7df945eadd7e59bee954Andy Huang */ 607bdc3750454efe59617b7df945eadd7e59bee954Andy Huang public V poll(K key) { 617bdc3750454efe59617b7df945eadd7e59bee954Andy Huang final Deque<V> pile = mMap.get(key); 627bdc3750454efe59617b7df945eadd7e59bee954Andy Huang if (pile == null) { 637bdc3750454efe59617b7df945eadd7e59bee954Andy Huang return null; 647bdc3750454efe59617b7df945eadd7e59bee954Andy Huang } 657bdc3750454efe59617b7df945eadd7e59bee954Andy Huang return pile.poll(); 667bdc3750454efe59617b7df945eadd7e59bee954Andy Huang } 677bdc3750454efe59617b7df945eadd7e59bee954Andy Huang 688fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang /** 698fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang * Returns, but does not remove, the first value V from the deque of Vs for key K, or null if 708fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang * no such Vs exist. 718fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang * 728fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang * @see Deque#peek() 738fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang * 748fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang * @param key 758fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang * @return a V, or null 768fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang */ 778fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang public V peek(K key) { 788fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang final Deque<V> pile = mMap.get(key); 798fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang if (pile == null) { 808fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang return null; 818fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang } 828fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang return pile.peek(); 838fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang } 848fdce82be7c643375470cd6dc48ff531f9175dd0Andy Huang 857bdc3750454efe59617b7df945eadd7e59bee954Andy Huang public void clear() { 867bdc3750454efe59617b7df945eadd7e59bee954Andy Huang mMap.clear(); 877bdc3750454efe59617b7df945eadd7e59bee954Andy Huang } 887bdc3750454efe59617b7df945eadd7e59bee954Andy Huang 897bdc3750454efe59617b7df945eadd7e59bee954Andy Huang /** 907bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * Allows a {@link Visitor} to operate on each value V in this structure, irrespective of each 917bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * value's key. Modifying this map during iteration is not supported. Iteration order is not 927bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * guaranteed. 937bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * 947bdc3750454efe59617b7df945eadd7e59bee954Andy Huang * @param visitor 957bdc3750454efe59617b7df945eadd7e59bee954Andy Huang */ 967bdc3750454efe59617b7df945eadd7e59bee954Andy Huang // An iterator would also suffice, but this is easier to write and understand. 977bdc3750454efe59617b7df945eadd7e59bee954Andy Huang public void visitAll(Visitor<V> visitor) { 987bdc3750454efe59617b7df945eadd7e59bee954Andy Huang for (Map.Entry<K, Deque<V>> entry : mMap.entrySet()) { 997bdc3750454efe59617b7df945eadd7e59bee954Andy Huang for (V item : entry.getValue()) { 1007bdc3750454efe59617b7df945eadd7e59bee954Andy Huang visitor.visit(item); 1017bdc3750454efe59617b7df945eadd7e59bee954Andy Huang } 1027bdc3750454efe59617b7df945eadd7e59bee954Andy Huang } 1037bdc3750454efe59617b7df945eadd7e59bee954Andy Huang } 1047bdc3750454efe59617b7df945eadd7e59bee954Andy Huang 1057bdc3750454efe59617b7df945eadd7e59bee954Andy Huang} 106