Blue Blazer

Achieve perfection by constant effort and creative will.
Code every day, no matter what...

漂亮的输入法前端界面

对scim呆板的界面厌烦了,对gtk不怎么感冒。
想要一个漂亮的能和系统主题相适应的输入法面板。

于是自己写了一个:)

  • 支持透明,支持采用Svg来作皮肤。KDE4 下面根据当前桌面(Plasma)主题自动换皮肤、和文字配色方案。还能根据你是否启用桌面效果调整外观。
  • 图形界面和后端是分开的,将来支持ibus也是可以做到的。
  • 简洁小巧,图形界面程序只有68k大,scim后端支持程序只有176k大小。

默认Oxygen主题下效果






Clean Blend主题下效果

简单文本编辑器的数据结构

先说vim和emacs吧。
vim文本存储采用的是链表,每个节点代表一行。
emacs采用的是间隙缓冲区(Gap buffer),如: abcdI____efg I是光标,这样在光标处插入删除就变得很快速,缺点是当光标移动距离过大时需要移动大量数据。

这两种方法各有优点,但是有没有更好的方法呢?
Data Structures for Text Sequences
介绍了Piece Table方法,就是使用两个缓冲区,一个只读,一个只能做尾部附加操作。
只读缓冲区的数据是原始文件,用户每次修改添加的数据记录在附加缓冲区中。
然后使用链表来表示当前文档:每个链表的节点有三个域:哪个缓冲区,起始偏移,长度。
插入操作最多让链表长度加2,删除操作最多让其长度加1。
这样链表长度是编辑次数的函数,而不是文档长度。
不妨设编辑次数为 m , 文本长度为 n,插入操作的长度为p,来分析复杂度,容易得:
时间复杂度:从上次临近位置插入 O(1),随机位置插入O(m),删除时间复杂度同插入。获得某个位置字符O(m),获得长度为l的字符串O(m+l),遍历所有字符O(n)。
内容占用:约等于S(n+mp),因为以前插入的内容会被一直保留在附加缓冲区中。
可以看到大部分操作的时间复杂度是与长度无关的,并且只读缓冲区可以根本不载入到内存中来,这样可以支持编辑非常大的文件(几百MB)。

如果采用平衡树而不是链表来表示节点的话,固定位置,随机位置插入/删除时间复杂度变为O(log m),
获得某个位置字符O(log m),获得长度为l的字符串O(log (m) +l),遍历所有字符O(n),但是这样实现(撤销/重做等操作)耗费更多内存,实现起来麻烦,并且一般需要用户交互的文档编辑软件的编辑次数不会太多(用户经常就会存盘,也不可能连续几小时编辑)。

因此这样的数据结构才是最适合简单文本编辑器使用的。

第一贴

为什么弄个博客:
记录下我的行动与想法,和大家分享。

主要内容:

  • Qt/KDE 应用开发相关
  • Linux 应用相关
  • 最新最酷的东东的转载/翻译/评论
不会包括的内容:
  • 政治,广告
欢迎与我交流,可以在帖子下面写上您的评论或给我发邮件:)