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
17package com.google.common.collect;
18
19import java.util.AbstractMap;
20import java.util.Iterator;
21import java.util.Map;
22import java.util.NavigableMap;
23import java.util.NavigableSet;
24import java.util.NoSuchElementException;
25import java.util.Set;
26import java.util.SortedMap;
27
28import javax.annotation.Nullable;
29
30/**
31 * Skeletal implementation of {@link NavigableMap}.
32 *
33 * @author Louis Wasserman
34 */
35abstract 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