From: Nicolas C. <war...@fr...> - 2004-08-28 16:28:50
|
> > Taken apart advantages of keys, you get only bidrectional iteration, which > > is IMHO not interesting enough to justify adding a new data structure to > > ExtLib. [snip on arrays] I think you should look at Brian proposal of IndexedTree (functionnal array). It provides exactly that : a low cost insertion at any part of the array. But any insertion/deletion will of course invalid the keys of some parts of the array items. That's not exactly what you need here... [snip on felix compilation] I understand correctly your problem, because I got same when writing compilers. It's often that you need several passes in order to optimize some code or simply for example when writing a forward jump of N instructions into a forward jump to address XX. But I don't think dllist are the best solution here. As you said, you need some rewriting rules, so what about : instead of : type opcode type code = opcode array type key = int (* index in the array *) use : type opcode type code = | Op of opcode | Array of code array type key = array * int (* pointer in the tree *) you can then translate any part of your code into not only a single opcode but into an array of opcodes, and they will remain correctly ordered. You need a tree structure to perform rewriting rules correctly and efficiently , a dllist for this kind of problem is just an inconvenient way of handling flat trees in a mutable fashion. Nicolas |