From: Nicolas C. <war...@fr...> - 2003-06-04 02:38:39
|
Hi list, After the recent talks about enum features, I have made a major update. First, I started to think about the "clone" implementation : it was actually very complicated and pretty inefficient : in fact, cloning an enumeration on a list or on an array should be O(1) since we only need to get a different pointer on the list of copy the current index for an array. Clone was trying his best by using a shared list as cache between the clone and the original, but this was costly in the end, and actually doing several clones was adding more and more overload. So I decided to add clone:(unit -> 'a t) as argument for Enum.make function. Like this, we can have an efficient clone when available. Enum.from is then having a default clone which is calling "force" and the clone() again. Since force is building the list of elements, he can provide an O(1) clone function. Now that the clone issues has been resolved, I have been adding peek (the real one, doesn't fetch any data) and "empty : 'a t -> bool". In order to satisfy people who are interested in count() cost, I have been adding a boolean flag "fast_count" that give an hint about count cost. So we have for exemple : let empty t = if fast_count t then t.count() = 0 else peek t = None Please note that fast_count doesn't mean O(1) , since it can depends on the underlying implementation of the count function given to make as parameter. After that, I've been updated the *.enum functions of DynArray , ExtList and ExtString to provide a good clone implementation. I also improved ExtList.enum count() function by using a little hack so List.length will be called only once. Now my next though is about having "clone" being an optional parameter in Enum.make. Actually most of the time when you create a data structure with Enum.make, providing a next() and count() function, implementing clone() can be done in an efficient way, but is requiring a little thinking and some recursion, which make Enum.make a bit more (too much?) difficult to use for the average user. Then clone should perhaps be implemented as "inneficient by default" an the user would care providing an efficient primitive only if he's actually using it. Nicolas Cannasse |