/**
 * Acquisition
 * http://www.xlife.org/
 *
 * Copyright (c) 2002-2003 David Keiichi Watanabe
 * davew@xlife.org
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */

#import "NSMutableArray-BinaryInsert.h"

//#define DEBUG
//#define VERBOSE_DEBUG
//#define PROFILE

#ifdef PROFILE
#import "Profile.h"
#endif

static BOOL impsInitialized;

static SEL count;
static IMP countimp;

static SEL objectindex;
static IMP objectindeximp;

static SEL insert;
static IMP insertimp;


@implementation NSMutableArray (BinaryInsert)

/* NOTE: these functions presume the array is sorted (using the provided function/selector) already.  The addition of the object will preserve the sorted order. */

static inline int _insertObject(id obj, SEL selector, IMP imp, void* function, void* context, id this)
{
    int size;			/* current array size    */
    int current;		/* current index         */
    int lastCurrent ;		/* top of useful objects */

    id lobject;				/* left object  */
    id robject;				/* right object */
    
    NSComparisonResult lresult;		/* left result  */
    NSComparisonResult rresult;		/* right result */

    if (!impsInitialized) 
    {
        count = @selector(count);
        countimp = [this methodForSelector: count];
        
        objectindex = @selector(objectAtIndex:);
        objectindeximp = [this methodForSelector: objectindex];
        
        insert = @selector(insertObject:atIndex:);
        insertimp = [this methodForSelector: insert];
        
        impsInitialized = YES;
    }
    
    size = (int)countimp(this, count);
    current = size/2;
    lastCurrent = size;
    
    #ifdef PROFILE
    [Profile start]; {
    #endif
    
    #ifdef DEBUG
    int iterations = 0;
    NSLog(@"inserting %@", obj);
    #endif
    
    do {
        
        #ifdef DEBUG
        NSLog(@"current is %i, lastCurrent is %i", current, lastCurrent);
        #endif
    
        lobject = (current > 0)    ? objectindeximp(this, objectindex, (current-1)) : nil;
        robject = (current < size) ? objectindeximp(this, objectindex, (current))   : nil;

        if (imp)
        {
            lresult = (NSComparisonResult)imp(lobject, selector, obj);
            rresult = (NSComparisonResult)imp(robject, selector, obj);
        }
        else if (selector)
        {
            lresult = (lobject) ? (NSComparisonResult)[lobject performSelector: selector withObject: obj] : NSOrderedSame;
            rresult = (robject) ? (NSComparisonResult)[robject performSelector: selector withObject: obj] : NSOrderedSame;
        } 
        else 
        {
            lresult = (lobject) ? ((int(*)(id,id,void*))function)(lobject, obj, context) : NSOrderedSame;
            rresult = (robject) ? ((int(*)(id,id,void*))function)(robject, obj, context) : NSOrderedSame;
        }
        
        #ifdef VERBOSE_DEBUG
        {
            NSString* ltext;
            NSString* rtext;
            if (lresult == NSOrderedAscending) ltext = @"NSOrderedAscending";
            else if (lresult == NSOrderedDescending) ltext = @"NSOrderedDescending";
            else if (lresult == NSOrderedSame) ltext = @"NSOrderedSame";
            else ltext = [NSString stringWithFormat: @"%i", lresult];
            
            if (rresult == NSOrderedAscending) rtext = @"NSOrderedAscending";
            else if (rresult == NSOrderedDescending) rtext = @"NSOrderedDescending";
            else if (rresult == NSOrderedSame) rtext = @"NSOrderedSame";
            else rtext = [NSString stringWithFormat: @"%i", rresult];
            
            NSLog(@"left: %@, right %@", lobject, robject);
            NSLog(@"left: %@, right: %@", ltext, rtext);
        }
        #endif
        
        if ((lresult == NSOrderedAscending || !lobject) && (rresult == NSOrderedDescending || !robject))
            break;
        
        if (lresult == NSOrderedSame && rresult == NSOrderedDescending) 
            break;
            
        if (lresult == NSOrderedAscending && rresult == NSOrderedSame)
            break;
        
        if (lresult == NSOrderedSame && rresult == NSOrderedSame)
            break;
        
        if (lresult == NSOrderedDescending) {
            lastCurrent = current;
            current = current/2;
        } else {
            current = (current + lastCurrent + 1)/2;
        }
        
        #ifdef DEBUG
        iterations ++;
        if (iterations > 30) {
            NSLog(@" **** FAILURE **** ");
            return;
        }
        #endif
        
    } while (1);

    #ifdef DEBUG
    NSLog(@"Took %i iterations to insert into array of size %i", iterations, size);
    #endif

    insertimp(this, insert, obj, current);
    
    #ifdef PROFILE
    } [Profile end];
    #endif

    #ifdef DEBUG
    NSLog(@"%@", this);
    #endif
    
    return current;
}


- (int) insertObject: (id) obj intoSortedArrayUsingFunction: (int(*)(id,id,void*)) function context: (void*) context; {
    return _insertObject(obj, nil, 0, function, context, self);
}

- (int) insertObject: (id) obj intoSortedArrayUsingSelector: (SEL) selector; {
    return _insertObject(obj, selector, 0, 0, 0, self);
}

- (int) insertObject: (id) obj intoSortedArrayUsingSelector: (SEL) selector imp: (IMP) imp; {
    return _insertObject(obj, selector, imp, 0, 0, self);
}

@end