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