NSString的constrainedToSize方法是什么？

Question

不要和返回CGSize的NSString sizeWithFont方法混淆，我需要的是一个可以返回NSString并限制在特定CGSize内的方法。我之所以想这么做，是因为在使用Core Text绘制文本时，我想在字符串末尾添加省略号(...)。我知道NSString的drawInRect方法可以为我实现这一点，但我正在使用Core Text，并且kCTLineBreakByTruncatingTail会截断每行的末尾而不是字符串的末尾。

我发现了一种字符串截断方法，可以将字符串截断到特定的宽度，并且很容易将其改为适用于CGSize，但是对于长字符串，该算法非常慢，实际上无法使用。（截取一个长字符串需要超过10秒）。必须有更快的“计算机科学”/数学算法方式来完成这个任务。是否有人敢尝试提出更快的实现方式？

编辑：我已经将其转换为二进制算法：

-(NSString*)getStringByTruncatingToSize:(CGSize)size string:(NSString*)string withFont:(UIFont*)font
{
    int min = 0, max = string.length, mid;
    while (min < max) {
        mid = (min+max)/2;

        NSString *currentString = [string substringWithRange:NSMakeRange(min, mid - min)];
        CGSize currentSize = [currentString sizeWithFont:font constrainedToSize:CGSizeMake(size.width, MAXFLOAT)];

        if (currentSize.height < size.height){
            min = mid + 1;
        } else if (currentSize.height > size.height) {
            max = mid - 1;
        } else {
            break;
        }
    }

   NSMutableString *finalString = [[string substringWithRange:NSMakeRange(0, min)] mutableCopy];
   if(finalString.length < self.length)
         [finalString replaceCharactersInRange:NSMakeRange(finalString.length - 3, 3) withString:@"..."];

   return finalString;
}

问题在于有时候会把字符串截短了，即使还有空间。我想这就是最后一个条件发挥作用的地方。如何确保它不会截断太多？

- Snowman

---

从你现有的东西开始，作为第一步，也许你可以尝试将其转换为二分查找，而不是线性查找？ - jscs

除非找到完全匹配（不太可能），否则必须继续搜索，直到退出循环底部为止，在此时点min> = max，并且其中一个值是您想要的索引。 - benzado

好的，我重新编辑了它。就我的测试而言，它运行得很好。有什么地方看起来不对吗？ - Snowman

看起来还好，但我不明白为什么你要比较高度而不是宽度。 - benzado

Answer 1

好消息！有一种“计算机科学/数学方法”可以更快地完成这个任务。

你链接到的示例执行的是线性搜索：它只是从字符串末尾逐个削减一个字符，直到长度足够短。因此，它需要的时间将随着字符串长度的增加呈线性增长，在处理长字符串时速度会非常慢，正如你所发现的那样。

然而，你可以很容易地将二分搜索技术应用于字符串。你不是从末尾开始逐个删除字符，而是从中间开始：

THIS IS THE STRING THAT YOU WANT TO TRUNCATE
                       ^

你需要计算“THIS IS THE STRING THAT”的宽度。如果太宽，就将测试点移动到左侧空格的中点。就像这样：

THIS IS THE STRING THAT YOU WANT TO TRUNCATE
          ^            |

另一方面，如果它不够宽，您将测试点移动到另一半的中点：

THIS IS THE STRING THAT YOU WANT TO TRUNCATE
                       |         ^

你需要重复这个过程，直到找到刚好在你宽度限制下的点。因为每次都将搜索区域减半，所以你最多只需要计算log2 N次宽度（其中N是字符串长度），即使对于非常长的字符串也不会增长得很快。

换句话说，如果你将输入字符串的长度加倍，那么只需要进行一次额外的宽度计算。

从维基百科的二分查找示例开始，这里有一个例子。请注意，由于我们不寻找精确匹配（你想要最大的适合的），所以逻辑略有不同。

int binary_search(NSString *A, float max_width, int imin, int imax)
{
  // continue searching while [imin,imax] is not empty
  while (imax >= imin)
    {
      /* calculate the midpoint for roughly equal partition */
      int imid = (imin + imax) / 2;

      // determine which subarray to search
      float width = ComputeWidthOfString([A substringToIndex:imid]);
      if      (width < max_width)
        // change min index to search upper subarray
        imin = imid + 1;
      else if (width > max_width )
        // change max index to search lower subarray
        imax = imid - 1;
      else
        // exact match found at index imid
        return imid;
  }
  // Normally, this is the "not found" case, but we're just looking for
  // the best fit, so we return something here.
  return imin;
}

你需要进行一些数学运算或测试，以确定底部的正确索引，但它肯定是imin或imax，加上或减去一。

- benzado

---

嘿，谢谢你的回答。我已经开始做了一些事情，但是似乎无法弄清楚如何执行第三步：“另一方面，如果它不够宽，您将测试点移动到另一半的中点：”。我怎么知道它是否足够宽呢？ - Snowman