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 9typedef 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