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