1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
% -*- mode: noweb; noweb-doc-mode: latex-mode; noweb-code-mode: emacs-lisp-mode; -*-
To improve the performance of zencoding-mode, caching/memoization of
previously entered input needed to be done. At first, a naive
hash-table implementation was chosen and this greatly cut down the
speed with which zencoding generated HTML. Then it was realized that a
trie data structure would be more efficient as the hash-table was
storing partially entered input as well. A trie could store the
partially entered data when needed and use less space than a
hash-table.
A trie is a tree where each node is a character in a string. When you
reach a leaf node, a word or sentence is spelled out.
The only operations we require for our trie are \emph{retrieve value}
and \emph{insert value}.
A node is a sequence of two elements. The first element is some cached
version of zencoding's AST (Abstract Syntax Tree) output. If this is
`nil' then there is no cached output. The second element is a sequence
of branches (more nodes).
<<Node creation function>>=
(defun make-zencoding-trie-node ()
"Creates a vector of two elements. The first element is some value,
the second element is a character table for storing more branches of the
trie. The value is initially NIL."
(vector nil (make-char-table 'trie-table)))
@
<<Node accessors>>=
(defun zencoding-trie-node-value (node)
(aref node 0))
(defun zencoding-trie-node-set-value (node value)
(aset node 0 value))
(defun zencoding-trie-node-branches (node)
(aref node 1))
(defun zencoding-trie-node-create-branch (node branch-key)
(aset node branch-key (make-zencoding-trie-node)))
@
<<Retrieve node operation>>=
(defun zencoding-trie-retrieve (s trie i)
@
Next we have a function for inserting a string and its value into a
trie. The pre-conditions are that $s$ is a type of string, $value$ and
$trie$ are non-\texttt{NIL}, and $0 < i \leq s_n$ (where $n$ is the
length of the string). We actually have two functions, the first one
defines the function that does the real work while the second is a
convenience function that removes the variable $i$.
Inserting a string into a trie involves the conversion of each
character into a key. The value given will be stored in the leaf node
which is reached when there is only a single character left in the
string.
We are moving forward through a string till we reach its end. The
current character is $s_{i - 1}$. If the current node we are visting
in the trie contains the current character as one of its branches,
then we have to insert the value or visit it. When there is a single
character in the string, we insert the value. Otherwise, we visit the
next node.
If the branch doesn't exist, we create the node then do the other
things needed.
<<Trie insertion function>>=
(defun zencoding-trie-insert-do (s value trie i)
(let ((c (aref s (1- i))))
(cond <<Insert the value if we are at the end>>
<<Visit the next node if we are not at the end>>
<<Otherwise signal an error because the string was too short>>)))
(defun zencoding-trie-insert (s value trie)
"`s' is the string used to navigate the trie (each character is a node
in the trie). `value' is the value we want to insert. `trie' is the node
where we start the insertion."
@
<<Insert the value if we are at the end>>=
((= i (length s))
<<Create a branch if it does not exist>>
(zencoding-trie-node-set-value (aref (zencoding-trie-node-branches trie) c)
value))
@
<<Visit the next node if we are not at the end>>=
((and (< 0 i) (<= i (length s)))
<<Create a branch if it does not exist>>
(zencoding-trie-insert s value (aref trie c) (1+ i)))
@
<<Otherwise signal an error because the string was too short>>=
(t (error "The string was too short"))
@
<<Create a branch if it does not exist>>=
(if (null (aref trie c))
(zencoding-trie-node-create-branch trie c))
@
The code is licensed under the GNU GPL version 3 or later.
<<Copyright info>>=
;;; zencoding-trie.el --- A trie data structure built for zencoding-mode
;;
;; Copyright (C) 2009, Rudolf Olah
;;
;; Author: Rudolf Olah <omouse@gmail.com>
;;
;; This file is free software; you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation; either version 3, or (at your option)
;; any later version.
;;
;; This file is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
;; GNU General Public License for more details.
;;
;; You should have received a copy of the GNU General Public License
;; along with GNU Emacs; see the file COPYING. If not, write to
;; the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
;; Boston, MA 02110-1301, USA.
;;
@
The final file looks like this:
<<zencoding-trie.el>>=
<<Copyright info>>
<<Node creation function>>
<<Node accessors>>
<<Retrieve node operation>>
<<Insert node operation>>
(provide 'zencoding-trie)
;; test code
(let ((x (make-zencoding-trie-node)))
(zencoding-trie-insert "i" "i" x 0)
x)
@
|
