11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2011 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in compliance with the License. You may obtain a copy of the License at 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software distributed under the 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * express or implied. See the License for the specific language governing permissions and 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkNotNull; 187dd252788645e940eada959bdde927426e2531c9Paul Duffinimport static com.google.common.base.Preconditions.checkPositionIndexes; 197dd252788645e940eada959bdde927426e2531c9Paul Duffinimport static com.google.common.collect.BoundType.CLOSED; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.primitives.Ints; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport javax.annotation.Nullable; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * An immutable sorted multiset with one or more distinct elements. 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 300888a09821a98ac0680fad765217302858e70fa4Paul Duffin@SuppressWarnings("serial") // uses writeReplace, not default serialization 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertfinal class RegularImmutableSortedMultiset<E> extends ImmutableSortedMultiset<E> { 327dd252788645e940eada959bdde927426e2531c9Paul Duffin private final transient RegularImmutableSortedSet<E> elementSet; 337dd252788645e940eada959bdde927426e2531c9Paul Duffin private final transient int[] counts; 347dd252788645e940eada959bdde927426e2531c9Paul Duffin private final transient long[] cumulativeCounts; 357dd252788645e940eada959bdde927426e2531c9Paul Duffin private final transient int offset; 367dd252788645e940eada959bdde927426e2531c9Paul Duffin private final transient int length; 37dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 380888a09821a98ac0680fad765217302858e70fa4Paul Duffin RegularImmutableSortedMultiset( 390888a09821a98ac0680fad765217302858e70fa4Paul Duffin RegularImmutableSortedSet<E> elementSet, 400888a09821a98ac0680fad765217302858e70fa4Paul Duffin int[] counts, 410888a09821a98ac0680fad765217302858e70fa4Paul Duffin long[] cumulativeCounts, 420888a09821a98ac0680fad765217302858e70fa4Paul Duffin int offset, 430888a09821a98ac0680fad765217302858e70fa4Paul Duffin int length) { 447dd252788645e940eada959bdde927426e2531c9Paul Duffin this.elementSet = elementSet; 457dd252788645e940eada959bdde927426e2531c9Paul Duffin this.counts = counts; 467dd252788645e940eada959bdde927426e2531c9Paul Duffin this.cumulativeCounts = cumulativeCounts; 477dd252788645e940eada959bdde927426e2531c9Paul Duffin this.offset = offset; 487dd252788645e940eada959bdde927426e2531c9Paul Duffin this.length = length; 49dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 50dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 510888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 520888a09821a98ac0680fad765217302858e70fa4Paul Duffin Entry<E> getEntry(int index) { 530888a09821a98ac0680fad765217302858e70fa4Paul Duffin return Multisets.immutableEntry( 540888a09821a98ac0680fad765217302858e70fa4Paul Duffin elementSet.asList().get(index), 550888a09821a98ac0680fad765217302858e70fa4Paul Duffin counts[offset + index]); 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 580888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 597dd252788645e940eada959bdde927426e2531c9Paul Duffin public Entry<E> firstEntry() { 607dd252788645e940eada959bdde927426e2531c9Paul Duffin return getEntry(0); 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 630888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 647dd252788645e940eada959bdde927426e2531c9Paul Duffin public Entry<E> lastEntry() { 657dd252788645e940eada959bdde927426e2531c9Paul Duffin return getEntry(length - 1); 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 680888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 697dd252788645e940eada959bdde927426e2531c9Paul Duffin public int count(@Nullable Object element) { 707dd252788645e940eada959bdde927426e2531c9Paul Duffin int index = elementSet.indexOf(element); 717dd252788645e940eada959bdde927426e2531c9Paul Duffin return (index == -1) ? 0 : counts[index + offset]; 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 740888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 757dd252788645e940eada959bdde927426e2531c9Paul Duffin public int size() { 767dd252788645e940eada959bdde927426e2531c9Paul Duffin long size = cumulativeCounts[offset + length] - cumulativeCounts[offset]; 777dd252788645e940eada959bdde927426e2531c9Paul Duffin return Ints.saturatedCast(size); 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 817dd252788645e940eada959bdde927426e2531c9Paul Duffin public ImmutableSortedSet<E> elementSet() { 827dd252788645e940eada959bdde927426e2531c9Paul Duffin return elementSet; 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 867dd252788645e940eada959bdde927426e2531c9Paul Duffin public ImmutableSortedMultiset<E> headMultiset(E upperBound, BoundType boundType) { 877dd252788645e940eada959bdde927426e2531c9Paul Duffin return getSubMultiset(0, elementSet.headIndex(upperBound, checkNotNull(boundType) == CLOSED)); 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 917dd252788645e940eada959bdde927426e2531c9Paul Duffin public ImmutableSortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType) { 927dd252788645e940eada959bdde927426e2531c9Paul Duffin return getSubMultiset(elementSet.tailIndex(lowerBound, checkNotNull(boundType) == CLOSED), 937dd252788645e940eada959bdde927426e2531c9Paul Duffin length); 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 967dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableSortedMultiset<E> getSubMultiset(int from, int to) { 977dd252788645e940eada959bdde927426e2531c9Paul Duffin checkPositionIndexes(from, to, length); 987dd252788645e940eada959bdde927426e2531c9Paul Duffin if (from == to) { 997dd252788645e940eada959bdde927426e2531c9Paul Duffin return emptyMultiset(comparator()); 1007dd252788645e940eada959bdde927426e2531c9Paul Duffin } else if (from == 0 && to == length) { 1017dd252788645e940eada959bdde927426e2531c9Paul Duffin return this; 1027dd252788645e940eada959bdde927426e2531c9Paul Duffin } else { 1030888a09821a98ac0680fad765217302858e70fa4Paul Duffin RegularImmutableSortedSet<E> subElementSet = 1040888a09821a98ac0680fad765217302858e70fa4Paul Duffin (RegularImmutableSortedSet<E>) elementSet.getSubSet(from, to); 1050888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new RegularImmutableSortedMultiset<E>( 1060888a09821a98ac0680fad765217302858e70fa4Paul Duffin subElementSet, counts, cumulativeCounts, offset + from, to - from); 107dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 108dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 109dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 1107dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 1117dd252788645e940eada959bdde927426e2531c9Paul Duffin boolean isPartialView() { 1127dd252788645e940eada959bdde927426e2531c9Paul Duffin return offset > 0 || length < counts.length; 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 115