1 /* 2 * Copyright (C) 2012 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect; 18 19 import java.util.AbstractMap; 20 import java.util.Iterator; 21 import java.util.Map; 22 import java.util.NavigableMap; 23 import java.util.NavigableSet; 24 import java.util.NoSuchElementException; 25 import java.util.Set; 26 import java.util.SortedMap; 27 28 import javax.annotation.Nullable; 29 30 /** 31 * Skeletal implementation of {@link NavigableMap}. 32 * 33 * @author Louis Wasserman 34 */ 35 abstract class AbstractNavigableMap<K, V> extends AbstractMap<K, V> implements NavigableMap<K, V> { 36 37 @Override 38 @Nullable 39 public abstract V get(@Nullable Object key); 40 41 @Override 42 @Nullable 43 public Entry<K, V> firstEntry() { 44 return Iterators.getNext(entryIterator(), null); 45 } 46 47 @Override 48 @Nullable 49 public Entry<K, V> lastEntry() { 50 return Iterators.getNext(descendingEntryIterator(), null); 51 } 52 53 @Override 54 @Nullable 55 public Entry<K, V> pollFirstEntry() { 56 return Iterators.pollNext(entryIterator()); 57 } 58 59 @Override 60 @Nullable 61 public Entry<K, V> pollLastEntry() { 62 return Iterators.pollNext(descendingEntryIterator()); 63 } 64 65 @Override 66 public K firstKey() { 67 Entry<K, V> entry = firstEntry(); 68 if (entry == null) { 69 throw new NoSuchElementException(); 70 } else { 71 return entry.getKey(); 72 } 73 } 74 75 @Override 76 public K lastKey() { 77 Entry<K, V> entry = lastEntry(); 78 if (entry == null) { 79 throw new NoSuchElementException(); 80 } else { 81 return entry.getKey(); 82 } 83 } 84 85 @Override 86 @Nullable 87 public Entry<K, V> lowerEntry(K key) { 88 return headMap(key, false).lastEntry(); 89 } 90 91 @Override 92 @Nullable 93 public Entry<K, V> floorEntry(K key) { 94 return headMap(key, true).lastEntry(); 95 } 96 97 @Override 98 @Nullable 99 public Entry<K, V> ceilingEntry(K key) { 100 return tailMap(key, true).firstEntry(); 101 } 102 103 @Override 104 @Nullable 105 public Entry<K, V> higherEntry(K key) { 106 return tailMap(key, false).firstEntry(); 107 } 108 109 @Override 110 public K lowerKey(K key) { 111 return Maps.keyOrNull(lowerEntry(key)); 112 } 113 114 @Override 115 public K floorKey(K key) { 116 return Maps.keyOrNull(floorEntry(key)); 117 } 118 119 @Override 120 public K ceilingKey(K key) { 121 return Maps.keyOrNull(ceilingEntry(key)); 122 } 123 124 @Override 125 public K higherKey(K key) { 126 return Maps.keyOrNull(higherEntry(key)); 127 } 128 129 abstract Iterator<Entry<K, V>> entryIterator(); 130 131 abstract Iterator<Entry<K, V>> descendingEntryIterator(); 132 133 @Override 134 public SortedMap<K, V> subMap(K fromKey, K toKey) { 135 return subMap(fromKey, true, toKey, false); 136 } 137 138 @Override 139 public SortedMap<K, V> headMap(K toKey) { 140 return headMap(toKey, false); 141 } 142 143 @Override 144 public SortedMap<K, V> tailMap(K fromKey) { 145 return tailMap(fromKey, true); 146 } 147 148 @Override 149 public NavigableSet<K> navigableKeySet() { 150 return new Maps.NavigableKeySet<K, V>(this); 151 } 152 153 @Override 154 public Set<K> keySet() { 155 return navigableKeySet(); 156 } 157 158 @Override 159 public abstract int size(); 160 161 @Override 162 public Set<Entry<K, V>> entrySet() { 163 return new Maps.EntrySet<K, V>() { 164 @Override 165 Map<K, V> map() { 166 return AbstractNavigableMap.this; 167 } 168 169 @Override 170 public Iterator<Entry<K, V>> iterator() { 171 return entryIterator(); 172 } 173 }; 174 } 175 176 @Override 177 public NavigableSet<K> descendingKeySet() { 178 return descendingMap().navigableKeySet(); 179 } 180 181 @Override 182 public NavigableMap<K, V> descendingMap() { 183 return new DescendingMap(); 184 } 185 186 private final class DescendingMap extends Maps.DescendingMap<K, V> { 187 @Override 188 NavigableMap<K, V> forward() { 189 return AbstractNavigableMap.this; 190 } 191 192 @Override 193 Iterator<Entry<K, V>> entryIterator() { 194 return descendingEntryIterator(); 195 } 196 } 197 198 } 199
