This is an automated email from the ASF dual-hosted git repository.
spricoder pushed a commit to branch research/seasonal-repair
in repository https://gitbox.apache.org/repos/asf/iotdb.git
The following commit(s) were added to refs/heads/research/seasonal-repair by
this push:
new ba9fc78d8e4 Add UDF "UDTFSeasonalRepair" to the research branch
"research/seasonal-repair" (#12671)
ba9fc78d8e4 is described below
commit ba9fc78d8e4226fd4491b673df9621068aca92cd
Author: Zane Chen <[email protected]>
AuthorDate: Thu Jun 6 10:54:15 2024 +0800
Add UDF "UDTFSeasonalRepair" to the research branch
"research/seasonal-repair" (#12671)
---
.../iotdb/library/drepair/UDTFSeasonalRepair.java | 149 ++++++++++++++++
.../iotdb/library/drepair/util/Decomposition.java | 130 ++++++++++++++
.../iotdb/library/drepair/util/LinearMedian.java | 130 ++++++++++++++
.../iotdb/library/drepair/util/MovingMedian.java | 187 +++++++++++++++++++++
.../iotdb/library/drepair/util/SeasonalRepair.java | 134 +++++++++++++++
5 files changed, 730 insertions(+)
diff --git
a/library-udf/src/main/java/org/apache/iotdb/library/drepair/UDTFSeasonalRepair.java
b/library-udf/src/main/java/org/apache/iotdb/library/drepair/UDTFSeasonalRepair.java
new file mode 100644
index 00000000000..8861dae26b9
--- /dev/null
+++
b/library-udf/src/main/java/org/apache/iotdb/library/drepair/UDTFSeasonalRepair.java
@@ -0,0 +1,149 @@
+/*
+ * 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.iotdb.library.drepair;
+
+import org.apache.iotdb.library.drepair.util.SeasonalRepair;
+import org.apache.iotdb.udf.api.UDTF;
+import org.apache.iotdb.udf.api.access.Row;
+import org.apache.iotdb.udf.api.access.RowIterator;
+import org.apache.iotdb.udf.api.access.RowWindow;
+import org.apache.iotdb.udf.api.collector.PointCollector;
+import org.apache.iotdb.udf.api.customizer.config.UDTFConfigurations;
+import org.apache.iotdb.udf.api.customizer.parameter.UDFParameterValidator;
+import org.apache.iotdb.udf.api.customizer.parameter.UDFParameters;
+import
org.apache.iotdb.udf.api.customizer.strategy.SlidingSizeWindowAccessStrategy;
+import org.apache.iotdb.udf.api.type.Type;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * This function is used to repair the value of the time series.
+ */
+public class UDTFSeasonalRepair implements UDTF {
+ private double k;
+ private int period;
+ private int max_iter;
+
+ private final List<Long> times = new ArrayList<>();
+ private final List<Double> values = new ArrayList<>();
+
+ @Override
+ public void validate(UDFParameterValidator validator) throws Exception {
+ validator
+ .validateInputSeriesNumber(1)
+ .validateInputSeriesDataType(0, Type.FLOAT, Type.DOUBLE,
Type.INT32, Type.INT64)
+ .validate(
+ period -> (int) period > 0,
+ "Parameter \"period\" should be a positive integer.",
+ validator.getParameters().getInt("period"))
+ .validate(
+ k -> (double) k > 0.0,
+ "parameter \"k\" should be a positive float number.",
+ validator.getParameters().getDoubleOrDefault("k", 9.0))
+ .validate(
+ max_iter -> (int) max_iter > 0,
+ "parameter \"max_iter\" should be a positive integer.",
+ validator.getParameters().getIntOrDefault("max_iter",
10));
+ }
+
+ @Override
+ public void beforeStart(UDFParameters parameters, UDTFConfigurations
configurations) throws Exception {
+ configurations.setAccessStrategy(new
SlidingSizeWindowAccessStrategy(Integer.MAX_VALUE))
+ .setOutputDataType(parameters.getDataType(0));
+ period = parameters.getInt("period");
+ k = parameters.getDoubleOrDefault("k", 9.0);
+ max_iter = parameters.getIntOrDefault("max_iter", 10);
+ }
+
+ @Override
+ public void transform(RowWindow rowWindow, PointCollector collector)
throws Exception {
+ RowIterator rowIterator = rowWindow.getRowIterator();
+ while (rowIterator.hasNextRow()) { // load data
+ Row row = rowIterator.next();
+ times.add(row.getTime());
+ double value = switch (row.getDataType(0)) {
+ case INT32 -> row.getInt(0);
+ case INT64 -> row.getLong(0);
+ case FLOAT -> row.getFloat(0);
+ case DOUBLE -> row.getDouble(0);
+ default -> throw new Exception();
+ };
+ values.add(value);
+ }
+ processNaN();
+ }
+
+ @Override
+ public void terminate(PointCollector collector) throws Exception {
+ SeasonalRepair seasonalRepair = new SeasonalRepair(getTimesArray(),
getValuesArray(), period, k, max_iter);
+ double[] repaired = seasonalRepair.getTd_repair();
+ for (int i = 0; i < values.size(); i++) {
+ collector.putDouble(times.get(i), repaired[i]);
+ }
+ }
+
+ private long[] getTimesArray() {
+ long[] rtn = new long[times.size()];
+ for (int i = 0; i < times.size(); ++i)
+ rtn[i] = times.get(i);
+ return rtn;
+ }
+
+ private double[] getValuesArray() {
+ double[] rtn = new double[values.size()];
+ for (int i = 0; i < values.size(); ++i)
+ rtn[i] = values.get(i);
+ return rtn;
+ }
+
+ private void setValues(int i, int idx1, int idx2) {
+ values.set(i, values.get(idx1) + (values.get(idx2) - values.get(idx1))
* (times.get(i) - times.get(idx1)) / (times.get(idx2) - times.get(idx1)));
+ }
+
+ private void processNaN() throws Exception {
+ int idx1 = 0, idx2, n = values.size();
+ while (idx1 < n && Double.isNaN(values.get(idx1))) {
+ idx1++;
+ }
+ idx2 = idx1 + 1;
+ while (idx2 < n && Double.isNaN(values.get(idx2))) {
+ idx2++;
+ }
+ if (idx2 >= n) {
+ throw new Exception("At least two non-NaN values are needed");
+ }
+ for (int i = 0; i < idx2; i++) {
+ setValues(i, idx1, idx2);
+ }
+ for (int i = idx2 + 1; i < n; i++) {
+ if (!Double.isNaN(values.get(i))) {
+ idx1 = idx2;
+ idx2 = i;
+ for (int j = idx1 + 1; j < idx2; j++) {
+ setValues(j, idx1, idx2);
+ }
+ }
+ }
+ for (int i = idx2 + 1; i < n; i++) {
+ setValues(i, idx1, idx2);
+ }
+ }
+}
diff --git
a/library-udf/src/main/java/org/apache/iotdb/library/drepair/util/Decomposition.java
b/library-udf/src/main/java/org/apache/iotdb/library/drepair/util/Decomposition.java
new file mode 100644
index 00000000000..a6c4d70c1ea
--- /dev/null
+++
b/library-udf/src/main/java/org/apache/iotdb/library/drepair/util/Decomposition.java
@@ -0,0 +1,130 @@
+package org.apache.iotdb.library.drepair.util;
+
+public class Decomposition {
+ private final long[] td_time;
+ private final double[] td;
+ private final int period;
+
+ private final double[] seasonal;
+ private final double[] trend;
+ private final double[] residual;
+
+ public Decomposition(long[] td_time, double[] td, int period) throws
Exception {
+ this.td = td;
+ this.td_time = td_time;
+ this.period = period;
+
+ this.seasonal = new double[period];
+ this.trend = new double[td.length];
+ this.residual = new double[td.length];
+
+ this.decompose();
+ }
+
+ private void decompose() throws Exception {
+ if (period > td.length)
+ throw new Exception("Error: Period exceed the size of time
series!");
+
+ // constant
+ int interval = period / 2;
+ int size = td.length;
+ // structure
+ double[] de_trend = new double[size];
+ MovingMedian movingMedian = new MovingMedian(period);
+
+ // step 1: trend
+ if (period % 2 == 1) {
+ throw new Exception("Period must be even.");
+ } else {
+ // initial
+ for (int i = 0; i < period - 1; ++i) movingMedian.update(td[i]);
+ // moving median
+ for (int i = period - 1; i < size; ++i) {
+ movingMedian.update(td[i]);
+ trend[i - interval + 1] = movingMedian.getMedian();
+ }
+ }
+
+ // trend extension
+ constant_ext();
+
+ // step 2: de-trend
+ for (int i = 0; i < size; ++i)
+ de_trend[i] = td[i] - trend[i];
+
+ // step 3: seasonal
+ double[] cal_median = new double[Math.max(period, size / period + 1)];
+ for (int i = 0; i < period; ++i) {
+ // in each cycle
+ for (int j = 0; j < size / period; ++j)
+ cal_median[j] = de_trend[j * period + i];
+
+ if (i < size % period) {
+ cal_median[size / period] = de_trend[i + (size / period) *
period];
+ seasonal[i] = LinearMedian.getMedian(cal_median, size / period
+ 1);
+ } else {
+ seasonal[i] = LinearMedian.getMedian(cal_median, size /
period);
+ }
+ }
+
+ // de-median
+ for (int i = 0; i < period; i++) {
+ cal_median[i] = seasonal[i];
+ }
+ // TODO: mean?
+ double median_s = LinearMedian.getMedian(cal_median, period);
+ for (int i = 0; i < period; ++i)
+ seasonal[i] = seasonal[i] - median_s;
+
+ // step 3: residual
+ for (int i = 0; i < size; ++i)
+ residual[i] = de_trend[i] - seasonal[i % period];
+ }
+
+ private void constant_ext() {
+ int interval = period / 2;
+ for (int i = interval; i > 0; --i)
+ trend[i - 1] = trend[i];
+ for (int i = trend.length - interval - 1; i < trend.length - 1; ++i)
+ trend[i + 1] = trend[i];
+ }
+
+ private void ar_ext() {
+ int interval = period / 2;
+ int end = trend.length - interval - 1;
+
+ double a = 0.0, b = 0.0, d = trend.length - 2 * interval - 1, tmp;
+ for (int i = interval; i < end; ++i) {
+ b -= trend[i];
+ a += trend[i] * trend[i];
+ }
+ tmp = a * d - b * b;
+ a /= tmp;
+ b /= tmp;
+ d /= tmp;
+
+ double sigma = 0.0, a1 = 0.0;
+ for (int i = interval; i < end; ++i) {
+ sigma += (a + b * trend[i]) * trend[i + 1];
+ a1 += (b + d * trend[i]) * trend[i + 1];
+ }
+
+ // extend
+ for (int i = interval; i > 0; --i)
+ trend[i - 1] = (trend[i] - sigma) / a1;
+ for (int i = trend.length - interval - 1; i < trend.length - 1; ++i)
+ trend[i + 1] = a1 * trend[i] + sigma;
+ }
+
+ public double[] getSeasonal() {
+ return seasonal;
+ }
+
+ public double[] getTrend() {
+ return trend;
+ }
+
+ public double[] getResidual() {
+ return residual;
+ }
+}
diff --git
a/library-udf/src/main/java/org/apache/iotdb/library/drepair/util/LinearMedian.java
b/library-udf/src/main/java/org/apache/iotdb/library/drepair/util/LinearMedian.java
new file mode 100644
index 00000000000..f0172c434b1
--- /dev/null
+++
b/library-udf/src/main/java/org/apache/iotdb/library/drepair/util/LinearMedian.java
@@ -0,0 +1,130 @@
+package org.apache.iotdb.library.drepair.util;
+
+public class LinearMedian {
+ //Function to invoke LinearSelect
+ public static double getMedian(double[] S, int size) {
+ return linearSelect(0, size - 1, S, size / 2);
+ }
+
+ //do linearSelect in a recursive way
+ private static double linearSelect(int left, int right, double[] array,
int k) {
+ //if there is only one element now, just record.
+ if (left >= right) {
+ return array[left];
+ }
+ //do the partition
+ int p = pickCleverPivot(left, right, array);
+ int eIndex = partition(left, right, array, p);
+ //after the partition, do following ops
+ if (k <= eIndex) {
+ return linearSelect(left, eIndex - 1, array, k);
+ } else if (k == eIndex + 1) {
+ return array[eIndex];
+ } else {
+ return linearSelect(eIndex + 1, right, array, k);
+ }
+
+ }
+
+ //do Partition with a pivot
+ private static int partition(int left, int right, double[] array, int
pIndex) {
+ //move pivot to last index of the array
+ swap(array, pIndex, right);
+
+ double p = array[right];
+ int l = left;
+ int r = right - 1;
+
+ while (l <= r) {
+ while (l <= r && array[l] <= p) {
+ l++;
+ }
+ while (l <= r && array[r] >= p) {
+ r--;
+ }
+ if (l < r) {
+ swap(array, l, r);
+ }
+ }
+
+ swap(array, l, right);
+ return l;
+ }
+
+ //Pick a random pivot to do the LinearSelect
+ //Implementation inspired from pseudocode provided in assignment
+ //instructions and at https://en.wikipedia.org/wiki/Median_of_medians
+ private static int pickCleverPivot(int left, int right, double[] array) {
+ int n = array.length;
+
+ //Base case: If array length is less than 5, get median of it
+ if ((right - left) < 5) {
+ return getMedianValue(left, right, array);
+ }//end if
+
+ int count = left;
+
+ //Divide array into subgroups of 5
+ //Sort respective subarray to retrieve its median
+ for (int i = left; i <= right; i += 5) {
+
+ int tempRight = i + 4;
+
+ if (tempRight > right) {
+ tempRight = right;
+ }//end if
+
+ int medianSubgroup;
+
+ if ((tempRight - i) <= 2) {
+ continue;
+ } else {
+ medianSubgroup = getMedianValue(i, tempRight, array);
//Retrieve median of subarray
+ }
+
+ //Swap median to front of array
+ swap(array, medianSubgroup, count);
+
+ count++;
+ }//end for
+
+ //Recursively call pickCleverPivot for median of medians
+ return pickCleverPivot(left, count, array);
+ }//end pickCleverPivot
+
+
+ private static int getMedianValue(int left, int right, double[] array) {
+
+ //Sort that subarray! (Using insertion sort that is.)
+ for (int i = left; i <= right; i++) {
+ int j = i;
+ while (j > left && array[j - 1] > array[j]) {
+ swap(array, j, j - 1);
+ j -= 1;
+ }//end while
+ }//end for
+
+
+ int medianPos = 0;
+
+ //Check if length of subarray is even or not
+ //Implementation inspired by code found here:
http://stackoverflow.com/a/11955900
+ if ((right - left) % 2 == 0) {
+ //Retrieve value left of middle to be treated as median
+ medianPos = ((right - left) / 2) - 1;
+ } else {
+ medianPos = (right - left) / 2;
+ }//end if/else statement
+
+ return left + medianPos;
+
+ }//end getMedianValue
+
+
+ //swap two elements in the array
+ private static void swap(double[] array, int a, int b) {
+ double tmp = array[a];
+ array[a] = array[b];
+ array[b] = tmp;
+ }
+}
diff --git
a/library-udf/src/main/java/org/apache/iotdb/library/drepair/util/MovingMedian.java
b/library-udf/src/main/java/org/apache/iotdb/library/drepair/util/MovingMedian.java
new file mode 100644
index 00000000000..84616a2e05e
--- /dev/null
+++
b/library-udf/src/main/java/org/apache/iotdb/library/drepair/util/MovingMedian.java
@@ -0,0 +1,187 @@
+package org.apache.iotdb.library.drepair.util;
+
+// period must be even
+public class MovingMedian {
+
+ private final int windowSize;
+
+ /* The current size of the window */
+ private int size;
+
+ /* Position of the oldest element of the window */
+ private int startIndex;
+
+ /*
+ * Each element of windowHeap is a pointer to either maxHeap or minHeap.
+ * Each element of windowHeapIndex is a index of the element in the
corresponding Heap.
+ * Together they represent the moving window, such that the k-th element
of the window
+ * can be accessed using windowHeap[k].heap[window[k]]
+ * */
+ private final Heap[] windowHeap;
+ private final int[] window;
+
+ private final Heap maxHeap;
+ private final Heap minHeap;
+ private double median;
+
+ public MovingMedian(int windowSize) {
+ this.windowSize = windowSize;
+ this.maxHeap = new Heap(windowSize / 2, false);
+ this.minHeap = new Heap(windowSize / 2, true);
+ window = new int[windowSize];
+ windowHeap = new Heap[windowSize];
+ }
+
+ private int inc(int k) {
+ return ++k == windowSize ? 0 : k;
+ }
+
+ private void calcMedian() {
+ median = (minHeap.top() + maxHeap.top()) / 2;
+ }
+
+ public double getMedian() {
+ return median;
+ }
+
+ public void update(double value) {
+ if (size >= windowSize) {
+ windowHeap[startIndex].extract(window[startIndex]);
+ size--;
+ }
+
+ if (value <= maxHeap.top()) {
+ if (maxHeap.size == maxHeap.cap || (maxHeap.size - minHeap.size)
>= 1) {
+ maxHeap.transfer(0, minHeap);
+ }
+ maxHeap.insert(value, startIndex);
+ } else {
+ if (minHeap.size == minHeap.cap || (minHeap.size - maxHeap.size)
>= 1) {
+ minHeap.transfer(0, maxHeap);
+ }
+ minHeap.insert(value, startIndex);
+ }
+
+ while (minHeap.size > 2 && maxHeap.top() > minHeap.top()) {
+ maxHeap.exchange(0, minHeap, 0);
+ }
+ size++;
+ startIndex = inc(startIndex);
+ calcMedian();
+ }
+
+ class Heap {
+ private int size = 0;
+ private final double[] heap;
+ // contains the inverted index of each element in the heap to their
positions in the window
+ // such that, heap[i] == heap[window[invertedIndex[i]]].
+ private final int[] invertedIndex;
+ private final boolean minHeap;
+ private final int cap;
+
+ public Heap(int cap, boolean minHeap) {
+ this.cap = cap;
+ this.heap = new double[cap + 1];
+ this.invertedIndex = new int[cap + 1];
+ this.minHeap = minHeap;
+ }
+
+ private double top() {
+ return heap[0];
+ }
+
+ void insert(double value, int qIndex) {
+ heap[size] = value;
+ window[qIndex] = size;
+ windowHeap[qIndex] = this;
+ invertedIndex[size] = qIndex;
+ size++;
+ bubleUp(size - 1);
+ }
+
+ void extract(int k) {
+ size--;
+ double d = heap[k];
+ if (size > k) {
+ // Move the last element to the k-th position
+ heap[k] = heap[size];
+ invertedIndex[k] = invertedIndex[size];
+ window[invertedIndex[k]] = k;
+ windowHeap[invertedIndex[k]] = this;
+ }
+ bubleUp(k);
+ bubleDown(k);
+ }
+
+ void transfer(int k, Heap other) {
+ other.insert(heap[k], invertedIndex[k]);
+ extract(k);
+ }
+
+ void exchange(int k, Heap other, int m) {
+ double val = other.heap[m];
+ int qIndex = other.invertedIndex[m];
+ other.extract(m);
+ transfer(k, other);
+ insert(val, qIndex);
+ }
+
+ private void swap(int i, int j) {
+ int eli = invertedIndex[i];
+ int elj = invertedIndex[j];
+ double di = heap[i];
+ double dj = heap[j];
+ window[elj] = i;
+ window[eli] = j;
+ heap[j] = di;
+ heap[i] = dj;
+ invertedIndex[i] = elj;
+ invertedIndex[j] = eli;
+ }
+
+ private void bubleUp(int k) {
+ while (k > 0) {
+ int parent = parentOf(k);
+ boolean swap = minHeap ? heap[parent] > heap[k] : heap[parent]
< heap[k];
+ if (swap) {
+ swap(k, parent);
+ }
+ k = parent;
+ }
+ }
+
+ private void bubleDown(int k) {
+ int half = size >>> 1;
+ while (k < half) {
+ double val = heap[k];
+ int leftChild = leftChildOf(k);
+ int rightChild = leftChild + 1;
+ int child = leftChild;
+ double childVal = heap[child];
+ boolean swap;
+
+ if (rightChild < size && (minHeap ? heap[rightChild] <
childVal : heap[rightChild] > childVal)) {
+ child = rightChild;
+ childVal = heap[child];
+ }
+ swap = minHeap ? childVal < val : childVal > val;
+ if (!swap)
+ break;
+ swap(k, child);
+ k = child;
+ }
+ }
+
+ private int parentOf(int k) {
+ return (k - 1) >>> 1;
+ }
+
+ private int leftChildOf(int k) {
+ return 2 * k + 1;
+ }
+
+ private int rightChildOf(int i) {
+ return leftChildOf(i) + 1;
+ }
+ }
+}
diff --git
a/library-udf/src/main/java/org/apache/iotdb/library/drepair/util/SeasonalRepair.java
b/library-udf/src/main/java/org/apache/iotdb/library/drepair/util/SeasonalRepair.java
new file mode 100644
index 00000000000..171206c8508
--- /dev/null
+++
b/library-udf/src/main/java/org/apache/iotdb/library/drepair/util/SeasonalRepair.java
@@ -0,0 +1,134 @@
+package org.apache.iotdb.library.drepair.util;
+
+import java.util.ArrayList;
+
+public class SeasonalRepair {
+ private final long[] td_time;
+ private final double[] td_dirty;
+ private final double[] td_repair;
+ private final int period;
+ private final double k; // k*mad
+ private final int max_iter;
+
+ private double mu, sigma;
+ private double[] seasonal, trend, residual;
+ private final int size;
+ private final long cost_time;
+
+ public SeasonalRepair(long[] td_time, double[] td_dirty, int period,
double k, int max_iter) throws Exception {
+ this.td_time = td_time;
+ this.td_dirty = td_dirty;
+ this.td_repair = new double[td_dirty.length];
+ this.period = period;
+ this.k = k;
+ this.max_iter = max_iter;
+
+ this.size = td_dirty.length;
+
+ long startTime = System.currentTimeMillis();
+ this.repair();
+ long endTime = System.currentTimeMillis();
+ this.cost_time = endTime - startTime;
+// System.out.println("SRRD time cost:" + cost_time + "ms");
+ }
+
+ private void repair() throws Exception {
+ System.arraycopy(td_dirty, 0, td_repair, 0, td_dirty.length);
+
+ int h = 0;
+ for (; h < max_iter; ++h) {
+ Decomposition de = new Decomposition(td_time, td_repair, period);
+ seasonal = de.getSeasonal();
+ trend = de.getTrend();
+ residual = de.getResidual();
+
+ estimate();
+
+ boolean flag = true;
+ for (int i = 0; i < size; ++i) {
+ if (sub(residual[i], mu) > k * sigma) {
+ flag = false;
+ td_repair[i] = generate(i);
+ }
+ }
+ if (flag) break;
+ }
+// System.out.println("Stop after " + (h + 1) + " iterations");
+ }
+
+
+ private void estimate() {
+ // get the sum of array
+ double sum = 0.0;
+ for (double i : residual) {
+ sum += i;
+ }
+
+ // get the mean of array
+ int length = residual.length;
+
+ mu = sum / length;
+
+ // calculate the standard deviation
+ double standardDeviation = 0.0;
+ for (double num : residual) {
+ standardDeviation += Math.pow(num - mu, 2);
+ }
+
+ sigma = Math.sqrt(standardDeviation / length);
+ }
+
+ private double generate(int pos) {
+ // in each cycle
+ int i = pos % period;
+ ArrayList<Double> arr = new ArrayList<>();
+
+ for (int j = 0; j < size / period; ++j)
+ if (j * period + i != pos) // remove anomaly
+ arr.add(residual[j * period + i]);
+ if (i < size % period && i + (size / period) * period != pos)
+ arr.add(residual[i + (size / period) * period]);
+
+ double[] cal_median = new double[arr.size()];
+ for (int j = 0; j < arr.size(); j++)
+ cal_median[j] = arr.get(j);
+
+ return get_median(cal_median) + seasonal[pos % period] + trend[pos];
+ }
+
+ private double sub(double a, double b) {
+ return a > b ? a - b : b - a;
+ }
+
+ private double get_median(double[] A) {
+ return quickSelect(A, 0, A.length - 1, A.length / 2);
+ }
+
+ private double quickSelect(double[] A, int l, int r, int k) {
+ if (l >= r) return A[k];
+
+ double x = A[l];
+ int i = l - 1, j = r + 1;
+ while (i < j) {
+ do i++; while (A[i] < x);
+ do j--; while (A[j] > x);
+ if (i < j) {
+ double temp = A[i];
+ A[i] = A[j];
+ A[j] = temp;
+ }
+ }
+
+ if (k <= j) return quickSelect(A, l, j, k);
+ else return quickSelect(A, j + 1, r, k);
+ }
+
+ public double[] getTd_repair() {
+ return td_repair;
+ }
+
+ public long getCost_time() {
+ return cost_time;
+ }
+}
+
