1 /**
  2  * verify if obj has property of key
  3  * @param {Objects} obj
  4  * @param {string} key
  5  */
  6 var hasKey = function(obj , key) {
  7     if(obj.hasOwnProperty(key))
  8         return true;
  9     return false;
 10 }
 11 
 12 //-------------------------------------------------------------------------------
 13 
 14 /**
 15  * compare arr[k1]+arr[k2] + ...arr[ki]  with keyvalues[k1] + ...keyvalues[ki]
 16  * @param {Array<key,value>}
 17  */
 18 var compare = function(array , keyvalues) {
 19     var temparray = "";
 20     var tempkeyvalues = "";
 21     var keys = Object.getOwnPropertyNames(keyvalues);
 22 
 23     keys.forEach(function(key){
 24         if(!array.hasOwnProperty(key)) {
 25             array[key] = "";
 26         }
 27         temparray += array[key];
 28         tempkeyvalues += keyvalues[key];
 29     });
 30     
 31     if(temparray == tempkeyvalues) 
 32         return 0;
 33     if(temparray > tempkeyvalues)
 34         return 1;
 35     if(temparray < tempkeyvalues)
 36         return -1;    
 37 }
 38 
 39 //-------------------------------------------------------------------------------
 40 
 41 /**
 42  * sort the array with keyvalues
 43  * @param array
 44  * @param keyvalues
 45  */
 46 var Sort = function(arr , keyvalues) {
 47     var keys = Object.getOwnPropertyNames(keyvalues);
 48     quickSort(arr , 0 , arr.length-1 , keys);
 49 } ;
 50 
 51 //-------------------------------------------------------------------------------
 52 /**
 53  * verify if obj[key] == keyvalues[key] when key in keyvalues
 54  * @param obj
 55  * @param keyvalues
 56  */
 57 
 58 var isMatch = function(obj , keyvalues) {
 59     var keys = Object.getOwnPropertyNames(keyvalues);
 60     var flag = true;
 61 
 62     for(var i = 0; i < keys.length; i++) {
 63         if((!hasKey(obj , keys[i])) || obj[keys[i]] != keyvalues[keys[i]]) {
 64             flag = false;
 65             break;
 66         }
 67     }
 68     return flag;    
 69 }
 70 
 71 //-------------------------------------------------------------------------------
 72 /**
 73  * use quick sort
 74  * @param arr
 75  * @param left
 76  * @param right
 77  * @param keys 
 78  */
 79 
 80 var quickSort = function (arr , left , right , keys ) {
 81     if(left < right) {
 82         var pivotIndex = Math.floor((right+left)/2);
 83         var pivotNewIndex = partition(arr , left , right , pivotIndex , keys);
 84 
 85         quickSort(arr , left , pivotNewIndex , keys );
 86         quickSort(arr , pivotNewIndex+1 , right , keys );
 87     }
 88 };
 89 
 90 //-------------------------------------------------------------------------------
 91 
 92 var partition = function (arr , left , right , pivotIndex , keys) {
 93 
 94     var pivotValue="";
 95 
 96     keys.forEach(function(key) {
 97         if(!hasKey(arr[pivotIndex] , key)) {
 98             arr[pivotIndex][key] = "";
 99         }
100         pivotValue += arr[pivotIndex][key];
101     });
102 
103     // swap arr[right] - arr[pivotIndex]
104     var temp1 = arr[pivotIndex];
105     arr[pivotIndex] = arr[right];
106     arr[right] = temp1;
107     // swap(arr[right] , arr[pivotIndex]);
108 
109     var storeIndex = left;
110 
111     for(i = left; i <= right -1; i++) {
112         var arrtemp = "";
113         keys.forEach(function(key){
114             if(!hasKey(arr[i] , key)) {
115                 arr[i][key] = "";
116             }
117             arrtemp += arr[i][key];
118         })
119 
120         if(arrtemp < pivotValue) {
121             // swap(arr[i] , arr[storeIndex]);
122             var temp2 = arr[i];
123             arr[i] = arr[storeIndex];
124             arr[storeIndex] = temp2;
125             storeIndex++;
126         }
127     }
128     // swap(arr[storeIndex]  , arr[right]);
129     var temp3 = arr[storeIndex];
130     arr[storeIndex] = arr[right];
131     arr[right] = temp3;
132 //    console.log(arr);
133     return storeIndex;
134 };
135 
136 //-------------------------------------------------------------------------------
137 /**
138  * search arr[i] when arr[i][key] = keyvalues[key] and key in keyvalues
139  * @param arr
140  * @param keyvalues
141  */
142 var Search = function(arr , keyvalues) {
143     var result =  BinarySearch(arr , 0 , arr.length-1 , keyvalues);
144     return result;
145 }
146 
147 
148 //-------------------------------------------------------------------------------
149 /**
150  * use binary search
151  */
152 var BinarySearch = function(arr , low , high , keyvalues) {
153     var mid = Math.floor((low + high) / 2);
154 
155     if(low > high){
156         return null;
157     }else {
158         var compareresult = compare(arr[mid] , keyvalues);
159 
160         if(compareresult == 0) {
161             if(isMatch(arr[mid] , keyvalues)){
162                 return arr[mid];
163             }
164             var ltemp = mid - 1;
165             var rtemp = mid + 1;
166             
167             while((ltemp >=0) && (compare(arr[ltemp] , keyvalues) == 0)) {
168                 if(isMatch(arr[ltemp] ,keyvalues )){
169                     return arr[ltemp];
170                 } 
171                 ltemp--;
172             }
173             while((rtemp <= high) && (compare(arr[rtemp] , keyvalues) == 0)) {
174                 if(isMatch(arr[rtemp] , keyvalues)) {
175                     return arr[rtemp];
176                 }
177                 rtemp++;
178             }
179             
180             return null;
181             
182         } else if(compareresult > 0) {
183             var m = BinarySearch(arr, low , mid-1 , keyvalues);
184             return m;    
185         } else{
186             var m = BinarySearch(arr , mid+1 , high , keyvalues);
187             return m;
188         }
189     }