Impact

This forum is read only and just serves as an archive. If you have any questions, please post them on github.com/phoboslab/impact

10 years ago by FelipeBudinich

I'll leave my Array utilities plugin up for grabs, critique and abuse.

PS: I created a public repository for this plugin:

https://github.com/Talesay/impact-plugin-array-utilities

It is meant to be used as a git submodule, so basically you need to do from the git command line:

git submodule add https://github.com/Talesay/impact-plugin-array-utilities.git lib/plugins/array

10 years ago by FelipeBudinich

- Removed Duff's Device (fun to have, but if you need it, it can be easily written in place).

- Added feature detection before extending the native object. Just in case the ECMAScript committee thinks my method names are too cool and decide to appropriate them.

- Added docs in the github repository

10 years ago by vincentpiel

Hi Felipe,

Thanks for your efforts !
There are quite some issues here i'd like to mention :
- Just like Impact does, you are polluting the Array prototype with enumerable methods that prevents to do a for..in. You have to use Object.defineProperty to avoid that. Bonus is that you can simplify the function getAssociativeArrayLength to function() { return this.length; } :-)
- you have a lot of redundant code to check/throw method.
- Two names seems misleading. I suggest :
first --> skipFirst
last --> skipLast
- Behaviour of first/last when called with no args seems very strange.
- You create tons of garbage in quite some methods. Rotate is a nightmare. Remember garbage is your enemy, Impact's framerate drop are caused by too many L0/L1 garbage created by collision/map collision/input/other parts of the lib. So avoid making things worse !!! :-)
- use the 'goods' methods of the array whenever you can (slice is good for example, when splice is not).

You might be interested in having a look at my post on arrays : http://gamealchemist.wordpress.com/2013/05/01/lets-get-those-javascript-arrays-to-work-fast/


Here's your code after some refactoring, !!!! i did not test it !!! but hopefully it'll help you write clearer, faster, garbage free code.


// !!! Untested code, provided for the discussion, do not use in your code !!!!

'use strict';

(function () {

    var newArrayMethods = {
        /**
         * Returns a shallow copy of this array
         */
        copy: function () {
            return this.slice(0);
        },

        /**
         * Returns true if this array contains 'element', returns false otherwise
         */
        contains: function (element) {
            return this.indexOf(element) >= 0 ;
        },

        /**
         * Returns a copy of this array, removing the elements
         *         'from' index 'to' index within it
         */
        remove: function (from, to) {
            var res = [];
            var i = 0,
                j = 0;
            for (i = 0; i < from; i++) {
                res[i] = this[i];
            }
            j = i;
            for (i = to; i < this.length; i++) {
                res[j++] = this[i];
            }
            return res;
        },

        /**
         * Returns a copy of this array, rotated 'n' places, 
         *     counterclockwise if 'n' is positive, clockwise otherwise
         */
        rotate: function (n) {
            if (!n) return this.slice(0);
            var length = this.length;
            var res = new Array(length);
            var thisIndex = (n > 0) ? n : length + n,
                i = 0,
                j = 0;
            for (i = thisIndex; i < length; i++) {
                res[j++] = this[i];
            }
            for (i = 0; i < thisIndex; i++) {
                res[j++] = this[i];
            }
            return res;
        },

        /**
         * Returns a copy of this array, removing but 
         *         the first 'n' elements from it
         *         assumes n=1 when called with no arguments.
         */
        skipFirst: function (n) {
            if (n === 'undefined') n = 1;
            return this.slice(n);
        },

        /**
         * Returns a copy of this array, removing 
         *         but the last 'n' elements from it
         *         assumes n=1 when called with no arguments.
         */
        skipLast: function (n) {
            if (n === 'undefined') n = 1;
            if (n > this.length) return [];
            return this.slice(0, this.length - n);
        },

        /**
         * Returns a copy of this array, 
         *         sorting its elements randomly
         */
        shuffle: function () {
            var copy = this.slice(0);
            return copy.sort(function () {
                return Math.random() - 0.5;
            });
        },

        /**
         * Returns this associative array length
         */
        getAssociativeArrayLength: function () {
            return this.length;
        },

        /**
         * Returns a copy of this array that contains the difference
         *         between source array and 'array'
         */
        difference: function (array) {
            var filterFunc = filterOnOtherArray_diff.bind(array);
            return this.filter(filterFunc);
        },

        /**
         * Returns a copy of this array that contains the 
         *         intersection between source array and 'array'
         */
        intersection: function (array) {
            var filterFunc = filterOnOtherArray_inter.bind(array);
            return this.filter(filterFunc);
        },

        /**
         * Returns a copy of this array that contains the union
         *   between source array with 'array', removing duplicates
         *    ! fails with a sparse array !
         */
        union: function (array) {
            var obj = {},
            res = [],
                i = 0,
                k = 0;
            for (i = 0; i < this.length; i++) {
                obj[this[i]] = this[i];
            }
            for (i = 0; i < array.length; i++) {
                obj[array[i]] = array[i];
            }
            for (k in obj) {
                res.push(obj[k]);
            }
            return res;
        }
    }
    
    // let's install those methods on the prototype
    for (var newMethodName in newArrayMethods) {
        installFunction(newMethodName, newArrayMethods[newMethodName]);
    }

    function installFunction(name, fn) {
        if (Array.prototype[name]) throw ('Array method ' + name + '() already defined.');
        Object.defineProperty(Array.prototype, name, {
            value: fn
        });
    }

    function filterOnOtherArray_diff(arr, i) {
        return (arr.indexOf(i) < 0);
    }

    function filterOnOtherArray_inter(arr, i) {
        return (arr.indexOf(i) >= 0);
    }
})();


10 years ago by FelipeBudinich

Thanks very much for your review vincentpiel!

There is only one problem:

Bonus is that you can simplify the function getAssociativeArrayLength to function() { return this.length; } :-)


Actually, there are no Associative Arrays on Javascript, just objects, and I use that function to interact with outside libraries/code, so I can't use the sensible solution, as it clashes with the realities of the jungle out there :)

(On the other hand, a for.. ..in loop without checking for hasOwnProperty makes my linter choke to death, and I agree with it, I try to code "defensibly").

As for "first" and "last", I'll rename those to "getFirst" and "getLast" (reversing their meaning using "skipFirst" and "skipLast" would confuse some people further)

/**
* Returns true if this array contains 'element', returns false otherwise
*/
contains: function (element) {
    return this.indexOf(element) >= 0 ;
}

All I can say about that is DOH!

Also, thanks very much for the "installer function" that would allow me to reduce the amount of Slocs in the file a lot

I'll review your review, and post an updated version later :)

10 years ago by vincentpiel

Glad i could help !

A few comments :
A javascript object *IS*an associative array. In doubt i did just re-read the definition, and no feature is missing.
So if the array's prototype was not polluted, the number of own property of an array == its length.
You might want to clear (== set as non-enumerable) any Impact or other lib pollution by doing something like :

  var dummyArray = [];
  for (var prop in dummyArray) {
        Object.defineProperty(Array.prototype, prop, { value : dummyArray[prop] } ) ;
  }

for the fact that linter does forbid you or that, never think those tools are always right. In the union() method for instance, you just created the lookup obj, so its prototype is empty, so checking for own property is strictly exactly useless.

And don't think you're defensive : you're not since you don't check 'from','to' being a number / in the right range in remove(), or 'array' being an array in difference/intersection/union, just to quote two things. And it's just perfectly fine, because you can't protect your API against every foolishness, and because performances matters.

for first and last functions, i rushed a bit the refactoring and misunderstood the comments, my bad. Still, you get the idea do NOT on earth create several arrays, use unshift, and so on -unless you worship the evil garbage collector ( ;-) ) -

10 years ago by FelipeBudinich

Quote from vincentpiel
Glad i could help !

A few comments :
A javascript object *IS*an associative array. In doubt i did just re-read the definition, and no feature is missing.


Careful with that assumption; a javascript object is a superset of an associative array, with the problem that the external representation is implementation dependent: http://www.amberweinberg.com/associative-arrays-in-javascript-are-evil/

So if the array's prototype was not polluted, the number of own property of an array == its length.


Impact does pollute the array prototype (i.e: Array.prototype.random and Array.prototype.erase). Tho your solution to this problem is pretty awesome :)

for the fact that linter does forbid you or that, never think those tools are always right. In the union() method for instance, you just created the lookup obj, so its prototype is empty, so checking for own property is strictly exactly useless.


Keep in mind that Object.prototype may be extended somewhere else.

Tho I'm very aware that linters are "opinionated" not "correct", that's why on different modules I disable some rules (e.g: I do nomen:true on modules that inject any impact class that has some supposedly "private" methods.)

The good thing about that approach is that I do "riskier/less proper" stuff very consciously.

And don't think you're defensive : you're not since you don't check 'from','to' being a number / in the right range in remove(), or 'array' being an array in difference/intersection/union, just to quote two things. And it's just perfectly fine, because you can't protect your API against every foolishness, and because performances matters.


True :) But if you pass a string as the argument, the program will fail and tell you "that argument you passed is not a number", or something along those lines, making the error quite obvious.

On the other hand, overwriting the prototype or having an object returning the wrong length, can cause bugs that are harder to track.

I try to be defensive about stuff that is gonna make my head hurt. Because of that I consider type checking superfluous outside of testing (unless you are accepting unsanitized data from users).

Still, you get the idea do NOT on earth create several arrays, use unshift, and so on -unless you worship the evil garbage collector ( ;-) ) -


Yes, I'm refactoring taking your advice into account. :)

10 years ago by vincentpiel

Keep in mind that Object.prototype may be extended somewhere else.


This is one of the infinite bad things that can be done. But it would have even consequences beyond for..in.
But testing ownProperty is not the proper answer : fix the issue at its root rather than having a performance penalty every time.
So to test, just do :

   if (Object.keys({}).length) throw('Object prototype is polluted');

And to fix, just like for arrays,

  var dummyObject = {};
  for (var prop in dummyObject) {
        Object.defineProperty(Object.prototype, prop, { value : dummyObject[prop] } ) ;
  }

I try to be defensive about stuff that is gonna make my head hurt.


Good strategy :-)

9 years ago by BNDBND

Used your work, but shuffle was not enough random, so I replaced It with Fisher Yates shuffle
 Array.prototype.shuffle = function () {
       array=this.splice(0);
	   var m = array.length, t, i;

  // While there remain elements to shuffle…
  while (m) {

    // Pick a remaining element…
    i = Math.floor(Math.random() * m--);

    // And swap it with the current element.
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
    };

9 years ago by FelipeBudinich

Very glad you found it useful, i'll test your suggestion to use Fisher Yates. (also I'm way past due of creating a proper github repository)

9 years ago by FelipeBudinich

@BNDBND there's an error in your implementation:

 Array.prototype.shuffle = function () {
       var array=this.splice(0),
       m = array.length, t, i;

  // While there remain elements to shuffle…
  while (m) {

    // Pick a remaining element…
    i = Math.floor(Math.random() * m--);

    // And swap it with the current element.
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
    };

spot the difference ;)

9 years ago by BNDBND2

oh, forgot that var initialization.

Inconsistency might be because of different implementation of array sort in browsers, and in general, sort might rely on these logics, which fails when using this random method:
A < B + B < C => A < C
A < B => B > A
A < B => A < B

Found a good demonstration site:
ht_tp://phrogz.net/JS/JavaScript_Random_Array_Sort.html

9 years ago by FelipeBudinich

Quote from BNDBND2
Found a good demonstration site:
ht_tp://phrogz.net/JS/JavaScript_Random_Array_Sort.html


Ok, I'm convinced, good call.

9 years ago by FelipeBudinich

It was long due, but I created a public repository for the plugin:

https://github.com/Talesay/impact-plugin-array-utilities

It is meant to be used as a git submodule, so basically you need to do:

username$ git submodule add https://github.com/Talesay/impact-plugin-array-utilities.git lib/plugins/array
Page 1 of 1
« first « previous next › last »