feb 21 2013

Unselect KendoUI Treeview (de verdad)

La mayoría de soluciones para deseleccionar un nodo de un árbol de Kendo UI no me han funcionado. O no funcionan, o dejan el widget en un estado ‘bastardo’ que no permite continuar con el funcionamiento esperado.
Desde la docu oficial dan una solución … que lamentablemente no funciona:

//Unselect all nodes
var treeView = $("#treeView").data("kendoTreeView");
treeView.select($());

Al final casi que ha sido más fácil destripar un poco la libraria. Si tienes instanciado un treeview y devuelves la función select esto es lo que obtienes;

/*
* var tree = $("#treeview").data("kendoTreeView");
* console.log(tree.select);
*/
function (n){var i=this,r=i.element;return arguments.length?(n=e(n,r).closest(H),n.length&&(r.find(".k-state-selected").each(function(){var e=i.dataItem(this);e.set("selected",!1),delete e.selected}),i.dataItem(n).set("selected",!0)),t):r.find(".k-state-selected").closest(H)}

El método .select() es un getsetter dependiendo del arguments.length, bueno pues hay que mirar la parte donde si que le pasas parámetros (ya que primero deselecciona antes de volver a seleccionar).

Deseleccionar los elementos de un árbol de kendo

No podiemos solo eliminar la clase ‘.k-state-selected’ porque en Kendo UI siempre hay un dataSource que mantiene al widget.
Hay que recuperar el dataItem y decirle “deseleccionate”, o lo que viene siendo lo mismo .set(“selected”, false)

false a.k.a. !1

$("#treeview").kendoTreeView();

//Unselect
$("button#deselect").click(function(){
  var tree=$("#treeview").data("kendoTreeView");

  $("#treeview")
    .find(".k-state-selected")
    .each(
      function () {
        var e = tree.dataItem(this);
        e.set("selected", !1);
        delete e.selected;
    });
});

Unselect en Kendo UI TreeView
Hay que tener en cuenta que en Kendo UI se suele seguir el patrón MVVM para tener sincronizado la interfaz con los datos que son representados.


feb 14 2013

LET – variables locales al ámbito de bloque

Let es una de las muchas mejoras previstas para la versión 6 de EcmaScript que la mayoría de navegadores/máquinas virtuales JS no soportan.

No es una aportación sustancial al lenguaje. Principalmente está descrita para alejar a los nuevos programadores de las malas prácticas que el lenguaje ofrece a los noobs.

SpiderMonkey (JS de Firefox) implementa en gran medida esta funcionalidad. A partir de la versión 1.7 de JavaScript podemos usar estas y otras mejoras, pero siempre es necesario indicar que versión de javascript se debe ejecutar.

Esta instrucción nos permite jugar con variables locales. Esto no es novedad en javascript, lo novedoso es que su ámbito local es el bloque de código, no la función.

En mis pruebas he comprobado que Firefox acepta el type del script como texto o aplicación. Este es el type recomendado, pero ambos funcionan.

<script type="text/javascript;version=1.7">...</script>
<script type="application/javascript;version=1.7">...</script>

-Let como Declaración-

En el primer console.log baz no se le ha asignado valor, pero dentro de ese ámbito ha sido reservada ese identificador.

<script type="text/javascript;version=1.7">
function yeah(){
    var foo="aaa";
    {
        console.log(foo, baz);// aaa, undefined
        let baz="zzz";
        console.log(foo, baz);// aaa, zzz
    }
    console.log(foo, baz);// ReferenceError: baz is not defined
}

yeah();
</script>

En el ámbito de la función no existe la variable baz puesto que es local al bloque. Aunque podemos acceder a las variables de este ámbito de función y de bloque, estos no son el mismo. Con la sentencia Let restringimos el acceso de ámbito al bloque. Con la sentencia var solo se restringe a la función.

Redeclaraciones

No están permitidas, así de simple. Este es un punto de rigidez mayor que con Var donde están completamente permitidas.

En el siguiente ejemplo mientras que con foo no tenemos problemas, con let no están permitidas múltiples declaraciones. Sin mostrar por consola ninguna línea anterior se nos devuelve un error de tipos:

TypeError: redeclaration of variable baz

<script type="text/javascript;version=1.7">
function yeah(){
    var foo="aaa";
    var foo="bbb";
    {
        var foo="ccc";
        let baz="zzz";
        console.log(foo, baz);
        let baz="_";//TypeError: redeclaration of variable baz
    }
    console.log(foo, baz);
}

yeah();
</script>

Sucede de la misma manera si declaramos baz en un bloque interior pero con la declaración var, con lo que las dos variables estarían en conflicto.

<script type="text/javascript;version=1.7">
function yeah(){
    var foo="aaa";
    var foo="bbb";
    {
        var foo="ccc";
        let baz="zzz";
        console.log(foo, baz);
        {
            var baz="_";//TypeError: redeclaration of variable baz
        }
    }
    console.log(foo, baz);
}

yeah();
</script>

Sacando el segundo baz a otro bloque ya no encontramos ningún problema en la nueva declaración. Estamos en otro bloque con distinto ámbito de bloque.

<script type="text/javascript;version=1.7">
function yeah(){
    var foo="aaa";
    var foo="bbb";
    {
        var foo="ccc";
        let baz="zzz";
        console.log(foo, baz);// ccc, zzz
    }
    console.log(foo, baz);// ccc, undefined
    let baz="_";
    console.log(foo, baz);// ccc, _
}

yeah();
</script>

Mezclando variables globales, locales y locales al bloque

Veamos el comportamiento a través de bloques y funciones. Modificamos una variable global en la línea 2 de la función:

<script type="text/javascript;version=1.7">
var a="aaa";
function yeah(){
    console.log(a);// aaa
    a="bbb";
    {
        console.log(a);// undefined
        let a="zzz";
        console.log(a);// zzz
    }
    console.log(a);// bbb
}

yeah();
console.log(a);// bbb
</script>

Dentro del bloque la variable ‘a’ global existe, pero también existe otra variable local a la función llamada ‘a’, solo que aun no se le ha asignado ningún valor.

Una vez asignado el string “zzz” se puede mostrar, pero al ser local al bloque no se puede trabajar con ella fuera del bloque.

Es importante tener en cuenta que un bloque viene definido solamente por llaves ( { } ). Aunque ciertas expresiones como if y for puedan tener efecto para sentencia siguiente sin bloque (se puede entender que está dentro de un bloque indirectamente) el caso de Let es estricto en el bloque definido por llaves.

<script type="text/javascript;version=1.7">
if (false) var x = 9; // legal
if (false) let x = 9; // SyntaxError: let declaration not directly within block
</script>

-Let como Expresión-

Una expresión let limita el alcance de la variable declarada a sólo esa expresión.

De esta manera podemos usar let para usar una variable en una sentencia solamente.

var a = 5;
let(a = 6) alert(a); // 6
alert(a); // 5

Claro que como las funciones son instrucciones, podemos utilizar una para ejecutar todo el código que queramos con determinado valor local

<script type="text/javascript;version=1.7">
var a = 5;
let(a = 6) (function(){
    console.log(a);// 6
    a+=100;
    console.log(a);// 106
})();
console.log(a); // 5
</script>

Pero todos los valores declarados con let seguirán siendo locales a esa expresión, sin existir fuera de ella.

<script type="text/javascript;version=1.7">
var a = 5;
let( a = 6, b=2000 )(function(){
    console.log(a);// 6
    a+=100 + b;
    console.log(a);// 2106
})();
console.log(a); // 5
console.log(b); // ReferenceError: b is not defined
</script>

El uso de Let como expresión de esta última manera lleva de forma natural a pensar en usarla como una sentencia más.

-Let como Sentencia-

La sintaxis es muy parecida a la expresión, y tiene precedentes en otras sentencias como for, while, if, … así que en definitiva podemos decir que es una expresión más que genera un ámbito local.

<script type="text/javascript;version=1.7">
var global_a = 10;
var global_b =20
let( a = global_a, b=2000 ){
    console.log(a);// 10
    a+=100 + b;
    console.log(a);// 2110
    global_b = a/2;
};
console.log(global_a); // 10
console.log(global_b); // 1055
console.log(a); // ReferenceError: a is not defined
</script>

así con Let creamos un ámbito en el que existen variables privadas y locales para ese ámbito.

-Let con otras sentencias-

Ya que tenemos una intrucción que declara variables locales al bloque, porqué no combinarla con las que ya existen.

Si declaramos variables con Let en un for en la parte de inicialización obtendremos variables locales al for.

<script type="text/javascript;version=1.7">
for(let i=0; i<5; i++){
    //...
    console.log(i);// 0 1 2 3 4
}
console.log(i); // ReferenceError: i is not defined
</script>

Así i desaparece al acabar el for, que es cuando acaba el bloque de la sentencia.

Lo mismo sucede en el caso de for..in y for..of para el uso de Let.

En conclusion:

Muchas veces la forma de programar en JS es como es porque sólo define ámbito una función. Usando let podemos jugar con los ámbitos de bloque como en otros lenguajes clásicos. Pero esto no le quita a var sus propiedades tradicionales de definicion de variables.

-Problemas con Let-

Redeclaraciones de parámetros

La redeclaración de un parámetro de la función con Let y con var es un tema pendiente. Las redeclaraciónes con var sobreescriben el valor del parámetro, si, pero las redeclaraciones con var están permitidas en cualquier bloque y función tantas veces como se desee. Con let no es igual.

La redeclaracion de un parámetro con var y su posterior uso modifica el objeto arguments en la posición donde aparece la variable.

function fun(a, b, c){

    var b = 1000;
    return arguments;

}
console.log(fun("a1", "b2", "c3")); // ["a1", 1000, "c3"]

Existe una discusión en la comunidad de si debería ser igual con Let en este caso.

function f(a) {

    let a = 42;
    return arguments[0]

}
console.log(f(7));// PROBLEMA -> 42 ¿debería ser 7 o 42?

Los chicos de Mozilla dicen que sí, por eso en su implementación la redeclaración de parámetros funciona igual en let que en var.

Let en primer nivel

Este si que es un bug real de mozilla y es que Let en primer nivel (nivel de función) se comporta como Var. Permite redeclaraciones, cosa que no debería ser posible. En mozilla tienen documentado el bug (https://bugzilla.mozilla.org/show_bug.cgi?id=589199) y está en sus planes de para completar la implementación de ecmascript 6


jun 23 2012

UnderscoreJS, funciones de delay

Me han parecido muy interesantes que veo necesario comentar. Salidas de underscore js que es una librería que cada vez me está gustando más. Es un conjunto de funcionalidades que se puede decir que “completan” el javascript básico de cualquier navegador.

-Delay-

Retrasar una funcion, wrapping del setTimeout ya existe en javascript. Es muy sencilla, pero solo por abstraer el temporizador se merece una mención.

// Delays a function for the given number of milliseconds, and then calls
// it with the arguments supplied.
_.delay = function(func, wait) {
    var args = slice.call(arguments, 2);
    return setTimeout(function(){ return func.apply(null, args); }, wait);
};

-Debounce-

Devuelve una función que mientras parecida a ‘_.delay‘. Si la función se vuelve a ejecutar antes del tiempo indicado la cuenta vuelve a empezar.
Cuántas veces has querido volver a empezar la cuenta atrás para alguna acción que has lanzado. Tiene mucho más sentido si son métodos asociados a eventos del usuario. Un pequeño retraso en algo a veces, como que aparezca/desaparezca info extra cuando se hace hover/blur da muy buena experiencia al usuario (solo es un ejemplo de uso, seguro que hay mil más).

// Returns a function, that, as long as it continues to be invoked, will not
// be triggered. The function will be called after it stops being called for
// N milliseconds. If `immediate` is passed, trigger the function on the
// leading edge, instead of the trailing.
_.debounce = function(func, wait, immediate) {
    var timeout;
    return function() {
    var context = this, args = arguments;
    var later = function() {
        timeout = null;
        if (!immediate) func.apply(context, args);
    };
    if (immediate && !timeout) func.apply(context, args);
        clearTimeout(timeout);
        timeout = setTimeout(later, wait);
    };
};

Así si ejecutamos:

function x(){
    return "executed";
}
var x_debounced = _.debounce(x, 60*1000);

x_debounced();// 00:00:00
x_debounced();// 00:00:10
x_debounced();// 00:00:21

//el resultado será:
"executed" // 00:01:21

Además la función incluye el parámetro ‘immediate‘. En caso de querer que la ejecución sea anterior al tiempo de espera solo debemos ponerlo a true.
De este modo el tiempo indicado es el tiempo tras la ejecución en el que no podrá volver a ejecutarse la función.

Un ejemplo sería:

function x(){
    return "executed";
}
var x_debounced = _.debounce(x, 60*1000, true);

x_debounced();// 00:00:00 : "executed"
x_debounced();// 00:00:10
x_debounced();// 00:00:21
x_debounced();// 00:00:46
x_debounced();// 00:01:47 : "executed"

//bloqueado hasta 00:02:47

-Throttle-

Devuelve una función que sólo se puede ejecutar una vez en un periodo de tiempo. Es similar al concepto de semáforos con un recurso, solo que el recurso es la propia función.

Internamente usa ‘_.debounce‘ para liberar la ejecución.

Mantiene un control de si se ha vuelto a ejecutar la función durante el periodo de bloqueo para ejecutarla de nuevo al final.

// Returns a function, that, when invoked, will only be triggered at most once
// during a given window of time.
_.throttle = function(func, wait) {
    var context, args, timeout, throttling, more, result;
    var whenDone = _.debounce(function(){ more = throttling = false; }, wait);
    return function() {
        context = this; args = arguments;
        var later = function() {
            timeout = null;
            if (more) func.apply(context, args);
            whenDone();
        };
        if (!timeout) timeout = setTimeout(later, wait);
        if (throttling) {
            more = true;
        } else {
            result = func.apply(context, args);
        }
        whenDone();
        throttling = true;
        return result;
    };
};

Del mismo modo, si ejecutamos:

var x_throttled = _.throttle(x, 60*1000);
x_throttled();// 00:00:00 “executed”
x_throttled();// 00:00:10
x_throttled();// 00:00:21

// 00:01:00"executed"

Ante un uso masivo de la función nos aseguramos que solo se ejecutará realmente en los periodos indicados.

Para tu toolkit

Podemos incluir las funciones entre los métodos de Function, así como en su prototipo, para que cualquier función herede este método y podamos generar funciones delay, debounce y throttle en modo inline.

Hacer esto es tan sencillo como:

Function.delay = function(func, wait) {
    var args = slice.call(arguments, 2);
    return setTimeout(function(){ return func.apply(null, args); }, wait);
};
Function.prototype.delay = function(wait) { return Function.delay(this,wait); };

Function.debounce = function(func, wait, immediate) {
    var timeout;
    return function() {
    var context = this, args = arguments;
    var later = function() {
        timeout = null;
        if (!immediate) func.apply(context, args);
    };
    if (immediate && !timeout) func.apply(context, args);
        clearTimeout(timeout);
        timeout = setTimeout(later, wait);
    };
};
Function.prototype.debounce = function(wait, immediate){ return Function.debounce(this,wait,immediate); };

Function.throttle = function(func, wait) {
    var context, args, timeout, throttling, more, result;
    var whenDone = Function.debounce(function(){ more = throttling = false; }, wait);
    return function() {
        context = this; args = arguments;
        var later = function() {
            timeout = null;
            if (more) func.apply(context, args);
            whenDone();
        };
        if (!timeout) timeout = setTimeout(later, wait);
        if (throttling) {
            more = true;
        } else {
            result = func.apply(context, args);
        }
            whenDone();
            throttling = true;
            return result;
    };
};
Function.prototype.throttle = function(wait) { return Function.throttle(this,wait); };

feb 11 2012

Fuciones publicas vs privilegiadas

Hace tiempo que encontré este texto de Douglas Crockford sobre las funciones privadas en JavaScript. En el explica como crear funciones privadas de un objeto. Estas son declaradas en el constructor pero no se le asignan al objeto this. De esta manera solo las funciones dentro del mismo ámbito (el del constructor) tienen el privilegio de acceder a ellas.

function myKlass(){
   var privateValue=0;
   function privateFunction(){
      return ++privateValue;
   }
   //Esta funcion tiene el privilegio de acceder a privateFunction
   this.pivileged=function(){
      return "Ejecución nº "+ privateFunction();
   }
}
var obj = new myKlass();
obj.pivileged();//Ejeción nº 1
obj.pivileged();//Ejeción nº 2
obj.pivileged();//Ejeción nº 3

Si extendemos el prototipo de la función myKlass podemos obtener una clase más rica, con muchas más funciones publicas que estarán en todos los objetos creados con la sentencia new.
Hasta aquí nada nuevo, porque esto es posible en javascript ya desde hace mucho. Pero el diferenciar entre Publica y Privilegiada es algo que no me acaba de gustar.

Toda función puede tener ciertos privilegios.

Las funciones creadas dentro del constructor tienen acceso a todas las funciones dentro del mismo ámbito. Sí, esto es un privilegio, pero estas funciones no tienen acceso a, por ejemplo, terceras funciones internas a otra funcion privilegiada (o publica).
Así que en realidad solo tiene privilegio a un ámbito, que casualmente es el del constructor. Es muy sencillo crear otro ábito y declarar alli una gran cantidad de funciones privadas y asignarselas al prototipo. En este nuevo ámbito podriamos tener otras funciones privilegiadas que solo tuviesen acceso a este ámbito. Veamoslo:

myKlass.prototype.otherPrivileged=(function(){
   var otherVariable=0;
   function otherExecution(){
      return otherVariable+=100;
   }
   return function(){
      return "Aqui vamos a "+otherExecution();
   }
})();
obj.otherPrivileged();//Aqui vamos a 100
obj.otherPrivileged();//Aqui vamos a 200

Aqí tenemos una función que también tiene ciertos privilegios. No tiene acceso a privateValue o a privateFunction, pero solo ella tiene acceso a otherVariable y otherExecution.

Para una función está muy bien. Pero ¿y si queremos un grupo de funciones ‘privilegiadas’?. Pues nuestro ámbito de privilegios debe devolver no una sola función, sino un objeto con las funciones que deseemos y extender el prototipo de nuestra ya muy nutrida clase con ellos.

var superFunctions=(function(){
   var v1=0,v2=2000,v3=775;//...
   function fprivate1(){/*...*/}
   function fprivate2(){/*...*/}
   function fprivate3(){/*...*/}

   function fpublic1(){/*...*/}
   function fpublic2(){/*...*/}
   function fpublic3(){/*...*/}
   return {
      fpublic1: fpublic1,
      fpublic2: fpublic2,
      x: fpublic3
   }
})();

for(fun in superFunctions){
    myKlass.prototype[fun]=superFunctions[fun];
}

new myKlass();
/* Cuidado con los nombres de las funciones, serán los del objeto devuelto
x	fpublic3()
fpublic1	fpublic1()
fpublic2	fpublic2()
otherPrivileged	function()
pivileged	function()
*/

Con una funcion para extender prototypos de funciones se habría quedado un código más legible, pero en definitiva esto es lo que se debe hacer.

Sea como sea, podemos hacer que cualquier función publica sea en cierta medida privilegiada. Por eso prefiero no hacer distinción entre las funciones de un objeto. Cada una puede implementar su funcionalidad con acceso a otros métodos o no, eso no importa.


dic 23 2011

Más pixels aleatorios, esta vez con Canvas

Hace tiempo escribí un post acerca de los pixels aleatorios. Dibujaba una imagen en java para probar que no ser repetían patrones en la funcion random. Para hacer lo propio en javascript ahora gracias al html5 podemos usar la etiqueta canvas y pintar dentro de ella. Nos declaramos un canvas del tamaño que queramos, por ejemplo de 300 x 300

<canvas height="300" width="300" id="mycanvas"></canvas>

Antes de dibujar en nuestro lienzo tenemos que usar el contexto, en este caso en 2d.

Para dibujar pixel a pixel solo tienes que dibujar cuadrados de un pixel de tamaño. Empezamos por la cordenada (0,0) hasta la (299,299). En realidad puedes dibujar fuera del canvas, pero por supuesto no esperes que se vea.

function drawRandom(id){
	var canvas = document.getElementById(id);
	var ctx = canvas.getContext('2d');

	for(var j=0;j<300; j++){
		for(var i=0;i<300; i++){
			ctx.fillStyle = getRandColor();
			ctx.fillRect(i, j,i+1, j+1);
		}
	}
}

function getRandColor(){
	//Si quieres puedes usar solo blanco y negro para verlo más claro
	//var blanco="rgb(255,255,255)";
	//var negro="rgb(0,0,0)";
	return ("rgb("+(parseInt( (Math.random()*1000) % 256))+","
		+(parseInt( (Math.random()*1000) % 256))+","
		+(parseInt( (Math.random()*1000) % 256))+")");
}

drawRandom("mycanvas");

Puede que tarde un rato, o incluso que el navegador piense que tienes un bucle infinito en ejecución. Después te pintará una imagen tan “bonita” como esta:

canvas con pixels de colores aleatorios

canvas con pixels de colores aleatorios

Para este ejemplo sencillo vemos que la funcion Math.random( ) se comporta bastante bien en cuanto al grado de aleatoriedad. Pero si quieres profundizar en hacer dibujos con canvas puedes ver más cosas aquí. Si ya lo has hecho en otros lenguajes (no como yo) no te resultará complicado hacerlo en javascript.


ago 27 2011

Visión general de un SQLInjection

Me ha parecido muy completa esta presentación de SQL injection. Toca un poco de Doctrine y Propel para dar ejemplos de buenas practicas.
Da un dato interesante, entre el 40-60% de los casos de acceso a datos no autorizados son por fallos de injecciones de SQL en el código de una web. Un error muy común por lo visto.
Las transparencias son de Krzysztof Kotowicz un experto en seguridad en e-comerce y web 2.0. Solo echarle un ojo a su blog ya es algo muy recomendable apara estar al día en seguridad para la web.


may 8 2011

Two ways to create custom objects

Visto en JSAPI User Guide una tan sencilla como complicada segunda opción

Hay dos formas de crear objetos personalizados que el JS engine puede utilizar:

  • Escribir un script JS que crea un objeto, sus propiedades, métodos, y el constructor, y luego pasa la secuencia de comandos para el motor de JS en tiempo de ejecución.
  • Insertar el código de la aplicación que define las propiedades del objeto y los métodos, llame al motor para inicializar un objeto nuevo, a continuación, establezcalas propiedades del objeto a través de llamadas adicionales al motor. Una ventaja de estemétodo es que su aplicación puede contener métodos nativos que manipulen directamente la incrustación de objetos.

La desventaja del segundo método es que para escribir algo en javascript tienes que escribirlo en C++. Sencillez vs rendimiento.

Hace tiempo leí una cita sobre Unix que decía algo así como:  ”UNIX es sencillo, solo que hace falta un genio para apreciar su sencillez”. Creo que no solo le pasa a Unix.


may 6 2011

Timsort. Porqué no había versión JavaScript

La ordenación de vectores es algo que se imparte desde los primeros años de carrera en informática con el método de la burbuja, inserción directa y alguno más con complejidad O(n^2). Más tarde cuando se profundiza en la algoritmia un poco llegamos a algoritmos más complejos de complejidad O(nLogn) se concluye que no hay nada mejor en la ordenación de vectores, y esas innovaciones son ya de hace bastante tiempo.

Métodos de ordenación de vectores

QuickSort,  MergeSort, HeapSort … hay muchos Sort’s por el mundo y todos tienen ventaja frente a otros. Los que he mencionado son de los más conocidos con complejidades de O(nLogn). Por lo que he estado viendo, el MergeSort es el que se suele utilizar más por su baja cantidad de operaciones de computo. Es muy sencillo, ya que mezclar listas ordenadas de elementos tiene complejidad lineal y no tiene mucha historia. Su principal desventaja, la gran cantidad de memoria temporal utilizada, tiene cada vez menos importancia gracias a que la memoria se va abaratando cada vez más. Pero…

¿Que pasa en los dispositivos que no tienen mucha memoria? Lo primero que viene a la mente es que siempre hay alguien que tiene un equipo en el que la memoria se mide en K’s, pero no van por ahí los tiros. Los smartphones y tablets son cada vez más populares, y por ahora lo que se considera normal en estos dispositivos es lo que se tenía en escritorio hace ya bastante tiempo.

TimSort

En esta visión del ahorro de memoria + mergeSort es donde surge el algoritmo TimSort. Lo ideó Tim Peters para la ordenacion en Python (donde se pueden programar librerias nativas en C) y lo bautizó con su propio nombre, como el dice: “eh, me lo he ganado”.

El TimSort no mejora en complejidad a su padre, el MergeSort, pero si que tiene ciertas optimizaciones que lo hacen que ahorre mucha memoria en los casos medios. Cuando una parte del vector está “bastante” ordenada no sigue dividiendo el vector en partes hasta llegar a una lista de un elemento, sino que utiliza la inserción directa para ordenar todo ese trozo. Aunque la inserción directa sea de complejidad O(n^2) para listas muy pequeñas de elementos es muy rápido gracias a su sencillez.

Si un tramo del vector que estamos intentado ordenar de mayor a menor por ejemplo, se encuentra ordenado de menor a mayor, el algoritmo invierte este tramo y continua.

Con esto y ajustando los vectores temporales al mínimo requerido timsort consigue un ahorro de memoria y de rendimiento respecto de MergeSort en vectores parcialmente ordenados o con muchos repetidos.

Ejemplo de ordenación con Timsort

TimSort en C (Python) y en Java

Es por estas pequeñas cosas que el TimSort ha sido seleccionado para ser el tipo de ordenación de vectores por defecto en Java 7 (lanzamiento estimado en Julio de 2001) y en la plataforma para móviles Android (que se puede decir que es Java también)

También es la ordenación por defecto en Python, bastante lógico cuando el algoritmo se ideó en principio para este lenguaje. Esta implementación es nativa de Python, por eso está escrito en C (no todo lo nativo de Python está escrito en C pero sí es aconsejable para aumentar el rendimiento).

El TimSort de Tim lo puedes encontrar aquí (timsort.c) y una explicación de sus pruebas de rendimiento.

Otra implementación en java Josh Bloch con bastantes menos lineas de código.

Y … en JavaScript

Siendo un obsesionado del JavaScript me pregunté, ¿y no hay implementación en JavaScript?. En javascipt ya se pueden ordenar vecteres con el metodo nativo del Array sort(funcionDeComparacion) pero cada maquina viertual de JS utiliza la ordenación que más le conviene. Bueno en realidad la que han decidido sus desarrolladores. Pero de todas maneras, si los desarrolladores de una maquina virtual de JS decidieran implementarlo usarían el código ya existente si implementan en C/C++ como son el SpiderMonkey y el V8, o la versión Java para Rhino.

Utilizar una versión JavaScript para ordenar vectores en JavaScript sería una perdida de rendimiento, al menos en gran cantidad de los casos.

Mi pequeña contribución

Si aun así no te fias y quieres hacer tus propias pruebas de rendimiento he portado la versión Java del algoritmo a JavaScript (TimSort JavaScript), con algunas optimizaciones propias del lenguaje; intentando utilizar el mayor numero de métodos nativos del lenguaje, aunque estoy seguro de que se puede optimizar algo más hasta equipararse en rendimiento 1 a 1 al sort nativo (que puede que en cada implementación sea un algoritmo distinto). Actualmente solo supera en rendimiento al nativo en muy pocas ocasiones, cuando el vector tiene muy poca entropía; y en casos muy malos llega a duplicar el tiempo de computo de la versión nativa.

No he buscado mucho y no sé que algoritmos utilizan las maquinas virtuales de los navegadores de hoy en día así que indagaré un poco pero eso es otro post.


mar 14 2011

Dibujando rutas en Google Maps

Dibujando rutas

Puedes consultar las partes anteriores del manual de Google Maps Api 3:
Primera parte del manual

Segunda parte del manual

Tercera parte del manual

Este servicio es interesante, a demás podemos usar coordenadas o direcciones directamente, ya que el servicio las traducirá por sí solo.
Las clases principales son: google.maps.DirectionsService que es la que ejecuta la peticion del servicio al servidor y nos devuelve los datos, y google.maps.DirectionsRenderer que es la encargada de mostrar la ruta en nuestro mapa.
El ejempo básico de inicialización es el siguiente:

directionsService = new google.maps.DirectionsService();
directionsDisplay = new google.maps.DirectionsRenderer();

directionsDisplay.setMap(map);

La llamada a route tiene el formato “directionsService.route(request, function(result, status)”. Hay que generar un objeto request primero(DirectionRequest) que solo es necesario rellenar los campos que no sinteresan. Despues la funcion de callback es la que a partir del status tratamos los reultados.

var request = {
  origin:start,
  destination:end,
  travelMode: google.maps.DirectionsTravelMode.DRIVING
};

La llamada y el tratamiento del objeto result. Comprobamos que el status es OK, si no no hay nada que hacer, salvo mostrar el tipo de error.

directionsService.route(request, function(result, status) {
  if (status == google.maps.DirectionsStatus.OK) {
    directionsDisplay.setMap(map);
    var mystr="";
    for(var i in result.routes){
      var mylegs=result.routes[i].legs
      for(var j in mylegs){
        mystr += mylegs[j].distance.text;
        mystr += " " + mylegs[j].duration.text+ " <br/>";
      }
      mystr+="<br/>";
      $(“#infoRecorrido).html(mystr);
    }
    directionsDisplay.setDirections(result);
  }
});

Lo que realmente dibuja el mapa es ‘directionsDisplay.setDirections(result)’ ¿y todo lo demas? pues bien, google nos envia un objeto con bastante información. Los margenes en que se visualizará el mapa, las coordenadas de los puntos de incio y fin, y otras cosas entre ellas la distancia y tiempo de recorrido.
La distancia se encuentra en “result.routes[0..n-1].legs[0..n-1].duration”. Se puede visualizar en texto en tiempo ya tranformado en horas:minutos:segundos con ‘.text’ o directamente en el numero de segundos con ‘.value’.
La respuesta contiene bastante información y se le puede sacar mucho partido (ver: http://code.google.com/intl/es/apis/maps/documentation/directions/ )

bounds = new google.maps.LatLngBounds();
for(var l in markers){
  bounds.extend( markers[l].getPosition() );
}
map.fitBounds(bounds);

visto en: http://blog.shamess.info/2009/09/29/zoom-to-fit-all-markers-on-google-maps-api-v3/

Finalmente y por experiencia propia recomiendo re posicionar los margenes con cierto retardo con una función como esta:

function rebounds(){
  setTimeout(recReBounds,250,(6));
}

function recReBounds(veces)
  if(!veces){
    return false;
  }
  try{
    bounds = new google.maps.LatLngBounds();
    for(var l in markers){
    bounds.extend( markers[l].getPosition() );
  }
  map.fitBounds(bounds);
  }
  catch(e){
    setTimeout(recReBounds,250,(veces-1));
  }
}

rebounds();

A veces la velocidad del navegador que esté utilizando el cliente no carga las imágenes del mapa con mucha velocidad. Si ejecutamos el reajuste de margenes una vez recogidos los datos puede que se reajusten los margenes antes de pintar el mapa, con lo cual el reajuste no tiene efecto. Con un retardo de un cuarto de segundo el usuario siente interacción de la web y el reajuste tiene efecto.


mar 11 2011

Dibujar marcas en un mapa

Trabajando con los markers

Puedes consultar las partes anteriores del manual de Google Maps Api 3

primera parte del manual

segunda parte del manual

Para empezar vamos a trabajar con un vector de marcas que va a ser una variable global markers. Tan sencillo como:

var markers={};

setMarker hace algo más que posicionar un marker en el mapa. Seleciona el campo donde tenemos la localidad (o direccion), esto lo hace con la funcion dollar de jquery. Esta direccion la traduce a coordenadas LatLng con el servicio geocoder.
Despues invoca al método marker que es el que realmente inserta el marcador en el punto correcto del mapa.

function setMarker(id,addid){
  var dir = $("#"+id).val();
  geocoder.geocode( { 'address': dir}, function(results, status) {
    if (status == google.maps.GeocoderStatus.OK) {
      marker(id, results[0].geometry.location);
    } else {
      marker(id,null);
    }
  });
}

Marker en realidad es una funcion muy sencilla. Si existe el marcador añade una nueva posición, si no existe lo crea indicandole el mapa y la posicion donde irá.
La unica complejidad en cuanto a configuracion del maker es indicarle que no sea arrastrable (draggable) ni que se pueda pinchar (clickable).

function marker(id, location){
  if(markers[id]){
    markers[id].setPosition(location);
  }
  else{
    markers[id] = new google.maps.Marker({
      map: map
      ,position: location
      ,markerOptions:{
        draggable:false
        ,clickable:false
      }
    });
  }

  map.setZoom(10);
}

Otras opciones posibles son hacer zoom y centrar el mapa en el marcador (en este caso está comentado) pero son opciones del mapa, no del marcador.

Borrar un marker

Para borrar un marker es tan sencillo como añadirle una posicion nula. Como en nuestro caso tenemos un objeto global donde están todos nuestros markers nos podemos hacer las funciones hideMarker y hideAllMarkers:

function hideAllMarkers(){
  for(var m in markers){
    markers[m].setPosition(null);
  }
}

function hideMarker(id){
  if(id && id != "" && markers[id]){
    markers[id].setPosition(null);
    return true;
  }
  return false;
}

*Cuidado si se usan otras propiedades de los markers como el texto que despliegan al clickarlos. Si volvemos a ponerle una posicion al marker esas propiedaden persisten. Suponemos que en esta aplicacion no añadimos informacion extra y que los markers no son clickables. En otro caso para más seguridad hay que hacer un new cada vez para chafar las propiedades anteriores, o cambiarlas una por una.