Creating Linked Lists in Python

[andrew cooke]

J-Burns wrote:
> How can I do this? And if I could do this by some other way than using
> linked lists than do tell me about that as well.

replying to this dead thread mainly for anyone using google.  there's now
a python regular expression engine in lepl and the source code can be seen
via http://www.acooke.org/lepl/api/lepl.regexp-module.html

in particular, i found that the critical collection was a map from
interval to values which automatically fragments (i think discussion of
this thread ended up looking at maps).  so, for example, if (1,10) maps to
'foo' then adding (4,5) -> 'bar' gives:

(1,3) -> foo
(4,5) -> foo, bar
(6,10) -> foo

in simple terms that lets you construct transitions for ranges of values -
typically a range of character with a mapped value that is the new state
in the machine.  so if you have a-d going to state 5, and then add d-f
going to state 6, you want d (ie ('d','d')) to go to both 5 and 6 when
constructing a nfa.

that structure is here -
http://www.acooke.org/lepl/api/lepl.regexp.interval-pysrc.html#TaggedFragments
(minimal docs at
http://www.acooke.org/lepl/api/lepl.regexp.interval.TaggedFragments-class.html)

hope that makes sense.  it could probably be more efficient (does an O(n)
scan of all intervals each time a new interval is added so is O(n^2)), but
since this is used in the "compile" part of a regexp, speed may not be as
important as in the "match" phase.

andrew