java/feathub-udf/flink-udf/src/main/java/com/alibaba/feathub/flink/udf/AbstractTimeWindowedAggFunc.java
/*
 * Copyright 2022 The FeatHub Authors
 *
 * Licensed 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
 *
 *     https://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 com.alibaba.feathub.flink.udf;

import org.apache.flink.table.api.DataTypes;
import org.apache.flink.table.api.dataview.MapView;
import org.apache.flink.table.catalog.DataTypeFactory;
import org.apache.flink.table.functions.AggregateFunction;
import org.apache.flink.table.types.DataType;
import org.apache.flink.table.types.inference.TypeInference;
import org.apache.flink.util.Preconditions;

import org.apache.commons.collections.IteratorUtils;

import java.time.Duration;
import java.time.Instant;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Optional;

/**
 * Base class for all the time windowed aggregation function.
 *
 * <p>The aggregate function should be called with a timeInterval. It only aggregates rows with row
 * time in the range of [rowTime - timeInterval, rowTime]. Currently, Flink SQL/Table only support
 * over window with either time range or row count-based range. This can be used with a row
 * count-based over window to achieve over window with both time range and row count-based range.
 *
 * @param <INPUT_T> The type of the input.
 * @param <RESULT_T> The result type of the aggregation.
 */
public abstract class AbstractTimeWindowedAggFunc<INPUT_T, RESULT_T>
        extends AggregateFunction<
                RESULT_T, AbstractTimeWindowedAggFunc.TimeWindowedAccumulator<INPUT_T>> {

    /** The time range of rows to include in the aggregation. */
    protected Duration timeInterval;

    @Override
    public RESULT_T getValue(TimeWindowedAccumulator<INPUT_T> accumulator) {
        final Long lowerBound = accumulator.latestTimestamp - timeInterval.toMillis();
        List<INPUT_T> values = new LinkedList<>();
        try {
            List<Long> timestamps = IteratorUtils.toList(accumulator.values.keys().iterator());
            timestamps.sort(Comparator.naturalOrder());
            for (Long timestamp : timestamps) {
                if (timestamp < lowerBound) {
                    continue;
                }
                values.addAll(accumulator.values.get(timestamp));
            }
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
        return getValue(values);
    }

    /**
     * Compute the aggregation result with the given value.
     *
     * @param values The values that are in the time window range.
     * @return The aggregation result.
     */
    protected abstract RESULT_T getValue(List<INPUT_T> values);

    @Override
    public TimeWindowedAccumulator<INPUT_T> createAccumulator() {
        return new TimeWindowedAccumulator<>();
    }

    public void accumulate(
            TimeWindowedAccumulator<INPUT_T> acc, Duration duration, INPUT_T value, Instant instant)
            throws Exception {
        if (this.timeInterval == null) {
            this.timeInterval = duration;
        }
        Preconditions.checkState(
                this.timeInterval.equals(duration), "timeInterval should not changes.");

        final long timestamp = instant.toEpochMilli();
        acc.addValue(value, timestamp);
    }

    public void retract(
            TimeWindowedAccumulator<INPUT_T> acc, Duration duration, INPUT_T value, Instant instant)
            throws Exception {
        if (this.timeInterval == null) {
            this.timeInterval = duration;
        }
        Preconditions.checkState(
                this.timeInterval.equals(duration), "timeInterval should not changes.");

        final long timestamp = instant.toEpochMilli();
        acc.removeValue(value, timestamp);
    }

    protected abstract DataType getResultDataType(DataType valueDataType);

    @Override
    public TypeInference getTypeInference(DataTypeFactory typeFactory) {
        return TypeInference.newBuilder()
                .outputTypeStrategy(
                        callContext ->
                                Optional.of(
                                        getResultDataType(
                                                callContext.getArgumentDataTypes().get(1))))
                .accumulatorTypeStrategy(
                        callContext ->
                                Optional.of(
                                        DataTypes.STRUCTURED(
                                                TimeWindowedAccumulator.class,
                                                DataTypes.FIELD(
                                                        "values",
                                                        MapView.newMapViewDataType(
                                                                DataTypes.BIGINT(),
                                                                DataTypes.ARRAY(
                                                                                getResultDataType(
                                                                                        callContext
                                                                                                .getArgumentDataTypes()
                                                                                                .get(
                                                                                                        1)))
                                                                        // TODO: Add unit test with
                                                                        // state backend to test
                                                                        // serializer
                                                                        .bridgedTo(List.class))),
                                                DataTypes.FIELD(
                                                        "latestTimestamp", DataTypes.BIGINT()))))
                .build();
    }

    /**
     * The accumulator for {@link AbstractTimeWindowedAggFunc}.
     *
     * <p>The accumulator keeps track of the accumulated value and the timestamp of the latest
     * value.
     *
     * @param <VALUE_T> The type of the value in the accumulator.
     */
    public static class TimeWindowedAccumulator<VALUE_T> {
        public MapView<Long, List<VALUE_T>> values = new MapView<>();

        public Long latestTimestamp = 0L;

        public void addValue(VALUE_T value, Long timestamp) throws Exception {
            if (timestamp > latestTimestamp) {
                latestTimestamp = timestamp;
            }
            List<VALUE_T> vals = values.get(timestamp);
            if (vals == null) {
                vals = new LinkedList<>();
            }
            vals.add(value);
            values.put(timestamp, vals);
        }

        public void removeValue(VALUE_T value, Long timestamp) throws Exception {
            final List<VALUE_T> vals = values.get(timestamp);
            vals.remove(value);
            if (vals.size() == 0) {
                values.remove(timestamp);

                if (latestTimestamp.equals(timestamp)) {
                    resetLatestTimestamp();
                }
                return;
            }
            values.put(timestamp, vals);
        }

        private void resetLatestTimestamp() throws Exception {
            latestTimestamp = 0L;
            for (Map.Entry<Long, List<VALUE_T>> entry : values.entries()) {
                if (entry.getKey() > latestTimestamp) {
                    latestTimestamp = entry.getKey();
                }
            }
        }
    }
}
