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 #define FAILURE -1 22 #define SUCCESS 0 23 24 @interface ACBKey : NSObject { 25 NSInteger recnum; /* record number */ 26 __strong NSString *key; /* key pointer id */ 27 char kstr[BTKeySize]; /* key entry */ 28 } 29 30 @property (assign) NSInteger recnum; 31 @property (retain) NSString *key; 32 33 + (ACBKey *)newKey; 34 + (ACBKey *)newKeyWithKStr:(NSString *)aKey; 35 - (id) init; 36 - (id) initWithKStr:(NSString *)aKey; 37 38 @end 39 40 @interface ACBTree : NSObject { 41 __strong AMutableDictionary *dict; /* The dictionary that this node belongs to */ 42 __strong ACBTree *lnode; /* pointer to left node */ 43 __strong ACBTree *rnode; /* pointer to right node */ 44 __strong ACBKey **keys; /* pointer to keys */ 45 __strong ACBTree **btNodes; /* pointers to btNodes */ 46 __strong ACBKey *keyArray[BTNODESIZE]; 47 __strong ACBTree *btNodeArray[BTNODESIZE]; 48 NSInteger lnodeid; /* nodeid of left node */ 49 NSInteger rnodeid; /* nodeid of right node */ 50 NSInteger nodeid; /* node id */ 51 NSInteger nodeType; /* 1 = node, 2 = leaf, -1 = unused */ 52 NSInteger numkeys; /* number of active entries */ 53 NSInteger numrecs; /* number of records */ 54 NSInteger updtd; /* modified since update flag */ 55 NSInteger keylen; /* length of key */ 56 NSInteger kidx; 57 } 58 59 @property (retain) AMutableDictionary *dict; 60 @property (retain) ACBTree *lnode; 61 @property (retain) ACBTree *rnode; 62 @property (assign) ACBKey **keys; 63 @property (assign) ACBTree **btNodes; 64 @property (assign) NSInteger lnodeid; 65 @property (assign) NSInteger rnodeid; 66 @property (assign) NSInteger nodeid; 67 @property (assign) NSInteger nodeType; 68 @property (assign) NSInteger numkeys; 69 @property (assign) NSInteger numrecs; 70 @property (assign) NSInteger updtd; 71 @property (assign) NSInteger keylen; 72 @property (assign) NSInteger kidx; 73 74 + (ACBTree *) newNodeWithDictionary:(AMutableDictionary *)theDict; 75 76 - (id)initWithDictionary:(AMutableDictionary *)theDict; 77 78 - (ACBTree *)createnode:(ACBKey *)kp0; 79 - (ACBTree *)deletekey:(NSString *)dkey; 80 - (ACBTree *)insertkey:(ACBKey *)ikp value:(id)value; 81 - (ACBKey *)internaldelete:(ACBKey *)dkp; 82 - (ACBTree *) internalinsert:(ACBKey *)key value:(id)value split:(NSInteger *)h; 83 - (ACBTree *) insert:(ACBKey *)key value:(id)value index:(NSInteger)hi split:(NSInteger *)h; 84 - (NSInteger)delfrmnode:(ACBKey *)ikp; 85 - (NSInteger)insinnode:(ACBKey *)key value:(id)value; 86 - (void)mergenode:(NSInteger)i; 87 - (ACBTree *)splitnode:(NSInteger)idx; 88 - (ACBTree *)search:(id)key; 89 - (NSInteger)searchnode:(id)key match:(BOOL)match; 90 - (void)borrowleft:(NSInteger)i; 91 - (void)borrowright:(NSInteger)i; 92 - (void)rotateleft:(NSInteger)j; 93 - (void)rotateright:(NSInteger)j; 94 - (NSInteger) keyWalkLeaves; 95 - (NSInteger) objectWalkLeaves; 96 - (void)dealloc; 97 @end 98