1 /* DBKBTreeNode.h 2 * 3 * Copyright (C) 2005-2010 Free Software Foundation, Inc. 4 * 5 * Author: Enrico Sersale <enrico@imago.ro> 6 * Date: June 2005 7 * 8 * This file is part of the GNUstep GWorkspace application 9 * 10 * This program is free software; you can redistribute it and/or modify 11 * it under the terms of the GNU General Public License as published by 12 * the Free Software Foundation; either version 2 of the License, or 13 * (at your option) any later version. 14 * 15 * This program is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU General Public License for more details. 19 * 20 * You should have received a copy of the GNU General Public License 21 * along with this program; if not, write to the Free Software 22 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111 USA. 23 */ 24 25 #ifndef DBK_BTREE_NODE_H 26 #define DBK_BTREE_NODE_H 27 28 #include <Foundation/Foundation.h> 29 30 @class DBKBTree; 31 32 @interface DBKBTreeNode: NSObject 33 { 34 DBKBTree *tree; 35 36 NSNumber *offset; 37 38 unsigned order; 39 unsigned minkeys; 40 unsigned maxkeys; 41 42 unsigned ulen; 43 unsigned llen; 44 45 NSMutableArray *keys; 46 NSMutableArray *subnodes; 47 48 BOOL loaded; 49 50 DBKBTreeNode *parent; 51 } 52 53 - (id)initInTree:(DBKBTree *)atree 54 withParent:(DBKBTreeNode *)pnode 55 atOffset:(NSNumber *)ofst; 56 57 - (BOOL)isLoaded; 58 59 - (void)setLoaded; 60 61 - (void)loadNodeData; 62 63 /** we use BOOL so not to conflict with the signature of NSBundle's unload */ 64 - (BOOL)unload; 65 66 - (void)setNodeData:(NSData *)ndata; 67 68 - (NSData *)nodeData; 69 70 - (void)save; 71 72 - (NSNumber *)offset; 73 74 - (void)setOffset:(NSNumber *)ofst; 75 76 - (DBKBTreeNode *)parent; 77 78 - (void)setParent:(DBKBTreeNode *)anode; 79 80 - (void)insertKey:(id)key 81 atIndex:(NSUInteger)index; 82 83 - (BOOL)insertKey:(id)key; 84 85 - (NSUInteger)indexForKey:(id)key 86 existing:(BOOL *)exists; 87 88 - (NSUInteger)indexOfKey:(id)key; 89 90 - (id)keyAtIndex:(NSUInteger)index; 91 92 - (void)setKeys:(NSArray *)newkeys; 93 94 - (void)addKey:(id)key; 95 96 - (void)removeKey:(id)key; 97 98 - (void)removeKeyAtIndex:(NSUInteger)index; 99 100 - (void)replaceKeyAtIndex:(NSUInteger)index 101 withKey:(id)key; 102 103 - (void)replaceKey:(id)key 104 withKey:(id)newkey; 105 106 - (NSArray *)keys; 107 108 - (id)minKeyInSubnode:(DBKBTreeNode **)node; 109 110 - (id)maxKeyInSubnode:(DBKBTreeNode **)node; 111 112 - (id)successorKeyInNode:(DBKBTreeNode **)node 113 forKey:(id)key; 114 115 - (id)successorKeyInNode:(DBKBTreeNode **)node 116 forKeyAtIndex:(NSUInteger)index; 117 118 - (id)predecessorKeyInNode:(DBKBTreeNode **)node 119 forKey:(id)key; 120 121 - (id)predecessorKeyInNode:(DBKBTreeNode **)node 122 forKeyAtIndex:(NSUInteger)index; 123 124 - (void)insertSubnode:(DBKBTreeNode *)node 125 atIndex:(NSUInteger)index; 126 127 - (void)addSubnode:(DBKBTreeNode *)node; 128 129 - (void)removeSubnode:(DBKBTreeNode *)node; 130 131 - (void)removeSubnodeAtIndex:(NSUInteger)index; 132 133 - (void)replaceSubnodeAtIndex:(NSUInteger)index 134 withNode:(DBKBTreeNode *)node; 135 136 - (NSUInteger)indexOfSubnode:(DBKBTreeNode *)node; 137 138 - (DBKBTreeNode *)subnodeAtIndex:(NSUInteger)index; 139 140 - (BOOL)isFirstSubnode:(DBKBTreeNode *)node; 141 142 - (BOOL)isLastSubnode:(DBKBTreeNode *)node; 143 144 - (void)setSubnodes:(NSArray *)nodes; 145 146 - (NSArray *)subnodes; 147 148 - (DBKBTreeNode *)leftSibling; 149 150 - (DBKBTreeNode *)rightSibling; 151 152 - (void)splitSubnodeAtIndex:(NSUInteger)index; 153 154 - (BOOL)mergeWithBestSibling; 155 156 - (void)borrowFromRightSibling:(DBKBTreeNode *)sibling; 157 158 - (void)borrowFromLeftSibling:(DBKBTreeNode *)sibling; 159 160 - (void)setRoot; 161 162 - (BOOL)isRoot; 163 164 - (BOOL)isLeaf; 165 166 @end 167 168 #endif // DBK_BTREE_NODE_H 169