import java.util.*;
import java.util.zip.*;
import java.util.List;
import java.util.regex.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.*;
import java.util.function.*;
import javax.swing.*;
import javax.swing.event.*;
import javax.swing.text.*;
import javax.swing.table.*;
import java.io.*;
import java.net.*;
import java.lang.reflect.*;
import java.lang.ref.*;
import java.lang.management.*;
import java.security.*;
import java.security.spec.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.image.*;
import java.awt.geom.*;
import javax.imageio.*;
import java.math.*;
import java.time.Duration;
import java.lang.invoke.VarHandle;
import java.lang.invoke.MethodHandles;
import static x30_pkg.x30_util.DynamicObject;
import java.text.*;
import java.text.NumberFormat;
import java.util.TimeZone;
import java.awt.geom.*;
class main {
static class CompressToInterpolatedDoubleArray {
// raw data to compress (integers)
int[] data;
// output
InterpolatedDoubleArray result;
// options
final public CompressToInterpolatedDoubleArray setSlopeTolerance(double slopeTolerance){ return slopeTolerance(slopeTolerance); }
public CompressToInterpolatedDoubleArray slopeTolerance(double slopeTolerance) { this.slopeTolerance = slopeTolerance; return this; } final public double getSlopeTolerance(){ return slopeTolerance(); }
public double slopeTolerance() { return slopeTolerance; }
double slopeTolerance = 0.01;
// internal
IntBuffer indices = new IntBuffer();
DoubleBuffer values = new DoubleBuffer();
CompressToInterpolatedDoubleArray(int[] data) {
this.data = data;}
InterpolatedDoubleArray get() {
int iData = 0;
while (iData < data.length) {
int startValue = data[iData];
// possible range of actual floating point starting value
DoubleRange startValueRange = doubleRange(startValue-0.5, startValue+0.5);
// see how far the straight line goes from iData
DoubleRange totalSlopeRange = null;
int jData; // our straight line ends at jData-1
for (jData = iData+1; jData < data.length; jData++) {
double x = data[jData], h = jData-iData;
// possible range of actual floating point value
DoubleRange xRange = doubleRange(x-0.5, x+0.5);
// most generous range for possible slope depending
// on possible floating point values at start and end
DoubleRange slopeRange = doubleRange(
(xRange.start-startValueRange.end)/h,
(xRange.end-startValueRange.start)/h);
// grow range a little to avoid size 0 ranges
slopeRange = growRange(slopeTolerance, slopeRange);
printVars("iData", iData, "jData", jData, "slopeRange", slopeRange, "totalSlopeRange", totalSlopeRange);
if (totalSlopeRange == null)
totalSlopeRange = slopeRange;
else {
slopeRange = intersectRanges(slopeRange, totalSlopeRange);
if (empty(slopeRange))
break;
else
totalSlopeRange = slopeRange;
}
}
indices.add(iData);
values.add(data[iData]);
iData = max(iData+1, jData-1);
}
return result = new InterpolatedDoubleArray(indices.toArrayNonNull(), values.toArrayNonNull());
}
}
static DoubleRange doubleRange(double start, double end) {
return new DoubleRange(start, end);
}
static DoubleRange growRange(DoubleRange r, double amount) {
return r == null ? null : doubleRange(r.start-amount, r.end+amount);
}
static DoubleRange growRange(double amount, DoubleRange r) {
return growRange(r, amount);
}
// Use like this: printVars(+x, +y);
// Or: printVars("bla", +x);
// Or: printVars bla(, +x);
static void printVars(Object... params) {
printVars_str(params);
}
static Range intersectRanges(Range a, Range b) {
float min = max(a.min, b.min);
float max = min(a.max, b.max);
return min <= max ? new Range(min, max) : null;
}
static DoubleRange intersectRanges(DoubleRange a, DoubleRange b) {
return intersectDoubleRanges(a, b);
}
static boolean empty(Collection c) { return c == null || c.isEmpty(); }
static boolean empty(Iterable c) { return c == null || !c.iterator().hasNext(); }
static boolean empty(CharSequence s) { return s == null || s.length() == 0; }
static boolean empty(Map map) { return map == null || map.isEmpty(); }
static boolean empty(Object[] o) { return o == null || o.length == 0; }
static boolean empty(BitSet bs) { return bs == null || bs.isEmpty(); }
static boolean empty(Object o) {
if (o instanceof Collection) return empty((Collection) o);
if (o instanceof String) return empty((String) o);
if (o instanceof Map) return empty((Map) o);
if (o instanceof Object[]) return empty((Object[]) o);
if (o instanceof byte[]) return empty((byte[]) o);
if (o == null) return true;
throw fail("unknown type for 'empty': " + getType(o));
}
static boolean empty(Iterator i) { return i == null || !i.hasNext(); }
static boolean empty(double[] a) { return a == null || a.length == 0; }
static boolean empty(float[] a) { return a == null || a.length == 0; }
static boolean empty(int[] a) { return a == null || a.length == 0; }
static boolean empty(long[] a) { return a == null || a.length == 0; }
static boolean empty(byte[] a) { return a == null || a.length == 0; }
static boolean empty(short[] a) { return a == null || a.length == 0; }
static boolean empty(IMultiMap mm) { return mm == null || mm.size() == 0; }
static boolean empty(File f) { return getFileSize(f) == 0; }
static boolean empty(DoubleRange r) { return r == null || r.isEmpty(); }
static boolean empty(IntBuffer b) { return b == null || b.isEmpty(); }
static boolean empty(Rect r) { return !(r != null && r.w != 0 && r.h != 0); }
static boolean empty(Chain c) { return c == null; }
static boolean empty(AppendableChain c) { return c == null; }
static int max(int a, int b) { return Math.max(a, b); }
static int max(int a, int b, int c) { return max(max(a, b), c); }
static long max(int a, long b) { return Math.max((long) a, b); }
static long max(long a, long b) { return Math.max(a, b); }
static double max(int a, double b) { return Math.max((double) a, b); }
static float max(float a, float b) { return Math.max(a, b); }
static double max(double a, double b) { return Math.max(a, b); }
static > A max (Iterable l) {
A max = null;
var it = iterator(l);
if (it.hasNext()) {
max = it.next();
while (it.hasNext()) {
A a = it.next();
if (cmp(a, max) > 0)
max = a;
}
}
return max;
}
/*Nah.
static int max(Collection c) {
int x = Integer.MIN_VALUE;
for (int i : c) x = max(x, i);
ret x;
}*/
static double max(double[] c) {
if (c.length == 0) return Double.MIN_VALUE;
double x = c[0];
for (int i = 1; i < c.length; i++) x = Math.max(x, c[i]);
return x;
}
static float max(float[] c) {
if (c.length == 0) return Float.MAX_VALUE;
float x = c[0];
for (int i = 1; i < c.length; i++) x = Math.max(x, c[i]);
return x;
}
static byte max(byte[] c) {
byte x = -128;
for (byte d : c) if (d > x) x = d;
return x;
}
static short max(short[] c) {
short x = -0x8000;
for (short d : c) if (d > x) x = d;
return x;
}
static int max(int[] c) {
int x = Integer.MIN_VALUE;
for (int d : c) if (d > x) x = d;
return x;
}
static > A max(A a, A b) {
return cmp(a, b) >= 0 ? a : b;
}
// Use like this: printVars_str(+x, +y);
// Or: printVars("bla", +x);
// Or: printVars bla(+x);
static void printVars_str(Object... params) {
print(renderVars_str(params));
}
static int min(int a, int b) {
return Math.min(a, b);
}
static long min(long a, long b) {
return Math.min(a, b);
}
static float min(float a, float b) { return Math.min(a, b); }
static float min(float a, float b, float c) { return min(min(a, b), c); }
static double min(double a, double b) {
return Math.min(a, b);
}
static double min(double[] c) {
double x = Double.MAX_VALUE;
for (double d : c) x = Math.min(x, d);
return x;
}
static float min(float[] c) {
float x = Float.MAX_VALUE;
for (float d : c) x = Math.min(x, d);
return x;
}
static byte min(byte[] c) {
byte x = 127;
for (byte d : c) if (d < x) x = d;
return x;
}
static short min(short[] c) {
short x = 0x7FFF;
for (short d : c) if (d < x) x = d;
return x;
}
static int min(int[] c) {
int x = Integer.MAX_VALUE;
for (int d : c) if (d < x) x = d;
return x;
}
static DoubleRange intersectDoubleRanges(DoubleRange a, DoubleRange b) {
double start = max(a.start, b.start);
double end = min(a.end, b.end);
return start <= end ? new DoubleRange(start, end) : null;
}
static RuntimeException fail() { throw new RuntimeException("fail"); }
static RuntimeException fail(Throwable e) { throw asRuntimeException(e); }
static RuntimeException fail(Object msg) { throw new RuntimeException(String.valueOf(msg)); }
static RuntimeException fail(Object... objects) { throw new Fail(objects); }
static RuntimeException fail(String msg) { throw new RuntimeException(msg == null ? "" : msg); }
static RuntimeException fail(String msg, Throwable innerException) { throw new RuntimeException(msg, innerException); }
static String getType(Object o) {
return getClassName(o);
}
static long getFileSize(String path) {
return path == null ? 0 : new File(path).length();
}
static long getFileSize(File f) {
return f == null ? 0 : f.length();
}
static Iterator iterator(Iterable c) {
return c == null ? emptyIterator() : c.iterator();
}
static int cmp(Number a, Number b) {
return a == null ? b == null ? 0 : -1 : cmp(a.doubleValue(), b.doubleValue());
}
static int cmp(double a, double b) {
return a < b ? -1 : a == b ? 0 : 1;
}
static int cmp(int a, int b) {
return a < b ? -1 : a == b ? 0 : 1;
}
static int cmp(long a, long b) {
return a < b ? -1 : a == b ? 0 : 1;
}
static int cmp(Object a, Object b) {
if (a == null) return b == null ? 0 : -1;
if (b == null) return 1;
return ((Comparable) a).compareTo(b);
}
static volatile StringBuffer local_log = new StringBuffer(); // not redirected
static boolean printAlsoToSystemOut = true;
static volatile Appendable print_log = local_log; // might be redirected, e.g. to main bot
// in bytes - will cut to half that
static volatile int print_log_max = 1024*1024;
static volatile int local_log_max = 100*1024;
static boolean print_silent = false; // total mute if set
static Object print_byThread_lock = new Object();
static volatile ThreadLocal