1//
2//  ACBTree.m
3//  ST4
4//
5//  Created by Alan Condit on 4/18/11.
6//  Copyright 2011 Alan Condit. All rights reserved.
7//
8
9#import <Foundation/Foundation.h>
10#import "ACBTree.h"
11#import "AMutableDictionary.h"
12#import "RuntimeException.h"
13
14@class AMutableDictionary;
15
16@implementation ACBKey
17
18static NSInteger RECNUM = 0;
19
20@synthesize recnum;
21@synthesize key;
22
23+ (ACBKey *)newKey
24{
25    return [[ACBKey alloc] init];
26}
27
28+ (ACBKey *)newKeyWithKStr:(NSString *)aKey
29{
30    return [[ACBKey alloc] initWithKStr:(NSString *)aKey];
31}
32
33- (id) init
34{
35    self =[super init];
36    if ( self != nil ) {
37        recnum = RECNUM++;
38    }
39    return self;
40}
41
42- (id) initWithKStr:(NSString *)aKey
43{
44    self =[super init];
45    if ( self != nil ) {
46        NSInteger len;
47        recnum = RECNUM++;
48        key = aKey;
49        len = [aKey length];
50        if ( len >= BTKeySize ) {
51            len = BTKeySize - 1;
52        }
53        strncpy( kstr, [aKey cStringUsingEncoding:NSASCIIStringEncoding], len);
54        kstr[len] = '\0';
55    }
56    return self;
57}
58
59- (void)dealloc
60{
61#ifdef DEBUG_DEALLOC
62    NSLog( @"called dealloc in ACBKey" );
63#endif
64    [super dealloc];
65}
66
67- (NSString *) description
68{
69    return [NSString stringWithFormat:@"len =%02d\nrecnum=%04d\nkey=%@\n", [key length], recnum, key];
70}
71
72@end
73
74@implementation ACBTree
75
76@synthesize dict;
77@synthesize lnode;
78@synthesize rnode;
79@synthesize keys;
80@synthesize btNodes;
81@synthesize lnodeid;
82@synthesize rnodeid;
83@synthesize nodeid;
84@synthesize nodeType;
85@synthesize numkeys;
86@synthesize numrecs;
87@synthesize updtd;
88@synthesize keylen;
89@synthesize kidx;
90
91+ (ACBTree *) newNodeWithDictionary:(AMutableDictionary *)theDict
92{
93    return [[ACBTree alloc] initWithDictionary:theDict];
94}
95
96- (id)initWithDictionary:(AMutableDictionary *)theDict
97{
98    self = [super init];
99    if (self) {
100        // Initialization code here.
101        dict = theDict;
102        nodeid = theDict.nxt_nodeid++;
103        keys = keyArray;
104        btNodes = btNodeArray;
105        if ( nodeid == 0 ) {
106            numkeys = 0;
107        }
108    }
109
110    return self;
111}
112
113- (void)dealloc
114{
115#ifdef DEBUG_DEALLOC
116    NSLog( @"called dealloc in ACBTree" );
117#endif
118    [super dealloc];
119}
120
121- (ACBTree *)createnode:(ACBKey *)kp
122{
123    ACBTree *tmp;
124
125    tmp = [ACBTree newNodeWithDictionary:dict];
126    tmp.nodeType = nodeType;
127    tmp.lnode = self;
128    tmp.rnode = self.rnode;
129    self.rnode = tmp;
130    //tmp.btNodes[0] = self;
131    //tmp.keys[0] = kp;
132    tmp.updtd = YES;
133    tmp.numrecs = ((nodeType == LEAF)?1:numrecs);
134    updtd = YES;
135    tmp.numkeys = 1;
136    [tmp retain];
137    return(tmp);
138}
139
140- (ACBTree *)deletekey:(NSString *)dkey
141{
142    ACBKey /* *del, */ *dkp;
143    ACBTree *told, *sNode;
144    BOOL mustRelease = NO;
145
146    if ( [dkey isKindOfClass:[NSString class]] ) {
147        dkp = [ACBKey newKeyWithKStr:dkey];
148        mustRelease = YES;
149    }
150    else if ( [dkey isKindOfClass:[ACBKey class]] )
151        dkp = (ACBKey *)dkey;
152    else
153        @throw [IllegalArgumentException newException:[NSString stringWithFormat:@"Don't understand this key:\"%@\"", dkey]];
154    sNode = [self search:dkp.key];
155    if ( sNode == nil || [sNode searchnode:dkp.key match:YES] == FAILURE ) {
156        if ( mustRelease ) [dkp release];
157        return(self);
158    }
159    told = dict.root;
160    /* del = */[self internaldelete:dkp];
161
162    /*  check for shrink at the root  */
163    if ( numkeys == 1 && nodeType != LEAF ) {
164        told = btNodes[0];
165        told.nodeid = 1;
166        told.updtd = YES;
167        dict.root = told;
168    }
169#ifdef DONTUSENOMO
170    if (debug == 'd') [self printtree];
171#endif
172    if ( mustRelease ) [dkp release];
173    return(told);
174}
175
176/** insertKey is the insertion entry point
177 *  It determines if the key exists in the tree already
178 *  it calls internalInsert to determine if the key already exists in the tree,
179 *  and returns the node to be updated
180 */
181- (ACBTree *)insertkey:(ACBKey *)kp value:(id)value
182{
183    ACBTree *tnew, *q;
184    NSInteger h, nodeNum;
185
186    tnew = self;
187    q = [self internalinsert:kp value:value split:&h];
188    /*  check for growth at the root  */
189    if ( q != nil ) {
190        tnew = [[ACBTree newNodeWithDictionary:dict] retain];
191        tnew.nodeType = BTNODE;
192        nodeNum = tnew.nodeid;
193        tnew.nodeid = 0;
194        self.nodeid = nodeNum;
195        [tnew insert:self.keys[numkeys-1] value:self index:0 split:&h];
196        [tnew insert:q.keys[q.numkeys-1] value:q index:1 split:&h];
197        tnew.numrecs = self.numrecs + q.numrecs;
198        tnew.lnodeid = self.nodeid;
199        tnew.rnodeid = self.rnodeid;
200        self.rnodeid = tnew.nodeid;
201        tnew.lnode = self;
202        tnew.rnode = self.rnode;
203        self.rnode = tnew;
204        /* affected by nodeid swap */
205        // newnode.lnodeid = tnew.btNodes[0].nodeid;
206    }
207    //dict.root = t;
208    //l.reccnt++;
209    return(tnew);
210}
211
212- (ACBTree *)search:(NSString *)kstr
213{
214    NSInteger i, ret;
215    NSInteger srchlvl = 0;
216    ACBTree *t;
217
218    t = self;
219    if ( self.numkeys == 0 && self.nodeType == LEAF )
220        return nil;
221    while (t != nil) {
222        for (i = 0; i < t.numkeys; i++) {
223            ret = [t.keys[i].key compare:kstr];
224            if ( ret >= 0 ) {
225                if ( t.nodeType == LEAF ) {
226                    if ( ret == 0 ) return (t);    /* node containing keyentry found */
227                    else return nil;
228                }
229                else {
230                    break;
231                }
232            }
233        }
234        srchlvl++;
235        if ( t.nodeType == BTNODE ) t = t.btNodes[i];
236        else {
237            t = nil;
238        }
239    }
240    return(nil);          /* entry not found */
241}
242
243/** SEARCHNODE
244 *  calling parameters --
245 *      BKEY PTR for key to search for.
246 *      TYPE for exact match(YES) or position(NO)
247 *  returns -- i
248 *      i == FAILURE when match required but does not exist.
249 *      i == t.numkeys if no existing insertion branch found.
250 *      otherwise i == insertion branch.
251 */
252- (NSInteger)searchnode:(NSString *)kstr match:(BOOL)match
253{
254    NSInteger i, ret;
255    for ( i = 0; i < numkeys; i++ ) {
256        ret = [keys[i].key compare:kstr];
257        if ( ret >= 0 ) {         /* key node found */
258            if ( ret == 0 && match == NO ) {
259                return FAILURE;
260            }
261            else if ( ret > 0 &&  match == YES ) {
262                return FAILURE;
263            }
264            break;
265        }
266    }
267    if ( i == numkeys && match == YES ) {
268        i = FAILURE;
269    }
270    return(i);
271}
272
273- (ACBKey *)internaldelete:(ACBKey *)dkp
274{
275    NSInteger i, nkey;
276    __strong ACBKey *del = nil;
277    ACBTree *tsb;
278    NSInteger srchlvl = 0;
279
280    /* find deletion branch */
281    if ( self.nodeType != LEAF ) {
282        srchlvl++;
283        /* search for end of tree */
284        i = [self searchnode:dkp.key match:NO];
285        del = [btNodes[i] internaldelete:dkp];
286        srchlvl--;
287        /* if not LEAF propagate back high key    */
288        tsb = btNodes[i];
289        nkey = tsb.numkeys - 1;
290    }
291    /***  the bottom of the tree has been reached       ***/
292    else {                   /* set up deletion ptrs      */
293        if ( [self delfrmnode:dkp] == SUCCESS ) {
294            if ( numkeys < BTHNODESIZE+1 ) {
295                del = dkp;
296            }
297            else {
298                del = nil;
299            }
300            dkp.recnum = nodeid;
301            return(del);
302        }
303    }
304    /***       indicate deletion to be done            ***/
305    if ( del != nil ) {
306        /*** the key in "del" has to be deleted from in present node ***/
307        if ( btNodes[i].numkeys >= BTHNODESIZE+1 ) {
308            /* node does not need balancing */
309            del = nil;
310            self.keys[i] = tsb.keys[nkey];
311        }
312        else {                         /* node requires balancing */
313            if ( i == 0 ) {
314                [self rotateright:0];
315                self.btNodes[0] = tsb;
316            } else if ( i < numkeys-1 ) {     /* look to the right first */
317                if ( self.btNodes[i+1].numkeys > BTHNODESIZE+1 ) {  /* carry from right */
318                    [self borrowright:i];
319                }
320                else {           /* merge present node with right node */
321                    [self mergenode:i];
322                }
323            }
324            else {                      /* look to the left */
325                if ( i > 0 ) {          /* carry or merge with left node */
326                    if ( self.btNodes[i-1].numkeys > BTHNODESIZE+1 ) { /* carry from left */
327                        [self borrowleft:i];
328                    }
329                    else { /*** merge present node with left node ***/
330                        i--;
331                        [self mergenode:i];
332                        tsb = self.btNodes[i];
333                    }
334                }
335            }
336        self.keys[i] = tsb.keys[nkey];
337        }
338    }
339    numrecs--;
340    updtd = TRUE;
341    return(del);
342}
343
344/** Search key kp on B-tree with root t; if found increment counter.
345 *  otherwise insert an item with key kp in tree.  If an ACBKey
346 *  emerges to be passed to a lower level, then assign it to kp;
347 *  h = "tree t has become higher"
348 */
349- (ACBTree *) internalinsert:(ACBKey *)kp value:(id)value split:(NSInteger *)h
350{
351    /* search key ins on node t^; h = false  */
352    NSInteger i, ret;
353    ACBTree *q, *tmp;
354
355    for (i = 0; i < numkeys; i++) {
356        ret = [keys[i].key compare:kp.key];
357        if ( ret >= 0 ) {
358            if ( nodeType == LEAF && ret == 0 ) return (self);    /* node containing keyentry found */
359            break;
360        }
361    }
362    if ( nodeType == LEAF ) { /*  key goes in this node  */
363        q = [self insert:kp value:value index:i split:h];
364    }
365    else  { /* nodeType == BTNODE */
366        /*  key is not on this node  */
367        q = [self.btNodes[i] internalinsert:kp value:value split:h];
368        if ( *h ) {
369            [self insert:kp value:q index:i split:h];
370        }
371        else {
372            self.numrecs++;
373        }
374        tmp = self.btNodes[numkeys-1];
375        keys[numkeys-1] = tmp.keys[tmp.numkeys-1];
376        if ( i != numkeys-1 ) {
377            tmp = self.btNodes[i];
378            keys[i] = tmp.keys[tmp.numkeys-1];
379        }
380        updtd = YES;
381    } /* search */
382    return q;
383}
384
385/** Do the actual insertion or split and insert
386 *  insert key to the right of t.keys[hi]
387 */
388- (ACBTree *) insert:(ACBKey *)kp value:(id)value index:(NSInteger)hi split:(NSInteger *)h
389{
390    ACBTree *b;
391
392    if ( numkeys < BTNODESIZE ) {
393        *h = NO;
394        [self rotateright:hi];
395        keys[hi] = kp;
396        btNodes[hi] = value;
397        numrecs++;
398        numkeys++;
399        updtd = YES;
400        //[kp retain];
401        return nil;
402    }
403    else { /*  node t is full; split it and assign the emerging ACBKey to olditem  */
404        b = [self splitnode:hi];
405        if ( hi <= BTHNODESIZE ) {              /* insert key in left page */
406            [self rotateright:hi];
407            keys[hi] = kp;
408            btNodes[hi] = value;
409            numrecs++;
410            numkeys++;
411        }
412        else {                                  /* insert key in right page */
413            hi -= BTHNODESIZE;
414            if ( b.rnode == nil ) hi--;
415            [b rotateright:hi];
416            b.keys[hi] = kp;
417            b.btNodes[hi] = value;
418            b.numrecs++;
419            b.numkeys++;
420        }
421        numkeys = b.numkeys = BTHNODESIZE+1;
422        b.updtd = updtd = YES;
423    }
424    return b;
425} /* insert */
426
427- (void)borrowleft:(NSInteger)i
428{
429    ACBTree *t0, *t1;
430    NSInteger nkey;
431
432    t0 = btNodes[i];
433    t1 = btNodes[i-1];
434    nkey = t1.numkeys-1;
435    [t0 insinnode:t1.keys[nkey] value:t1.btNodes[nkey]];
436    [t1 delfrmnode:t1.keys[nkey]];
437    nkey--;
438    keys[i-1] = t1.keys[nkey];
439    keys[i-1].recnum = t1.nodeid;
440}
441
442- (void)borrowright:(NSInteger)i
443{
444    ACBTree *t0, *t1;
445    NSInteger nkey;
446
447    t0 = btNodes[i];
448    t1 = btNodes[i+1];
449    [t0 insinnode:t1.keys[0] value:t1.btNodes[0]];
450    [t1 delfrmnode:t1.keys[0]];
451    nkey = t0.numkeys - 1;
452    keys[i] = t0.keys[nkey];
453    keys[i].recnum = t0.nodeid;
454}
455
456- (NSInteger)delfrmnode:(ACBKey *)ikp
457{
458    NSInteger j;
459
460    j = [self searchnode:ikp.key match:YES];
461    if (j == FAILURE) {
462        return(FAILURE);
463    }
464    ACBKey *k0 = nil;
465    ACBTree *n0 = nil;
466    if ( self.nodeType == LEAF ) {
467        k0 = self.keys[j];
468        n0 = self.btNodes[j];
469    }
470    [self rotateleft:j];
471    self.numkeys--;
472    numrecs -= ((self.nodeType == LEAF)?1:btNodes[j].numrecs);
473    if ( k0 ) [k0 release];
474    if ( n0 ) [n0 release];
475    updtd = TRUE;
476    return(SUCCESS);
477}
478
479- (NSInteger)insinnode:(ACBKey *)ikp value:(id)value
480{
481    NSInteger j;
482
483    j = [self searchnode:ikp.key match:NO];
484    [self rotateright:j];
485    keys[j] = ikp;
486    btNodes[j] = value;
487    numkeys++;
488    if ( nodeType == LEAF ) {
489        numrecs++;
490    }
491    else {
492        numrecs += btNodes[j].numrecs;
493    }
494    updtd = TRUE;
495    return(j);
496}
497
498- (void)mergenode:(NSInteger)i
499{
500    ACBTree *t0, *t1, *tr;
501    NSInteger j, k, nkeys;
502
503    t0 = btNodes[i];
504    t1 = btNodes[i+1];
505    /*** move keys and pointers from
506     t1 node to t0 node           ***/
507    for (j=t0.numkeys, k=0; j < BTNODESIZE && k < t1.numkeys; j++, k++) {
508        t0.keys[j] = t1.keys[k];
509        t0.btNodes[j] = t1.btNodes[k];
510        t0.numkeys++;
511    }
512    t0.numrecs += t1.numrecs;
513    t0.rnode = t1.rnode;
514    t0.rnodeid = t1.rnodeid;
515    t0.updtd = YES;
516    nkeys = t0.numkeys - 1;
517    keys[i] = t0.keys[nkeys]; /* update key to point to new high key */
518    [self rotateleft:i+1]; /* copy over the keys and nodes */
519
520    t1.nodeType = -1;
521    if (t1.rnodeid != 0xffff && i < numkeys - 2) {
522        tr = btNodes[i+1];
523        tr.lnodeid = t0.nodeid;
524        tr.lnode = t0;
525        tr.updtd = YES;
526    }
527    self.numkeys--;
528    updtd = YES;
529}
530
531- (ACBTree *)splitnode:(NSInteger)idx
532{
533    ACBTree *t1;
534    NSInteger j, k;
535
536    k = (idx <= BTHNODESIZE) ? BTHNODESIZE : BTHNODESIZE+1;
537    /*** create new node ***/
538    // checknode(l, t, k);
539    t1 = [ACBTree newNodeWithDictionary:dict];
540    t1.nodeType = nodeType;
541    t1.rnode = self.rnode;
542    self.rnode = t1;
543    t1.lnode = self;
544    self.updtd = t1.updtd = YES;
545    /*** move keys and pointers ***/
546    NSInteger i = 0;
547    for (j = k; j < BTNODESIZE; j++, i++ ) {
548        t1.keys[i] = keys[j];
549        t1.btNodes[i] = btNodes[j];
550        t1.numrecs += ((nodeType == LEAF) ? 1 : btNodes[j].numrecs);
551        numrecs     -= ((nodeType == LEAF) ? 1 : btNodes[j].numrecs);
552        keys[j] = nil;
553        btNodes[j] = nil;
554    }
555    t1.numkeys  = BTNODESIZE-k;
556    self.numkeys = k;
557    return(t1);
558}
559
560#ifdef DONTUSENOMO
561freetree(l, t)
562FIDB *l;
563ACBTree *t;
564{
565    ACBTree *tmp;
566    NSInteger i;
567
568    if (dict.root == nil) return(SUCCESS);
569    if (t.nodeid == 1) {
570        srchlvl = 0;
571    }
572    else srchlvl++;
573    for (i = 0; i < t.numkeys; i++) {
574        tmp = t.btNodes[i];
575        if (tmp != nil) {
576            if (tmp.nodeType == LEAF) {
577                free(tmp);    /* free the leaf */
578                if (tmp == l.rrnode) {
579                    l.rrnode = nil;
580                }
581                t.btNodes[i] = nil;
582                l.chknode.nods_inuse--;
583                /*              putpage(l, l.chknode, 0);
584                 */
585            }
586            else {
587                freetree(l, tmp); /* continue up the tree */
588                srchlvl--;        /* decrement the srchlvl on return */
589            }
590        }
591    }
592    free(t); /* free the node entered with */
593    if (t == l.rrnode) {
594        l.rrnode = nil;
595    }
596    l.chknode.nods_inuse--;
597    /*     putpage(l, l.chknode, 0);
598     */
599    t = nil;
600}
601
602- (void) notfound:(ACBKey *)kp
603{
604    /* error routine to perform if entry was expected and not found */
605}
606
607- (void)printtree:(ACBTree *)t
608{
609    BYTE *str;
610    NSInteger i, j;
611    NSUInteger *pdate, *ptime;
612
613    syslst = stdprn;
614    if ( t.nodeid == 1 ) {
615        srchlvl = 0;
616    }
617    else srchlvl++;
618    for (j = 0; j < t.numkeys; j++) {
619        checknode(l, t, j);
620        if ( t.btNodes[j] != nil ) [self printtree:t.btNodes[j]];
621    }
622    NSLog(@"Nodeid = %d, nodeType = %s, numkeys = %d, numrecs = %d\n",
623          t.nodeid, (t.nodeType == BTNODE)?@"NODE":@"LEAF", t.numkeys, t.numrecs);
624    NSLog(@"Left nodeid = %d, Right nodeid = %d\n", t.lnodeid, t.rnodeid);
625    for (i = 0; i < t.numkeys; i++) {
626        NSLog(@"     t.keys[%d] recnum = %d, keyval = %@",
627              i, t.keys[i].recnum, t.keys[i]);
628        str = t.keys[i].kstr;
629        pdate = (NSUInteger *) (str + 6);
630        ptime = (NSUInteger *) (str + 8);
631        NSLog(@" date = %04.4x,  time = %04.4x\n",
632              *pdate, *ptime);
633    }
634}
635
636- (BOOL)puttree:(ACBTree *)t
637{
638    NSInteger i;
639    if (t.nodeType != LEAF) {
640        for (i = 0; i < t.numkeys; i++) {
641            if ( t.btNodes[i] != nil ) puttree(l, t.btNodes[i]);
642        }
643    }
644    if ( t.updtd ) {
645        putnode(l, t, t.nodeid);
646        return(YES);
647    }
648    return(NO);
649}
650
651#endif
652
653/** ROTATELEFT -- rotate keys from right to the left
654 *  starting at position j
655 */
656- (void)rotateleft:(NSInteger)j
657{
658    while ( j+1 < numkeys ) {
659        keys[j] = keys[j+1];
660        btNodes[j] = btNodes[j+1];
661        j++;
662    }
663}
664
665/** ROTATERIGHT -- rotate keys to the right by 1 position
666 *  starting at the last key down to position j.
667 */
668- (void)rotateright:(NSInteger)j
669{
670    NSInteger k;
671
672    for ( k = numkeys; k > j; k-- ) {
673        keys[k] = keys[k-1];
674        btNodes[k] = btNodes[k-1];
675    }
676    keys[j] = nil;
677    btNodes[j] = nil;
678}
679
680- (NSInteger) keyWalkLeaves
681{
682    NSInteger i, idx = 0;
683    NSInteger keycnt;
684    ACBTree *t;
685
686    if ( self != dict.root ) {
687        return 0; // maybe I need to throw an exception here
688    }
689    t = self;
690    self.dict.data = [[NSMutableData dataWithLength:(numkeys * sizeof(id))] retain];
691    self.dict.ptrBuffer = [self.dict.data mutableBytes];
692    while ( t != nil && t.nodeType != LEAF ) {
693        t = t.btNodes[0];
694    }
695    do {
696        keycnt = t.numkeys;
697        for ( i = 0; i < keycnt; i++ ) {
698            if ( t.btNodes[i] != nil ) {
699                dict.ptrBuffer[idx++] = (id) t.keys[i].key;
700            }
701        }
702        t = t.rnode;
703    } while ( t != nil );
704    return( idx );
705}
706
707- (NSInteger) objectWalkLeaves
708{
709    NSInteger i, idx = 0;
710    NSInteger keycnt;
711    ACBTree *t;
712
713    if ( self != dict.root ) {
714        return 0; // maybe I need to throw an exception here
715    }
716    t = self;
717    self.dict.data = [[NSMutableData dataWithLength:(numrecs * sizeof(id))] retain];
718    self.dict.ptrBuffer = [self.dict.data mutableBytes];
719    while ( t != nil && t.nodeType != LEAF ) {
720        t = t.btNodes[0];
721    }
722    do {
723        keycnt = t.numkeys;
724        for ( i = 0; i < keycnt; i++ ) {
725            if ( t.btNodes[i] != nil ) {
726                dict.ptrBuffer[idx++] = (id) t.btNodes[i];
727            }
728        }
729        t = t.rnode;
730    } while ( t != nil );
731    return( idx );
732}
733
734- (NSString *) description
735{
736    NSMutableString *str = [NSMutableString stringWithCapacity:16];
737    NSInteger i;
738    for (i = 0; i < numkeys; i++ ) {
739        [str appendString:[NSString stringWithFormat:@"key[%d]=%@", i, [keys[i] description]]];
740    }
741    for (i = 0; i < numkeys; i++ ) {
742        [str appendString:[NSString stringWithFormat:@"btnodes[%d]=%@\n", i, [btNodes[i] description]]];
743    }
744    return str;
745}
746
747@end
748