001/*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.collect.ForwardingSortedMap.unsafeCompare;
020
021import com.google.common.annotations.GwtCompatible;
022import java.util.Comparator;
023import java.util.Iterator;
024import java.util.NoSuchElementException;
025import java.util.SortedSet;
026import javax.annotation.CheckForNull;
027import org.checkerframework.checker.nullness.qual.Nullable;
028
029/**
030 * A sorted set which forwards all its method calls to another sorted set. Subclasses should
031 * override one or more methods to modify the behavior of the backing sorted set as desired per the
032 * <a href="http://en.wikipedia.org/wiki/Decorator_pattern">decorator pattern</a>.
033 *
034 * <p><b>Warning:</b> The methods of {@code ForwardingSortedSet} forward <i>indiscriminately</i> to
035 * the methods of the delegate. For example, overriding {@link #add} alone <i>will not</i> change
036 * the behavior of {@link #addAll}, which can lead to unexpected behavior. In this case, you should
037 * override {@code addAll} as well, either providing your own implementation, or delegating to the
038 * provided {@code standardAddAll} method.
039 *
040 * <p><b>{@code default} method warning:</b> This class does <i>not</i> forward calls to {@code
041 * default} methods. Instead, it inherits their default implementations. When those implementations
042 * invoke methods, they invoke methods on the {@code ForwardingSortedSet}.
043 *
044 * <p>Each of the {@code standard} methods, where appropriate, uses the set's comparator (or the
045 * natural ordering of the elements, if there is no comparator) to test element equality. As a
046 * result, if the comparator is not consistent with equals, some of the standard implementations may
047 * violate the {@code Set} contract.
048 *
049 * <p>The {@code standard} methods and the collection views they return are not guaranteed to be
050 * thread-safe, even when all of the methods that they depend on are thread-safe.
051 *
052 * @author Mike Bostock
053 * @author Louis Wasserman
054 * @since 2.0
055 */
056@GwtCompatible
057@ElementTypesAreNonnullByDefault
058public abstract class ForwardingSortedSet<E extends @Nullable Object> extends ForwardingSet<E>
059    implements SortedSet<E> {
060
061  /** Constructor for use by subclasses. */
062  protected ForwardingSortedSet() {}
063
064  @Override
065  protected abstract SortedSet<E> delegate();
066
067  @Override
068  @CheckForNull
069  public Comparator<? super E> comparator() {
070    return delegate().comparator();
071  }
072
073  @Override
074  @ParametricNullness
075  public E first() {
076    return delegate().first();
077  }
078
079  @Override
080  public SortedSet<E> headSet(@ParametricNullness E toElement) {
081    return delegate().headSet(toElement);
082  }
083
084  @Override
085  @ParametricNullness
086  public E last() {
087    return delegate().last();
088  }
089
090  @Override
091  public SortedSet<E> subSet(@ParametricNullness E fromElement, @ParametricNullness E toElement) {
092    return delegate().subSet(fromElement, toElement);
093  }
094
095  @Override
096  public SortedSet<E> tailSet(@ParametricNullness E fromElement) {
097    return delegate().tailSet(fromElement);
098  }
099
100  /**
101   * A sensible definition of {@link #contains} in terms of the {@code first()} method of {@link
102   * #tailSet}. If you override {@link #tailSet}, you may wish to override {@link #contains} to
103   * forward to this implementation.
104   *
105   * @since 7.0
106   */
107  @Override
108  protected boolean standardContains(@CheckForNull Object object) {
109    try {
110      // any ClassCastExceptions and NullPointerExceptions are caught
111      @SuppressWarnings({"unchecked", "nullness"})
112      SortedSet<@Nullable Object> self = (SortedSet<@Nullable Object>) this;
113      Object ceiling = self.tailSet(object).first();
114      return unsafeCompare(comparator(), ceiling, object) == 0;
115    } catch (ClassCastException | NoSuchElementException | NullPointerException e) {
116      return false;
117    }
118  }
119
120  /**
121   * A sensible definition of {@link #remove} in terms of the {@code iterator()} method of {@link
122   * #tailSet}. If you override {@link #tailSet}, you may wish to override {@link #remove} to
123   * forward to this implementation.
124   *
125   * @since 7.0
126   */
127  @Override
128  protected boolean standardRemove(@CheckForNull Object object) {
129    try {
130      // any ClassCastExceptions and NullPointerExceptions are caught
131      @SuppressWarnings({"unchecked", "nullness"})
132      SortedSet<@Nullable Object> self = (SortedSet<@Nullable Object>) this;
133      Iterator<?> iterator = self.tailSet(object).iterator();
134      if (iterator.hasNext()) {
135        Object ceiling = iterator.next();
136        if (unsafeCompare(comparator(), ceiling, object) == 0) {
137          iterator.remove();
138          return true;
139        }
140      }
141    } catch (ClassCastException | NullPointerException e) {
142      return false;
143    }
144    return false;
145  }
146
147  /**
148   * A sensible default implementation of {@link #subSet(Object, Object)} in terms of {@link
149   * #headSet(Object)} and {@link #tailSet(Object)}. In some situations, you may wish to override
150   * {@link #subSet(Object, Object)} to forward to this implementation.
151   *
152   * @since 7.0
153   */
154  protected SortedSet<E> standardSubSet(
155      @ParametricNullness E fromElement, @ParametricNullness E toElement) {
156    return tailSet(fromElement).headSet(toElement);
157  }
158}