Function findDuplicate is more like "mark duplicates". The side effect
is that it adds a __marker property to each object. As it stands, this
function can not be called more than once. The second call might be
passed a different array, but containing one of those objects that had
the __marker left over. Calling delete in a second loop would make the
algorithm 2n (best time). But this is not entirely safe; calling
delete on a Host object or window property will throw errors in
JScript env; and the property will still be there. So you can set
__marker = false, but then you've got a 2N algorithm that leaks a
"__marker" to objects in the program.
Unsafe:
if (map[array[i]])
// array[i].toString() returns a property name that exists in the
prototype chain of map (such as "toString").
Safer:
if(map.hasOwnProperty([array[i]])
However, relying on toString in the second part is still unsafe.
findDuplicate([1, "1", !window, "false", new Date()+'', new Date()+'']);
What is really going into this Array?
I think I see the intent, but the function is easily breakable, even
if fixed to have a second loop to set marker to null when done; and
including the hasOwnProperty fix.
Interop might be an issue, but the code is broken even in ES3.
JavaScript does not provide basic functionality for unique collections.
Consider a case where we have an array-like collection of objects and
we want to exclude duplicates. Not uncommon at all.
This could be a shopping cart of unique items (properties), a list of
attendees, a ledger of customers, a merge of n number of Lists,
containing top-scoring players
We want a unique collection.
Using SortedSet:
//-----------------------------------------------------------
// lis1, lis2 and lis3 are NodeList of LI, in Abstract View.
function compareFn(a, b) {
return getScore(a) - getScore(b);
}
var players:Set = new SortedSet( compareFn );
players.addAll(lis1);
players.addAll(lis2);
players.addAll(lis3);
var top10:Set = new Set(players);
top10.trimToSize(10);
//-----------------------------------------------------------
Pros: fast, explicit
What's missing from ES4:
Set, SortedSet
Using Array:
//-----------------------------------------------------------
// Copy of array-like, as array, w/o duplicates.
var players = Array.concat(lis1, lis2).concat(lis3).unique();
players.sort(compareFn);
var top10 = players.toArray();
top10.length = 10;
//-----------------------------------------------------------
Pros: compact
Cons:
1) probably not as efficient (using quicksort)
2) slightly less explicit than the SortedSet example
What's missing from ES4:
Array.prototype.unique();
Array.prototype.toArray( arrayLike ) (also as Array.toArray(arrayLike))
ES3 concat and splice are the only way to obtain a copy of an array.
These are not explicit uses, but workarounds for a missing arraycopy
function.
I don't know how this problem could be solved with a Map. Doesn't feel
natural here. Here's my best shot at it:
//----------------------------------------------------------
var players = new Map<Object,Object>();
// Add all the players from each list into the players Map.
for(var i = 0; i < lis1.length; i++) {
if(!Map.containsKey(lis1[i])
players.add(lis1[i], null);
}
for(var i = 0; i < lis2.length; i++) {
if(!Map.containsKey(lis2[i])
players.add(lis2[i], null);
}
for(var i = 0; i < lis3.length; i++) {
if(!Map.containsKey(lis3[i])
players.add(lis3[i], null);
}
var keys = map.getKeys();
var newPlayers = Array.toArray(keys);
newPlayers.sort(compareFn);
newPlayers.length = 10;
//----------------------------------------------------------
Pros:
Cons:
1) not very straightforward or intuitive; not explicit
2) Verbose, requires two collections and a for loop.
3) Not efficient
What's missing:
Array.toArray( arraylike );
On Nov 9, 2007 10:00 AM, Lars Hansen <[EMAIL PROTECTED]> wrote:
>
>
> Map and intrinsic::hashcode are your friends, indeed. Cleaner solution,
> too.
>
> <rambling>
> For non-dynamic classes you can still use meta::set and meta::get to allow
> for
> limited applications like this. I keep thinking that there are use cases
> for
> global meta::get and meta::set functions, so just like operator overloading
> can be done by extending global, generic functions a la intrinsic::+, it
> ought to
> be possible to hook into catchalls on the global level, using generic
> functions.
>
> class C { ... } // not dynamic
>
> meta generic function get(c: C, name) {
> if (name == "__marker")
> ...
> else
> return nextMethod()
> }
>
> meta generic function set(c: C, name, val) {
> if (name == "__marker")
> ...
> else
> nextMethod()
> }
> </rambling>
>
> --lars
>
>
>
> ________________________________
> From: [EMAIL PROTECTED]
> [mailto:[EMAIL PROTECTED] On Behalf Of Kris Zyp
> Sent: 9. november 2007 09:20
> To: es4-discuss@mozilla.org
> Subject: ES3 quasi incompatibilities
>
>
>
>
> > or whether ES4 precludes the use of current ES3 AOP patterns and how
> > that might be solved. Among other things.)
> ES3 AOP is in a class of patterns that is not strictly incompatible as ES3
> code alone won't break, but ES3 code would no longer behave as expected when
> interacting with ES4 code. AOP and other patterns in ES3 rely on the ability
> to add or modify properties on any object. Another example that should be
> noted is the O(n) algorithm for duplicate item and cyclic reference
> detection. For example:
> function findDuplicate(array){
> var map={};
> for (var i = 0; i < array.length; i++) {
> if (typeof array[i] == 'object') {
> if (array[i].__marker)
> alert('found duplicate');
> array[i].__marker = true;
> }
> else {
> if (map[array[i]])
>
> alert('found duplicate');
> map[array[i]] = true; }
> }
> }
> This algorithm will fail if an array of objects is passed in that includes
> instances of non-dynamic (default for user created) classes. Temporarily
> marking objects with dynamic properties is the only way I am aware of to
> create O(n) algorithms in ES3 to detect duplicates and cyclic references.
> I don't think there is anything that can be done about this, it is just a
> result of static classes. Code written for ES4 can use maps (I think anyway)
> to solve this problem. This has probably already been discussed, but I just
> wanted to make sure it was noted.
> Kris
> _______________________________________________
> Es4-discuss mailing list
> Es4-discuss@mozilla.org
> https://mail.mozilla.org/listinfo/es4-discuss
>
>
--
Programming is a collaborative art.
_______________________________________________
Es4-discuss mailing list
Es4-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es4-discuss
