ugrás a tartalomhoz

JavaScript objektumok azonosítása

inf3rno · 2011. Ápr. 13. (Sze), 21.18

Néhányszor belefutottam abba a problémába JavaScriptnél, hogy csak nehezen lehet létrehozni objektum kulcsos mapeket ill. seteket. Ezért úgy döntöttem, hogy írok egy kis bejegyzést ennek a mikéntjéről. Ez a probléma többek között abban az esetben merül fel, amikor van két objektumokat tartalmazó gyűjteményünk, és a kettő metszetére van szükségünk úgy, hogy az nem tartalmazhatja kétszer ugyanazt az objektumot. Erre a leghétköznapibb példa, ha több CSS kiválasztót használunk egy lekérdezésben.


<p class="red underlined">
piros és aláhúzott
</p>
<p class="red">
piros
</p>
<p class="underline">
aláhúzott
</p>

Először dobjunk össze egy nagyon egyszerű parsert a CSS kiválasztókhoz. Annyit kell tudnia, hogy elemnév és osztálynév alapján ki tudjon választani elemeket, és ezeket egy setben dobja vissza. Egyelőre set helyett elég a tömb használata:


var Set=Array;

(function ()
{
	var parseMultiSelectorText=function (multiSelectorText)
	{
		var selectors=[];
		multiSelectorText.split(",").forEach(function (selectorText)
		{
			selectors.push(parseSelectorText(selectorText));
		});
		return createMultiSelector(selectors);
	};
	
	var parseSelectorText=function (selectorText)
	{
		var selectorPattern=new RegExp("^([\\w]+)\\.([\\w]+)$");
		var match=selectorText.match(selectorPattern);
		var tagName=match[1];
		var className=match[2];
		return createSelector(tagName,className);
	};
	
	var createMultiSelector=function (selectors)
	{
		return function (context)
		{
			var selectedNodes=new Set();
			selectors.forEach(function (selector)
			{
				selectedNodes.push.apply(selectedNodes,selector(context));
			});
			return selectedNodes;
		};
	};
	
	var createSelector=function (tagName,className)
	{
		return function (context)
		{
			var selectedNodes=[];
			Array.prototype.forEach.call(context.getElementsByTagName(tagName),function (node)
			{
				if (String(" "+node.className+" ").indexOf(" "+className+" ")!=-1)
				{
					selectedNodes.push(node);
				}
			});
			return selectedNodes;
		};
	};

	$=function (multiSelectorText)
	{
		return parseMultiSelectorText(multiSelectorText)(document);
	};
	
})();

Felhasználtam az Array.forEach()-et.


if (!Array.prototype.forEach)
{
  Array.prototype.forEach = function(fun)
  {
    if (this === void 0 || this === null)
      throw new TypeError();

    var t = Object(this);
    var len = t.length >>> 0;
    if (typeof fun !== "function")
      throw new TypeError();

    var thisp = arguments[1];
    for (var i = 0; i < len; i++)
    {
      if (i in t)
        fun.call(thisp, t[i], i, t);
    }
  };
}

Ha teszteljük most a selectorokat,


window.onload=function ()
{
	alert($("p.red,p.underlined"));
};

akkor látszik, hogy egy négy elemű tömböt ad vissza a $ függvény. Ez azért van, mert a piros és aláhúzott paragrafus kétszer lett kiválasztva; egyszer mint piros, és egyszer mint aláhúzott. A dupla bejegyzéseket az új elemek felvételekor érdemes szűrni.

A szűrést kétféleképpen lehet megoldani:

  1. Végigmegyünk a teljes gyűjteményen, és minden elemet összehasonlítunk az újonnan hozzáadandó elemmel. Ha találunk egyezést, akkor nem adjuk hozzá a gyűjteményhez az elemet, mert már benne van.
  2. Az új elemhez lekérünk egy azonosító kódot, megnézzük, hogy az azonosító kód szerepel e már a gyűjteményben. Ha igen, akkor nem adjuk hozzá újra. Ez a megoldás azért jobb, mert egyszerű típusokat már lehet kulcsnak használni mapekhez. A JavaScript alapból minden kulcsot stringre alakít, és úgy használ fel az objektumoknál.

Most csináljuk egy egyszerű setet. Kell neki egy push() és egy toString() metódus.


var Set=function ()
{
	this.table={};
};
Set.prototype.push=function ()
{
	var set=this;
	Array.prototype.forEach.call(arguments,function (value)
	{
		set.add(value);
	});
	return this;
};
Set.prototype.add=function (value)
{
	var key=
	(
		("identity" in value)
		?id=value.identity()
		:value
	);
	if (!this.table.hasOwnProperty(key))
	{
		this.table[key]=value;
	}
	return this;
};
Set.prototype.forEach=function (fun,thisp)
{
	if (!thisp)
	{
		thisp=this;
	}
	for (var i in this.table)
	{
		if (this.table.hasOwnProperty(i))
		{
			fun.call(thisp,this.table[i],i,this);
		}
	}
	return thisp;
};
Set.prototype.toArray=function ()
{
	var array=[];
	this.forEach(function (value)
	{
		array.push(value);
	});
	return array;
};
Set.prototype.toString=function ()
{
	return this.toArray().toString();
};

Mivel nincs identity() metódus beállítva a paragrafusokhoz, ezért most csak egy paragrafus szerepel majd a listában, ugyanis a toString() minden paragrafusra ugyanaz lesz.

Most jön a dolog lényegi része: hogyan oldjuk meg az objektumok egyedi azonosítását? A legegyszerűbb, ha számozzuk az objektumokat, és az adott objektum számát eltároljuk egy tulajdonságban.


(function ()
{
	var i=0;
	var table={};
	Object.prototype.identity=function ()
	{
		if (!this.__hashcode__)
		{
			this.__hashcode__=++i;
			table[i]=this;
		}
		return this.__hashcode__;
	};
	
	Object.identify=function (i)
	{
		return table[i];
	};
	
	var hasOwnProperty=Object.prototype.hasOwnProperty;
	Object.prototype.hasOwnProperty=function (property)
	{
		return (hasOwnProperty.call(this,property) && property!="__hashcode__");
	};
})();

A hasOwnProperty()-t azért kell felülírni, hogy a tároló tulajdonság esetleges iterálásnál ne szerepeljen.

Ez a megoldás Firefox és a többi böngésző esetén jól vizsgázik, Internet Explorer 8 alatt viszont ugyanúgy egy elem marad a setben. Ez azért van, mert MSIE-ben a DOM Node-oknak semmi köze nincs az Objecthez, így hiába írjuk át az Object.prototype-ot, az nem lesz hatással rájuk. Ezt a problémát jelenlegi ismereteim szerint egyedül behavior használatával lehet áthidalni. A behavior ElementNode-okra alkalmazható, szóval TextNode-okra a módszer nem használható – de általában nem is keresünk TextNode-okra.

Először csináljuk meg a HTC fájlt:


<PUBLIC:COMPONENT lightWeight="true">
<script type="text/javascript">
for (var property in Object.prototype)
{
	element[property]=Object.prototype[property];
}
</script>
</PUBLIC:COMPONENT>

A komponens az aktuális elemet jelöli, taget nem adtuk meg, mert minden elemre alkalmazzuk a behaviort, a lightWeight attribútum pedig ahhoz kell, hogy új elemeknél is működjön a dolog. A component-en belüli részben a szkriptnél az element az aktuális elemet jelöli. Annyit csinálunk, hogy átmásoljuk az Object.prototype-ból az összes tulajdonságot az aktuális elemre.

Ahhoz, hogy működjön a dolog, MSIE esetén az összes elemre alkalmazni kell a behaviort, és át kell írni a document.createElement()-et is, hogy az új elemekhez is hozzáadjuk a viselkedést.


<!--[if IE]>
<style type="text/css">
*{behavior:url(identity.htc)}
</style>
<script type="text/javascript">
(function ()
{
	var createElement=document.createElement;
	document.createElement=function ()
	{
		var element=createElement.apply(this,arguments);
		element.addBehavior("identity.htc");
		return element;
	};
})();
</script>
<![endif]-->

Így már MSIE esetén is működik a metszet kiválasztása.

Összegezve a böngészők közötti eltérések miatt már egy ilyen – amúgy egyszerűnek tűnő – dolog is csak nehezen és csak részben megvalósítható.

 
1

Kipróbált módszer?

T.G · 2011. Ápr. 13. (Sze), 23.20
Az itt leírtak mennyire kísérletiek illetve mennyire kipróbáltak használat közben?

Nekem egy általános halmaz típusnál nagyon hiányozna a primitív típusok használata. Típushibát kapunk erre, ha nem objektum a value érték: ("identity" in value)

Közben nem arról van szó, hogy null és az undefined értéken kívül minden másnak lehetne azonosítója? Bár a primitív elemek azonosítójával azért vannak problémák:
var a = b = 10;
a.identity() === b.identity(); // false
Ami viszont nem érthető, hogy miért nem a hagyományos módon az egyenlőséggel vizsgálod az objektumok egyenlőségét? Ez tényleg gyorsabb?

Végül egy apróság, hogy konstruktivitás is legyen a hozzászólásomban. :)
A „lényegi” résznél a table lehetne tömb (szerintem szebb lenne:).
this.__hashcode__ = table.length;
table.push(this);
2

"Ez tényleg gyorsabb?" - Egy

prom3theus · 2011. Ápr. 14. (Cs), 02.47
"Ez tényleg gyorsabb?"
- Egy hash-ben azonosítani egy konkrét elemet gyorsabb valószínűleg, mint ciklusban végigpásztázni adott esetben soktucat elemet és mindet egyesével ellenőrizni, hogy azonos-e az éppen hozzáadni kívánt elemmel.

Egyébként egy csomó helyen nem értem a kódot:
1. Array.forEach()-nél a 13-ik sor értékadása felesleges, az arguments[1]-et minden további nélkül át lehetne adni a 17-ik sorban thisp helyett, mivel thisp sehol sincs használva, csak ott.
2. A Set-et létrehozó script-ben a push() deklarációját biztosan így oldottam volna meg - valamivel szerintem érthetőbbé válik a kód:
Set.prototype.push=function ()
{
    var args = Array.prototype.slice.call(arguments);
    args.forEach.call(this, function (value)
    {
        this.add(value);
    });
    return this;
};
...vagy ha a cél a mégkisebb kód, egy deklaráció megtakarításával:
Set.prototype.push=function ()
{
    Array.prototype.slice.call(arguments).forEach.call(this, function (value)
    {
        this.add(value);
    });
    return this;
};
3. A Set.forEach() implementációjában az első if-et kiváltanám, a thisp paramétert pedig scope-nak hívnám és helyette this-t adnám visszatérésnek:
Set.prototype.forEach=function (fun, scope)
{
    scope = scope || this;
    for (var i in this.table)
    {
        if (this.table.hasOwnProperty(i))
        {
            fun.call(scope, this.table[i], i, this);
        }  
    }  
    return this;
};
A scope visszaadása könnyen összezavarhatja a fejlesztőt, nem jellemző.

Elkerülendő a behavior használatát, az Object.prototype.identity()-t a DOM object-ekre is ráhúznám, például DOMNode.prototype.identity() deklarálásával, vagy akár on the fly: ha egy hozzáadni tervezett objektumnak nem létezik ilyen metódusa, akkor hozzárendelném a metódust.
Object.prototype.identifiable = function()
{
    if (!this.identity)
    {
        this.identity = function ()  
        {  
            if (!this.__hashcode__)  
            {  
                this.__hashcode__=++i;  
                table[i]=this;  
            }
        }
    }
    return this;
}
És így elvileg (hangsúlyozom: nem teszteltem, de valószínűsítem) szép formával ellenőrizhetővé válik az is, amit az Object prototype-jának bővítése nem tesz azzá:
Set.prototype.add=function (value)
{
    var key=
    (
        (typeof value == 'string')
        ? value : 
            (typeof value == 'number')
            ? (new Number(value)).toString() :
                (typeof value == 'boolean')
                ? (new Boolean(value).toString() :
                (new Number(Object.prototype.identifiable.call(value).identity()).toString()
    );
    if (!this.table.hasOwnProperty(key))
    {
        this.table[key]=value;
    }
    return this;
};
Ha az utóbbi nem is működik így ebben a formában, a cél/szándék azt hiszem látható belőle.
(Megj.: A toString()-ekre a magyarázatom csupán annyi, hogy a kód így elvileg strict-ebb lesz, nem vagyok biztos benne, hogy szabvány szerint a valami->string konverziót a JS parser-nek kéne megoldania)
3

Re: "Ez tényleg gyorsabb?"

T.G · 2011. Ápr. 14. (Cs), 08.05
A Set-nél biztos nem jó az, hogy az objektumokat a sorszámukkal, míg a számokat az értékükkel azonosítjuk, mert ugye akkor az első objektum és a 0 összeakad.

Ezért kérdeztem rá, hogy használat közben is megállja a helyét a kód? :)

Mindemellett én nem vagyok biztos abban, hogy egy tömbben egy indexOf lassabb, minthogy minden változóhoz létrehozunk egy plusz metódust, illetve azonosításnál plusz függvényhívás, egy különálló tömbben az összes változónkat gyűjtjük stb.)

Az én verzióm a Set.push-ra, ha már... :)

Set.prototype.push = function ()   {  
    for (var i = 0, l = arguments.length; i < l; i++) {
        this.add(arguments[i]);
    }
    return this;  
};
4

Set-nél és Map-nél is úgy

inf3rno · 2011. Ápr. 14. (Cs), 08.20
@TG:
Set-nél és Map-nél is úgy lehet megoldani, hogy vagy két objektumban tárolod a dolgokat, vagy beteszel valamilyen prefix-et a hashCode elé, ami megkülönbözteti a sima szövegektől, mondjuk tabot vagy ilyesmit... Nyilván ha általánosan oldja meg az ember, akkor lassabb lesz, mintha külön csinál egy HashMap-et meg HashSet-et. Azt hiszem így hívják java-ban azokat, amiknél a hashCode a kulcs. Szerintem primitív típusoknál ott sincs értelmezve a hashCode, de lehet, hogy tévedek.

Azt, hogy a ciklusnál gyorsabb e teljesen felesleges tesztelni, mert nyilvánvaló, hogy az. A primitív típusoknál az identity mindig mást ad, nem jegyzi meg őket, szóval őket jobb a saját értékükkel azonosítani, azazhogy a toString-el. Gondolkodtam azon, hogy az Object.prototype.toString-et írjam át olyanra, hogy hashCode-ot adjon, így nem kéne tesztelni, hogy primitív típusról van e szó, de aztán a végén elvetettem ezt a megoldást a Function, Array, Date és RegExp miatt, jobb ha látjuk, hogy mi van ezekben az objektumokban.

@prom3theus:
Az Array.forEach-et a developer.mozilla.org-ról másoltam be, kicsit módosítottam rajta, aztán az arguments-es rész úgy maradt bent. Nyilván ha én írtam volna, akkor thisp helyett scope vagy context lenne ott.
A scope visszaadása sokszor segít a láncok képzésénél, persze jobban átlátható, ha minden külön sorban van, valóban rontja az átláthatóságot.

Felesleges ennyi short-if, meg az identifiable is, elég lenne a primitív típusok toString metódusait betenni az identity tulajdonsághoz, úgy már nem hashCode-t adnának vissza, hanem a rendes értéküket. Esetleg még az Object.prototype-ost lehetne módosítani a tabulátorral, ahogy fentebb írtam, és úgy már kész is lenne.
(A null az jogos az "identity" in -nél.)

Elkerülendő a behavior használatát, az Object.prototype.identity()-t a DOM object-ekre is ráhúznám, például DOMNode.prototype.identity() deklarálásával, vagy akár on the fly: ha egy hozzáadni tervezett objektumnak nem létezik ilyen metódusa, akkor hozzárendelném a metódust.

Nem tudom, lehet, hogy nem tettem elég világossá, msie-ben ha DOM Node tulajdonságát akarod manipulálni, akkor hibaüzenetet kapsz. Ez azért van, mert ezek a Node-ok igazából nem javascript objektumok, nem lehet beállítani rajtuk tulajdonságot, sőt még lekérni sem. Az "identitity" in this is ezért van bent, mert arra nem dobnak hibaüzentet. Egyedül a htc az, amivel rá lehet őket venni, hogy viszonylag normálisan viselkedjenek :-P Ne kérdezd, hogy ennek mi a logikája, szerintem aki ezt microsoftnál kitalálta az sem tudja...

Olyan szempontból nincs sok értelmük ezeknek, hogy az ember úgyis keretrendszert használ, és nem ír ilyesmiket a nulláról. :-) Azért érdekes, hogy még ilyen apróságot is mennyire nehéz cross-browser megírni. MSIE tényleg egy rémálom fejlesztői (meg felhasználói) szempontból.
5

Azt nézem, hogy van egy üres

inf3rno · 2011. Ápr. 14. (Cs), 08.30
Azt nézem, hogy van egy üres kód sor a bejegyzés elején, hűha :-P

Amúgy a htc-re azt írták, hogy nagyon eszi a processzort, dehát sajna nincs jobb megoldás :S Majd ha több időm lesz (az még 1-2 hónap), akkor megtákolom úgy a rendszert, hogy javascript szúrja be a style tag-et, ha szükséges. Egyelőre nem tudom, hogy ilyen menet közbeni DOM manipulációnál alkalmazza e az összes meglévő node-ra a htc-t vagy sem. Az igazán jó az lenne ha mindezt XML-re is meg tudnám csinálni, de sajnos lehetetlen :S
6

Nem tudom, mennyire

Hidvégi Gábor · 2011. Ápr. 14. (Cs), 09.41
Nem tudom, mennyire egyszerűsítené a problémát, ha a HTML generálásakor minden elemnek adnál egy id-t, amelyikről szóba jöhet, hogy később kiválasztod a dollár függvényeddel.
7

Valamennyire hasonló dologról

inf3rno · 2011. Ápr. 14. (Cs), 16.36
Valamennyire hasonló dologról van szó, annyi, hogy akkor document.getElementById lenne a table helyett, és getAttribute("id") a __hashcode__ helyett. Nagyjából ugyanarról van szó, de elvileg getAttribute az lassabb, mint egy sima tulajdonság elérés. Érdemes lenne tesztelni, hogy mennyivel lassabb. Ja meg hát persze akkor kötelező lenne mindennek id-t adni, ami szóba jöhet. Előnye ennek, hogy XML-ben is működne. Hmm szerintem lehetne ezt az id dolgot automatizálni is... Aminek nincs egyedi id-je, annak generálna egyet a rendszer... Itt tényleg csak a sebesség ami számítana.
8

Szebben, könnyebben, gyorsabban

Adam · 2011. Ápr. 14. (Cs), 17.27
És nem lenne egyszerűbb és gyorsabb, ha a már meglevő DOM (szabvány / nem szabvány) megoldásokat használnánk?

var result = [DOMElementA, DOMElementB, DOMElementC, DOMElementA];

// result = A, B, C, A

result.sort(function(a, b)
{
	if (a === b) {
		return 0;
	}

	if (document.documentElement.compareDocumentPosition) {
		return a.compareDocumentPosition(b) & 4 ? -1 : 1;
	}
	
	if (document.documentElement.sourceIndex === 0) {
		return a.sourceIndex > b.sourceIndex ? -1 : 1;
	}
});

// result = A, A, B, C

for (var i = 0, iL = result.length - 1; i < iL; i++) {
	if (result[i] === result[i + 1]) {
		result.splice(i, 1);
	}
}

// result = A, B, C
Persze nincs minden eset lekezelve, meg FF és IE alatt teszteltem csak, de a lényeget láthatod, hogy hogyan lehetne egyszerűbben, gyorsabban egy unique listát csinálni a node-jaidat tartalmazó tömbből.
9

Ez a sourceIndex érdekes,

inf3rno · 2011. Ápr. 14. (Cs), 17.42
Ez a sourceIndex érdekes, kerestem ilyen index-elő tulajdonságot, de eredménytelenül, azt hittem nem csináltak a node-okhoz. :-) Na majd utánanézek, kösz, hogy írtál róla. Ha működik ez a sourceIndex-es megoldás, akkor az Object.prototype-ból is ki lehetne emelni a kódot.


Tákoltam is rajta, és megy. Úgy néz ki, mintha ff alatt nem lenne sourceIndex (__hashcode__-al állítja be a dolgokat). Msie alatt érdekesen viselkedik, az új elemeknek -1-es értéket ad, szóval lehet, hogy azokat a létrehozáskor be kell szúrni valahova... Ez sem tökéletes megoldás, de talán jobb, mint a htc, még tesztelni kéne...

	Object.identity=function (o)
	{
		if ((o===null || o===undefined) && typeof(o)!="object" && typeof(o)!="function" && !("sourceIndex" in o))
		{
			return;
		}
		if (o.sourceIndex)
		{
			var hashCode="."+o.sourceIndex;
			if (!(hashCode in table))
			{
				table[hashCode]=o;
			}
			return hashCode;
		}
		else
		{
			if (!o.__hashcode__)
			{
				o.__hashcode__=++i;
				table[i]=o;
			}
			return o.__hashcode__;
		}
	};
Ha jól sejtem, akkor a sourceIndex megváltozik a dokumentum átrendezésekor, szóval ilyen egzakt azonosításra nem a legjobb, rendezésre és szűrésre talán használható.
10

A sourceIndex és compareDocumentPosition()

Adam · 2011. Ápr. 15. (P), 09.37
A sourceIndex az IE specifikus. DOM3-ban van benne a compareDocumentPosition().

Bár ott a w3 oldalán nincs a doksiban, hogy mit ad vissza, itt egy táblázat rá:
Bits   | Number | Meaning
---------------------------------
000000 | 0      | Elements are identical.
000001 | 1      | The nodes are in different documents (or one is outside of a document).
000010 | 2      | Node B precedes Node A.
000100 | 4      | Node A precedes Node B.
001000 | 8      | Node B contains Node A.
010000 | 16     | Node A contains Node B.
100000 | 32     | For private use by the browser.

Egy node egzakt azonosítására az id szolgálna.

További érdekes olvasmány lehet:
Comparing Document Position
contains() for Mozilla
Sizzle.sortOrder()
11

Oks, köszi.

inf3rno · 2011. Ápr. 15. (P), 09.41
Oks, köszi.
12

garbage collector

T.G · 2011. Ápr. 15. (P), 10.33
Hadd kössem egy kicsit az ebet a karóhoz. :)
A biztos gyorsabb, mert miért ne lenne gyorsabb válaszok nem nagyon győznek meg. :)
A nagy probléma a fenti scripttel, hogy létrehozunk egy tömböt, amiben minden változó bekerül, ezeket a változókat az egyik segédfüggvény segítségével bármikor el is érhetjük. Ha, ezt tényleg minden objektumnál akarjuk használni, akkor 15 perc használat után fejre áll a Firefox is. (legalábbis nagyon durván belassul) Ezzel a tömbbel kikapcsoljuk a garbage collector-t.
Szerintem ezzel sokkal többet vesztünk a réven, mint nyerünk a vámon. :)
13

Jó, hát egy nagy központi

inf3rno · 2011. Ápr. 15. (P), 11.40
Jó, hát egy nagy központi tábla helyett lehet minden egyes Set-hez meg Map-hez külön táblát csinálni, máris meg van oldva a probléma. Ezeket a megoldásokat még nem teszteltem nagy adatmennyiségre, de nem hiszem, hogy ennyitől fejre állna a firefox. Írj tesztet, ha van időd, nekem most nagyon nincs.