
/*
 * Portable Object Compiler (c) 1997,98.  All Rights Reserved.
 * $Id$
 */

/*
 * 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 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 Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#include "config.h"
#include <assert.h>
#include <string.h>
#include "ordcltn.h"
#include "cltnseq.h"
#include "set.h"
#include "sequence.h"
#include "ascfiler.h"
#include "ocstring.h"
#if OBJC_BLOCKS
#include "Block.h"
#endif

#define DEFAULT_CAPACITY (16)

@implementation OrdCltn

/*****************************************************************************
 *
 * Creation
 *
 ****************************************************************************/

static void 
ptrinit(id *p, id q, int c)
{
  while (c--)
    *p++ = q;
}

static void 
init(objcol_t self, int n, int c)
{
  assert(0 <= n && n <= c);
  self->count = n;
  self->capacity = c;
  self->ptr = (id *) OC_Calloc(c * sizeof(id));
}

+ new
{
  return [self new:DEFAULT_CAPACITY];
}

+ new:(unsigned)n
{
  id newObject = [super new];

  init([newObject objcolvalue], 0, n);
  return newObject;
}

/*****************************************************************************
 *
 * Creating with contents.
 *
 ****************************************************************************/

+ with:(int)nArgs,...
{
  id newObject;

  /* use OC macros for porting to SunOS4 */
  OC_VA_LIST vp;

  newObject = [self new];

  /* #if 0 this piece of code if problems with stdarg
   * typically this means the driver is not configured with
   * the right -builtintype
   * or builtinfunction flags (because the macros might expand to these)
   * 
   * alternative solution: check the .P output (-retain) and 
   * do a setenv OBJCOPT -builtinfunction __builtin_foo
   * (and please let me know)
   */

#ifdef NSTDARG
  [self notImplemented];
#else
  OC_VA_START(vp, nArgs);
  while (nArgs-- > 0) {
    id anObject = OC_VA_ARG(vp, id);

    [newObject add:anObject];
  }
  OC_VA_END(vp);
#endif

  return newObject;
}

+ with:firstObject with:nextObject
{
  return [[[self new] add:firstObject] add:nextObject];
}

+ add:firstObject
{
  return [[self new] add:firstObject];
}

static void 
ptrcopy(id *p, id *q, int c)
{
  while (c--) {
    *p++ = *q++;
  }
}

static void 
copy(objcol_t dst, objcol_t src)
{
  init(dst, src->count, src->count);
  ptrcopy(dst->ptr, src->ptr, src->count);
}

- copy
{
  id aCopy = [super copy];

  copy([aCopy objcolvalue], (&value));
  return aCopy;
}

static void 
ptrdeepcopy(id *p, id *q, int c)
{
  while (c--) {
    id obj = *q++;

    *p++ = (obj) ? [obj deepCopy] : nil;
  }
}

static void 
deepcopy(objcol_t dst, objcol_t src)
{
  init(dst, src->count, src->count);
  ptrdeepcopy(dst->ptr, src->ptr, src->count);
}

- deepCopy
{
  /* not all Object implementations have |deepCopy| */
  /* so we send |copy| to super instead             */

  id aCopy = [super copy];

  deepcopy([aCopy objcolvalue], (&value));
  return aCopy;
}

static void 
empty(objcol_t self)
{
  ptrinit(self->ptr, nil, self->count);		/* not same as memset ! */
  self->count = 0;
}

- emptyYourself
{
  empty((&value));
  return self;
}

static void 
ptrclear(id *p, int c)
{
  while (c--) {
    id obj = *p;

    *p++ = (obj) ? [obj free] : nil;
  }
}

static void 
freecontents(objcol_t self)
{
  ptrclear(self->ptr, self->count);
  self->count = 0;
}

- freeContents
{
  freecontents((&value));
  return self;
}

static void 
ptrclearall(id *p, int c)
{
  while (c--) {
    id obj = *p;

    *p++ = (obj) ? [obj freeAll] : nil;
  }
}

static void 
freeall(objcol_t self)
{
  ptrclearall(self->ptr, self->count);
  self->count = 0;
}

- freeAll
{
  freeall((&value));
  return self;
}

static void 
clear(objcol_t self)
{
  self->count = 0;
  self->capacity = 0;
  OC_Free(self->ptr);
  self->ptr = NULL;
}

- free
{
  clear((&value));
  return [super free];
}

- release
{
  empty((&value));
  clear((&value));
  return [super release];
}

/*****************************************************************************
 *
 * Interrogation
 *
 ****************************************************************************/

- (objcol_t) objcolvalue
{
  return &value;
}

- (unsigned) size
{
  return (unsigned) ((&value)->count);
}

- (BOOL) isEmpty
{
  return (&value)->count == 0;
}

- (unsigned) lastOffset
{
  return (&value)->count - 1;
}

- eachElement
{
  id aCarrier = [CollectionSequence over:self];

  return [Sequence over:aCarrier];
}

static id 
ptrfirst(id *p, int n)
{
  return (n) ? p[0] : nil;
}

static id 
first(objcol_t self)
{
  return ptrfirst(self->ptr, self->count);
}

- firstElement
{
  return first((&value));
}

static id 
ptrlast(id *p, int n)
{
  return (n) ? p[n - 1] : nil;
}

static id 
last(objcol_t self)
{
  return ptrlast(self->ptr, self->count);
}

- lastElement
{
  return last((&value));
}

/*****************************************************************************
 *
 * Comparing
 *
 ****************************************************************************/

static unsigned 
ptrhash(id *p, int n)
{
  unsigned code = n;

  while (n--) {
    code ^= [*p++ hash];
  }
  return code;
}

static unsigned 
hashcontents(objcol_t a)
{
  return ptrhash(a->ptr, a->count);
}

- (unsigned) hash
{
  return hashcontents(&value);
}

static BOOL 
ptreq(id *p, id *q, int n)
{
  while (n--) {
    if (![*p++ isEqual:*q++]) {
      return NO;
    }
  }
  return YES;
}

static BOOL 
eq(objcol_t a, objcol_t b)
{
  if (a->count == b->count) {
    return ptreq(a->ptr, b->ptr, a->count);
  } else {
    return NO;
  }
}

- (BOOL) isEqual:aCltn
{
  return (self == aCltn) ? YES : eq((&value), [aCltn objcolvalue]);
}

/*****************************************************************************
 *
 * Adding
 *
 ****************************************************************************/

static BOOL 
needsexpand(objcol_t self)
{
  assert(self->count <= self->capacity);
  return self->count == self->capacity;
}

static void 
expand(objcol_t self)
{
  self->capacity = 1 + 2 * self->capacity;
  self->ptr = (id *) OC_Realloc(self->ptr, sizeof(id) * self->capacity);
  memset(self->ptr + self->count, 0, sizeof(id) * (self->capacity - self->count));
}

static int 
ptraddlast(id *p, id obj, int n)
{
  p[n] = obj;
  return n + 1;
}

static void 
addlast(objcol_t self, id obj)
{
  if (needsexpand(self)) {
    expand(self);
  }
  self->count = ptraddlast(self->ptr, obj, self->count);
}

- add:anObject
{
  if (anObject) {
    addlast((&value), anObject);
    return self;
  } else {
    return self;
  }
}

- addYourself
{
  int i, n = [self size];

  for (i = 0; i < n; i++)
    [self add:[self at:i]];
  return self;
}

static int 
ptraddfirst(id *p, id obj, int n)
{
  int m = n;

  p += n;
  while (m--) {
    id *q = p - 1;

    *p = *q;
    p = q;
  }
  *p = obj;
  return n + 1;
}

static void 
addfirst(objcol_t self, id obj)
{
  if (needsexpand(self)) {
    expand(self);
  }
  self->count = ptraddfirst(self->ptr, obj, self->count);
}

- addFirst:newObject
{
  if (newObject) {
    addfirst((&value), newObject);
    return self;
  } else {
    return self;
  }
}

- addLast:newObject
{
  return [self add:newObject];
}

- addIfAbsent:anObject
{
  if ([self find:anObject] == nil) {
    [self add:anObject];
  }
  return self;
}

- addIfAbsentMatching:anObject
{
  if ([self findMatching:anObject] == nil) {
    [self add:anObject];
  }
  return self;
}

/*****************************************************************************
 *
 * Insertion
 *
 ****************************************************************************/

static int 
ptrinsert(id *p, id obj, int i, int n)
{
  if (i == n) {
    return ptraddlast(p, obj, n);
  } else {
    return i + ptraddfirst(p + i, obj, n - i);
  }
}

static void 
insert(objcol_t self, id obj, int i)
{
  if (needsexpand(self)) {
    expand(self);
  }
  self->count = ptrinsert(self->ptr, obj, i, self->count);
}

- boundserror
{
  return [self error:"Offset out of bounds."];
}

- at:(unsigned )anOffset insert:anObject
{
  if (anObject) {
    if (anOffset > [self size]) {
      [self boundserror];
    }
    insert((&value), anObject, (int) anOffset);
    return self;
  } else {
    return self;
  }
}

- couldntfind
{
  return [self error:"Could not find object."];
}

- insert:newObject after:oldObject
{
  if (newObject) {
    unsigned offset = [self offsetOf:oldObject];

    if (offset == (unsigned) -1) {
      [self couldntfind];
    }
    return [self at:offset + 1 insert:newObject];
  } else {
    return self;
  }
}

- insert:newObject before:oldObject
{
  if (newObject) {
    unsigned offset = [self offsetOf:oldObject];

    if (offset == (unsigned) -1) {
      [self couldntfind];
    }
    return [self at:offset - 1 insert:newObject];
  } else {
    return self;
  }
}

/*****************************************************************************
 *
 * Relative Accessing
 *
 ****************************************************************************/

- after:anObject
{
  unsigned offset = [self offsetOf:anObject];

  if (offset == (unsigned) -1) {
    return [self couldntfind];
  }
  return (offset == [self lastOffset]) ? nil : [self at:offset + 1];
}

- before:anObject
{
  unsigned offset = [self offsetOf:anObject];

  if (offset == (unsigned) -1) {
    return [self couldntfind];
  }
  return (offset == 0) ? nil : [self at:offset - 1];
}

static id 
at(objcol_t self, int i)
{
  assert(0 <= i && i < self->count);
  return (self->ptr) [i];
}

- at:(unsigned )anOffset
{
  if (anOffset >= [self size]) {
    [self boundserror];
  }
  return at((&value), anOffset);
}

static id 
atput(objcol_t self, int i, id obj)
{
  id tmp;

  assert(0 <= i && i < self->count);
  tmp = (self->ptr) [i];
  (self->ptr) [i] = obj;
  return tmp;
}

- at:(unsigned )anOffset put:anObject
{
  if (anOffset >= [self size]) {
    [self boundserror];
  }
  return atput((&value), anOffset, anObject);
}

/*****************************************************************************
 *
 * Removing
 *
 ****************************************************************************/

static id 
ptrremovefirst(id *p, int n)
{
  id obj = *p;

  n--;
  while (n--) {
    id *q = p + 1;

    *p = *q;
    p = q;
  }
  *p = nil;
  return obj;
}

static id 
removefirst(objcol_t self)
{
  if (self->count) {
    id obj = ptrremovefirst(self->ptr, self->count);

    self->count--;
    return obj;
  } else {
    return nil;
  }
}

- removeFirst
{
  return removefirst((&value));
}

static id 
ptrremove(id *p)
{
  id obj = *p;

  *p = nil;
  return obj;
}

static id 
removelast(objcol_t self)
{
  if (self->count) {
    id obj = ptrremove(self->ptr + self->count - 1);

    self->count--;
    return obj;
  } else {
    return nil;
  }
}

- removeLast
{
  return removelast((&value));
}

static id 
ptrremoveat(id *p, int i, int n)
{
  if (i == n - 1) {
    return ptrremove(p + n - 1);
  } else {
    return ptrremovefirst(p + i, n - i);
  }
}

static id 
removeat(objcol_t self, int i)
{
  if (self->count) {
    id obj = ptrremoveat(self->ptr, i, self->count);

    self->count--;
    return obj;
  } else {
    return nil;
  }
}

- removeAt:(unsigned )anOffset
{
  if (anOffset >= [self size]) {
    [self boundserror];
  }
  return removeat((&value), anOffset);
}

- removeAtIndex:(unsigned )anOffset
{
  return [self removeAt:anOffset];
}

- remove:oldObject
{
  unsigned offset = [self offsetOf:oldObject];

  if (offset == (unsigned) -1) {
    return nil;
  }
  return [self removeAt:offset];
}

#if OBJC_BLOCKS
- remove:oldObject ifAbsent:exceptionBlock
{
  id anObject = [self remove:oldObject];

  return (anObject) ? anObject : [exceptionBlock value];
}
#endif				/* OBJC_BLOCKS */

/*****************************************************************************
 *
 * Testing Contents
 *
 ****************************************************************************/

- (BOOL) includesAllOf:aCltn
{
  if (self == aCltn) {
    return YES;
  } else {
    BOOL res = YES;
    id e, seq = [aCltn eachElement];

    while ((e = [seq next])) {
      if (![self includes:e]) {
	res = NO;
	goto done;
      }
    }
  done:
#ifndef OBJC_REFCNT
    [seq free];
#endif
    return res;
  }
}

- (BOOL) includesAnyOf:aCltn
{
  if (self == aCltn) {
    return YES;
  } else {
    BOOL res = NO;
    id e, seq = [aCltn eachElement];

    while ((e = [seq next])) {
      if ([self includes:e]) {
	res = YES;
	goto done;
      }
    }
  done:
#ifndef OBJC_REFCNT
    [seq free];
#endif
    return res;
  }
}

/*****************************************************************************
 *
 * Adding and Removing Contents
 *
 ****************************************************************************/

- addAll:aCltn
{
  if (self == aCltn) {
    [self addYourself];
  } else {
    id e, seq;

    seq = [aCltn eachElement];
    while ((e = [seq next])) {
      [self add:e];
    }
#ifndef OBJC_REFCNT
    seq = [seq free];
#endif
  }

  return self;
}

- addContentsOf:aCltn
{
  return [self addAll:aCltn];
}

- addContentsTo:aCltn
{
  return [aCltn addAll:self];
}

- removeAll:aCltn
{
  if (self == aCltn) {
    [self emptyYourself];
  } else {
    id e, seq;

    seq = [aCltn eachElement];
    while ((e = [seq next])) {
      [self remove:e];
    }
#ifndef OBJC_REFCNT
    seq = [seq free];
#endif
  }

  return self;
}

- removeContentsFrom:aCltn
{
  return [aCltn removeAll:self];
}

- removeContentsOf:aCltn
{
  return [self removeAll:aCltn];
}

/*****************************************************************************
 *
 * Combining
 *
 ****************************************************************************/

- intersection:bag
{
  if (self == bag) {
    return [self copy];
  } else {
    id anElement, elements;
    id intersection = [isa new];

    elements = [self eachElement];
    while ((anElement = [elements next])) {
      if ([bag find:anElement])
	[intersection add:anElement];
    }
#ifndef OBJC_REFCNT
    elements = [elements free];
#endif

    return intersection;
  }
}

- union:bag
{
  if (self == bag) {
    return [self copy];
  } else {
    return [[self copy] addAll:bag];
  }
}

- difference:bag
{
  if (self == bag) {
    return [isa new];
  } else {
    return [[self copy] removeAll:bag];
  }
}

/*****************************************************************************
 *
 * Converting to different type of collection.
 *
 ****************************************************************************/

- asSet
{
  /* Stepstone isKindOf takes a id but class returns SHR */
  if ([self isKindOf:(id) [Set class]]) {
    return self;
  } else {
    return [[Set new] addAll:self];
  }
}

- asOrdCltn
{
  /* Stepstone isKindOf takes a id but class returns SHR */
  if ([self isKindOf:(id) [OrdCltn class]]) {
    return self;
  } else {
    return [[OrdCltn new] addAll:self];
  }
}

/*****************************************************************************
 *
 * Block methods
 *
 ****************************************************************************/

#if OBJC_BLOCKS
- detect:aBlock
{
  id e, seq;

  seq = [self eachElement];

  while ((e = [seq next])) {
    if (([aBlock value:e])) {
#ifndef OBJC_REFCNT
      seq = [seq free];
#endif
      return e;
    }
  }

#ifndef OBJC_REFCNT
  seq = [seq free];
#endif
  return nil;
}

- detect:aBlock ifNone:noneBlock
{
  id e, seq;

  seq = [self eachElement];

  while ((e = [seq next])) {
    if (([aBlock value:e])) {
#ifndef OBJC_REFCNT
      seq = [seq free];
#endif
      return e;
    }
  }

#ifndef OBJC_REFCNT
  seq = [seq free];
#endif
  return [noneBlock value];
}

- select:testBlock
{
  id e, seq;
  id newObject = [isa new];

  seq = [self eachElement];

  while ((e = [seq next])) {
    if (([testBlock value:e])) {
      [newObject add:e];
    }
  }

#ifndef OBJC_REFCNT
  seq = [seq free];
#endif
  return newObject;
}

- reject:testBlock
{
  id e, seq;
  id newObject = [isa new];

  seq = [self eachElement];

  while ((e = [seq next])) {
    if (!([testBlock value:e])) {
      [newObject add:e];
    }
  }

#ifndef OBJC_REFCNT
  seq = [seq free];
#endif
  return newObject;
}

- collect:transformBlock
{
  id e, seq;
  id newObject = [isa new];

  seq = [self eachElement];

  while ((e = [seq next])) {
    id anImage = [transformBlock value:e];

    if (anImage) {
      [newObject add:anImage];
    }
  }

#ifndef OBJC_REFCNT
  seq = [seq free];
#endif
  return newObject;
}

- (unsigned) count:aBlock
{
  id e, seq;
  unsigned c = 0;

  seq = [self eachElement];
  while ((e = [seq next])) {
    if ([aBlock value:e]) {
      c++;
    }
  }
#ifndef OBJC_REFCNT
  seq = [seq free];
#endif

  return c;
}

#endif				/* OBJC_BLOCKS */

/*****************************************************************************
 *
 * Making elements perform actions.
 *
 ****************************************************************************/

- elementsPerform:(SEL)aSelector
{
  id e, seq;

  seq = [self eachElement];
  while ((e = [seq next])) {
    [e perform:aSelector];
  }
#ifndef OBJC_REFCNT
  seq = [seq free];
#endif

  return self;
}

- elementsPerform:(SEL)aSelector with:anObject
{
  id e, seq;

  seq = [self eachElement];
  while ((e = [seq next])) {
    [e perform:aSelector with:anObject];
  }
#ifndef OBJC_REFCNT
  seq = [seq free];
#endif

  return self;
}

- elementsPerform:(SEL)aSelector with:anObject with:otherObject
{
  id e, seq;

  seq = [self eachElement];
  while ((e = [seq next])) {
    [e perform:aSelector with:anObject with:otherObject];
  }
#ifndef OBJC_REFCNT
  seq = [seq free];
#endif

  return self;
}

- elementsPerform:(SEL)aSelector with:anObject with:otherObject with:thirdObj
{
  id e, seq;

  seq = [self eachElement];
  while ((e = [seq next])) {
    [e perform:aSelector with:anObject with:otherObject with:thirdObj];
  }
#ifndef OBJC_REFCNT
  seq = [seq free];
#endif

  return self;
}
/*****************************************************************************
 *
 * Do Blocks  (also provide a -reverseDo: here)
 *
 ****************************************************************************/

#if OBJC_BLOCKS
- do:aBlock
{
  int i = 0;
  int n = [self size];

  for (i = 0; i < n; i++) {
    [aBlock value:[self at:i]];
  }
  return self;
}

- do:aBlock until:(BOOL*)flag
{
  int i = 0;
  int n = [self size];

  for (i = 0; i < n; i++) {
    [aBlock value:[self at:i]];
    if (*flag)
      break;
  }
  return self;
}

- reverseDo:aBlock
{
  unsigned n = [self size];

  while (n--) {
    [aBlock value:[self at:n]];
  }
  return self;
}
#endif				/* OBJC_BLOCKS */

/*****************************************************************************
 *
 * Locating
 *
 ****************************************************************************/

static id 
ptrfind(id *p, id obj, int n)
{
  int i;

  for (i = 0; i < n; i++) {
    if (p[i] == obj) {
      return p[i];
    }
  }
  return nil;
}

static id 
find(objcol_t self, id obj)
{
  return ptrfind(self->ptr, obj, self->count);
}

- find:anObject
{
  return find((&value), anObject);
}

static id 
ptrfindmatch(id *p, id obj, int n)
{
  int i;

  for (i = 0; i < n; i++) {
    if (p[i] == obj || [p[i] isEqual:obj]) {
      return p[i];
    }
  }
  return nil;
}

static id 
findmatch(objcol_t self, id obj)
{
  return ptrfindmatch(self->ptr, obj, self->count);
}

- findMatching:anObject
{
  return findmatch((&value), anObject);
}

- (BOOL) includes:anObject
{
  return [self findMatching:anObject] == nil;
}

static id 
ptrfindstr(id *p, STR s, int n)
{
  int i;

  for (i = 0; i < n; i++) {
    if ([*p++ isEqualSTR:s]) {
      return *p;
    }
  }
  return nil;
}

static id 
findstr(objcol_t self, STR s)
{
  return ptrfindstr(self->ptr, s, self->count);
}

- findSTR:(STR )aString
{
  return findstr((&value), aString);
}

- (BOOL) contains:anObject
{
  return [self find:anObject] != nil;
}

static int 
ptroffset(id *p, id obj, int n)
{
  int i;

  for (i = 0; i < n; i++) {
    if (*p++ == obj) {
      return i;
    }
  }
  return -1;
}

static int 
offset(objcol_t self, id obj)
{
  return ptroffset(self->ptr, obj, self->count);
}

- (unsigned) offsetOf:anObject
{
  return (unsigned) offset((&value), anObject);
}

/*****************************************************************************
 *
 * Printing
 *
 ****************************************************************************/

- printOn:(IOD)aFile
{
  int i, n = [self size];

  for (i = 0; i < n; i++) {
    id s = [self at:i];

    [s printOn:aFile];
    fprintf(aFile, "\n");
  }
  return self;
}

/*****************************************************************************
 *
 * Archiving
 *
 ****************************************************************************/

#ifdef __PORTABLE_OBJC__
static void 
ptrfileout(id aFiler, id *a, int n)
{
  while (n--) {
    [aFiler fileOut:a++ type:'@'];
  }
}

static void 
ptrfilein(id aFiler, id *a, int n)
{
  while (n--) {
    [aFiler fileIn:a++ type:'@'];
  }
}

static void 
fileout(id aFiler, objcol_t self)
{
  [aFiler fileOut:&self->count type:'i'];
  [aFiler fileOut:&self->capacity type:'i'];
  ptrfileout(aFiler, self->ptr, self->count);
}

static void 
filein(id aFiler, objcol_t self)
{
  int n, c;

  [aFiler fileIn:&n type:'i'];
  [aFiler fileIn:&c type:'i'];
  init(self, n, c);
  ptrfilein(aFiler, self->ptr, n);
}

- fileOutOn:aFiler
{
  [super fileOutOn:aFiler];
  fileout(aFiler, &value);
  return self;
}

- fileInFrom:aFiler
{
  [super fileInFrom:aFiler];
  filein(aFiler, &value);
  return self;
}

#endif				/* __PORTABLE_OBJC__ */

@end
 
