RegularImmutableSortedMultiset.java revision 7dd252788645e940eada959bdde927426e2531c9
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 */ 307dd252788645e940eada959bdde927426e2531c9Paul Duffin@SuppressWarnings("serial") 317dd252788645e940eada959bdde927426e2531c9Paul Duffin// uses writeReplace, not default serialization 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertfinal class RegularImmutableSortedMultiset<E> extends ImmutableSortedMultiset<E> { 337dd252788645e940eada959bdde927426e2531c9Paul Duffin private final transient RegularImmutableSortedSet<E> elementSet; 347dd252788645e940eada959bdde927426e2531c9Paul Duffin private final transient int[] counts; 357dd252788645e940eada959bdde927426e2531c9Paul Duffin private final transient long[] cumulativeCounts; 367dd252788645e940eada959bdde927426e2531c9Paul Duffin private final transient int offset; 377dd252788645e940eada959bdde927426e2531c9Paul Duffin private final transient int length; 38dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 397dd252788645e940eada959bdde927426e2531c9Paul Duffin RegularImmutableSortedMultiset(RegularImmutableSortedSet<E> elementSet, int[] counts, 407dd252788645e940eada959bdde927426e2531c9Paul Duffin long[] cumulativeCounts, int offset, int length) { 417dd252788645e940eada959bdde927426e2531c9Paul Duffin this.elementSet = elementSet; 427dd252788645e940eada959bdde927426e2531c9Paul Duffin this.counts = counts; 437dd252788645e940eada959bdde927426e2531c9Paul Duffin this.cumulativeCounts = cumulativeCounts; 447dd252788645e940eada959bdde927426e2531c9Paul Duffin this.offset = offset; 457dd252788645e940eada959bdde927426e2531c9Paul Duffin this.length = length; 46dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 47dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 487dd252788645e940eada959bdde927426e2531c9Paul Duffin private Entry<E> getEntry(int index) { 497dd252788645e940eada959bdde927426e2531c9Paul Duffin return Multisets.immutableEntry(elementSet.asList().get(index), counts[offset + index]); 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 527dd252788645e940eada959bdde927426e2531c9Paul Duffin public Entry<E> firstEntry() { 537dd252788645e940eada959bdde927426e2531c9Paul Duffin return getEntry(0); 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 567dd252788645e940eada959bdde927426e2531c9Paul Duffin public Entry<E> lastEntry() { 577dd252788645e940eada959bdde927426e2531c9Paul Duffin return getEntry(length - 1); 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 607dd252788645e940eada959bdde927426e2531c9Paul Duffin public int count(@Nullable Object element) { 617dd252788645e940eada959bdde927426e2531c9Paul Duffin int index = elementSet.indexOf(element); 627dd252788645e940eada959bdde927426e2531c9Paul Duffin return (index == -1) ? 0 : counts[index + offset]; 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 657dd252788645e940eada959bdde927426e2531c9Paul Duffin public int size() { 667dd252788645e940eada959bdde927426e2531c9Paul Duffin long size = cumulativeCounts[offset + length] - cumulativeCounts[offset]; 677dd252788645e940eada959bdde927426e2531c9Paul Duffin return Ints.saturatedCast(size); 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 717dd252788645e940eada959bdde927426e2531c9Paul Duffin public ImmutableSortedSet<E> elementSet() { 727dd252788645e940eada959bdde927426e2531c9Paul Duffin return elementSet; 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 767dd252788645e940eada959bdde927426e2531c9Paul Duffin public ImmutableSortedMultiset<E> headMultiset(E upperBound, BoundType boundType) { 777dd252788645e940eada959bdde927426e2531c9Paul Duffin return getSubMultiset(0, elementSet.headIndex(upperBound, checkNotNull(boundType) == CLOSED)); 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 817dd252788645e940eada959bdde927426e2531c9Paul Duffin public ImmutableSortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType) { 827dd252788645e940eada959bdde927426e2531c9Paul Duffin return getSubMultiset(elementSet.tailIndex(lowerBound, checkNotNull(boundType) == CLOSED), 837dd252788645e940eada959bdde927426e2531c9Paul Duffin length); 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 867dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableSortedMultiset<E> getSubMultiset(int from, int to) { 877dd252788645e940eada959bdde927426e2531c9Paul Duffin checkPositionIndexes(from, to, length); 887dd252788645e940eada959bdde927426e2531c9Paul Duffin if (from == to) { 897dd252788645e940eada959bdde927426e2531c9Paul Duffin return emptyMultiset(comparator()); 907dd252788645e940eada959bdde927426e2531c9Paul Duffin } else if (from == 0 && to == length) { 917dd252788645e940eada959bdde927426e2531c9Paul Duffin return this; 927dd252788645e940eada959bdde927426e2531c9Paul Duffin } else { 937dd252788645e940eada959bdde927426e2531c9Paul Duffin RegularImmutableSortedSet<E> subElementSet = (RegularImmutableSortedSet<E>) elementSet 947dd252788645e940eada959bdde927426e2531c9Paul Duffin .getSubSet(from, to); 957dd252788645e940eada959bdde927426e2531c9Paul Duffin return new RegularImmutableSortedMultiset<E>(subElementSet, counts, cumulativeCounts, offset 967dd252788645e940eada959bdde927426e2531c9Paul Duffin + from, to - from); 977dd252788645e940eada959bdde927426e2531c9Paul Duffin } 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 100dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin @Override 1017dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableSet<Entry<E>> createEntrySet() { 1027dd252788645e940eada959bdde927426e2531c9Paul Duffin return new EntrySet(); 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1057dd252788645e940eada959bdde927426e2531c9Paul Duffin private final class EntrySet extends ImmutableMultiset<E>.EntrySet { 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1077dd252788645e940eada959bdde927426e2531c9Paul Duffin public int size() { 1087dd252788645e940eada959bdde927426e2531c9Paul Duffin return length; 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1117dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 1127dd252788645e940eada959bdde927426e2531c9Paul Duffin public UnmodifiableIterator<Entry<E>> iterator() { 1137dd252788645e940eada959bdde927426e2531c9Paul Duffin return asList().iterator(); 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1167dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 1177dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableList<Entry<E>> createAsList() { 1187dd252788645e940eada959bdde927426e2531c9Paul Duffin return new ImmutableAsList<Entry<E>>() { 1197dd252788645e940eada959bdde927426e2531c9Paul Duffin 1207dd252788645e940eada959bdde927426e2531c9Paul Duffin public Entry<E> get(int index) { 1217dd252788645e940eada959bdde927426e2531c9Paul Duffin return getEntry(index); 1227dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1237dd252788645e940eada959bdde927426e2531c9Paul Duffin 1247dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 1257dd252788645e940eada959bdde927426e2531c9Paul Duffin ImmutableCollection<Entry<E>> delegateCollection() { 1267dd252788645e940eada959bdde927426e2531c9Paul Duffin return EntrySet.this; 1277dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1287dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 129dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 130dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 131dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 1327dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 1337dd252788645e940eada959bdde927426e2531c9Paul Duffin boolean isPartialView() { 1347dd252788645e940eada959bdde927426e2531c9Paul Duffin return offset > 0 || length < counts.length; 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 137