title: Unique array values with callback
body: <p>SO,</p>
  
  <p><strong>Problem</strong></p>
  
  <p><em>First case</em></p>
  
  <p>I have an array with some values - for start, let them all be strings (or can be plainly treated as strings). Example:</p>
  
  <pre><code>$rgData = ['foo', 'feo', 'bar', 'baz', 'bee'];
  </code></pre>
  
  <p>Now, I want to create unique array from this, where <a href="http://en.wikipedia.org/wiki/Levenshtein_distance" rel="nofollow">Levenshtein distance</a> between two items is less than 2. I.e. items <code>$x</code> and <code>$y</code> are treated as equal if <code>levenshtein($x, $y) &lt; 2</code>. For example, <code>foo</code> and <code>feo</code> are equal, and also <code>bar</code> and <code>baz</code> - but not <code>bar</code> and <code>bee</code>.</p>
  
  <p><em>Second case</em></p>
  
  <p>I have an array with points coordinates <code>[x, y]</code> each, for example:</p>
  
  <pre><code>$rgData = [[0, 0.1], [-5, 4.5], [0, 0.5], [-5.5, 4.5]];
  </code></pre>
  
  <p>Now, I want to create unique array from this, where distance between two points is less than 1. I.e. points <code>$x</code> and <code>$y</code> are treated as equal if <code>pow((pow($x[0]-$y[0], 2) + pow($x[1]-$y[1],2)), 0.5)&lt;1</code></p>
  
  <p>It's obvious that both cases can be resolved via some function, which will be similar to standard PHP <a href="http://php.net/manual/en/function.array-unique.php" rel="nofollow">array_unique()</a> - but which accepts comparison function for check if items are equal. My question is about that function.</p>
  
  <p><strong>My approach</strong></p>
  
  <p>Now, I have the easiest solution for this with function:</p>
  
  <pre><code>function array_uunique($rgData, $fnCompare=null)
  {
      if(!isset($fnCompare))
      {
          return array_unique($rgData);
      }
      if(!is_callable($fnCompare))
      {
          return null;
      }
      if(!count($rgData))
      {
          return array();
      }
      $rgResult = array();
      foreach($rgData as $mItem)
      {
          foreach($rgResult as $mTest)
          {
             if(!call_user_func_array($fnCompare, [$mItem, $mTest]))
             {
                continue 2;
             }
          }
          $rgResult[]=$mItem;
      }
      return $rgResult;
  }
  </code></pre>
  
  <p>-it accepts callback as a second argument, and returns elements which are <em>not equal</em> with this comparison rule, i.e. for levenshtein the described result will be:</p>
  
  <pre><code>$rgResult = array_uunique(['foo', 'feo', 'bar', 'baz', 'bee'], function($x, $y)
  {
     return levenshtein($x, $y)&gt;1; //or !levenshtein($x, $y)&lt;2
  });
  </code></pre>
  
  <p>-this will result in</p>
  
  <pre>
  array(3) {
    [0]=>
    string(3) "foo"
    [1]=>
    string(3) "bar"
    [2]=>
    string(3) "bee"
  }
  </pre>
  
  <p>-you can use <a href="http://3v4l.org/Bj1i4" rel="nofollow">this fiddle</a> to test that.</p>
  
  <p><strong>Specifics</strong></p>
  
  <p>As mentioned above, this is the <em>easiest</em> way, but it contains 2 nested dependent cycles inside. Therefore, the complexity of such construct will be <code>O(N^2)</code> - which is sad - and will not work for me, especially if comparison function operation costs much - since I'll have big amount of elements in data array (~1E5..1E6 at least). </p>
  
  <p>And my question is - how to improve this? May be there is another good algorithm at all? Or may be my code can be improved somehow? </p>
  
  <p><em>update</em> (based on good comment below): I'm aware that in common case, such problem upcomes to a <a href="http://en.wikipedia.org/wiki/Transitive_relation" rel="nofollow">transitive function</a> problem, i.e. <code>xFy = yFz =&gt; xFz</code> - for example, <code>levenshtein()</code> is not transitive. So, entire result will be dependent from at least items order (but not only from it) in <em>common case</em> - and it is not a problem for me now since I'm sure about my data order and content (or, at least, it's not a matter if <code>bar</code> or <code>baz</code> will be returned by <code>levenshtein</code> comparison). So, my goal is to minimize count of comparisons (so is comparison function transitive or not changes nothing, I think, since I want to optimize or even recreate comparison algorithm itself)</p>