Help/Collections/IdentitySet.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
   2 <html>
   3 <head>
   4 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
   5 <meta http-equiv="Content-Style-Type" content="text/css">
   6 <title></title>
   7 <meta name="Generator" content="Cocoa HTML Writer">
   8 <meta name="CocoaVersion" content="949.43">
   9 <style type="text/css">
  10 p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica}
  11 p.p2 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica; min-height: 14.0px}
  12 p.p3 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica; color: #0021e7}
  13 p.p4 {margin: 0.0px 0.0px 0.0px 0.0px; font: 13.0px Helvetica; min-height: 16.0px}
  14 p.p5 {margin: 0.0px 0.0px 0.0px 0.0px; font: 13.0px Helvetica}
  15 p.p6 {margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Monaco; min-height: 16.0px}
  16 p.p7 {margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco; color: #001bb9; min-height: 12.0px}
  17 p.p8 {margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco}
  18 p.p9 {margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco; min-height: 12.0px}
  19 p.p10 {margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco; color: #ad140d}
  20 p.p11 {margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco; color: #606060}
  21 p.p12 {margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco; color: #2c7014}
  22 p.p13 {margin: 0.0px 0.0px 0.0px 0.0px; font: 14.0px Helvetica; min-height: 17.0px}
  23 p.p14 {margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco; color: #000000}
  24 p.p15 {margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco; color: #ad140d; min-height: 12.0px}
  25 span.s1 {font: 18.0px Helvetica}
  26 span.s2 {color: #0021e7}
  27 span.s3 {color: #001bb9}
  28 span.s4 {color: #000000}
  29 span.s5 {text-decoration: underline}
  30 span.s6 {font: 12.0px Helvetica}
  31 span.s7 {color: #0000bf}
  32 span.Apple-tab-span {white-space:pre}
  33 </style>
  34 </head>
  35 <body>
  36 <p class="p1"><span class="s1"><b>IdentitySet<span class="Apple-tab-span">      </span><span class="Apple-tab-span">    </span><span class="Apple-tab-span">    </span><span class="Apple-tab-span">    </span></b></span><b>a set according to identity</b></p>
  37 <p class="p2"><br></p>
  38 <p class="p1"><b>Inherits from: </b><a href="../Core/Object.html"><span class="s2"><b>Object</b></span></a><b> : </b><a href="Collection.html"><span class="s2"><b>Collection</b></span></a><span class="s3"><b> : </b><a href="Set.html"><b>Set</b></a></span></p>
  39 <p class="p2"><br></p>
  40 <p class="p1">An IdentitySet is a collection of objects, no two of which are the same object (aka. "identical").</p>
  41 <p class="p1">Most of its methods are inherited (see <a href="Collection.html"><span class="s3">Collection</span></a> and <a href="Set.html"><span class="s3">Set</span></a> classes).</p>
  42 <p class="p1">The contents of an IdentitySet are <b>unordered</b>. You must not depend on the order of items in an IdentitySet.</p>
  43 <p class="p1">For an ordered set, see <a href="OrderedIdentitySet.html"><span class="s3">OrderedIdentitySet</span></a>.</p>
  44 <p class="p2"><br></p>
  45 <p class="p1">IdentitySets are faster than Sets because testing for identity is much faster than testing for</p>
  46 <p class="p1">equality. Different classes may implement equality in different ways, but identity can be determined</p>
  47 <p class="p1">just by comparing the object addresses. This allows some methods of IdentitySet to be implemented</p>
  48 <p class="p1">by fast primitives.</p>
  49 <p class="p2"><br></p>
  50 <p class="p3"><span class="s4">See also: <a href="IdentitySet.html"><span class="s5">IdentitySet</span></a>, <a href="List.html"><span class="s5">List</span></a>, <a href="Dictionary.html"><span class="s5">Dictionary</span></a></span></p>
  51 <p class="p4"><br></p>
  52 <p class="p5"><b>Adding and Removing:</b></p>
  53 <p class="p2"><br></p>
  54 <p class="p1"><b>add(anObject)</b></p>
  55 <p class="p2"><br></p>
  56 <p class="p1"><span class="Apple-tab-span">     </span>Add anObject to the IdentitySet.<span class="Apple-converted-space"> </span></p>
  57 <p class="p1"><span class="Apple-tab-span">     </span>An object which is equal to an object already in the IdentitySet will not be added.</p>
  58 <p class="p6"><br></p>
  59 <p class="p7"><br></p>
  60 <p class="p8"><span class="s3"><span class="Apple-tab-span">    </span>IdentitySet</span>[1, 2, 3].add(4);</p>
  61 <p class="p9"><span class="Apple-tab-span">     </span></p>
  62 <p class="p8"><span class="Apple-tab-span">     </span><span class="s3">IdentitySet</span>[1, 2, 3].add(3);</p>
  63 <p class="p9"><span class="Apple-tab-span">     </span></p>
  64 <p class="p10"><span class="s4"><span class="Apple-tab-span">   </span></span>// the two strings are equal but not identical</p>
  65 <p class="p11"><span class="s4"><span class="Apple-tab-span">   </span></span><span class="s3">IdentitySet</span><span class="s4">[</span>"abc"<span class="s4">, </span>"def"<span class="s4">, </span>"ghi"<span class="s4">].add(</span>"def"<span class="s4">); <span class="Apple-converted-space"> </span></span></p>
  66 <p class="p9"><span class="Apple-tab-span">     </span></p>
  67 <p class="p10"><span class="s4"><span class="Apple-tab-span">   </span></span>// symbols are guaranteed to be identical if they are equal</p>
  68 <p class="p12"><span class="s4"><span class="Apple-tab-span">   </span></span><span class="s3">IdentitySet</span><span class="s4">[</span>'abc'<span class="s4">, </span>'def'<span class="s4">, </span>'ghi'<span class="s4">].add(</span>'def'<span class="s4">); <span class="Apple-converted-space"> </span></span></p>
  69 <p class="p9"><span class="Apple-tab-span">     </span></p>
  70 <p class="p12"><span class="s4"><span class="Apple-tab-span">   </span></span><span class="s3">IdentitySet</span><span class="s4">[</span>'abc'<span class="s4">, </span>'def'<span class="s4">, </span>'ghi'<span class="s4">].add(</span>'jkl'<span class="s4">);</span></p>
  71 <p class="p2"><br></p>
  72 <p class="p2"><br></p>
  73 <p class="p2"><br></p>
  74 <p class="p1"><b>remove(anObject)</b></p>
  75 <p class="p2"><br></p>
  76 <p class="p1"><span class="Apple-tab-span">     </span>Remove anObject from the IdentitySet.</p>
  77 <p class="p2"><br></p>
  78 <p class="p8"><span class="Apple-tab-span">     </span><span class="s3">IdentitySet</span>[1, 2, 3].remove(3);</p>
  79 <p class="p6"><br></p>
  80 <p class="p13"><br></p>
  81 <p class="p5"><b>Iteration:</b></p>
  82 <p class="p2"><br></p>
  83 <p class="p1"><b>do(function)</b></p>
  84 <p class="p2"><br></p>
  85 <p class="p1"><span class="Apple-tab-span">     </span>Evaluates function for each item in the IdentitySet.<span class="Apple-converted-space">  </span>You must not depend on the order of items.</p>
  86 <p class="p1"><span class="Apple-tab-span">     </span>The function is passed two arguments, the item and an integer index.</p>
  87 <p class="p2"><br></p>
  88 <p class="p8"><span class="Apple-tab-span">     </span><span class="s3">IdentitySet</span>[1, 2, 3, 300].do { <span class="s3">|item, i|</span> item.postln };</p>
  89 <p class="p2"><br></p>
  90 <p class="p4"><br></p>
  91 <p class="p5"><b>Finding an element:</b></p>
  92 <p class="p2"><br></p>
  93 <p class="p1"><b>findMatch(item)</b></p>
  94 <p class="p2"><span class="Apple-tab-span">     </span></p>
  95 <p class="p1"><span class="Apple-tab-span">     </span>Returns item if it is in the collection, otherwise returns nil.</p>
  96 <p class="p2"><span class="Apple-tab-span">     </span></p>
  97 <p class="p8"><span class="s6"><span class="Apple-tab-span">    </span></span>a = <span class="s3">IdentitySet</span>[1, 2, 3, 300];</p>
  98 <p class="p8"><span class="Apple-tab-span">     </span>a.findMatch(1);</p>
  99 <p class="p8"><span class="Apple-tab-span">     </span>a.findMatch(1.5);</p>
 100 <p class="p2"><br></p>
 101 <p class="p2"><br></p>
 102 <p class="p1">This is fairly efficient. compare the following benchmarks:</p>
 103 <p class="p2"><br></p>
 104 <p class="p10">// comparison of array indexing and identity set lookup</p>
 105 <p class="p8">(</p>
 106 <p class="p14">f = { <span class="s7">|n=4|</span></p>
 107 <p class="p14"><span class="Apple-tab-span">    </span><span class="s7">var</span> x, y, i;</p>
 108 <p class="p14"><span class="Apple-tab-span">    </span>x = (0..n);</p>
 109 <p class="p14"><span class="Apple-tab-span">    </span>y = x.as(<span class="s7">IdentitySet</span>);</p>
 110 <p class="p14"><span class="Apple-tab-span">    </span>i = x.choose;</p>
 111 <p class="p14"><span class="Apple-tab-span">    </span>bench { 100.do { x[i] } };</p>
 112 <p class="p14"><span class="Apple-tab-span">    </span>bench { 100.do { y.scanFor(i) } };</p>
 113 <p class="p14">}</p>
 114 <p class="p8">);</p>
 115 <p class="p9"><br></p>
 116 <p class="p8">f.(4)</p>
 117 <p class="p8">f.(8)</p>
 118 <p class="p8">f.(100)</p>
 119 <p class="p8">f.(10000)</p>
 120 <p class="p2"><br></p>
 121 <p class="p2"><br></p>
 122 <p class="p10">// you can use IdentitySet to efficiently remove identical duplicates from an array:</p>
 123 <p class="p9"><br></p>
 124 <p class="p8">(</p>
 125 <p class="p8"><span class="s3">var</span> e, f, g, h;</p>
 126 <p class="p11"><span class="s4">e = </span>"such"<span class="s4">; f = </span>"fallacy"<span class="s4">; g = </span>"is"<span class="s4">; h = </span>"common"<span class="s4">;</span></p>
 127 <p class="p8">a = [e, e, f, g, e, h, e];</p>
 128 <p class="p8">);</p>
 129 <p class="p10"><span class="s4">a.as(</span><span class="s3">IdentitySet</span><span class="s4">);<span class="Apple-tab-span"> </span></span>// convert to set</p>
 130 <p class="p10"><span class="s4">a.as(</span><span class="s3">Set</span><span class="s4">).as(</span><span class="s3">Array</span><span class="s4">); </span>// and convert back</p>
 131 <p class="p2"><br></p>
 132 <p class="p10">// note that the following behaves differently:</p>
 133 <p class="p11"><span class="s4">a = [ </span>"such"<span class="s4">, </span>"such"<span class="s4">, </span>"fallacy"<span class="s4">, </span>"is"<span class="s4">, </span>"such"<span class="s4">, </span>"common"<span class="s4">, </span>"such"<span class="s4"> ]</span></p>
 134 <p class="p10"><span class="s4">a.as(</span><span class="s3">IdentitySet</span><span class="s4">);<span class="Apple-tab-span"> </span></span>// convert to set. All elements are still here.<span class="Apple-converted-space"> </span></p>
 135 <p class="p10"><span class="Apple-tab-span">    </span><span class="Apple-tab-span">    </span><span class="Apple-tab-span">    </span><span class="Apple-tab-span">    </span>// Different strings may look the same, but be different objects.<span class="Apple-converted-space"> </span></p>
 136 <p class="p15"><br></p>
 137 <p class="p10">// To remove equals in stead of identicals, use Set:</p>
 138 <p class="p8">a.as(<span class="s3">Set</span>);</p>
 139 <p class="p9"><br></p>
 140 <p class="p9"><br></p>
 141 </body>
 142 </html>