sventon subversion web client - http://www.sventon.org
[show recent changes]
 
  Help
Rev: HEAD (53458) - http://anonsvn.icesoft.org/repo / bridge-support / patches / bridge-support-sf-12692 / src / main / javascript / hashtable.js
Show File - hashtable.js  [show properties]
spinner
1  /*
2   * Copyright 2004-2013 ICEsoft Technologies Canada Corp.
3   *
4   * Licensed under the Apache License, Version 2.0 (the "License");
5   * you may not use this file except in compliance with the
6   * License. You may obtain a copy of the License at
7   *
8   * http://www.apache.org/licenses/LICENSE-2.0
9   *
10   * Unless required by applicable law or agreed to in writing,
11   * software distributed under the License is distributed on an "AS
12   * IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
13   * express or implied. See the License for the specific language
14   * governing permissions and limitations under the License.
15   */
16 
17  var at = operator();
18  var putAt = operator();
19  var removeAt = operator();
20 
21  var HashTable;
22  var HashSet;
23 
24  (function() {
25      var removeInArray = Array.prototype.splice ? function(array, index) {
26          array.splice(index, 1);
27      } : function(array, index) {
28          if (index == array.length - 1) {
29              array.length = index;
30          } else {
31              var rightSlice = array.slice(index + 1);
32              array.length = index;
33              for (var i = 0, l = rightSlice.length; i < l; ++i) {
34                  array[index + i] = rightSlice[i];
35              }
36          }
37      };
38 
39      function atPrimitive(buckets, bucketCount, k, notFoundThunk) {
40          var index = hash(k) % bucketCount;
41          var bucket = buckets[index];
42          if (bucket) {
43              for (var i = 0, l = bucket.length; i < l; i++) {
44                  var entry = bucket[i];
45                  if (equal(entry.key, k)) {
46                      return entry.value;
47                  }
48              }
49              if (notFoundThunk) notFoundThunk();
50              return null;
51          } else {
52              if (notFoundThunk) notFoundThunk();
53              return null;
54          }
55      }
56 
57      function putAtPrimitive(buckets, bucketCount, k, v) {
58          var index = hash(k) % bucketCount;
59          var bucket = buckets[index];
60          if (bucket) {
61              for (var i = 0, l = bucket.length; i < l; i++) {
62                  var entry = bucket[i];
63                  if (equal(entry.key, k)) {
64                      var oldValue = entry.value;
65                      entry.value = v;
66                      return oldValue;
67                  }
68              }
69              bucket.push({ key:k, value: v });
70              return null;
71          } else {
72              bucket = [
73                  {
74                      key:k,
75                      value: v
76                  }
77              ];
78              buckets[index] = bucket;
79              return null;
80          }
81      }
82 
83      function removeAtPrimitive(buckets, bucketCount, k) {
84          var index = hash(k) % bucketCount;
85          var bucket = buckets[index];
86          if (bucket) {
87              for (var i = 0, l = bucket.length; i < l; i++) {
88                  var entry = bucket[i];
89                  if (equal(entry.key, k)) {
90                      removeInArray(bucket, i);
91                      if (bucket.length == 0) {
92                          removeInArray(buckets, index);
93                      }
94                      return entry.value;
95                  }
96              }
97              return null;
98          } else {
99              return null;
100          }
101      }
102 
103      function injectPrimitive(buckets, initialValue, iterator) {
104          var tally = initialValue;
105          for (var i = 0, lbs = buckets.length; i < lbs; i++) {
106              var bucket = buckets[i];
107              if (bucket) {
108                  for (var j = 0, lb = bucket.length; j < lb; j++) {
109                      var entry = bucket[j];
110                      if (entry) {
111                          tally = iterator(tally, entry.key, entry.value);
112                      }
113                  }
114              }
115          }
116 
117          return tally;
118      }
119 
120      var internalBuckets = operator();
121      var internalBucketCount = operator();
122 
123      HashTable = function() {
124          var buckets = [];
125          var bucketCount = 5000;
126 
127          return object(function(method) {
128              method(at, function(self, k, notFoundThunk) {
129                  return atPrimitive(buckets, bucketCount, k, notFoundThunk);
130              });
131 
132              method(putAt, function(self, k, v) {
133                  return putAtPrimitive(buckets, bucketCount, k, v);
134              });
135 
136              method(removeAt, function(self, k) {
137                  return removeAtPrimitive(buckets, bucketCount, k);
138              });
139 
140              method(each, function(iterator) {
141                  injectPrimitive(buckets, null, function(tally, k, v) {
142                      iterator(k, v);
143                  });
144              });
145          });
146      };
147 
148      HashSet = function(list) {
149          var buckets = [];
150          var bucketCount = 5000;
151          var present = new Object;
152 
153          if (list) {
154              each(list, function(k) {
155                  putAtPrimitive(buckets, bucketCount, k, present);
156              });
157          }
158 
159          return object(function(method) {
160              method(append, function(self, k) {
161                  putAtPrimitive(buckets, bucketCount, k, present);
162              });
163 
164              method(each, function(self, iterator) {
165                  injectPrimitive(buckets, null, function(t, k, v) {
166                      iterator(k);
167                  });
168              });
169 
170              method(contains, function(self, k) {
171                  return !!atPrimitive(buckets, bucketCount, k);
172              });
173 
174              method(complement, function(self, other) {
175                  var result = [];
176                  var c;
177                  try {
178                      var othersInternalBuckets = internalBuckets(other);
179                      var othersInternalBucketCount = internalBucketCount(other);
180                      c = function(items, k) {
181                          return !!atPrimitive(othersInternalBuckets, othersInternalBucketCount, k);
182                      };
183                  } catch (e) {
184                      c = contains;
185                  }
186 
187                  return injectPrimitive(buckets, result, function(tally, k, v) {
188                      if (!c(other, k)) {
189                          result.push(k);
190                      }
191                      return tally;
192                  });
193              });
194 
195              method(asString, function(self) {
196                  return 'HashSet[' + join(injectPrimitive(buckets, [], function(tally, k, v) {
197                      tally.push(k);
198                      return tally;
199                  }), ',') + ']';
200              });
201 
202              method(internalBuckets, function(self) {
203                  return buckets;
204              });
205 
206              method(internalBucketCount, function(self) {
207                  return bucketCount;
208              });
209          });
210      };
211  })();


feed icon

sventon 2.5.1