# protoype

Protoype is a cool javascript framework very usefull for dynamic webapp creation; however, the uniq algorithm in prototype.js is rather slow for large sets, infact it is O(n2) (quadratic).

This happens because uniq does not expects a sorted array and thus all elements are compared to all elements in the array (the array.include does a foreach for each value). And secondly, the array.concat function ‘will yield a new, intermediary array every time it encounters a new value (a value that wasnâ€™t already in the result array)’.

 ```1 2 3 4 5 ``` ``` uniq: function() { return this.inject([], function(array, value) { return array.include(value) ? array : array.concat([value]); }); },```

## stl

If you look at the c++ stl (standard template libary), this problem is solved in O(n) (linear) time, so a solution is near: convert a little bit of c++ to javascript!

(Note: there is a jsstl available on the web, but it does not implement the algorithm part of the stl, only the containers & iterators …)

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 ``` ``` // TEMPLATE FUNCTION unique template inline _FwdIt unique(_FwdIt _First, _FwdIt _Last) { // remove each matching previous for (_FwdIt _Firstb; (_Firstb = _First) != _Last && ++_First != _Last; ) if (*_Firstb == *_First) { // copy down for (; ++_First != _Last; ) if (!(*_Firstb == *_First)) *++_Firstb = *_First; return (++_Firstb); } return (_Last); }```

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ``` ``` // Removes redundant elements from the array function unique_inplace(an_array) { var first = 0; var last = an_array.length; for(var firstb; (firstb = first) != last && ++first != last; ) { if(an_array[firstb] == an_array[first]) { for(; ++first != last; ) { if (!(an_array[firstb] == an_array[first])) { an_array[++firstb] = an_array[first]; } } ++firstb; an_array.length = firstb; return; } an_array.length = firstb; }```