// Protocol Buffers - Google's data interchange format
// Copyright 2008 Google Inc.  All rights reserved.
// https://developers.google.com/protocol-buffers/
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

package com.google.protobuf;

import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * {@code RepeatedFieldBuilder} implements a structure that a protocol
 * message uses to hold a repeated field of other protocol messages. It supports
 * the classical use case of adding immutable {@link Message}'s to the
 * repeated field and is highly optimized around this (no extra memory
 * allocations and sharing of immutable arrays).
 * <br>
 * It also supports the additional use case of adding a {@link Message.Builder}
 * to the repeated field and deferring conversion of that {@code Builder}
 * to an immutable {@code Message}. In this way, it's possible to maintain
 * a tree of {@code Builder}'s that acts as a fully read/write data
 * structure.
 * <br>
 * Logically, one can think of a tree of builders as converting the entire tree
 * to messages when build is called on the root or when any method is called
 * that desires a Message instead of a Builder. In terms of the implementation,
 * the {@code SingleFieldBuilder} and {@code RepeatedFieldBuilder}
 * classes cache messages that were created so that messages only need to be
 * created when some change occurred in its builder or a builder for one of its
 * descendants.
 *
 * @param <MType> the type of message for the field
 * @param <BType> the type of builder for the field
 * @param <IType> the common interface for the message and the builder
 *
 * @author jonp@google.com (Jon Perlow)
 */
public class RepeatedFieldBuilder
    <MType extends GeneratedMessage,
     BType extends GeneratedMessage.Builder,
     IType extends MessageOrBuilder>
    implements GeneratedMessage.BuilderParent {

  // Parent to send changes to.
  private GeneratedMessage.BuilderParent parent;

  // List of messages. Never null. It may be immutable, in which case
  // isMessagesListMutable will be false. See note below.
  private List<MType> messages;

  // Whether messages is an mutable array that can be modified.
  private boolean isMessagesListMutable;

  // List of builders. May be null, in which case, no nested builders were
  // created. If not null, entries represent the builder for that index.
  private List<SingleFieldBuilder<MType, BType, IType>> builders;

  // Here are the invariants for messages and builders:
  // 1. messages is never null and its count corresponds to the number of items
  //    in the repeated field.
  // 2. If builders is non-null, messages and builders MUST always
  //    contain the same number of items.
  // 3. Entries in either array can be null, but for any index, there MUST be
  //    either a Message in messages or a builder in builders.
  // 4. If the builder at an index is non-null, the builder is
  //    authoritative. This is the case where a Builder was set on the index.
  //    Any message in the messages array MUST be ignored.
  // t. If the builder at an index is null, the message in the messages
  //    list is authoritative. This is the case where a Message (not a Builder)
  //    was set directly for an index.

  // Indicates that we've built a message and so we are now obligated
  // to dispatch dirty invalidations. See GeneratedMessage.BuilderListener.
  private boolean isClean;

  // A view of this builder that exposes a List interface of messages. This is
  // initialized on demand. This is fully backed by this object and all changes
  // are reflected in it. Access to any item converts it to a message if it
  // was a builder.
  private MessageExternalList<MType, BType, IType> externalMessageList;

  // A view of this builder that exposes a List interface of builders. This is
  // initialized on demand. This is fully backed by this object and all changes
  // are reflected in it. Access to any item converts it to a builder if it
  // was a message.
  private BuilderExternalList<MType, BType, IType> externalBuilderList;

  // A view of this builder that exposes a List interface of the interface
  // implemented by messages and builders. This is initialized on demand. This
  // is fully backed by this object and all changes are reflected in it.
  // Access to any item returns either a builder or message depending on
  // what is most efficient.
  private MessageOrBuilderExternalList<MType, BType, IType>
      externalMessageOrBuilderList;

  /**
   * Constructs a new builder with an empty list of messages.
   *
   * @param messages the current list of messages
   * @param isMessagesListMutable Whether the messages list is mutable
   * @param parent a listener to notify of changes
   * @param isClean whether the builder is initially marked clean
   */
  public RepeatedFieldBuilder(
      List<MType> messages,
      boolean isMessagesListMutable,
      GeneratedMessage.BuilderParent parent,
      boolean isClean) {
    this.messages = messages;
    this.isMessagesListMutable = isMessagesListMutable;
    this.parent = parent;
    this.isClean = isClean;
  }

  public void dispose() {
    // Null out parent so we stop sending it invalidations.
    parent = null;
  }

  /**
   * Ensures that the list of messages is mutable so it can be updated. If it's
   * immutable, a copy is made.
   */
  private void ensureMutableMessageList() {
    if (!isMessagesListMutable) {
      messages = new ArrayList<MType>(messages);
      isMessagesListMutable = true;
    }
  }

  /**
   * Ensures that the list of builders is not null. If it's null, the list is
   * created and initialized to be the same size as the messages list with
   * null entries.
   */
  private void ensureBuilders() {
    if (this.builders == null) {
      this.builders =
          new ArrayList<SingleFieldBuilder<MType, BType, IType>>(
              messages.size());
      for (int i = 0; i < messages.size(); i++) {
        builders.add(null);
      }
    }
  }

  /**
   * Gets the count of items in the list.
   *
   * @return the count of items in the list.
   */
  public int getCount() {
    return messages.size();
  }

  /**
   * Gets whether the list is empty.
   *
   * @return whether the list is empty
   */
  public boolean isEmpty() {
    return messages.isEmpty();
  }

  /**
   * Get the message at the specified index. If the message is currently stored
   * as a {@code Builder}, it is converted to a {@code Message} by
   * calling {@link Message.Builder#buildPartial} on it.
   *
   * @param index the index of the message to get
   * @return the message for the specified index
   */
  public MType getMessage(int index) {
    return getMessage(index, false);
  }

  /**
   * Get the message at the specified index. If the message is currently stored
   * as a {@code Builder}, it is converted to a {@code Message} by
   * calling {@link Message.Builder#buildPartial} on it.
   *
   * @param index the index of the message to get
   * @param forBuild this is being called for build so we want to make sure
   *     we SingleFieldBuilder.build to send dirty invalidations
   * @return the message for the specified index
   */
  private MType getMessage(int index, boolean forBuild) {
    if (this.builders == null) {
      // We don't have any builders -- return the current Message.
      // This is the case where no builder was created, so we MUST have a
      // Message.
      return messages.get(index);
    }

    SingleFieldBuilder<MType, BType, IType> builder = builders.get(index);
    if (builder == null) {
      // We don't have a builder -- return the current message.
      // This is the case where no builder was created for the entry at index,
      // so we MUST have a message.
      return messages.get(index);

    } else {
      return forBuild ? builder.build() : builder.getMessage();
    }
  }

  /**
   * Gets a builder for the specified index. If no builder has been created for
   * that index, a builder is created on demand by calling
   * {@link Message#toBuilder}.
   *
   * @param index the index of the message to get
   * @return The builder for that index
   */
  public BType getBuilder(int index) {
    ensureBuilders();
    SingleFieldBuilder<MType, BType, IType> builder = builders.get(index);
    if (builder == null) {
      MType message = messages.get(index);
      builder = new SingleFieldBuilder<MType, BType, IType>(
          message, this, isClean);
      builders.set(index, builder);
    }
    return builder.getBuilder();
  }

  /**
   * Gets the base class interface for the specified index. This may either be
   * a builder or a message. It will return whatever is more efficient.
   *
   * @param index the index of the message to get
   * @return the message or builder for the index as the base class interface
   */
  @SuppressWarnings("unchecked")
  public IType getMessageOrBuilder(int index) {
    if (this.builders == null) {
      // We don't have any builders -- return the current Message.
      // This is the case where no builder was created, so we MUST have a
      // Message.
      return (IType) messages.get(index);
    }

    SingleFieldBuilder<MType, BType, IType> builder = builders.get(index);
    if (builder == null) {
      // We don't have a builder -- return the current message.
      // This is the case where no builder was created for the entry at index,
      // so we MUST have a message.
      return (IType) messages.get(index);

    } else {
      return builder.getMessageOrBuilder();
    }
  }

  /**
   * Sets a  message at the specified index replacing the existing item at
   * that index.
   *
   * @param index the index to set.
   * @param message the message to set
   * @return the builder
   */
  public RepeatedFieldBuilder<MType, BType, IType> setMessage(
      int index, MType message) {
    if (message == null) {
      throw new NullPointerException();
    }
    ensureMutableMessageList();
    messages.set(index, message);
    if (builders != null) {
      SingleFieldBuilder<MType, BType, IType> entry =
          builders.set(index, null);
      if (entry != null) {
        entry.dispose();
      }
    }
    onChanged();
    incrementModCounts();
    return this;
  }

  /**
   * Appends the specified element to the end of this list.
   *
   * @param message the message to add
   * @return the builder
   */
  public RepeatedFieldBuilder<MType, BType, IType> addMessage(
      MType message) {
    if (message == null) {
      throw new NullPointerException();
    }
    ensureMutableMessageList();
    messages.add(message);
    if (builders != null) {
      builders.add(null);
    }
    onChanged();
    incrementModCounts();
    return this;
  }

  /**
   * Inserts the specified message at the specified position in this list.
   * Shifts the element currently at that position (if any) and any subsequent
   * elements to the right (adds one to their indices).
   *
   * @param index the index at which to insert the message
   * @param message the message to add
   * @return the builder
   */
  public RepeatedFieldBuilder<MType, BType, IType> addMessage(
      int index, MType message) {
    if (message == null) {
      throw new NullPointerException();
    }
    ensureMutableMessageList();
    messages.add(index, message);
    if (builders != null) {
      builders.add(index, null);
    }
    onChanged();
    incrementModCounts();
    return this;
  }

  /**
   * Appends all of the messages in the specified collection to the end of
   * this list, in the order that they are returned by the specified
   * collection's iterator.
   *
   * @param values the messages to add
   * @return the builder
   */
  public RepeatedFieldBuilder<MType, BType, IType> addAllMessages(
      Iterable<? extends MType> values) {
    for (final MType value : values) {
      if (value == null) {
        throw new NullPointerException();
      }
    }

    // If we can inspect the size, we can more efficiently add messages.
    int size = -1;
    if (values instanceof Collection) {
      @SuppressWarnings("unchecked") final
      Collection<MType> collection = (Collection<MType>) values;
      if (collection.size() == 0) {
        return this;
      }
      size = collection.size();
    }
    ensureMutableMessageList();

    if (size >= 0 && messages instanceof ArrayList) {
      ((ArrayList<MType>) messages)
          .ensureCapacity(messages.size() + size);
    }

    for (MType value : values) {
      addMessage(value);
    }

    onChanged();
    incrementModCounts();
    return this;
  }

  /**
   * Appends a new builder to the end of this list and returns the builder.
   *
   * @param message the message to add which is the basis of the builder
   * @return the new builder
   */
  public BType addBuilder(MType message) {
    ensureMutableMessageList();
    ensureBuilders();
    SingleFieldBuilder<MType, BType, IType> builder =
        new SingleFieldBuilder<MType, BType, IType>(
            message, this, isClean);
    messages.add(null);
    builders.add(builder);
    onChanged();
    incrementModCounts();
    return builder.getBuilder();
  }

  /**
   * Inserts a new builder at the specified position in this list.
   * Shifts the element currently at that position (if any) and any subsequent
   * elements to the right (adds one to their indices).
   *
   * @param index the index at which to insert the builder
   * @param message the message to add which is the basis of the builder
   * @return the builder
   */
  public BType addBuilder(int index, MType message) {
    ensureMutableMessageList();
    ensureBuilders();
    SingleFieldBuilder<MType, BType, IType> builder =
        new SingleFieldBuilder<MType, BType, IType>(
            message, this, isClean);
    messages.add(index, null);
    builders.add(index, builder);
    onChanged();
    incrementModCounts();
    return builder.getBuilder();
  }

  /**
   * Removes the element at the specified position in this list. Shifts any
   * subsequent elements to the left (subtracts one from their indices).
   * Returns the element that was removed from the list.
   *
   * @param index the index at which to remove the message
   */
  public void remove(int index) {
    ensureMutableMessageList();
    messages.remove(index);
    if (builders != null) {
      SingleFieldBuilder<MType, BType, IType> entry =
          builders.remove(index);
      if (entry != null) {
        entry.dispose();
      }
    }
    onChanged();
    incrementModCounts();
  }

  /**
   * Removes all of the elements from this list.
   * The list will be empty after this call returns.
   */
  public void clear() {
    messages = Collections.emptyList();
    isMessagesListMutable = false;
    if (builders != null) {
      for (SingleFieldBuilder<MType, BType, IType> entry :
          builders) {
        if (entry != null) {
          entry.dispose();
        }
      }
      builders = null;
    }
    onChanged();
    incrementModCounts();
  }

  /**
   * Builds the list of messages from the builder and returns them.
   *
   * @return an immutable list of messages
   */
  public List<MType> build() {
    // Now that build has been called, we are required to dispatch
    // invalidations.
    isClean = true;

    if (!isMessagesListMutable && builders == null) {
      // We still have an immutable list and we never created a builder.
      return messages;
    }

    boolean allMessagesInSync = true;
    if (!isMessagesListMutable) {
      // We still have an immutable list. Let's see if any of them are out
      // of sync with their builders.
      for (int i = 0; i < messages.size(); i++) {
        Message message = messages.get(i);
        SingleFieldBuilder<MType, BType, IType> builder = builders.get(i);
        if (builder != null) {
          if (builder.build() != message) {
            allMessagesInSync = false;
            break;
          }
        }
      }
      if (allMessagesInSync) {
        // Immutable list is still in sync.
        return messages;
      }
    }

    // Need to make sure messages is up to date
    ensureMutableMessageList();
    for (int i = 0; i < messages.size(); i++) {
      messages.set(i, getMessage(i, true));
    }

    // We're going to return our list as immutable so we mark that we can
    // no longer update it.
    messages = Collections.unmodifiableList(messages);
    isMessagesListMutable = false;
    return messages;
  }

  /**
   * Gets a view of the builder as a list of messages. The returned list is live
   * and will reflect any changes to the underlying builder.
   *
   * @return the messages in the list
   */
  public List<MType> getMessageList() {
    if (externalMessageList == null) {
      externalMessageList =
          new MessageExternalList<MType, BType, IType>(this);
    }
    return externalMessageList;
  }

  /**
   * Gets a view of the builder as a list of builders. This returned list is
   * live and will reflect any changes to the underlying builder.
   *
   * @return the builders in the list
   */
  public List<BType> getBuilderList() {
    if (externalBuilderList == null) {
      externalBuilderList =
          new BuilderExternalList<MType, BType, IType>(this);
    }
    return externalBuilderList;
  }

  /**
   * Gets a view of the builder as a list of MessageOrBuilders. This returned
   * list is live and will reflect any changes to the underlying builder.
   *
   * @return the builders in the list
   */
  public List<IType> getMessageOrBuilderList() {
    if (externalMessageOrBuilderList == null) {
      externalMessageOrBuilderList =
          new MessageOrBuilderExternalList<MType, BType, IType>(this);
    }
    return externalMessageOrBuilderList;
  }

  /**
   * Called when a the builder or one of its nested children has changed
   * and any parent should be notified of its invalidation.
   */
  private void onChanged() {
    if (isClean && parent != null) {
      parent.markDirty();

      // Don't keep dispatching invalidations until build is called again.
      isClean = false;
    }
  }

  @Override
  public void markDirty() {
    onChanged();
  }

  /**
   * Increments the mod counts so that an ConcurrentModificationException can
   * be thrown if calling code tries to modify the builder while its iterating
   * the list.
   */
  private void incrementModCounts() {
    if (externalMessageList != null) {
      externalMessageList.incrementModCount();
    }
    if (externalBuilderList != null) {
      externalBuilderList.incrementModCount();
    }
    if (externalMessageOrBuilderList != null) {
      externalMessageOrBuilderList.incrementModCount();
    }
  }

  /**
   * Provides a live view of the builder as a list of messages.
   *
   * @param <MType> the type of message for the field
   * @param <BType> the type of builder for the field
   * @param <IType> the common interface for the message and the builder
   */
  private static class MessageExternalList<
      MType extends GeneratedMessage,
      BType extends GeneratedMessage.Builder,
      IType extends MessageOrBuilder>
      extends AbstractList<MType> implements List<MType> {

    RepeatedFieldBuilder<MType, BType, IType> builder;

    MessageExternalList(
        RepeatedFieldBuilder<MType, BType, IType> builder) {
      this.builder = builder;
    }

    @Override
    public int size() {
      return this.builder.getCount();
    }

    @Override
    public MType get(int index) {
      return builder.getMessage(index);
    }

    void incrementModCount() {
      modCount++;
    }
  }

  /**
   * Provides a live view of the builder as a list of builders.
   *
   * @param <MType> the type of message for the field
   * @param <BType> the type of builder for the field
   * @param <IType> the common interface for the message and the builder
   */
  private static class BuilderExternalList<
      MType extends GeneratedMessage,
      BType extends GeneratedMessage.Builder,
      IType extends MessageOrBuilder>
      extends AbstractList<BType> implements List<BType> {

    RepeatedFieldBuilder<MType, BType, IType> builder;

    BuilderExternalList(
        RepeatedFieldBuilder<MType, BType, IType> builder) {
      this.builder = builder;
    }

    @Override
    public int size() {
      return this.builder.getCount();
    }

    @Override
    public BType get(int index) {
      return builder.getBuilder(index);
    }

    void incrementModCount() {
      modCount++;
    }
  }

  /**
   * Provides a live view of the builder as a list of builders.
   *
   * @param <MType> the type of message for the field
   * @param <BType> the type of builder for the field
   * @param <IType> the common interface for the message and the builder
   */
  private static class MessageOrBuilderExternalList<
      MType extends GeneratedMessage,
      BType extends GeneratedMessage.Builder,
      IType extends MessageOrBuilder>
      extends AbstractList<IType> implements List<IType> {

    RepeatedFieldBuilder<MType, BType, IType> builder;

    MessageOrBuilderExternalList(
        RepeatedFieldBuilder<MType, BType, IType> builder) {
      this.builder = builder;
    }

    @Override
    public int size() {
      return this.builder.getCount();
    }

    @Override
    public IType get(int index) {
      return builder.getMessageOrBuilder(index);
    }

    void incrementModCount() {
      modCount++;
    }
  }
}