• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1// Copyright 2013 The Flutter Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5part of engine;
6
7enum _ComparisonResult {
8  inside,
9  higher,
10  lower,
11}
12
13/// Each instance of [UnicodeRange] represents a range of unicode characters
14/// that are assigned a [CharProperty]. For example, the following snippet:
15///
16/// ```dart
17/// UnicodeRange(0x0041, 0x005A, CharProperty.ALetter);
18/// ```
19///
20/// is saying that all characters between 0x0041 ("A") and 0x005A ("Z") are
21/// assigned the property [CharProperty.ALetter].
22///
23/// Note that the Unicode spec uses inclusive ranges and we are doing the
24/// same here.
25class UnicodeRange<P> {
26  const UnicodeRange(this.start, this.end, this.property);
27
28  final int start;
29
30  final int end;
31
32  final P property;
33
34  /// Compare a [value] to this range.
35  ///
36  /// The return value is either:
37  /// - lower: The value is lower than the range.
38  /// - higher: The value is higher than the range
39  /// - inside: The value is within the range.
40  _ComparisonResult compare(int value) {
41    if (value < start) {
42      return _ComparisonResult.lower;
43    }
44    if (value > end) {
45      return _ComparisonResult.higher;
46    }
47    return _ComparisonResult.inside;
48  }
49}
50
51/// Given a list of [UnicodeRange]s, this class performs efficient lookup
52/// to find which range a value falls into.
53///
54/// The lookup algorithm expects the ranges to have the following constraints:
55/// - Be sorted.
56/// - No overlap between the ranges.
57/// - Gaps between ranges are ok.
58///
59/// This is used in the context of unicode to find out what property a letter
60/// has. The properties are then used to decide word boundaries, line break
61/// opportunities, etc.
62class UnicodePropertyLookup<P> {
63  const UnicodePropertyLookup(this.ranges);
64
65  final List<UnicodeRange<P>> ranges;
66
67  P find(int value) {
68    final int index = _binarySearch(value);
69    return index == -1 ? null : ranges[index].property;
70  }
71
72  int _binarySearch(int value) {
73    int min = 0;
74    int max = ranges.length;
75    while (min < max) {
76      final int mid = min + ((max - min) >> 1);
77      final UnicodeRange<P> range = ranges[mid];
78      switch (range.compare(value)) {
79        case _ComparisonResult.higher:
80          min = mid + 1;
81          break;
82        case _ComparisonResult.lower:
83          max = mid;
84          break;
85        case _ComparisonResult.inside:
86          return mid;
87      }
88    }
89    return -1;
90  }
91}
92