1 // 2 // ACBtree.h 3 // ST4 4 // 5 // Created by Alan Condit on 4/18/11. 6 // Copyright 2011 Alan Condit. All rights reserved. 7 // 8 9 typedef enum { 10 BTNODE, 11 LEAF 12 } NodeType; 13 14 #import <Foundation/Foundation.h> 15 16 @class AMutableDictionary; 17 18 #define BTNODESIZE 11 19 #define BTHNODESIZE ((BTNODESIZE-1)/2) 20 #define BTKeySize 38 21 #if defined FAILURE 22 #undef FAILURE 23 #endif 24 #define FAILURE -1 25 #if defined SUCCESS 26 #undef SUCCESS 27 #endif 28 #define SUCCESS 0 29 30 @interface ACBKey : NSObject { 31 NSInteger recnum; /* record number */ 32 __strong NSString *key; /* key pointer id */ 33 char kstr[BTKeySize]; /* key entry */ 34 } 35 36 @property (assign) NSInteger recnum; 37 @property (retain) NSString *key; 38 39 + (ACBKey *)newKey; 40 + (ACBKey *)newKeyWithKStr:(NSString *)aKey; 41 - (id) init; 42 - (id) initWithKStr:(NSString *)aKey; 43 - (void)dealloc; 44 - (NSString *) description; 45 @end 46 47 @interface ACBTree : NSObject { 48 __strong AMutableDictionary *dict; /* The dictionary that this node belongs to */ 49 __strong ACBTree *lnode; /* pointer to left node */ 50 __strong ACBTree *rnode; /* pointer to right node */ 51 __strong ACBKey **keys; /* pointer to keys */ 52 __strong ACBTree **btNodes; /* pointers to btNodes */ 53 __strong ACBKey *keyArray[BTNODESIZE]; 54 __strong ACBTree *btNodeArray[BTNODESIZE]; 55 NSInteger lnodeid; /* nodeid of left node */ 56 NSInteger rnodeid; /* nodeid of right node */ 57 NSInteger nodeid; /* node id */ 58 NSInteger nodeType; /* 1 = node, 2 = leaf, -1 = unused */ 59 NSInteger numkeys; /* number of active entries */ 60 NSInteger numrecs; /* number of records */ 61 NSInteger updtd; /* modified since update flag */ 62 NSInteger keylen; /* length of key */ 63 NSInteger kidx; 64 } 65 66 @property (retain) AMutableDictionary *dict; 67 @property (retain) ACBTree *lnode; 68 @property (retain) ACBTree *rnode; 69 @property (assign) ACBKey **keys; 70 @property (assign) ACBTree **btNodes; 71 @property (assign) NSInteger lnodeid; 72 @property (assign) NSInteger rnodeid; 73 @property (assign) NSInteger nodeid; 74 @property (assign) NSInteger nodeType; 75 @property (assign) NSInteger numkeys; 76 @property (assign) NSInteger numrecs; 77 @property (assign) NSInteger updtd; 78 @property (assign) NSInteger keylen; 79 @property (assign) NSInteger kidx; 80 81 + (ACBTree *) newNodeWithDictionary:(AMutableDictionary *)theDict; 82 83 - (id)initWithDictionary:(AMutableDictionary *)theDict; 84 - (void)dealloc; 85 86 - (ACBTree *)createnode:(ACBKey *)kp0; 87 - (ACBTree *)deletekey:(NSString *)dkey; 88 - (ACBTree *)insertkey:(ACBKey *)ikp value:(id)value; 89 - (ACBKey *)internaldelete:(ACBKey *)dkp; 90 - (ACBTree *) internalinsert:(ACBKey *)key value:(id)value split:(NSInteger *)h; 91 - (ACBTree *) insert:(ACBKey *)key value:(id)value index:(NSInteger)hi split:(NSInteger *)h; 92 - (NSInteger)delfrmnode:(ACBKey *)ikp; 93 - (NSInteger)insinnode:(ACBKey *)key value:(id)value; 94 - (void)mergenode:(NSInteger)i; 95 - (ACBTree *)splitnode:(NSInteger)idx; 96 - (ACBTree *)search:(id)key; 97 - (NSInteger)searchnode:(id)key match:(BOOL)match; 98 - (void)borrowleft:(NSInteger)i; 99 - (void)borrowright:(NSInteger)i; 100 - (void)rotateleft:(NSInteger)j; 101 - (void)rotateright:(NSInteger)j; 102 - (NSInteger) keyWalkLeaves; 103 - (NSInteger) objectWalkLeaves; 104 - (NSString *) description; 105 @end 106