001: package org.drools.util;
002:
003: /*
004: * Copyright 2005 JBoss Inc
005: *
006: * Licensed under the Apache License, Version 2.0 (the "License");
007: * you may not use this file except in compliance with the License.
008: * You may obtain a copy of the License at
009: *
010: * http://www.apache.org/licenses/LICENSE-2.0
011: *
012: * Unless required by applicable law or agreed to in writing, software
013: * distributed under the License is distributed on an "AS IS" BASIS,
014: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015: * See the License for the specific language governing permissions and
016: * limitations under the License.
017: */
018:
019: import java.io.Serializable;
020: import java.util.Arrays;
021: import java.util.Collection;
022:
023: /**
024: *
025: * @author Mark Proctor
026: */
027: public class PrimitiveLongMap implements Serializable {
028: /**
029: *
030: */
031: private static final long serialVersionUID = 400L;
032:
033: private final static Object NULL = new Serializable() {
034:
035: /**
036: *
037: */
038: private static final long serialVersionUID = 400L;
039: };
040:
041: private final int indexIntervals;
042: private final int intervalShifts;
043: private final int midIntervalPoint;
044: private final int tableSize;
045: private final int shifts;
046: private final int doubleShifts;
047: private Page firstPage;
048: private Page lastPage;
049: private int lastPageId;
050: private long maxKey;
051: private Page[] pageIndex;
052: private int totalSize;
053:
054: public PrimitiveLongMap() {
055: this (32, 8);
056: }
057:
058: public PrimitiveLongMap(final int tableSize) {
059: this (tableSize, 8);
060: }
061:
062: public PrimitiveLongMap(final int tableSize,
063: final int indexIntervals) {
064: // determine number of shifts for intervals
065: int i = 1;
066: int size = 2;
067: while (size < indexIntervals) {
068: size <<= 1;
069: ++i;
070: }
071: this .indexIntervals = size;
072: this .intervalShifts = i;
073:
074: // determine number of shifts for tableSize
075: i = 1;
076: size = 2;
077: while (size < tableSize) {
078: size <<= 1;
079: ++i;
080: }
081: this .tableSize = size;
082: this .shifts = i;
083: this .doubleShifts = this .shifts << 1;
084:
085: // determine mid point of an interval
086: this .midIntervalPoint = ((this .tableSize << this .shifts) << this .intervalShifts) >> 1;
087:
088: this .lastPageId = 0;
089:
090: init();
091: }
092:
093: private void init() {
094: // instantiate the first page
095: // previous sibling of first page is null
096: // next sibling of last page is null
097: this .firstPage = new Page(null, this .lastPageId, this .tableSize);
098: this .maxKey = this .lastPageId + 1 << this .doubleShifts;
099: // create an index of one
100: this .pageIndex = new Page[] { this .firstPage };
101:
102: // our first page is also our last page
103: this .lastPage = this .firstPage;
104: }
105:
106: public void clear() {
107: init();
108: }
109:
110: public boolean isEmpty() {
111: return this .totalSize == 0;
112: }
113:
114: public Object put(final long key, Object value) {
115: if (key < 0) {
116: throw new IllegalArgumentException(
117: "-ve keys not supported: " + key);
118: }
119:
120: // NULL is a placeholder to show the key exists
121: // but contains a null value
122: if (value == null) {
123: value = PrimitiveLongMap.NULL;
124: }
125:
126: final Page page = findPage(key);
127:
128: final Object oldValue = page.put(key, value);
129:
130: if (oldValue == null) {
131: this .totalSize++;
132: }
133:
134: return oldValue;
135: }
136:
137: public Object remove(final long key) {
138: if (key > this .maxKey || key < 0) {
139: return null;
140: }
141:
142: final Page page = findPage(key);
143:
144: final Object oldValue = page.put(key, null);
145:
146: if (this .lastPageId != 0 && this .lastPage.isEmpty()) {
147: shrinkPages(this .lastPageId);
148: }
149:
150: if (oldValue != null) {
151: this .totalSize--;
152: }
153:
154: return oldValue;
155: }
156:
157: public Object get(final long key) {
158: if (key > this .maxKey || key < 0) {
159: return null;
160: }
161:
162: Object value = findPage(key).get(key);
163:
164: // NULL means the key exists, so return a real null
165: if (value == PrimitiveLongMap.NULL) {
166: value = null;
167: }
168: return value;
169: }
170:
171: /**
172: * gets the next populated key, after the given key position.
173: * @param key
174: * @return
175: */
176: public long getNext(long key) {
177: final int currentPageId = (int) key >> this .doubleShifts;
178: final int nextPageId = (int) (key + 1) >> this .doubleShifts;
179:
180: if (currentPageId != nextPageId) {
181: Page page = findPage(key + 1);
182: while (page.isEmpty()) {
183: page = page.getNextSibling();
184: }
185: key = this .doubleShifts << page.getPageId();
186: } else {
187: key += 1;
188: }
189:
190: while (!containsKey(key) && key <= this .maxKey) {
191: key++;
192: }
193:
194: if (key > this .maxKey) {
195: key -= 1;
196: }
197:
198: return key;
199: }
200:
201: public int size() {
202: return this .totalSize;
203: }
204:
205: public Collection values() {
206: final CompositeCollection collection = new CompositeCollection();
207: Page page = this .firstPage;
208:
209: while (page != null && page.getPageId() <= this .lastPageId) {
210: collection.addComposited(Arrays.asList(page.getValues()));
211: page = page.getNextSibling();
212: }
213: return collection;
214: }
215:
216: public boolean containsKey(final long key) {
217: if (key < 0) {
218: return false;
219: }
220:
221: return get(key) != null;
222: }
223:
224: /**
225: * Expand index to accomodate given pageId Create empty TopNodes
226: */
227: public Page expandPages(final int toPageId) {
228: for (int x = this .lastPageId; x < toPageId; x++) {
229: this .lastPage = new Page(this .lastPage, ++this .lastPageId,
230: this .tableSize);
231: // index interval, so expand index
232: if (this .lastPage.getPageId() % this .indexIntervals == 0) {
233: final int newSize = this .pageIndex.length + 1;
234: resizeIndex(newSize);
235: this .pageIndex[newSize - 1] = this .lastPage;
236: }
237: }
238: this .maxKey = (this .lastPageId + 1 << this .doubleShifts) - 1;
239: return this .lastPage;
240: }
241:
242: /**
243: * Shrink index to accomodate given pageId
244: */
245: public void shrinkPages(final int toPageId) {
246: for (int x = this .lastPageId; x >= toPageId; x--) {
247: // last page is on index so shrink index
248: if ((this .lastPageId) % this .indexIntervals == 0
249: && this .lastPageId != 0) {
250: resizeIndex(this .pageIndex.length - 1);
251: }
252:
253: final Page page = this .lastPage.getPreviousSibling();
254: page.setNextSibling(null);
255: this .lastPage.clear();
256: this .lastPage = page;
257: this .lastPageId = page.getPageId();
258:
259: }
260: }
261:
262: public void resizeIndex(final int newSize) {
263: final Page[] newIndex = new Page[newSize];
264: System
265: .arraycopy(
266: this .pageIndex,
267: 0,
268: newIndex,
269: 0,
270: (newSize > this .pageIndex.length) ? this .pageIndex.length
271: : newSize);
272: this .pageIndex = newIndex;
273: }
274:
275: private Page findPage(final long key) {
276: // determine Page
277: final int pageId = (int) key >> this .doubleShifts;
278: Page page;
279:
280: // if pageId is lastNodeId use lastNode reference
281: if (pageId == this .lastPageId) {
282: page = this .lastPage;
283: }
284: // if pageId is zero use first page reference
285: else if (pageId == 0) {
286: page = this .firstPage;
287: }
288: // if pageId is greater than lastTopNodeId need to expand
289: else if (pageId > this .lastPageId) {
290: page = expandPages(pageId);
291: } else {
292: // determine offset
293: final int offset = pageId >> this .intervalShifts;
294: // are we before or after the halfway point of an index interval
295: if ((offset != (this .pageIndex.length - 1))
296: && ((key - (offset << this .intervalShifts << this .doubleShifts)) > this .midIntervalPoint)) {
297: // after so go to next node index and go backwards
298: page = this .pageIndex[offset + 1];
299: while (page.getPageId() != pageId) {
300: page = page.getPreviousSibling();
301: }
302: } else {
303: // before so go to node index and go forwards
304: page = this .pageIndex[offset];
305: while (page.getPageId() != pageId) {
306: page = page.getNextSibling();
307: }
308: }
309: }
310:
311: return page;
312: }
313:
314: private static class Page implements Serializable {
315: /**
316: *
317: */
318: private static final long serialVersionUID = 400L;
319: private final int pageSize;
320: private final int pageId;
321: private final int shifts;
322: private final int tableSize;
323: private Page nextSibling;
324: private Page previousSibling;
325: private Object[][] tables;
326: private int filledSlots;
327:
328: Page(final Page previousSibling, final int pageId,
329: final int tableSize) {
330: // determine number of shifts
331: int i = 1;
332: int size = 2;
333: while (size < tableSize) {
334: size <<= 1;
335: ++i;
336: }
337: // make sure table size is valid
338: this .tableSize = size;
339: this .shifts = i;
340:
341: // create bi-directional link
342: this .previousSibling = previousSibling;
343: if (this .previousSibling != null) {
344: this .previousSibling.setNextSibling(this );
345: }
346: this .pageId = pageId;
347: this .pageSize = tableSize << this .shifts;
348: }
349:
350: public int getPageId() {
351: return this .pageId;
352: }
353:
354: void setNextSibling(final Page nextSibling) {
355: this .nextSibling = nextSibling;
356: }
357:
358: public Page getNextSibling() {
359: return this .nextSibling;
360: }
361:
362: void setPreviousSibling(final Page previousSibling) {
363: this .previousSibling = previousSibling;
364: }
365:
366: public Page getPreviousSibling() {
367: return this .previousSibling;
368: }
369:
370: public Object get(long key) {
371: if (this .tables == null) {
372: return null;
373: }
374: // normalise key
375: key -= this .pageSize * this .pageId;
376:
377: // determine table
378: final int table = (int) key >> this .shifts;
379:
380: // determine offset
381: final int offset = table << this .shifts;
382:
383: // tables[table][slot]
384: return this .tables[table][(int) key - offset];
385: }
386:
387: public Object put(long key, final Object newValue) {
388: if (this .tables == null) {
389: // initiate tree;
390: this .tables = new Object[this .tableSize][this .tableSize];
391: }
392:
393: // normalise key
394: key -= this .pageSize * this .pageId;
395:
396: // determine table
397: final int table = (int) key >> this .shifts;
398:
399: // determine offset
400: final int offset = table << this .shifts;
401:
402: // determine slot
403: final int slot = (int) key - offset;
404:
405: // get old value
406: final Object oldValue = this .tables[table][slot];
407: this .tables[table][slot] = newValue;
408:
409: // update number of empty cells for TopNode
410: if (oldValue == null && newValue != null) {
411: this .filledSlots++;
412: } else if (oldValue != null && newValue == null) {
413: this .filledSlots--;
414: }
415:
416: // if this page contains no values then null the array
417: // to allow it to be garbage collected
418: if (this .filledSlots == 0) {
419: this .tables = null;
420: }
421:
422: return oldValue;
423: }
424:
425: Object[][] getTables() {
426: return this .tables;
427: }
428:
429: Object[] getValues() {
430: final Object[] values = new Object[this .filledSlots];
431: if (values.length == 0) {
432: return values;
433: }
434: int x = 0;
435: Object value;
436: for (int i = 0; i < this .tableSize; i++) {
437: for (int j = 0; j < this .tableSize; j++) {
438: value = this .tables[i][j];
439: if (value != null) {
440: // swap NULL out placeholder
441: // Also filter out InitialFact
442: if (value == PrimitiveLongMap.NULL) {
443: value = null;
444: }
445: values[x] = value;
446: x++;
447: }
448: }
449: }
450: return values;
451: }
452:
453: public boolean isEmpty() {
454: return this .filledSlots == 0;
455: }
456:
457: void clear() {
458: this.previousSibling = null;
459: this.nextSibling = null;
460: this.tables = null;
461: }
462: }
463: }
|