1/*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package android.media;
18
19import android.util.Log;
20import android.util.Pair;
21import android.util.Range;
22import android.util.Rational;
23import android.util.Size;
24
25import java.util.Arrays;
26import java.util.Comparator;
27import java.util.Vector;
28
29import static com.android.internal.util.Preconditions.checkNotNull;
30
31// package private
32class Utils {
33    private static final String TAG = "Utils";
34
35    /**
36     * Sorts distinct (non-intersecting) range array in ascending order.
37     * @throws java.lang.IllegalArgumentException if ranges are not distinct
38     */
39    public static <T extends Comparable<? super T>> void sortDistinctRanges(Range<T>[] ranges) {
40        Arrays.sort(ranges, new Comparator<Range<T>>() {
41            @Override
42            public int compare(Range<T> lhs, Range<T> rhs) {
43                if (lhs.getUpper().compareTo(rhs.getLower()) < 0) {
44                    return -1;
45                } else if (lhs.getLower().compareTo(rhs.getUpper()) > 0) {
46                    return 1;
47                }
48                throw new IllegalArgumentException(
49                        "sample rate ranges must be distinct (" + lhs + " and " + rhs + ")");
50            }
51        });
52    }
53
54    /**
55     * Returns the intersection of two sets of non-intersecting ranges
56     * @param one a sorted set of non-intersecting ranges in ascending order
57     * @param another another sorted set of non-intersecting ranges in ascending order
58     * @return the intersection of the two sets, sorted in ascending order
59     */
60    public static <T extends Comparable<? super T>>
61            Range<T>[] intersectSortedDistinctRanges(Range<T>[] one, Range<T>[] another) {
62        int ix = 0;
63        Vector<Range<T>> result = new Vector<Range<T>>();
64        for (Range<T> range: another) {
65            while (ix < one.length &&
66                    one[ix].getUpper().compareTo(range.getLower()) < 0) {
67                ++ix;
68            }
69            while (ix < one.length &&
70                    one[ix].getUpper().compareTo(range.getUpper()) < 0) {
71                result.add(range.intersect(one[ix]));
72                ++ix;
73            }
74            if (ix == one.length) {
75                break;
76            }
77            if (one[ix].getLower().compareTo(range.getUpper()) <= 0) {
78                result.add(range.intersect(one[ix]));
79            }
80        }
81        return result.toArray(new Range[result.size()]);
82    }
83
84    /**
85     * Returns the index of the range that contains a value in a sorted array of distinct ranges.
86     * @param ranges a sorted array of non-intersecting ranges in ascending order
87     * @param value the value to search for
88     * @return if the value is in one of the ranges, it returns the index of that range.  Otherwise,
89     * the return value is {@code (-1-index)} for the {@code index} of the range that is
90     * immediately following {@code value}.
91     */
92    public static <T extends Comparable<? super T>>
93            int binarySearchDistinctRanges(Range<T>[] ranges, T value) {
94        return Arrays.binarySearch(ranges, Range.create(value, value),
95                new Comparator<Range<T>>() {
96                    @Override
97                    public int compare(Range<T> lhs, Range<T> rhs) {
98                        if (lhs.getUpper().compareTo(rhs.getLower()) < 0) {
99                            return -1;
100                        } else if (lhs.getLower().compareTo(rhs.getUpper()) > 0) {
101                            return 1;
102                        }
103                        return 0;
104                    }
105                });
106    }
107
108    /**
109     * Returns greatest common divisor
110     */
111    static int gcd(int a, int b) {
112        if (a == 0 && b == 0) {
113            return 1;
114        }
115        if (b < 0) {
116            b = -b;
117        }
118        if (a < 0) {
119            a = -a;
120        }
121        while (a != 0) {
122            int c = b % a;
123            b = a;
124            a = c;
125        }
126        return b;
127    }
128
129    /** Returns the equivalent factored range {@code newrange}, where for every
130     * {@code e}: {@code newrange.contains(e)} implies that {@code range.contains(e * factor)},
131     * and {@code !newrange.contains(e)} implies that {@code !range.contains(e * factor)}.
132     */
133    static Range<Integer>factorRange(Range<Integer> range, int factor) {
134        if (factor == 1) {
135            return range;
136        }
137        return Range.create(divUp(range.getLower(), factor), range.getUpper() / factor);
138    }
139
140    /** Returns the equivalent factored range {@code newrange}, where for every
141     * {@code e}: {@code newrange.contains(e)} implies that {@code range.contains(e * factor)},
142     * and {@code !newrange.contains(e)} implies that {@code !range.contains(e * factor)}.
143     */
144    static Range<Long>factorRange(Range<Long> range, long factor) {
145        if (factor == 1) {
146            return range;
147        }
148        return Range.create(divUp(range.getLower(), factor), range.getUpper() / factor);
149    }
150
151    private static Rational scaleRatio(Rational ratio, int num, int den) {
152        int common = gcd(num, den);
153        num /= common;
154        den /= common;
155        return new Rational(
156                (int)(ratio.getNumerator() * (double)num),     // saturate to int
157                (int)(ratio.getDenominator() * (double)den));  // saturate to int
158    }
159
160    static Range<Rational> scaleRange(Range<Rational> range, int num, int den) {
161        if (num == den) {
162            return range;
163        }
164        return Range.create(
165                scaleRatio(range.getLower(), num, den),
166                scaleRatio(range.getUpper(), num, den));
167    }
168
169    static Range<Integer> alignRange(Range<Integer> range, int align) {
170        return range.intersect(
171                divUp(range.getLower(), align) * align,
172                (range.getUpper() / align) * align);
173    }
174
175    static int divUp(int num, int den) {
176        return (num + den - 1) / den;
177    }
178
179    private static long divUp(long num, long den) {
180        return (num + den - 1) / den;
181    }
182
183    /**
184     * Returns least common multiple
185     */
186    private static long lcm(int a, int b) {
187        if (a == 0 || b == 0) {
188            throw new IllegalArgumentException("lce is not defined for zero arguments");
189        }
190        return (long)a * b / gcd(a, b);
191    }
192
193    static Range<Integer> intRangeFor(double v) {
194        return Range.create((int)v, (int)Math.ceil(v));
195    }
196
197    static Range<Long> longRangeFor(double v) {
198        return Range.create((long)v, (long)Math.ceil(v));
199    }
200
201    static Size parseSize(Object o, Size fallback) {
202        try {
203            return Size.parseSize((String) o);
204        } catch (ClassCastException e) {
205        } catch (NumberFormatException e) {
206        } catch (NullPointerException e) {
207            return fallback;
208        }
209        Log.w(TAG, "could not parse size '" + o + "'");
210        return fallback;
211    }
212
213    static int parseIntSafely(Object o, int fallback) {
214        try {
215            String s = (String)o;
216            return Integer.parseInt(s);
217        } catch (ClassCastException e) {
218        } catch (NumberFormatException e) {
219        } catch (NullPointerException e) {
220            return fallback;
221        }
222        Log.w(TAG, "could not parse integer '" + o + "'");
223        return fallback;
224    }
225
226    static Range<Integer> parseIntRange(Object o, Range<Integer> fallback) {
227        try {
228            String s = (String)o;
229            int ix = s.indexOf('-');
230            if (ix >= 0) {
231                return Range.create(
232                        Integer.parseInt(s.substring(0, ix), 10),
233                        Integer.parseInt(s.substring(ix + 1), 10));
234            }
235            int value = Integer.parseInt(s);
236            return Range.create(value, value);
237        } catch (ClassCastException e) {
238        } catch (NumberFormatException e) {
239        } catch (NullPointerException e) {
240            return fallback;
241        } catch (IllegalArgumentException e) {
242        }
243        Log.w(TAG, "could not parse integer range '" + o + "'");
244        return fallback;
245    }
246
247    static Range<Long> parseLongRange(Object o, Range<Long> fallback) {
248        try {
249            String s = (String)o;
250            int ix = s.indexOf('-');
251            if (ix >= 0) {
252                return Range.create(
253                        Long.parseLong(s.substring(0, ix), 10),
254                        Long.parseLong(s.substring(ix + 1), 10));
255            }
256            long value = Long.parseLong(s);
257            return Range.create(value, value);
258        } catch (ClassCastException e) {
259        } catch (NumberFormatException e) {
260        } catch (NullPointerException e) {
261            return fallback;
262        } catch (IllegalArgumentException e) {
263        }
264        Log.w(TAG, "could not parse long range '" + o + "'");
265        return fallback;
266    }
267
268    static Range<Rational> parseRationalRange(Object o, Range<Rational> fallback) {
269        try {
270            String s = (String)o;
271            int ix = s.indexOf('-');
272            if (ix >= 0) {
273                return Range.create(
274                        Rational.parseRational(s.substring(0, ix)),
275                        Rational.parseRational(s.substring(ix + 1)));
276            }
277            Rational value = Rational.parseRational(s);
278            return Range.create(value, value);
279        } catch (ClassCastException e) {
280        } catch (NumberFormatException e) {
281        } catch (NullPointerException e) {
282            return fallback;
283        } catch (IllegalArgumentException e) {
284        }
285        Log.w(TAG, "could not parse rational range '" + o + "'");
286        return fallback;
287    }
288
289    static Pair<Size, Size> parseSizeRange(Object o) {
290        try {
291            String s = (String)o;
292            int ix = s.indexOf('-');
293            if (ix >= 0) {
294                return Pair.create(
295                        Size.parseSize(s.substring(0, ix)),
296                        Size.parseSize(s.substring(ix + 1)));
297            }
298            Size value = Size.parseSize(s);
299            return Pair.create(value, value);
300        } catch (ClassCastException e) {
301        } catch (NumberFormatException e) {
302        } catch (NullPointerException e) {
303            return null;
304        } catch (IllegalArgumentException e) {
305        }
306        Log.w(TAG, "could not parse size range '" + o + "'");
307        return null;
308    }
309}
310