11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2008 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you may not use this file except in compliance with the License. 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * You may obtain a copy of the License at 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * distributed under the License is distributed on an "AS IS" BASIS, 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * See the License for the specific language governing permissions and 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkNotNull; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Supplier; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Comparator; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Map; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Set; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.SortedMap; 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.SortedSet; 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Implementation of {@code Table} whose iteration ordering across row keys is 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * sorted by their natural ordering or by a supplied comparator. Note that 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * iterations across the columns keys for a single row key may or may not be 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ordered, depending on the implementation. When rows and columns are both 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * sorted, it's easier to use the {@link TreeBasedTable} subclass. 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The {@link #rowKeySet} method returns a {@link SortedSet} and the {@link 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * #rowMap} method returns a {@link SortedMap}, instead of the {@link Set} and 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link Map} specified by the {@link Table} interface. 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Null keys and values are not supported. 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>See the {@link StandardTable} superclass for more information about the 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * behavior of this class. 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Jared Levy 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertclass StandardRowSortedTable<R, C, V> extends StandardTable<R, C, V> 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert implements RowSortedTable<R, C, V> { 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * TODO(jlevy): Consider adding headTable, tailTable, and subTable methods, 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * which return a Table view with rows keys in a given range. Create a 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * RowSortedTable subinterface with the revised methods? 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert StandardRowSortedTable(SortedMap<R, Map<C, V>> backingMap, 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Supplier<? extends Map<C, V>> factory) { 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super(backingMap, factory); 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private SortedMap<R, Map<C, V>> sortedBackingMap() { 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (SortedMap<R, Map<C, V>>) backingMap; 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private transient SortedSet<R> rowKeySet; 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@inheritDoc} 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This method returns a {@link SortedSet}, instead of the {@code Set} 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * specified in the {@link Table} interface. 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public SortedSet<R> rowKeySet() { 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedSet<R> result = rowKeySet; 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (result == null) ? rowKeySet = new RowKeySortedSet() : result; 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private class RowKeySortedSet extends RowKeySet implements SortedSet<R> { 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Comparator<? super R> comparator() { 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return sortedBackingMap().comparator(); 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public R first() { 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return sortedBackingMap().firstKey(); 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public R last() { 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return sortedBackingMap().lastKey(); 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public SortedSet<R> headSet(R toElement) { 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(toElement); 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new StandardRowSortedTable<R, C, V>( 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert sortedBackingMap().headMap(toElement), factory).rowKeySet(); 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public SortedSet<R> subSet(R fromElement, R toElement) { 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(fromElement); 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(toElement); 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new StandardRowSortedTable<R, C, V>( 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert sortedBackingMap().subMap(fromElement, toElement), factory) 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert .rowKeySet(); 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public SortedSet<R> tailSet(R fromElement) { 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(fromElement); 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new StandardRowSortedTable<R, C, V>( 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert sortedBackingMap().tailMap(fromElement), factory).rowKeySet(); 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private transient RowSortedMap rowMap; 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@inheritDoc} 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This method returns a {@link SortedMap}, instead of the {@code Map} 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * specified in the {@link Table} interface. 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public SortedMap<R, Map<C, V>> rowMap() { 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert RowSortedMap result = rowMap; 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (result == null) ? rowMap = new RowSortedMap() : result; 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private class RowSortedMap extends RowMap implements SortedMap<R, Map<C, V>> { 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Comparator<? super R> comparator() { 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return sortedBackingMap().comparator(); 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public R firstKey() { 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return sortedBackingMap().firstKey(); 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public R lastKey() { 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return sortedBackingMap().lastKey(); 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public SortedMap<R, Map<C, V>> headMap(R toKey) { 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(toKey); 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new StandardRowSortedTable<R, C, V>( 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert sortedBackingMap().headMap(toKey), factory).rowMap(); 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public SortedMap<R, Map<C, V>> subMap(R fromKey, R toKey) { 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(fromKey); 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(toKey); 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new StandardRowSortedTable<R, C, V>( 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert sortedBackingMap().subMap(fromKey, toKey), factory).rowMap(); 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public SortedMap<R, Map<C, V>> tailMap(R fromKey) { 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(fromKey); 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new StandardRowSortedTable<R, C, V>( 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert sortedBackingMap().tailMap(fromKey), factory).rowMap(); 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final long serialVersionUID = 0; 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 173