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 
17 package android.media;
18 
19 import android.util.Log;
20 import android.util.Pair;
21 import android.util.Range;
22 import android.util.Rational;
23 import android.util.Size;
24 
25 import java.util.Arrays;
26 import java.util.Comparator;
27 import java.util.Vector;
28 
29 // package private
30 class 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      */
sortDistinctRanges(Range<T>[] ranges)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>>
intersectSortedDistinctRanges(Range<T>[] one, Range<T>[] another)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>>
binarySearchDistinctRanges(Range<T>[] ranges, T value)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