/* Implementation for Objective-C IndexedCollection object

   Copyright (C) 1993 R. Andrew McCallum <mccallum@cs.rochester.edu>
   Dept. of Computer Science, U. of Rochester, Rochester, NY  14627

   This file is part of the GNU Objective-C Collection library.

   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.
   
   This library 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
   Library General Public License for more details.

   You should have received a copy of the GNU Library General Public
   License along with this library; if not, write to the Free
   Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/ 

#include <coll/IndexedCollection.h>
#include <coll/IndexedCollectionPrivate.h>
#include <objc/objc-api.h>

@implementation IndexedCollection

+ initialize
{
    if (self == [IndexedCollection class])
	[self setVersion:-1];	/* alpha release */
    return self;
}

/* This is the designated initializer of this class */
- initDescription: (const char *)description
{
  [super initDescription:description keyDescription:"I"];
  return self;
}

/* Override the designated initializer for our superclass KeyedCollection
   to make sure we have unsigned int keys. */
- initDescription: (const char *)contentType 
    keyDescription: (const char *)keyType
{
  if (*keyType != _C_UINT)
    [self error:"IndexedCollection key must be an unsigned integer."];
  return [self initDescription:contentType];
}

// ADDING;

- insertElement: (elt)newElement atIndex: (unsigned)index
{
  return [self subclassResponsibility:_cmd];
}

- insertObject: newObject atIndex: (unsigned)index
{
  return [self insertElement:newObject atIndex:index];
}

- insertElement: (elt)newElement before: (elt)oldElement
{
  unsigned index = [self indexOfElement:oldElement];

  if (index == COLL_NO_INDEX)
    return nil;
  [self insertElement:newElement atIndex:index];
  return self;
}

- insertObject: newObject before: oldObject
{
  return [self insertElement:newObject before:oldObject];
}

- insertElement: (elt)newElement after: (elt)oldElement
{
  unsigned index = [self indexOfElement:oldElement];

  if (index == COLL_NO_INDEX)
    return nil;
  [self insertElement:newElement atIndex:index+1];
  return self;
}

- insertObject: newObject after: oldObject
{
  return [self insertElement:newObject after:oldObject];
}

/* Possibly inefficient.  Should be overridden. */
- appendElement: (elt)newElement
{
  return [self insertElement:newElement atIndex:[self count]];
}

- appendObject: newObject
{
  return [self appendElement:newObject];
}

/* Possibly inefficient.  Should be overridden. */
- prependElement: (elt)newElement
{
  return [self insertElement:newElement atIndex:0];
}

- prependObject: newObject
{
  return [self prependElement:newObject];
}

- appendContentsOf: (id <Collecting>) aCollection
{
  void doIt(elt e)
    {
      [self appendElement:e];
    }
  if (aCollection == self)
    [[[self shallowCopy] withElementsCall:doIt] free];
  else
    [aCollection withElementsCall:doIt];
  return self;
}

- prependContentsOf: (id <Collecting>) aCollection
{
  void doIt(elt e)
    {
      /* could use objc_msg_lookup here */
      [self prependElement:e];
    }
  if (aCollection == self)
    [[[self shallowCopy] withElementsInReverseCall:doIt] free];
  else
    {
      /* Can I assume that all Collections will inherit from Object? */
      if ([(Object*)aCollection 
	   respondsTo:@selector(withElementsInReverseCall:)])
	[(id <IndexedCollecting>)aCollection withElementsInReverseCall:doIt];
      else
	[aCollection withElementsCall:doIt];
    }
  return self;
}

/* We can not implement this <Collecting> protocol method */
- addElement: (elt)newElement
{
  return [self appendElement:newElement];
}


// REPLACING;

/* Subclasses may require different ordering semantics */
- (elt) replaceElement: (elt)oldElement with: (elt)newElement
{
  unsigned index = [self indexOfElement:oldElement];

  if (index == COLL_NO_INDEX)
    return nil;
  return [self replaceElementAtIndex:index with:newElement];
}

/* Inefficient.  Should be overridden */
- (elt) replaceElementAtIndex: (unsigned)index with: (elt)newElement
{
  elt ret;

  ret = [self removeElementAtIndex:index];
  [self insertElement:newElement atIndex:index];
  return ret;
}

- replaceObjectAtIndex: (unsigned)index with: newObject
{
  return [self replaceElementAtIndex:index with:newObject].id_t;
}


// SWAPPING;

/* Perhaps inefficient.  May be overridden. */
- swapAtIndeces: (unsigned)index1 : (unsigned)index2
{
  elt tmp = [self elementAtIndex:index1];
  [self replaceElementAtIndex:index1 with:[self elementAtIndex:index2]];
  [self replaceElementAtIndex:index2 with:tmp];
  return self;
}


// REMOVING;

- (elt) removeElementAtIndex: (unsigned)index
{
  return [self subclassResponsibility:_cmd];
}

- removeObjectAtIndex: (unsigned)index
{
  return [self removeElementAtIndex:index].id_t;
}

- (elt) removeFirstElement
{
  return [self removeElementAtIndex:0];
}

- removeFirstObject
{
  return [self removeFirstElement].id_t;
}

- (elt) removeLastElement
{
  return [self removeElementAtIndex:[self count]-1];
}

- removeLastObject
{
  return [self removeLastElement].id_t;
}

/* We can not implement this <Collecting> protocol method */
- (elt) removeElement: (elt)oldElement
{
  unsigned index = [self indexOfElement:oldElement];

  /* This should be object-not-found warning */
  if (index == COLL_NO_INDEX)
    return COLL_NO_ELEMENT;
  return [self removeElementAtIndex:index];
}
  

// GETTING MEMBERS BY INDEX;

- (elt) elementAtIndex: (unsigned)index
{
  return [self subclassResponsibility:_cmd];
}

- objectAtIndex: (unsigned)index
{
  return [self elementAtIndex:index].id_t;
}

- (elt) firstElement
{
  return [self elementAtIndex:0];
}

- firstObject
{
  return [self firstElement].id_t;
}

- (elt) lastElement
{
  return [self elementAtIndex:[self count]-1];
}

- lastObject
{
  return [self lastElement].id_t;
}


// GETTING INDICES BY ELEMENT;

/* Possibly inefficient. */
- (unsigned) indexOfElement: (elt)anElement
{
  unsigned index = 0;
  BOOL flag = YES;
  void doIt(elt e)
    {
      if (_compare_func(anElement.void_ptr_t, e.void_ptr_t))
	flag = NO;
      else
	index++;
    }

  [self withElementsCall:doIt whileTrue:&flag];
  if (flag)
    {
      index = COLL_NO_INDEX;
      [self errorElementNotFound:anElement inMethod:_cmd];
    }
  return index;
}

- (unsigned) indexOfObject: anObject
{
  return [self indexOfElement:anObject];
}


// TESTING;

- (BOOL) includesIndex: (unsigned)index
{
  if (index < [self count])
    return YES;
  else
    return NO;
}

- (BOOL) includesSameContentsInOrder: (id <IndexedCollecting>)anIndexedColl
{
  elt e1, e2;
  void *s1, *s2;

  if ([self count] != [anIndexedColl count])
    return NO;
  s1 = s2 = 0;
  while ([self getNextElement:&e1 withEnumState:&s1]
	 && [anIndexedColl getNextElement:&e2 withEnumState:&s2])
    {
      if (!_compare_func(e1.void_ptr_t, e2.void_ptr_t))
	return NO;
    }
  return YES;
}

/* is this what we want? */
- (BOOL) isEqual: anObject
{
  if ([anObject class] != [self class] && 
      [self includesSameContentsInOrder:anObject])
    return YES;
  else
    return NO;
}


// COPYING;
  
- shallowCopyFrom: (unsigned)start to: (unsigned)stop
{
  id newColl = [self emptyCopyAs:[self species]];
  unsigned i, myCount = [self count];
  
  for (i = start; i <= stop && i < myCount; i++)
    [newColl addElement:[self elementAtIndex:i]];
  return newColl;
}

- shallowCopyReplaceFrom: (unsigned)start to: (unsigned)stop 
    with: (id <Collecting>)replaceCollection
{
  id newColl = [self emptyCopyAs:[self species]];
  unsigned i, myCount = [self count];
  
  for (i = 0; i < start && i < myCount; i++)
    [newColl appendElement:[self elementAtIndex:i]];
  [newColl appendContentsOf:replaceCollection];
  for (i = stop+1; i < myCount; i++)
    [newColl appendElement:[self elementAtIndex:i]];
  return newColl;
}

- shallowCopyReplaceFrom: (unsigned)start to: (unsigned)stop 
    using: (id <Collecting>)replaceCollection
{
  id newColl = [self shallowCopy];
  unsigned index = start;
  BOOL cont = YES;
  void doIt (elt e)
    {
      [newColl replaceElementAtIndex: index with: e];
      cont = (index++ != stop);
    }
  [replaceCollection withElementsCall: doIt whileTrue: &cont];
  return newColl;
}

- shallowCopyInReverseAs: aCollectionClass
{
  id newColl = [self emptyCopyAs:aCollectionClass];
  void doIt(elt e)
    {
      [newColl appendElement:e];
    }
  [self withElementsInReverseCall:doIt];
  return self;
}


// ENUMERATING;

- (BOOL) getNextKey: (elt*)aKeyPtr content: (elt*)anElementPtr 
  withEnumState: (void**)enumState
{
  /* (unsigned)*enumState is the index of the element that will be returned */
  if (((unsigned)(*enumState)) > [self count]-1)
    return NO;
  *anElementPtr = [self elementAtIndex:((unsigned)*enumState)];
  *aKeyPtr = ((unsigned)*enumState);
  ((unsigned)(*enumState))++;
  return YES;
}

- (BOOL) getNextElement:(elt *)anElementPtr withEnumState: (void**)enumState
{
  /* (unsigned)*enumState is the index of the element that will be returned */
  if (((unsigned)(*enumState)) > [self count]-1)
    return NO;
  *anElementPtr = [self elementAtIndex:((unsigned)*enumState)];
  ((unsigned)(*enumState))++;
  return YES;
}

- (BOOL) getPrevElement:(elt *)anElementPtr withEnumState: (void**)enumState
{
  /* (unsigned)*enumState-1 is the index of the element 
     that will be returned */
  if (!(*enumState))
    (unsigned)(*enumState) = [self count]-1;
  else
    ((unsigned)(*enumState))--;
  *anElementPtr = [self elementAtIndex:((unsigned)(*enumState))];
  return YES;
}

- prevObject: (void**)enumState
{
  elt o;

  if ([self getPrevElement:&o withEnumState:enumState])
    return o.id_t;
  else
    return COLL_NO_OBJECT;
}
  
- withElementsInReverseCall: (void(*)(elt))aFunc;
{
  BOOL flag = NO;
  [self withElementsInReverseCall:aFunc whileTrue:&flag];
  return self;
}

- withObjectsInReverseCall: (void(*)(id))aFunc
{
  void doIt(elt e)
    {
      aFunc(e.id_t);
    }
  if (OBJECTS_REQUIRED_WARNING())
    return nil;
  return [self withElementsInReverseCall:doIt];
}

- withElementsInReverseCall: (void(*)(elt))aFunc whileTrue:(BOOL *)flag
{
  unsigned i;

  for (i = [self count]-1; *flag && i >= 0; i--)
    aFunc([self elementAtIndex:i]);
  return self;
}

- withObjectsInReverseCall: (void(*)(id))aFunc whileTrue:(BOOL *)flag
{
  void doIt(elt e)
    {
      aFunc(e.id_t);
    }
  if (OBJECTS_REQUIRED_WARNING())
    return nil;
  return [self withElementsInReverseCall:doIt whileTrue:flag];
}

- withObjectsInReversePerform: (SEL)aSel in: selObject
{
  id (*aSelImp)(id,SEL,id) = (id(*)(id,SEL,id))
    objc_msg_lookup(selObject, aSel);
  void doIt(elt e)
    {
      aSelImp(selObject, aSel, e.id_t);
    }

  if (OBJECTS_REQUIRED_WARNING())
    return nil;
  [self withElementsInReverseCall:doIt];
  return self;
}

- withObjectsInReversePerform: (SEL)aSel in: selObject with: argObject
{
  id (*aSelImp)(id,SEL,id,id) = (id(*)(id,SEL,id,id))
    objc_msg_lookup(selObject, aSel);
  void doIt(elt e)
    {
      aSelImp(selObject, aSel, e.id_t, argObject);
    }

  if (OBJECTS_REQUIRED_WARNING())
    return nil;
  [self withElementsInReverseCall:doIt];
  return self;
}

- makeObjectsPerformInReverse: (SEL)aSel
{
  void doIt(elt e)
    {
      [e.id_t perform:aSel];
    }
  if (OBJECTS_REQUIRED_WARNING())
    return nil;
  return [self withElementsInReverseCall:doIt];
}

- makeObjectsPerformInReverse: (SEL)aSel with: argObject
{
  void doIt(elt e)
    {
      [e.id_t perform:aSel with:argObject];
    }
  if (OBJECTS_REQUIRED_WARNING())
    return nil;
  return [self withElementsInReverseCall:doIt];
}

- withElementsCall: (void(*)(elt))aFunc whileTrue:(BOOL *)flag
{
  unsigned i;
  unsigned count = [self count];

  for (i = 0; *flag && i < count; i++)
    aFunc([self elementAtIndex:i]);
  return self;
}

- withKeysAndContentsCall: (void(*)(const elt,elt))aFunc 
    whileTrue: (BOOL *)flag
{
  unsigned index = 0;
  void doIt(elt e)
    {
      aFunc(index, e);
      index++;
    }
  [self withElementsCall:doIt];
  return self;
}

  
// SORTING;

- sortContentsByCalling: (int(*)(elt,elt))aFunc
{
  /* Ugly, horrible, inefficient, temporary. */
  id collCopy;
  void doIt(elt e)
    {
      [self sortAddElement:e byCalling:aFunc];
    }

  collCopy = [self shallowCopy];
  [self empty];
  [collCopy withElementsCall:doIt];
  [collCopy free];
  return self;
}

- sortAddElement: (elt)newElement byCalling: (int(*)(elt,elt))aFunc
{
  unsigned insertionIndex = 0;
  BOOL insertionNotFound = YES;
  void test(elt e)
    {
      if (aFunc(newElement, e) < 0)
	insertionNotFound = NO;
      else
	insertionIndex++;
    }
  [self withElementsCall:test whileTrue:&insertionNotFound];
  [self insertElement:newElement atIndex:insertionIndex];
  return self;
}

- sortContentsByPerforming: (SEL)aSortingSel
{
  int compare(elt e1, elt e2)
    {
      return (int)[e1.id_t perform:aSortingSel with:e2.id_t];
    }
  if (OBJECTS_REQUIRED_WARNING())
    return nil;
  [self sortContentsByCalling:compare];
  return self;
}

- sortContentsByPerforming: (SEL)aSortingSel in: selObject
{
  int (*aSortingSelImp)(id,SEL,id,id) = (int(*)(id,SEL,id,id))
    objc_msg_lookup(selObject, aSortingSel);
  int compare(elt e1, elt e2)
    {
      return aSortingSelImp(selObject, aSortingSel, e1.id_t, e2.id_t);
    }
  if (OBJECTS_REQUIRED_WARNING())
    return nil;
  return [self sortContentsByCalling:compare];
}

- sortAddObject: newObject byPerforming: (SEL)aSortingSel
{
  int compare(elt e1, elt e2)
    {
      return (int)[e1.id_t perform:aSortingSel with:e2.id_t];
    }
  if (OBJECTS_REQUIRED_WARNING())
    return nil;
  return [self sortAddElement:newObject byCalling:compare];
}

- sortAddObject: newObject byPerforming: (SEL)aSortingSel in: selObject
{
  int (*aSortingSelImp)(id,SEL,id,id) = (int(*)(id,SEL,id,id))
    objc_msg_lookup(selObject, aSortingSel);
  int compare(elt e1, elt e2)
    {
      return (int)aSortingSelImp(selObject, aSortingSel, 
				 e1.id_t, e2.id_t);
    }
  if (OBJECTS_REQUIRED_WARNING())
    return nil;
  return [self sortAddElement:newObject byCalling:compare];
}



// RELATION WITH KeyedCollection;

- insertElement: (elt)newContentElement atKey: (elt)aKey
{
  return [self insertElement:newContentElement atIndex:aKey.unsigned_int_t];
}

- (elt) replaceElementAtKey: (elt)aKey with: (elt)newContentElement
{
  return [self replaceElementAtIndex:aKey.unsigned_int_t 
	       with:newContentElement];
}

- (elt) removeElementAtKey: (elt)aKey
{
  return [self removeElementAtIndex:aKey.unsigned_int_t];
}

- (elt) elementAtKey: (elt)aKey
{
  return [self elementAtIndex:aKey.unsigned_int_t];
}

- (BOOL) includesKey: (elt)aKey
{
  return [self includesIndex:aKey.unsigned_int_t];
}

- printForDebugger
{
  void doIt(elt e)
    {
      [self printElement:e];
      printf(" ");
    }
  [self withElementsCall:doIt];
  printf(" :%s\n", [self name]);
  return self;
}

@end    


@implementation IndexedCollection (ErrorReporting)

- errorIndex: (unsigned)index beyondRange: (unsigned)over inMethod: (SEL)aSel
{
  [self warning:"in %s, index=%u out of range (< %u)",
	sel_get_name(aSel), index, over];
  return self;
}

@end
