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