ES3 quasi incompatibilities

[Garrett Smith]

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 <lhansen at adobe.com> 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: es4-discuss-bounces at mozilla.org
> [mailto:es4-discuss-bounces at mozilla.org] On Behalf Of Kris Zyp
> Sent: 9. november 2007 09:20
> To: es4-discuss at 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 at mozilla.org
> https://mail.mozilla.org/listinfo/es4-discuss
>
>



-- 
Programming is a collaborative art.