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.collect.SortedLists.KeyAbsentBehavior.INVERTED_INSERTION_INDEX;
19import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_HIGHER;
20import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_LOWER;
21import static com.google.common.collect.SortedLists.KeyPresentBehavior.ANY_PRESENT;
22
23import com.google.common.primitives.Ints;
24
25import java.util.Comparator;
26import java.util.List;
27
28import javax.annotation.Nullable;
29
30/**
31 * An immutable sorted multiset with one or more distinct elements.
32 *
33 * @author Louis Wasserman
34 */
35final class RegularImmutableSortedMultiset<E> extends ImmutableSortedMultiset<E> {
36  private static final class CumulativeCountEntry<E> extends Multisets.AbstractEntry<E> {
37    final E element;
38    final int count;
39    final long cumulativeCount;
40
41    CumulativeCountEntry(E element, int count, @Nullable CumulativeCountEntry<E> previous) {
42      this.element = element;
43      this.count = count;
44      this.cumulativeCount = count + ((previous == null) ? 0 : previous.cumulativeCount);
45    }
46
47    @Override
48    public E getElement() {
49      return element;
50    }
51
52    @Override
53    public int getCount() {
54      return count;
55    }
56  }
57
58  static <E> RegularImmutableSortedMultiset<E> createFromSorted(Comparator<? super E> comparator,
59      List<? extends Multiset.Entry<E>> entries) {
60    List<CumulativeCountEntry<E>> newEntries = Lists.newArrayListWithCapacity(entries.size());
61    CumulativeCountEntry<E> previous = null;
62    for (Multiset.Entry<E> entry : entries) {
63      newEntries.add(
64          previous = new CumulativeCountEntry<E>(entry.getElement(), entry.getCount(), previous));
65    }
66    return new RegularImmutableSortedMultiset<E>(comparator, ImmutableList.copyOf(newEntries));
67  }
68
69  final transient ImmutableList<CumulativeCountEntry<E>> entries;
70
71  RegularImmutableSortedMultiset(
72      Comparator<? super E> comparator, ImmutableList<CumulativeCountEntry<E>> entries) {
73    super(comparator);
74    this.entries = entries;
75    assert !entries.isEmpty();
76  }
77
78  ImmutableList<E> elementList() {
79    return new TransformedImmutableList<CumulativeCountEntry<E>, E>(entries) {
80      @Override
81      E transform(CumulativeCountEntry<E> entry) {
82        return entry.getElement();
83      }
84    };
85  }
86
87  @Override
88  ImmutableSortedSet<E> createElementSet() {
89    return new RegularImmutableSortedSet<E>(elementList(), comparator());
90  }
91
92  @Override
93  ImmutableSortedSet<E> createDescendingElementSet() {
94    return new RegularImmutableSortedSet<E>(elementList().reverse(), reverseComparator());
95  }
96
97  @SuppressWarnings("unchecked")
98  @Override
99  UnmodifiableIterator<Multiset.Entry<E>> entryIterator() {
100    return (UnmodifiableIterator) entries.iterator();
101  }
102
103  @SuppressWarnings("unchecked")
104  @Override
105  UnmodifiableIterator<Multiset.Entry<E>> descendingEntryIterator() {
106    return (UnmodifiableIterator) entries.reverse().iterator();
107  }
108
109  @Override
110  public CumulativeCountEntry<E> firstEntry() {
111    return entries.get(0);
112  }
113
114  @Override
115  public CumulativeCountEntry<E> lastEntry() {
116    return entries.get(entries.size() - 1);
117  }
118
119  @Override
120  public int size() {
121    CumulativeCountEntry<E> firstEntry = firstEntry();
122    CumulativeCountEntry<E> lastEntry = lastEntry();
123    return Ints.saturatedCast(
124        lastEntry.cumulativeCount - firstEntry.cumulativeCount + firstEntry.count);
125  }
126
127  @Override
128  int distinctElements() {
129    return entries.size();
130  }
131
132  @Override
133  boolean isPartialView() {
134    return entries.isPartialView();
135  }
136
137  @SuppressWarnings("unchecked")
138  @Override
139  public int count(@Nullable Object element) {
140    if (element == null) {
141      return 0;
142    }
143    try {
144      int index = SortedLists.binarySearch(
145          elementList(), (E) element, comparator(), ANY_PRESENT, INVERTED_INSERTION_INDEX);
146      return (index >= 0) ? entries.get(index).getCount() : 0;
147    } catch (ClassCastException e) {
148      return 0;
149    }
150  }
151
152  @Override
153  public ImmutableSortedMultiset<E> headMultiset(E upperBound, BoundType boundType) {
154    int index;
155    switch (boundType) {
156      case OPEN:
157        index = SortedLists.binarySearch(
158            elementList(), checkNotNull(upperBound), comparator(), ANY_PRESENT, NEXT_HIGHER);
159        break;
160      case CLOSED:
161        index = SortedLists.binarySearch(
162            elementList(), checkNotNull(upperBound), comparator(), ANY_PRESENT, NEXT_LOWER) + 1;
163        break;
164      default:
165        throw new AssertionError();
166    }
167    return createSubMultiset(0, index);
168  }
169
170  @Override
171  public ImmutableSortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType) {
172    int index;
173    switch (boundType) {
174      case OPEN:
175        index = SortedLists.binarySearch(
176            elementList(), checkNotNull(lowerBound), comparator(), ANY_PRESENT, NEXT_LOWER) + 1;
177        break;
178      case CLOSED:
179        index = SortedLists.binarySearch(
180            elementList(), checkNotNull(lowerBound), comparator(), ANY_PRESENT, NEXT_HIGHER);
181        break;
182      default:
183        throw new AssertionError();
184    }
185    return createSubMultiset(index, distinctElements());
186  }
187
188  private ImmutableSortedMultiset<E> createSubMultiset(int newFromIndex, int newToIndex) {
189    if (newFromIndex == 0 && newToIndex == entries.size()) {
190      return this;
191    } else if (newFromIndex >= newToIndex) {
192      return emptyMultiset(comparator());
193    } else {
194      return new RegularImmutableSortedMultiset<E>(
195          comparator(), entries.subList(newFromIndex, newToIndex));
196    }
197  }
198}
199