Source Code Cross Referenced for IndexNode.java in  » Search-Engine » Jofti » com » jofti » btree » 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 » Search Engine » Jofti » com.jofti.btree 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


001:        /*
002:         * IndexNode.java
003:         *  Copyright (C) <2005>  <Steve Woodcock>
004:         *  
005:
006:         * Created on 09 May 2003, 15:13
007:         */
008:        package com.jofti.btree;
009:
010:        /**
011:         * <p>
012:         * The internal nodes in the BTree. These nodes do not contain any data - they are simply pointers to lower level 
013:         * index nodes or leaf nodes.</p>
014:         * <p>
015:         * Each node follows the pattern of an indexnode which is an array of sorted pointers to a lower level index or leaf node. Each entry 
016:         * in the array contains the largest value in the subtree under the pointer. The Node itself in its right value contains the largest 
017:         * entry in its array.
018:         * </p>
019:         *
020:         * @author  Steve Woodcock (steve@jofti.com)<br>
021:         * @version 1.12<br>
022:         * 
023:         */
024:        class IndexNode extends Node {
025:
026:            private IndexNodeEntry parentKey = null;
027:
028:            protected Object[] keyList = new Object[BTree.getMaxNodeSize() + 1];
029:
030:            private Comparable rightValue = null;
031:            // b+ linked list metaphor to traverse sequentially
032:
033:            private NodeLink nextNode = null;
034:
035:            private boolean deleted = false;
036:
037:            /**
038:             * @return  if the node has been deleted.
039:             */
040:            public boolean isDeleted() {
041:                return deleted;
042:            }
043:
044:            /**
045:             * @param deleted Sets the node to deleted if true.
046:             */
047:            public void setDeleted(boolean deleted) {
048:                this .deleted = deleted;
049:            }
050:
051:            /** Creates a new instance of IndexNode */
052:            protected IndexNode() {
053:            }
054:
055:            /**
056:             * Returns the node entry where the entry should be. This is achieved by comparing the right values 
057:             * of the node entries in the node.<p>
058:             * 
059:             * 
060:             * @param entry the value to find.
061:             * @return The node in this index node that the value should be in (or in a subtreee from that node).
062:             */
063:            public Node getContainingNode(Comparable entry) {
064:
065:                if (entryNumber == 0) {
066:                    return null;
067:                }
068:
069:                // look through list and see if we have a match
070:
071:                return indexedBinaryRetrieve(keyList, entry);
072:
073:            }
074:
075:            protected Node indexedBinaryRetrieve(Object[] list1, Object obj) {
076:                int i = 0;
077:                IndexNodeEntry entry = null;
078:                int size = entryNumber;
079:                for (int j = size - 1; i <= j;) {
080:                    int k = i + j >> 1;
081:                    entry = (IndexNodeEntry) list1[k];
082:                    int l = entry.value.compareTo(obj);
083:                    if (l < 0) {
084:                        i = k + 1;
085:                    } else if (l > 0) {
086:                        j = k - 1;
087:                    } else {
088:                        return entry.getChildNode();
089:                    }
090:                }
091:
092:                i = -(i + 1);
093:
094:                if (-i == entryNumber) {
095:                    return entry.getChildNode();
096:                } else {
097:                    return ((IndexNodeEntry) list1[-i - 1]).getChildNode();
098:                }
099:
100:            }
101:
102:            protected int indexedBinaryLocate(Object[] list1, Object obj) {
103:
104:                int low = 0;
105:                int high = entryNumber - 1;
106:
107:                IndexNodeEntry entry = null;
108:                while (low <= high) {
109:                    int mid = (low + high) >> 1;
110:
111:                    entry = (IndexNodeEntry) list1[mid];
112:                    int cmp = entry.compareTo(obj);
113:
114:                    if (cmp < 0)
115:                        low = mid + 1;
116:                    else if (cmp > 0)
117:                        high = mid - 1;
118:                    else
119:                        return mid; // key found
120:                }
121:                return -(low + 1); // key not found
122:
123:            }
124:
125:            /* (non-Javadoc)
126:             * @see com.jofti.btree.INode#insertEntry(com.jofti.btree.NodeEntry)
127:             */
128:            public Object[] insertEntry(NodeEntry key) {
129:
130:                //lets reset the next node if it is deleted
131:                resetNextNode();
132:
133:                IndexNodeEntry entry = (IndexNodeEntry) key;
134:
135:                // if there are no entries then set it in
136:                if (entryNumber == 0) {
137:                    keyList[0] = entry;
138:                    entry.setContainingNode(this );
139:                    entryNumber++;
140:                    rightValue = entry.getValue();
141:                    return keyList;
142:
143:                } else {
144:                    //loop through entries to find right place
145:                    // we do not use a binary search here as we want to do different things
146:                    for (int i = 0; i < entryNumber; i++) {
147:                        IndexNodeEntry listEntry = (IndexNodeEntry) keyList[i];
148:                        // the current node is bigger so insert here
149:
150:                        // is it bigger than a value in the list
151:                        int comparison = listEntry.getValue().compareTo(
152:                                entry.getValue());
153:                        if (comparison > 0) {
154:
155:                            System.arraycopy(keyList, i, keyList, i + 1,
156:                                    entryNumber - i);
157:                            keyList[i] = entry;
158:
159:                            entry.setContainingNode(this );
160:                            entryNumber++;
161:                            return keyList;
162:                            // is it equal - which means we will need to rest the conflicting value to make sure
163:                            // there is no problem - should be as the result of a split
164:                        } else if (comparison == 0) {
165:                            // this is a split node that has a key value that is equal
166:                            listEntry.updateValue();
167:                            if (i == entryNumber - 1) {
168:                                keyList[entryNumber] = entry;
169:                                rightValue = entry.getValue();
170:
171:                            } else {
172:                                int inner = i + 1;
173:                                System.arraycopy(keyList, inner, keyList,
174:                                        inner + 1, entryNumber - inner);
175:                                keyList[inner] = entry;
176:                            }
177:                            entry.setContainingNode(this );
178:                            entryNumber++;
179:                            return keyList;
180:                        }
181:                    }
182:
183:                    keyList[entryNumber] = entry;
184:                    rightValue = entry.getValue();
185:                    entry.setContainingNode(this );
186:                    entryNumber++;
187:                    return keyList;
188:                }
189:
190:            }
191:
192:            private void resetNextNode() {
193:                if (nextNode != null && nextNode.getNode() != null
194:                        && nextNode.getNode().isDeleted()) {
195:                    nextNode = nextNode.getNode().getLinkNode();
196:                }
197:            }
198:
199:            /**
200:             * updates the key right value for the node entry passed in.<p> 
201:             * 
202:             * @param key - the key for the entry to update.<br>
203:             * @return - true of the right value for the entire node was updated - false if the node entry was 
204:             * not the right most entry.
205:             */
206:            public boolean updateEntry(NodeEntry key) {
207:
208:                resetNextNode();
209:                IndexNodeEntry entry = (IndexNodeEntry) key;
210:
211:                if (entryNumber == 0) {
212:
213:                    return false;
214:
215:                } else {
216:                    int length = entryNumber;
217:                    for (int i = 0; i < length; i++) {
218:                        IndexNodeEntry listEntry = (IndexNodeEntry) keyList[i];
219:                        if (listEntry.getValue().equals(entry.getValue())) {
220:                            // this is a split node that has a key value that is equal
221:                            listEntry.updateValue();
222:                            if (i == length - 1) {
223:                                rightValue = listEntry.getValue();
224:                            }
225:                            return true;
226:                        }
227:                    }
228:                    return false;
229:                }
230:
231:            }
232:
233:            /**
234:             * Sets the keylist for the node entries.<p>
235:             * 
236:             * @param keys - the new entry list for the node.
237:             */
238:            public void setKeyList(Object[] temp) {
239:
240:                for (int i = 0; i < entryNumber; i++) {
241:                    IndexNodeEntry entry = (IndexNodeEntry) temp[i];
242:                    entry.setContainingNode(this );
243:                    keyList[i] = entry;
244:                }
245:
246:            }
247:
248:            /* (non-Javadoc)
249:             * @see com.jofti.btree.INode#isEmpty()
250:             */
251:            public boolean isEmpty() {
252:                if (entryNumber == 0) {
253:                    return true;
254:                }
255:                return false;
256:            }
257:
258:            /* (non-Javadoc)
259:             * @see com.jofti.btree.INode#getRightValue()
260:             */
261:            public Comparable getRightValue() {
262:                return rightValue;
263:            }
264:
265:            IndexNodeEntry getParentKey() {
266:                return parentKey;
267:            }
268:
269:            public String toString() {
270:                StringBuffer buf = new StringBuffer();
271:                buf.append("  IndexNode{");
272:
273:                buf.append(" rightValue:" + getRightValue() + "}");
274:                return buf.toString();
275:            }
276:
277:            public boolean isUnderFull() {
278:                if (entryNumber < BTree.getMaxNodeSize()) {
279:                    return true;
280:                }
281:                return false;
282:            }
283:
284:            /** Setter for property parentNode.
285:             * @param parentNode New value of property parentNode.
286:             *
287:             *
288:             */
289:            void setParentKey(IndexNodeEntry parentKey) {
290:                this .parentKey = parentKey;
291:            }
292:
293:            /* (non-Javadoc)
294:             * @see com.jofti.btree.INode#deleteEntry(com.jofti.btree.NodeEntry)
295:             */
296:            public boolean deleteEntry(NodeEntry entry) {
297:
298:                resetNextNode();
299:
300:                int location = indexedBinaryLocate(keyList, entry);
301:
302:                if (location >= 0) {
303:                    // we need to remove the entry
304:
305:                    int numMoved = entryNumber - location - 1;
306:                    if (numMoved > 0)
307:                        System.arraycopy(keyList, location + 1, keyList,
308:                                location, numMoved);
309:                    keyList[--entryNumber] = null; // Let gc do its work
310:
311:                    if (entryNumber == 0) {
312:                        rightValue = BTree.MIN_RIGHT_VALUE;
313:                    } else {
314:                        ((IndexNodeEntry) keyList[entryNumber - 1])
315:                                .updateValue();
316:                        setRightValue(((IndexNodeEntry) keyList[entryNumber - 1])
317:                                .getValue());
318:                    }
319:                    return true;
320:                }
321:                return false;
322:
323:            }
324:
325:            /* (non-Javadoc)
326:             * @see com.jofti.btree.INode#splitNode()
327:             */
328:            public Node splitNode(Object[] entries) {
329:                // first insert the entry
330:
331:                Object[] entriesList = split(entries, entryNumber);
332:
333:                Node newNode = NodeFactory.getInstance().createIndexNode();
334:
335:                Comparable currentRight = rightValue;
336:
337:                //set up new node
338:                EntrySplitWrapper newEntries = ((EntrySplitWrapper) entriesList[1]);
339:
340:                newNode.entryNumber = newEntries.size;
341:                newNode.setEntries((Object[]) newEntries.entries);
342:
343:                newNode.setRightValue(currentRight);
344:                newNode.setLinkNode(getLinkNode());
345:
346:                //			replace values in current node
347:
348:                EntrySplitWrapper replacements = (EntrySplitWrapper) entriesList[0];
349:
350:                keyList = (Object[]) replacements.entries;
351:                entryNumber = replacements.size;
352:                setRightValue(((NodeEntry) keyList[entryNumber - 1]).getValue());
353:
354:                return newNode;
355:
356:            }
357:
358:            /* (non-Javadoc)
359:             * @see com.jofti.btree.INode#getEntryNumber()
360:             */
361:            public int getEntryNumber() {
362:                return entryNumber;
363:            }
364:
365:            /* (non-Javadoc)
366:             * @see com.jofti.btree.INode#getEntries()
367:             */
368:            public Object[] getEntries() {
369:
370:                return keyList;
371:            }
372:
373:            /* (non-Javadoc)
374:             * @see com.jofti.btree.Node#setRightValue(java.lang.Comparable)
375:             */
376:            public void setRightValue(Comparable value) {
377:                this .rightValue = value;
378:
379:            }
380:
381:            /* (non-Javadoc)
382:             * @see com.jofti.btree.Node#split()
383:             */
384:
385:            /* (non-Javadoc)
386:             * @see com.jofti.btree.Node#setEntries(java.util.List)
387:             */
388:            public void setEntries(Object[] entries) {
389:                setKeyList(entries);
390:
391:            }
392:
393:            /* (non-Javadoc)
394:             * @see com.jofti.btree.Node#getLinkNode()
395:             */
396:            public NodeLink getLinkNode() {
397:
398:                return nextNode;
399:            }
400:
401:            /* (non-Javadoc)
402:             * @see com.jofti.btree.Node#setLinkNode(com.jofti.btree.Node)
403:             */
404:            public void setLinkNode(NodeLink node) {
405:                this .nextNode = node;
406:
407:            }
408:
409:            /** 
410:             * This method checks to see if the value should be contained in the leaf nodes that are 
411:             * children of this indexNode (or children of its children). It does not check if the actual 
412:             * value is in the sub tree- rather it checks if its values are larger than this value.<p>
413:             * 
414:             * @param value
415:             * 
416:             * @return true if the node has a larger value in it - false otherwise.
417:             */
418:            public boolean contains(Comparable value) {
419:                if (entryNumber == 0 || value == null) {
420:                    return false;
421:                }
422:
423:                if (value instanceof  MinComparableValue) {
424:                    return true;
425:                }
426:                return rightValue.compareTo(value) >= 0;
427:            }
428:
429:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.