Home | History | Annotate | Download | only in cros 
      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."""
      7 from __future__ import absolute_import
      8 from __future__ import division
      9 from __future__ import print_function
     10 
     11 import bisect
     12 
     13 
     14 class StringTooLongError(Exception):
     15     """Raised when string is too long to manipulate."""
     16 
     17 
     18 def 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