/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.beam.sdk.extensions.timeseries;

import com.google.auto.value.AutoValue;
import java.util.List;
import java.util.Random;
import org.apache.beam.sdk.Pipeline;
import org.apache.beam.sdk.schemas.AutoValueSchema;
import org.apache.beam.sdk.schemas.annotations.DefaultSchema;
import org.apache.beam.sdk.testing.PAssert;
import org.apache.beam.sdk.testing.TestPipeline;
import org.apache.beam.sdk.testing.UsesLoopingTimer;
import org.apache.beam.sdk.testing.UsesStatefulParDo;
import org.apache.beam.sdk.testing.UsesStrictTimerOrdering;
import org.apache.beam.sdk.testing.UsesTimersInParDo;
import org.apache.beam.sdk.transforms.Create;
import org.apache.beam.sdk.transforms.Reify;
import org.apache.beam.sdk.transforms.windowing.BoundedWindow;
import org.apache.beam.sdk.transforms.windowing.FixedWindows;
import org.apache.beam.sdk.values.PCollection;
import org.apache.beam.sdk.values.TimestampedValue;
import org.apache.beam.vendor.guava.v26_0_jre.com.google.common.collect.ImmutableList;
import org.apache.beam.vendor.guava.v26_0_jre.com.google.common.collect.Iterables;
import org.apache.beam.vendor.guava.v26_0_jre.com.google.common.collect.Lists;
import org.joda.time.Duration;
import org.joda.time.Instant;
import org.junit.Rule;
import org.junit.Test;
import org.junit.experimental.categories.Category;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;

@RunWith(JUnit4.class)
public class FillGapsTest {
  @Rule public final transient TestPipeline pipeline = TestPipeline.create();

  @DefaultSchema(AutoValueSchema.class)
  @AutoValue
  abstract static class Message {
    abstract String getKey();

    abstract String getValue();

    abstract Instant getTimestamp();

    static Message update(FillGaps.InterpolateData<Message> interpolateData) {
      Message value = interpolateData.getValue().getValue();
      Instant nextWindowMax = interpolateData.getNextWindow().maxTimestamp();
      return value.toBuilder().setTimestamp(nextWindowMax).build();
    }

    static Message of(String key, String value, Instant timestamp) {
      return new AutoValue_FillGapsTest_Message.Builder()
          .setKey(key)
          .setValue(value)
          .setTimestamp(timestamp)
          .build();
    }

    static TimestampedValue<Message> ofTimestamped(String key, String value, Instant timestamp) {
      return TimestampedValue.of(of(key, value, timestamp), timestamp);
    }

    @AutoValue.Builder
    abstract static class Builder {
      abstract Builder setKey(String key);

      abstract Builder setValue(String value);

      abstract Builder setTimestamp(Instant timestamp);

      abstract Message build();
    }

    abstract Builder toBuilder();
  }

  @Test
  public void testFillGaps() {
    List<TimestampedValue<Message>> values =
        ImmutableList.of(
            Message.ofTimestamped("key1", "value0<", Instant.ofEpochSecond(0)),
            Message.ofTimestamped("key2", "value0", Instant.ofEpochSecond(0)),
            Message.ofTimestamped("key1", "value1<", Instant.ofEpochSecond(1)),
            Message.ofTimestamped(
                "key1", "value1", Instant.ofEpochSecond(1).plus(Duration.millis(1))),
            Message.ofTimestamped("key2", "value1<", Instant.ofEpochSecond(1)),
            Message.ofTimestamped(
                "key2", "value1", Instant.ofEpochSecond(1).plus(Duration.millis(1))),
            Message.ofTimestamped("key1", "value3", Instant.ofEpochSecond(3)),
            Message.ofTimestamped("key2", "value3", Instant.ofEpochSecond(3)));

    PCollection<Message> input = pipeline.apply(Create.timestamped(values));
    PCollection<TimestampedValue<Message>> gapFilled =
        input
            .apply(
                FillGaps.<Message>of(Duration.standardSeconds(1), "key")
                    .withStopTime(Instant.ofEpochSecond(5)))
            .apply(Reify.timestamps());

    FixedWindows fixedWindows = FixedWindows.of(Duration.standardSeconds(1));
    PAssert.that(gapFilled)
        .containsInAnyOrder(
            Iterables.concat(
                values,
                ImmutableList.of(
                    TimestampedValue.of(
                        Message.of(
                            "key1", "value1", Instant.ofEpochSecond(1).plus(Duration.millis(1))),
                        fixedWindows.assignWindow(Instant.ofEpochSecond(2)).maxTimestamp()),
                    TimestampedValue.of(
                        Message.of(
                            "key2", "value1", Instant.ofEpochSecond(1).plus(Duration.millis(1))),
                        fixedWindows.assignWindow(Instant.ofEpochSecond(2)).maxTimestamp()),
                    TimestampedValue.of(
                        Message.of("key1", "value3", Instant.ofEpochSecond(3)),
                        fixedWindows.assignWindow(Instant.ofEpochSecond(4)).maxTimestamp()),
                    TimestampedValue.of(
                        Message.of("key2", "value3", Instant.ofEpochSecond(3)),
                        fixedWindows.assignWindow(Instant.ofEpochSecond(4)).maxTimestamp()))));
    pipeline.run();
  }

  @Test
  public void testFillGapsKeepEarliest() {
    List<TimestampedValue<Message>> values =
        ImmutableList.of(
            Message.ofTimestamped("key1", "value0<", Instant.ofEpochSecond(0)),
            Message.ofTimestamped("key2", "value0", Instant.ofEpochSecond(0)),
            Message.ofTimestamped("key1", "value1<", Instant.ofEpochSecond(1)),
            Message.ofTimestamped(
                "key1", "value1", Instant.ofEpochSecond(1).plus(Duration.millis(1))),
            Message.ofTimestamped("key2", "value1<", Instant.ofEpochSecond(1)),
            Message.ofTimestamped(
                "key2", "value1", Instant.ofEpochSecond(1).plus(Duration.millis(1))),
            Message.ofTimestamped("key1", "value3", Instant.ofEpochSecond(3)),
            Message.ofTimestamped("key2", "value3", Instant.ofEpochSecond(3)));

    PCollection<Message> input = pipeline.apply(Create.timestamped(values));
    PCollection<TimestampedValue<Message>> gapFilled =
        input
            .apply(
                FillGaps.<Message>of(Duration.standardSeconds(1), "key")
                    .withMergeFunction(FillGaps.keepEarliest())
                    .withStopTime(Instant.ofEpochSecond(5)))
            .apply(Reify.timestamps());

    FixedWindows fixedWindows = FixedWindows.of(Duration.standardSeconds(1));
    PAssert.that(gapFilled)
        .containsInAnyOrder(
            Iterables.concat(
                values,
                ImmutableList.of(
                    TimestampedValue.of(
                        Message.of("key1", "value1<", Instant.ofEpochSecond(1)),
                        fixedWindows.assignWindow(Instant.ofEpochSecond(2)).maxTimestamp()),
                    TimestampedValue.of(
                        Message.of("key2", "value1<", Instant.ofEpochSecond(1)),
                        fixedWindows.assignWindow(Instant.ofEpochSecond(2)).maxTimestamp()),
                    TimestampedValue.of(
                        Message.of("key1", "value3", Instant.ofEpochSecond(3)),
                        fixedWindows.assignWindow(Instant.ofEpochSecond(4)).maxTimestamp()),
                    TimestampedValue.of(
                        Message.of("key2", "value3", Instant.ofEpochSecond(3)),
                        fixedWindows.assignWindow(Instant.ofEpochSecond(4)).maxTimestamp()))));
    pipeline.run();
  }

  @Test
  public void testFillGapsMaxDuration() {
    List<TimestampedValue<Message>> values =
        ImmutableList.of(
            Message.ofTimestamped("key1", "value0", Instant.ofEpochSecond(0)),
            Message.ofTimestamped("key2", "value0", Instant.ofEpochSecond(0)),
            Message.ofTimestamped("key1", "value1", Instant.ofEpochSecond(1)),
            Message.ofTimestamped("key2", "value1", Instant.ofEpochSecond(1)),
            Message.ofTimestamped("key1", "value3", Instant.ofEpochSecond(10)),
            Message.ofTimestamped("key2", "value3", Instant.ofEpochSecond(10)));

    PCollection<Message> input = pipeline.apply(Create.timestamped(values));
    PCollection<TimestampedValue<Message>> gapFilled =
        input
            .apply(
                FillGaps.<Message>of(Duration.standardSeconds(1), "key")
                    .withMaxGapFillBuckets(4L)
                    .withStopTime(Instant.ofEpochSecond(11)))
            .apply(Reify.timestamps());

    FixedWindows fixedWindows = FixedWindows.of(Duration.standardSeconds(1));
    PAssert.that(gapFilled)
        .containsInAnyOrder(
            Iterables.concat(
                values,
                ImmutableList.of(
                    TimestampedValue.of(
                        Message.of("key1", "value1", Instant.ofEpochSecond(1)),
                        fixedWindows.assignWindow(Instant.ofEpochSecond(2)).maxTimestamp()),
                    TimestampedValue.of(
                        Message.of("key1", "value1", Instant.ofEpochSecond(1)),
                        fixedWindows.assignWindow(Instant.ofEpochSecond(3)).maxTimestamp()),
                    TimestampedValue.of(
                        Message.of("key1", "value1", Instant.ofEpochSecond(1)),
                        fixedWindows.assignWindow(Instant.ofEpochSecond(4)).maxTimestamp()),
                    TimestampedValue.of(
                        Message.of("key1", "value1", Instant.ofEpochSecond(1)),
                        fixedWindows.assignWindow(Instant.ofEpochSecond(5)).maxTimestamp()),
                    TimestampedValue.of(
                        Message.of("key2", "value1", Instant.ofEpochSecond(1)),
                        fixedWindows.assignWindow(Instant.ofEpochSecond(2)).maxTimestamp()),
                    TimestampedValue.of(
                        Message.of("key2", "value1", Instant.ofEpochSecond(1)),
                        fixedWindows.assignWindow(Instant.ofEpochSecond(3)).maxTimestamp()),
                    TimestampedValue.of(
                        Message.of("key2", "value1", Instant.ofEpochSecond(1)),
                        fixedWindows.assignWindow(Instant.ofEpochSecond(4)).maxTimestamp()),
                    TimestampedValue.of(
                        Message.of("key2", "value1", Instant.ofEpochSecond(1)),
                        fixedWindows.assignWindow(Instant.ofEpochSecond(5)).maxTimestamp()))));
    pipeline.run();
  }

  @Test
  public void testFillGapsPropagateFunction() {
    List<TimestampedValue<Message>> values =
        ImmutableList.of(
            Message.ofTimestamped("key1", "value0<", Instant.ofEpochSecond(0)),
            Message.ofTimestamped("key2", "value0", Instant.ofEpochSecond(0)),
            Message.ofTimestamped("key1", "value1<", Instant.ofEpochSecond(1)),
            Message.ofTimestamped(
                "key1", "value1", Instant.ofEpochSecond(1).plus(Duration.millis(1))),
            Message.ofTimestamped("key2", "value1<", Instant.ofEpochSecond(1)),
            Message.ofTimestamped(
                "key2", "value1", Instant.ofEpochSecond(1).plus(Duration.millis(1))),
            Message.ofTimestamped("key1", "value3", Instant.ofEpochSecond(3)),
            Message.ofTimestamped("key2", "value3", Instant.ofEpochSecond(3)));

    PCollection<Message> input = pipeline.apply(Create.timestamped(values));
    PCollection<TimestampedValue<Message>> gapFilled =
        input
            .apply(
                FillGaps.<Message>of(Duration.standardSeconds(1), "key")
                    .withInterpolateFunction(Message::update)
                    .withStopTime(Instant.ofEpochSecond(5)))
            .apply(Reify.timestamps());

    FixedWindows fixedWindows = FixedWindows.of(Duration.standardSeconds(1));
    Instant bucketTwoMax = fixedWindows.assignWindow(Instant.ofEpochSecond(2)).maxTimestamp();
    Instant bucketFourMax = fixedWindows.assignWindow(Instant.ofEpochSecond(4)).maxTimestamp();

    PAssert.that(gapFilled)
        .containsInAnyOrder(
            Iterables.concat(
                values,
                ImmutableList.of(
                    Message.ofTimestamped("key1", "value1", bucketTwoMax),
                    Message.ofTimestamped("key2", "value1", bucketTwoMax),
                    Message.ofTimestamped("key1", "value3", bucketFourMax),
                    Message.ofTimestamped("key2", "value3", bucketFourMax))));
    pipeline.run();
  }

  // TODO: This test fails due to DirectRunner bugs. Uncomment once those bugs are fixed.
  @Test
  @Category({
    UsesTimersInParDo.class,
    UsesLoopingTimer.class,
    UsesStatefulParDo.class,
    UsesStrictTimerOrdering.class
  })
  public void testFillGapsFuzz() {
    for (int i = 0; i < 6; ++i) {
      fuzzTest(10, 500, 25, 20);
    }
  }

  public void fuzzTest(int numKeys, int numBuckets, int maxGapSizeToGenerate, long maxGapSize) {
    Pipeline p = Pipeline.create();
    List<TimestampedValue<Message>> values = Lists.newArrayList();
    List<TimestampedValue<Message>> expectedGaps = Lists.newArrayList();
    for (int i = 0; i < numKeys; ++i) {
      String key = "key" + i;
      generateFuzzTimerseries(
          key, numBuckets, maxGapSizeToGenerate, maxGapSize, values, expectedGaps);
    }

    PCollection<Message> input = p.apply(Create.timestamped(values));
    PCollection<TimestampedValue<Message>> gapFilled =
        input
            .apply(
                FillGaps.<Message>of(Duration.standardSeconds(1), "key")
                    .withInterpolateFunction(Message::update)
                    .withMaxGapFillBuckets(maxGapSize)
                    .withStopTime(Instant.ofEpochSecond(numBuckets)))
            .apply(Reify.timestamps());

    PAssert.that(gapFilled).containsInAnyOrder(Iterables.concat(values, expectedGaps));
    p.run();
  }

  void generateFuzzTimerseries(
      String key,
      int numBuckets,
      int maxGapSizeToGenerate,
      long maxGapSize,
      List<TimestampedValue<Message>> values,
      List<TimestampedValue<Message>> expectedGaps) {
    Random random = new Random();
    String lastValue = null;
    int currentGapSize = 0;
    for (int bucket = 0; bucket < numBuckets; ) {
      if (lastValue != null && currentGapSize < maxGapSizeToGenerate && random.nextInt(10) == 0) {
        // 10% chance of creating a gap.
        int gapSize = random.nextInt(maxGapSizeToGenerate) + 1;
        int lastGapBucket = Math.min(bucket + gapSize, numBuckets);

        for (; bucket < lastGapBucket; ++bucket) {
          if (currentGapSize < maxGapSize) {
            addBucketToTimeseries(key, lastValue, bucket, expectedGaps);
          }
          ++currentGapSize;
        }
      } else {
        lastValue = "bucket" + bucket;
        currentGapSize = 0;
        addBucketToTimeseries(key, lastValue, bucket, values);
        ++bucket;
      }
    }
  }

  void addBucketToTimeseries(
      String key, String value, int bucket, List<TimestampedValue<Message>> list) {
    FixedWindows fixedWindows = FixedWindows.of(Duration.standardSeconds(1));
    BoundedWindow currentBucket = fixedWindows.assignWindow(Instant.ofEpochSecond(bucket));
    TimestampedValue<Message> message =
        Message.ofTimestamped(key, value, currentBucket.maxTimestamp());
    list.add(message);
  }
}
