'Assuming that s is the prefix of a string in self.completions,
return the longest string which is a prefix of all the strings which
s is a prefix of them. If s is not a prefix of a string, return s.'

def _complete_string(self, s):

    first = self._binary_search(s)
    if (self.completions[first][:len(s)] != s):
        return s
    i = (first + 1)
    j = len(self.completions)
    while (j > i):
        m = ((i + j) // 2)
        if (self.completions[m][:len(s)] != s):
            j = m
        else:
            i = (m + 1)
    last = (i - 1)
    if (first == last):
        return self.completions[first]
    first_comp = self.completions[first]
    last_comp = self.completions[last]
    min_len = min(len(first_comp), len(last_comp))
    i = len(s)
    while ((i < min_len) and (first_comp[i] == last_comp[i])):
        i += 1
    return first_comp[:i]
