RegularImmutableSortedMultiset.java revision 3c77433663281544363151bf284b0240dfd22a42 
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  private Entry<E> getEntry(int index) {
52    return Multisets.immutableEntry(
53        elementSet.asList().get(index),
54        counts[offset + index]);
55  }
56
57  @Override
58  public Entry<E> firstEntry() {
59    return getEntry(0);
60  }
61
62  @Override
63  public Entry<E> lastEntry() {
64    return getEntry(length - 1);
65  }
66
67  @Override
68  public int count(@Nullable Object element) {
69    int index = elementSet.indexOf(element);
70    return (index == -1) ? 0 : counts[index + offset];
71  }
72
73  @Override
74  public int size() {
75    long size = cumulativeCounts[offset + length] - cumulativeCounts[offset];
76    return Ints.saturatedCast(size);
77  }
78
79  @Override
80  public ImmutableSortedSet<E> elementSet() {
81    return elementSet;
82  }
83
84  @Override
85  public ImmutableSortedMultiset<E> headMultiset(E upperBound, BoundType boundType) {
86    return getSubMultiset(0, elementSet.headIndex(upperBound, checkNotNull(boundType) == CLOSED));
87  }
88
89  @Override
90  public ImmutableSortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType) {
91    return getSubMultiset(elementSet.tailIndex(lowerBound, checkNotNull(boundType) == CLOSED),
92        length);
93  }
94
95  ImmutableSortedMultiset<E> getSubMultiset(int from, int to) {
96    checkPositionIndexes(from, to, length);
97    if (from == to) {
98      return emptyMultiset(comparator());
99    } else if (from == 0 && to == length) {
100      return this;
101    } else {
102      RegularImmutableSortedSet<E> subElementSet =
103          (RegularImmutableSortedSet<E>) elementSet.getSubSet(from, to);
104      return new RegularImmutableSortedMultiset<E>(
105          subElementSet, counts, cumulativeCounts, offset + from, to - from);
106    }
107  }
108
109  @Override
110  ImmutableSet<Entry<E>> createEntrySet() {
111    return new EntrySet();
112  }
113
114  private final class EntrySet extends ImmutableMultiset<E>.EntrySet {
115    @Override
116    public int size() {
117      return length;
118    }
119
120    @Override
121    public UnmodifiableIterator<Entry<E>> iterator() {
122      return asList().iterator();
123    }
124
125    @Override
126    ImmutableList<Entry<E>> createAsList() {
127      return new ImmutableAsList<Entry<E>>() {
128        @Override
129        public Entry<E> get(int index) {
130          return getEntry(index);
131        }
132
133        @Override
134        ImmutableCollection<Entry<E>> delegateCollection() {
135          return EntrySet.this;
136        }
137      };
138    }
139  }
140
141  @Override
142  boolean isPartialView() {
143    return offset > 0 || length < counts.length;
144  }
145}
146