11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2011 The Guava Authors 37dd252788645e940eada959bdde927426e2531c9Paul Duffin * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); you may not 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * use this file except in compliance with the License. You may obtain a copy of 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the License at 77dd252788645e940eada959bdde927426e2531c9Paul Duffin * 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 97dd252788645e940eada959bdde927426e2531c9Paul Duffin * 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, WITHOUT 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * License for the specific language governing permissions and limitations under 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 197dd252788645e940eada959bdde927426e2531c9Paul Duffinimport static com.google.common.collect.BoundType.CLOSED; 207dd252788645e940eada959bdde927426e2531c9Paul Duffinimport static com.google.common.collect.BoundType.OPEN; 217dd252788645e940eada959bdde927426e2531c9Paul Duffin 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 230888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport com.google.common.annotations.GwtIncompatible; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.Multiset.Entry; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Comparator; 270888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.util.Iterator; 283ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffinimport java.util.NavigableSet; 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.NoSuchElementException; 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.SortedSet; 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 320888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport javax.annotation.Nullable; 330888a09821a98ac0680fad765217302858e70fa4Paul Duffin 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Provides static utility methods for creating and working with 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link SortedMultiset} instances. 377dd252788645e940eada959bdde927426e2531c9Paul Duffin * 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 407dd252788645e940eada959bdde927426e2531c9Paul Duffin@GwtCompatible(emulated = true) 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertfinal class SortedMultisets { 420888a09821a98ac0680fad765217302858e70fa4Paul Duffin private SortedMultisets() { 430888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * A skeleton implementation for {@link SortedMultiset#elementSet}. 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 480888a09821a98ac0680fad765217302858e70fa4Paul Duffin static class ElementSet<E> extends Multisets.ElementSet<E> implements 490888a09821a98ac0680fad765217302858e70fa4Paul Duffin SortedSet<E> { 507dd252788645e940eada959bdde927426e2531c9Paul Duffin private final SortedMultiset<E> multiset; 517dd252788645e940eada959bdde927426e2531c9Paul Duffin 527dd252788645e940eada959bdde927426e2531c9Paul Duffin ElementSet(SortedMultiset<E> multiset) { 537dd252788645e940eada959bdde927426e2531c9Paul Duffin this.multiset = multiset; 547dd252788645e940eada959bdde927426e2531c9Paul Duffin } 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 560888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override final SortedMultiset<E> multiset() { 577dd252788645e940eada959bdde927426e2531c9Paul Duffin return multiset; 587dd252788645e940eada959bdde927426e2531c9Paul Duffin } 597dd252788645e940eada959bdde927426e2531c9Paul Duffin 600888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Comparator<? super E> comparator() { 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return multiset().comparator(); 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 640888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public SortedSet<E> subSet(E fromElement, E toElement) { 657dd252788645e940eada959bdde927426e2531c9Paul Duffin return multiset().subMultiset(fromElement, CLOSED, toElement, OPEN).elementSet(); 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 680888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public SortedSet<E> headSet(E toElement) { 697dd252788645e940eada959bdde927426e2531c9Paul Duffin return multiset().headMultiset(toElement, OPEN).elementSet(); 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 720888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public SortedSet<E> tailSet(E fromElement) { 737dd252788645e940eada959bdde927426e2531c9Paul Duffin return multiset().tailMultiset(fromElement, CLOSED).elementSet(); 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 760888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public E first() { 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return getElementOrThrow(multiset().firstEntry()); 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 800888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public E last() { 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return getElementOrThrow(multiset().lastEntry()); 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 853ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin /** 863ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * A skeleton navigable implementation for {@link SortedMultiset#elementSet}. 873ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin */ 883ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @GwtIncompatible("Navigable") 893ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin static class NavigableElementSet<E> extends ElementSet<E> implements NavigableSet<E> { 903ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin NavigableElementSet(SortedMultiset<E> multiset) { 913ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin super(multiset); 923ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 933ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 943ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 953ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public E lower(E e) { 963ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return getElementOrNull(multiset().headMultiset(e, OPEN).lastEntry()); 973ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 983ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 993ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1003ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public E floor(E e) { 1013ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return getElementOrNull(multiset().headMultiset(e, CLOSED).lastEntry()); 1023ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1033ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1043ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1053ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public E ceiling(E e) { 1063ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return getElementOrNull(multiset().tailMultiset(e, CLOSED).firstEntry()); 1073ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1083ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1093ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1103ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public E higher(E e) { 1113ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return getElementOrNull(multiset().tailMultiset(e, OPEN).firstEntry()); 1123ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1133ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1143ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1153ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public NavigableSet<E> descendingSet() { 1163ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return new NavigableElementSet<E>(multiset().descendingMultiset()); 1173ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1183ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1193ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1203ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public Iterator<E> descendingIterator() { 1213ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return descendingSet().iterator(); 1223ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1233ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1243ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1253ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public E pollFirst() { 1263ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return getElementOrNull(multiset().pollFirstEntry()); 1273ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1283ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1293ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1303ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public E pollLast() { 1313ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return getElementOrNull(multiset().pollLastEntry()); 1323ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1333ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1343ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1353ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public NavigableSet<E> subSet( 1363ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { 1373ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return new NavigableElementSet<E>(multiset().subMultiset( 1383ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin fromElement, BoundType.forBoolean(fromInclusive), 1393ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin toElement, BoundType.forBoolean(toInclusive))); 1403ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1413ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1423ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1433ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public NavigableSet<E> headSet(E toElement, boolean inclusive) { 1443ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return new NavigableElementSet<E>( 1453ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin multiset().headMultiset(toElement, BoundType.forBoolean(inclusive))); 1463ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1473ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1483ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin @Override 1493ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { 1503ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin return new NavigableElementSet<E>( 1513ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin multiset().tailMultiset(fromElement, BoundType.forBoolean(inclusive))); 1523ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1533ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1543ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 155dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin private static <E> E getElementOrThrow(Entry<E> entry) { 156dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin if (entry == null) { 157dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin throw new NoSuchElementException(); 158dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 159dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin return entry.getElement(); 160dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 1610888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1620888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static <E> E getElementOrNull(@Nullable Entry<E> entry) { 1630888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (entry == null) ? null : entry.getElement(); 1640888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 166