• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1# -*- coding: utf-8 -*-
2# Copyright 2018 The Chromium OS Authors. All rights reserved.
3# Use of this source code is governed by a BSD-style license that can be
4# found in the LICENSE file.
5
6"""A collection of classes/functions to manipulate strings."""
7from __future__ import absolute_import
8from __future__ import division
9from __future__ import print_function
10
11import bisect
12
13
14class StringTooLongError(Exception):
15    """Raised when string is too long to manipulate."""
16
17
18def join_longest_with_length_limit(string_list, length_limit, separator='',
19                                   do_join=True):
20    """Join strings to meet length limit and yield results.
21
22    Join strings from |string_list| using |separator| and yield the results.
23    Each result string should be as long as possible while still shorter than
24    |length_limit|. In other words, this function yields minimum number of
25    result strings.
26
27    An error will be raised when any string in |string_list| is longer than
28    |length_limit| because the result string joined must be longer than
29    |length_limit| in any case.
30
31    @param string_list: A list of strings to be joined.
32    @param length_limit: The maximum length of the result string.
33    @param separator: The separator to join strings.
34    @param do_join: join the result list to string if True, else just return the
35        result list.
36
37    @yield The result string.
38    @throws StringTooLongError when any string in |string_list| is longer than
39        |length_limit|."""
40    # The basic idea is, always select longest string which shorter than length
41    # limit, then update the limit with subtracting the length of selected
42    # string plus separator. Repeat the process until no more strings shorter
43    # than the updated limit. Then yield the result and start next loop.
44
45    string_list = sorted(string_list, key=len)
46    # The length of longest string should shorter than the limit.
47    if len(string_list[-1]) > length_limit:
48        raise StringTooLongError('At least one string is longer than length '
49                                 'limit: %s' % length_limit)
50
51    length_list = [len(s) for s in string_list]
52    len_sep = len(separator)
53    length_limit += len_sep
54    # Call str.join directly when possible.
55    if sum(length_list) + len_sep * len(string_list) <= length_limit:
56        yield separator.join(string_list) if do_join else string_list
57        return
58
59    result = []
60    new_length_limit = length_limit
61    while string_list:
62        index = bisect.bisect_right(length_list,
63                                    new_length_limit - len_sep) - 1
64        if index < 0:  # All available strings are longer than the limit.
65            yield separator.join(result) if do_join else result
66            result = []
67            new_length_limit = length_limit
68            continue
69
70        result.append(string_list.pop(index))
71        new_length_limit -= length_list.pop(index) + len_sep
72
73    if result:
74        yield separator.join(result) if do_join else result
75