自动换行是现代文本编辑器中的必备功能之一。

我们知道如何处理自动换行吗？
换行的最佳算法是什么？

更新：
如果文本是几百万行，我怎样才能使自动换行呢？

更新：为什么我需要解决方案？因为我的项目必须绘制具有各种缩放级别并同时具有美观外观的文本。

已更新：运行环境是Windows Mobile设备。很小的内存大小，最高600MHz速度。

更新：我应该如何处理线路信息？假设原始数据有三行。

THIS IS LINE 1.
THIS IS LINE 2.
THIS IS LINE 3.

断词后，文本将显示为：

THIS IS
LINE 1.
THIS IS
LINE 2.
THIS IS
LINE 3.

我应该再分配3行吗？或者其他建议？

解决方案

回答

有没有断字？

没有它的容易。只需将文本封装为每个单词的单词对象，并为它们提供方法getWidth()，然后从第一个单词开始，将行长加起来，直到行长大于可用空间为止。如果是这样，请包装最后一个单词，并从该一个对象开始对下一行再次计数。

使用连字符时，我们需要采用通用格式的连字符规则，例如：hy-phen-a-tion

然后，除了我们需要拆分导致溢出的最后一个单词外，其余步骤与上述相同。

《四个设计模式的帮派》一书中提供了一个很好的示例和教程，说明了如何为优秀的文本编辑器构建代码。它是显示图案的主要样本之一。

回答

我不知道任何特定的算法，但是以下内容不能大致概述其工作原理：

• 对于当前的文本大小，字体，显示大小，窗口大小，边距等，请确定一行上可以容纳多少个字符(如果是固定类型)，或者一行上可以容纳多少个像素(如果不是固定类型)。
• 逐个字符地逐行检查，计算自行开始以来已记录了多少个字符或者像素。
• 当我们超过该行的最大字符数/像素时，移回最后一个空格/标点符号，将所有文本移至下一行。
• 重复直到浏览完文档中的所有文本。

问题：在.net中，自动换行功能内置于诸如TextBox之类的控件中。我确信其他语言也存在类似的内置功能。我们是否有理由不想使用预先构建的解决方案？这似乎是重新发明轮子的路线。

回答

关于更新和速度问题，请记住稍后进行优化。首先，编写自动换行算法。如果输入文字，请在一百万行上运行它。当且仅当它对于要求而言太慢时，才可以优化。

回答

这是我用C＃编写的自动换行算法。翻译成其他语言应该很容易(也许除了IndexOfAny之外)。

static char[] splitChars = new char[] { ' ', '-', '\t' };

private static string WordWrap(string str, int width)
{
    string[] words = Explode(str, splitChars);

    int curLineLength = 0;
    StringBuilder strBuilder = new StringBuilder();
    for(int i = 0; i < words.Length; i += 1)
    {
        string word = words[i];
        // If adding the new word to the current line would be too long,
        // then put it on a new line (and split it up if it's too long).
        if (curLineLength + word.Length > width)
        {
            // Only move down to a new line if we have text on the current line.
            // Avoids situation where wrapped whitespace causes emptylines in text.
            if (curLineLength > 0)
            {
                strBuilder.Append(Environment.NewLine);
                curLineLength = 0;
            }

            // If the current word is too long to fit on a line even on it's own then
            // split the word up.
            while (word.Length > width)
            {
                strBuilder.Append(word.Substring(0, width - 1) + "-");
                word = word.Substring(width - 1);

                strBuilder.Append(Environment.NewLine);
            }

            // Remove leading whitespace from the word so the new line starts flush to the left.
            word = word.TrimStart();
        }
        strBuilder.Append(word);
        curLineLength += word.Length;
    }

    return strBuilder.ToString();
}

private static string[] Explode(string str, char[] splitChars)
{
    List<string> parts = new List<string>();
    int startIndex = 0;
    while (true)
    {
        int index = str.IndexOfAny(splitChars, startIndex);

        if (index == -1)
        {
            parts.Add(str.Substring(startIndex));
            return parts.ToArray();
        }

        string word = str.Substring(startIndex, index - startIndex);
        char nextChar = str.Substring(index, 1)[0];
        // Dashes and the likes should stick to the word occuring before it. Whitespace doesn't have to.
        if (char.IsWhiteSpace(nextChar))
        {
            parts.Add(word);
            parts.Add(nextChar.ToString());
        }
        else
        {
            parts.Add(word + nextChar);
        }

        startIndex = index + 1;
    }
}

它相当原始，它以空格，制表符和破折号分隔。它确实确保在其之前的单词上都包含破折号(这样就不会导致堆栈\ n溢出)，尽管它不希望将带小连字符的单词移至换行符，而不是将其拆分。如果单词太长而不能排成一行，则会将其拆分。

它在文化上也相当具体，因为我对其他文化的自动换行规则了解不多。

回答

Donald E. Knuth在他的TeX排版系统中对换行算法做了很多工作。就结果的视觉外观而言，这可以说是换行"最佳"的最佳算法之一。

他的算法避免了贪婪的行填充问题，在此情况下，我们可能会得到非常密集的行，然后是非常宽松的行。

可以使用动态编程来实现有效的算法。

关于TeX换行的论文。

回答

我不知道有人问这个问题有多老，但我最近有机会写一个自动换行功能，我想分享一下我的想法。我使用的TDD方法几乎与Go示例中的方法一样严格。我首先进行了测试，将字符串" Hello，world！"包装起来。在80宽度处应返回" Hello，World！"显然，最简单的方法是返回未修改的输入字符串。从那开始，我进行了越来越复杂的测试，最后得到了一个递归解决方案(至少出于我的目的)非常有效地处理了任务。

递归解决方案的伪代码：

Function WordWrap (inputString, width)
    Trim the input string of leading and trailing spaces.

    If the trimmed string's length is <= the width,
        Return the trimmed string.
    Else,
        Find the index of the last space in the trimmed string, starting at width

        If there are no spaces, use the width as the index.

        Split the trimmed string into two pieces at the index.

        Trim trailing spaces from the portion before the index,
        and leading spaces from the portion after the index.

        Concatenate and return:
          the trimmed portion before the index,
          a line break,
          and the result of calling WordWrap on the trimmed portion after
            the index (with the same width as the original call).

这仅在空格处换行，并且如果我们要包装已经包含换行符的字符串，则需要在换行符处将其拆分，将每个片段发送给该函数，然后重新组装该字符串。即使这样，在运行于快速计算机上的VB.NET中，这也可以处理大约20 mb / sec。

回答

我自己的编辑器项目也想知道同样的事情。我的解决方案是一个两步过程：

• 找到行尾并将它们存储在数组中。
• 对于很长的线，请以大约1K的间隔找到合适的断点，并将其保存在线阵列中。这是为了捕获"没有单个换行符的4MB文本"。

当我们需要显示文本时，找到有问题的行并将其自动换行。在高速缓存中记住此信息以便快速重绘。当用户滚动整个页面时，刷新缓存并重复。

如果可以，请在后台线程中加载/分析整个文本。这样，当我们仍在检查文档的其余部分时，我们已经可以显示文本的第一页。这里最简单的解决方案是切掉前16KB的文本并在子字符串上运行算法。这非常快，即使编辑器仍在加载文本，也可以使我们立即呈现第一页。

当光标最初位于文本末尾时，可以使用类似的方法。只需阅读最后16KB的文字并进行分析。在这种情况下，请使用两个编辑缓冲区，并在用户锁定到第二个缓冲区的同时将除最后16KB以外的所有内容都加载到第一个缓冲区中。而且我们可能想要记住关闭编辑器时文本有多少行，因此滚动条看起来并不奇怪。

当用户可以使用光标在中间的某个位置启动编辑器时，它变得很繁琐，但最终，这只是结束问题的扩展。只有我们需要记住字节位置，当前行号和上次会话后的行总数，还需要三个编辑缓冲区，或者需要一个编辑缓冲区，我们可以在其中减少16KB。

或者，在加载文本时锁定滚动条和其他界面元素。允许用户在完全加载时查看文本。

回答

@ICR，感谢我们分享Cexample。
我没有成功使用它，但是想出了另一个解决方案。如果对此有任何兴趣，请随时使用：
http://johan.andersson.net/2010/11/03/wordwrap-function-in-c/

我已经包含了单元测试/样本。

谢谢！