Source Code Cross Referenced for PrimitiveLongMap.java in  » Rule-Engine » drolls-Rule-Engine » org » drools » util » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Rule Engine » drolls Rule Engine » org.drools.util 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


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:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.