1/*
2 * Copyright (C) 2008 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 static com.google.common.base.Preconditions.checkNotNull;
20
21import com.google.common.annotations.GwtCompatible;
22import com.google.common.base.Supplier;
23
24import java.util.Comparator;
25import java.util.Map;
26import java.util.Set;
27import java.util.SortedMap;
28import java.util.SortedSet;
29
30/**
31 * Implementation of {@code Table} whose iteration ordering across row keys is
32 * sorted by their natural ordering or by a supplied comparator. Note that
33 * iterations across the columns keys for a single row key may or may not be
34 * ordered, depending on the implementation. When rows and columns are both
35 * sorted, it's easier to use the {@link TreeBasedTable} subclass.
36 *
37 * <p>The {@link #rowKeySet} method returns a {@link SortedSet} and the {@link
38 * #rowMap} method returns a {@link SortedMap}, instead of the {@link Set} and
39 * {@link Map} specified by the {@link Table} interface.
40 *
41 * <p>Null keys and values are not supported.
42 *
43 * <p>See the {@link StandardTable} superclass for more information about the
44 * behavior of this class.
45 *
46 * @author Jared Levy
47 */
48@GwtCompatible
49class StandardRowSortedTable<R, C, V> extends StandardTable<R, C, V>
50    implements RowSortedTable<R, C, V> {
51  /*
52   * TODO(jlevy): Consider adding headTable, tailTable, and subTable methods,
53   * which return a Table view with rows keys in a given range. Create a
54   * RowSortedTable subinterface with the revised methods?
55   */
56
57  StandardRowSortedTable(SortedMap<R, Map<C, V>> backingMap,
58      Supplier<? extends Map<C, V>> factory) {
59    super(backingMap, factory);
60  }
61
62  private SortedMap<R, Map<C, V>> sortedBackingMap() {
63    return (SortedMap<R, Map<C, V>>) backingMap;
64  }
65
66  private transient SortedSet<R> rowKeySet;
67
68  /**
69   * {@inheritDoc}
70   *
71   * <p>This method returns a {@link SortedSet}, instead of the {@code Set}
72   * specified in the {@link Table} interface.
73   */
74  @Override public SortedSet<R> rowKeySet() {
75    SortedSet<R> result = rowKeySet;
76    return (result == null) ? rowKeySet = new RowKeySortedSet() : result;
77  }
78
79  private class RowKeySortedSet extends RowKeySet implements SortedSet<R> {
80    @Override
81    public Comparator<? super R> comparator() {
82      return sortedBackingMap().comparator();
83    }
84
85    @Override
86    public R first() {
87      return sortedBackingMap().firstKey();
88    }
89
90    @Override
91    public R last() {
92      return sortedBackingMap().lastKey();
93    }
94
95    @Override
96    public SortedSet<R> headSet(R toElement) {
97      checkNotNull(toElement);
98      return new StandardRowSortedTable<R, C, V>(
99          sortedBackingMap().headMap(toElement), factory).rowKeySet();
100    }
101
102    @Override
103    public SortedSet<R> subSet(R fromElement, R toElement) {
104      checkNotNull(fromElement);
105      checkNotNull(toElement);
106      return new StandardRowSortedTable<R, C, V>(
107          sortedBackingMap().subMap(fromElement, toElement), factory)
108          .rowKeySet();
109    }
110
111    @Override
112    public SortedSet<R> tailSet(R fromElement) {
113      checkNotNull(fromElement);
114      return new StandardRowSortedTable<R, C, V>(
115          sortedBackingMap().tailMap(fromElement), factory).rowKeySet();
116    }
117  }
118
119  private transient RowSortedMap rowMap;
120
121  /**
122   * {@inheritDoc}
123   *
124   * <p>This method returns a {@link SortedMap}, instead of the {@code Map}
125   * specified in the {@link Table} interface.
126   */
127  @Override public SortedMap<R, Map<C, V>> rowMap() {
128    RowSortedMap result = rowMap;
129    return (result == null) ? rowMap = new RowSortedMap() : result;
130  }
131
132  private class RowSortedMap extends RowMap implements SortedMap<R, Map<C, V>> {
133    @Override
134    public Comparator<? super R> comparator() {
135      return sortedBackingMap().comparator();
136    }
137
138    @Override
139    public R firstKey() {
140      return sortedBackingMap().firstKey();
141    }
142
143    @Override
144    public R lastKey() {
145      return sortedBackingMap().lastKey();
146    }
147
148    @Override
149    public SortedMap<R, Map<C, V>> headMap(R toKey) {
150      checkNotNull(toKey);
151      return new StandardRowSortedTable<R, C, V>(
152          sortedBackingMap().headMap(toKey), factory).rowMap();
153    }
154
155    @Override
156    public SortedMap<R, Map<C, V>> subMap(R fromKey, R toKey) {
157      checkNotNull(fromKey);
158      checkNotNull(toKey);
159      return new StandardRowSortedTable<R, C, V>(
160          sortedBackingMap().subMap(fromKey, toKey), factory).rowMap();
161    }
162
163    @Override
164    public SortedMap<R, Map<C, V>> tailMap(R fromKey) {
165      checkNotNull(fromKey);
166      return new StandardRowSortedTable<R, C, V>(
167          sortedBackingMap().tailMap(fromKey), factory).rowMap();
168    }
169  }
170
171  private static final long serialVersionUID = 0;
172}
173