1/* 2 * Copyright (C) 2011 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 5 * in compliance with the License. You may obtain a copy of the License at 6 * 7 * http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * Unless required by applicable law or agreed to in writing, software distributed under the 10 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 11 * express or implied. See the License for the specific language governing permissions and 12 * limitations under the License. 13 */ 14 15package com.google.common.collect; 16 17import static com.google.common.base.Preconditions.checkNotNull; 18import static com.google.common.base.Preconditions.checkPositionIndexes; 19import static com.google.common.collect.BoundType.CLOSED; 20 21import com.google.common.primitives.Ints; 22 23import javax.annotation.Nullable; 24 25/** 26 * An immutable sorted multiset with one or more distinct elements. 27 * 28 * @author Louis Wasserman 29 */ 30@SuppressWarnings("serial") // uses writeReplace, not default serialization 31final class RegularImmutableSortedMultiset<E> extends ImmutableSortedMultiset<E> { 32 private final transient RegularImmutableSortedSet<E> elementSet; 33 private final transient int[] counts; 34 private final transient long[] cumulativeCounts; 35 private final transient int offset; 36 private final transient int length; 37 38 RegularImmutableSortedMultiset( 39 RegularImmutableSortedSet<E> elementSet, 40 int[] counts, 41 long[] cumulativeCounts, 42 int offset, 43 int length) { 44 this.elementSet = elementSet; 45 this.counts = counts; 46 this.cumulativeCounts = cumulativeCounts; 47 this.offset = offset; 48 this.length = length; 49 } 50 51 @Override 52 Entry<E> getEntry(int index) { 53 return Multisets.immutableEntry( 54 elementSet.asList().get(index), 55 counts[offset + index]); 56 } 57 58 @Override 59 public Entry<E> firstEntry() { 60 return getEntry(0); 61 } 62 63 @Override 64 public Entry<E> lastEntry() { 65 return getEntry(length - 1); 66 } 67 68 @Override 69 public int count(@Nullable Object element) { 70 int index = elementSet.indexOf(element); 71 return (index == -1) ? 0 : counts[index + offset]; 72 } 73 74 @Override 75 public int size() { 76 long size = cumulativeCounts[offset + length] - cumulativeCounts[offset]; 77 return Ints.saturatedCast(size); 78 } 79 80 @Override 81 public ImmutableSortedSet<E> elementSet() { 82 return elementSet; 83 } 84 85 @Override 86 public ImmutableSortedMultiset<E> headMultiset(E upperBound, BoundType boundType) { 87 return getSubMultiset(0, elementSet.headIndex(upperBound, checkNotNull(boundType) == CLOSED)); 88 } 89 90 @Override 91 public ImmutableSortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType) { 92 return getSubMultiset(elementSet.tailIndex(lowerBound, checkNotNull(boundType) == CLOSED), 93 length); 94 } 95 96 ImmutableSortedMultiset<E> getSubMultiset(int from, int to) { 97 checkPositionIndexes(from, to, length); 98 if (from == to) { 99 return emptyMultiset(comparator()); 100 } else if (from == 0 && to == length) { 101 return this; 102 } else { 103 RegularImmutableSortedSet<E> subElementSet = 104 (RegularImmutableSortedSet<E>) elementSet.getSubSet(from, to); 105 return new RegularImmutableSortedMultiset<E>( 106 subElementSet, counts, cumulativeCounts, offset + from, to - from); 107 } 108 } 109 110 @Override 111 boolean isPartialView() { 112 return offset > 0 || length < counts.length; 113 } 114} 115