//Paul E Johnson Sept. 14, 2000 GPL copyright
//AVLTRSet is a Set (and ordered set) class replacement for Swarm.
//avltr is "right threaded" avl tree. Better if you need "next" support.
//requires a swarm 2000-09-10 or better

#import <simtools.h> // initSwarm
#import <collections.h> // Array
#import <defobj/Create.h> // CreateDrop
#import <objectbase/Swarm.h> // Swarm
#import <defobj/defalloc.h> // getZone
#import <objectbase/SwarmObject.h>  //superclass of AVLtree

#include <collections/Collection.h> 

#include <misc/avl.h> 
#include <misc/avltr.h> //for the AVLtree


#define COUNT 10



     
typedef int (*compare_avl_t) (const void *, const void *,void *);

//@interface AVLTRSet: Collection_any 
@interface AVLTRSet: SwarmObject
{
  avltr_tree * aTree;
  compare_avl_t  compareFunc;
}

+ createBegin: aZone;

+ createBegin:  (int (*)(const void*,const void*,void*)) compareFunc  Param: (void *) param Zone: aZone;

- setCompareFunction: (compare_avl_t) compareFunction;

- setCompareCStrings;

- setCompareIDs;

- setCompareIntegers;

- setCompareUnsignedIntegers;

- createEnd;

- (int) count;

- (unsigned) getCount;

-(BOOL) add: anObject;

- (id *) replace: anObject;

- (BOOL) contains: aKey;

- (BOOL) containsKey: aKey;

- at:  aKey;

- (BOOL)at: aKey memberSlot: (id **)memptr;


- remove: aKey;

- removeKey: aKey;

- (void)forEach: (SEL)aSelector;

- (void)forEach: (SEL)aSelector : arg1;

- (void)forEach: (SEL)aSelector : arg1 : arg2;

- (void)forEach: (SEL)aSelector : arg1 : arg2 : arg3;

- (void)forEachKey: (SEL)aSelector;

- (void)forEachKey: (SEL)aSelector : arg1;

- (void)forEachKey: (SEL)aSelector : arg1 : arg2;

- (void)forEachKey: (SEL)aSelector : arg1 : arg2 : arg3;

- begin: aZone;



- createIndex: (id <Zone>)aZone fromMember: anObject ;

- (void) drop;

- removeAll;

- deleteAll;


//New thing I made up because I didn't like the Swarm's Set default behavior
- forcefulReplace: anObject;

-(void)  walk: (void (*)(void*,void*)) aFunction Param: (void *) PARAM;

- traverse: (avltr_traverser *) travPtr;

- (avltr_tree *) getTree;

@end


@interface AVLTRSetIndex_c: Index_any <KeyedCollectionIndex>
{
  int offset;
  void ** traverser;
  void *currentObject;
  id <Symbol> position;
@public
  avltr_tree * tree; 
}
- init;
- next;
- prev;
- get;
- replace: anObject;
- remove;
- (id <Symbol>)getLoc;
- (void)setLoc: (id <Symbol>)locSymbol;
- (int)getOffset;
- setOffset: (unsigned)targetOffset;

//- (void)mapAllocations: (mapalloc_t)mapalloc;

@end



@implementation AVLTRSet

//compare functions for AVLtrees must take 3 args, 2 objects and 1 optional parameter.
static int
compare_object_ids (const void *A, const void *B, void *PARAM)
{
  int a = (unsigned) A;
  int b = (unsigned) B;

  if (a  < b )
    return -1;

  return a > b;
}

static int
compare_integers (const void * val1, const void *val2, void *PARAM)
{
  if ((PTRINT) val1 < (PTRINT) val2)
    return -1;
  return ((PTRINT) val1 > (PTRINT) val2);
}

static int
compare_unsigned (const void * val1, const void * val2, void * PARAM)
{
  if ((PTRUINT) val1 < (PTRUINT) val2)
    return -1;
  return ((PTRUINT) val1 > (PTRUINT) val2);
}

static int
compare_cstrings (const void* val1, const void * val2, void * PARAM)
{
  return strcmp ((const char *)val1, (const char *)val2);
}

PHASE(Creating)

+createBegin: aZone  
{
  AVLTRSet * obj; 
  obj = [super createBegin: aZone];
  return obj;
}

//It is mandatory to choose one of these compare functions at create time.

- setCompareFunction: (compare_avl_t) compareFunction
{
  compareFunc = compareFunction;
  aTree = avltr_create ( compareFunc, NULL);
  return self;
}

- setCompareCStrings
{
  compareFunc = compare_cstrings;
  aTree = avltr_create ( compareFunc, NULL);
  return self;
}

- setCompareIDs
{
  compareFunc = compare_object_ids;
  aTree = avltr_create ( compareFunc, NULL);
  return self;
}

- setCompareIntegers
{
  compareFunc = compare_integers;
  aTree = avltr_create ( compareFunc, NULL);
  return self;
}

- setCompareUnsignedIntegers
{
  compareFunc = compare_unsigned;
  aTree = avltr_create ( compareFunc, NULL);
  return self;
}

//Consider instead to use default comparison of IDs. That makes it a Set.
-createEnd
{
  if ( aTree == NULL )
    raiseEvent (InvalidArgument, "You Forgot to set a compare function");
  return [super createEnd];
}

//convenience method
+createBegin: (int (*)(const void*,const void*,void*)) comparFunc  Param: (void *) param Zone: aZone
{
  AVLTRSet * obj; 
  obj = [super createBegin: aZone];
  obj->aTree = avltr_create (comparFunc, param);
  return obj;
}

PHASE(Using)

//Methods in Set_c have to be implemented, so here they are:

//JUST a shallow copy! Note passing NULL as 2nd argument of avltr_copy
- copy: aZone
{
  AVLTRSet *newSet;
  newSet = [aZone copyIVars: self];
  newSet->aTree = avltr_copy (aTree,NULL);
  return newSet;
}

- (int) count
{
  return avltr_count(aTree);
}

- (unsigned) getCount
{
  return (unsigned)  avltr_count(aTree);
}


//add an object if it is not currently in the set
//if anObject is in the set, then return that value.
//does nothing and returns NO otherwise
-(BOOL) add: anObject
  {
    id value = avltr_insert (aTree, anObject );//uses integer keys;
    if (value == NULL)
      return YES;
    else return NO;
  }

// if anObject matching key exists, replace it, return old one.
// otherwise do nothing and return nil
- (id *) replace: anObject
{
  void * value;
  if (( value = avltr_find(aTree, anObject) ))
    {
      avltr_replace (aTree, anObject);
    }
  return value; //have to worry about NULL being different from nil?
}


- (BOOL) contains: aKey
{
  if (avltr_find(aTree, aKey))
    return YES;
  else
    return NO;
}

- (BOOL)containsKey: aKey
{
  return [self contains: aKey];
}

//Note: There is no way to have more than one object with that key, so the
//at: method does not make any effort to do the Swarm thing and collect
//all objects with a key.

- at: aKey
{
  void ** value = avltr_find(aTree, aKey);
  return  *value;
}

- (BOOL)at: aKey memberSlot: (id **)memptr
{
  raiseEvent (NotImplemented, nil);
  return NO;
}

- remove: aKey
{
  return avltr_delete(aTree, aKey);
}

- removeKey: aKey
{
  return avltr_delete(aTree, aKey);
}

- (void)forEach: (SEL)aSelector
{
  void ** anObjectPtr;
  for ( anObjectPtr = avltr_next (aTree, NULL); anObjectPtr != NULL; anObjectPtr = avltr_next(aTree, anObjectPtr))
    {
      id anObject = * anObjectPtr;
      [anObject perform: aSelector];
    }
}

- (void)forEach: (SEL)aSelector : arg1
{
  void ** anObjectPtr;
  for ( anObjectPtr = avltr_next (aTree, NULL); anObjectPtr != NULL; anObjectPtr = avltr_next(aTree, anObjectPtr))
    {
      id anObject = * anObjectPtr;
      [anObject perform: aSelector with: arg1];
    }
}

- (void)forEach: (SEL)aSelector : arg1 : arg2
{ 
 void ** anObjectPtr;
  for ( anObjectPtr = avltr_next (aTree, NULL); anObjectPtr != NULL; anObjectPtr = avltr_next(aTree, anObjectPtr))
    {
      id anObject = * anObjectPtr;
      [anObject perform: aSelector with: arg1 with: arg2];
    }
}

- (void)forEach: (SEL)aSelector : arg1 : arg2 : arg3
{
 void ** anObjectPtr;
  for ( anObjectPtr = avltr_next (aTree, NULL); anObjectPtr != NULL; anObjectPtr = avltr_next(aTree, anObjectPtr))
    {
      id anObject = * anObjectPtr;
      [anObject perform: aSelector with: arg1 with: arg2 with: arg3];
    }
}


- (void)forEachKey: (SEL)aSelector
{
  [self forEach: (SEL)aSelector];
}
- (void)forEachKey: (SEL)aSelector : arg1
{
  [self forEach: (SEL)aSelector: arg1];
}
- (void)forEachKey: (SEL)aSelector : arg1 : arg2
{
  [self forEach: (SEL)aSelector: arg1 : arg2];
}
- (void)forEachKey: (SEL)aSelector : arg1 : arg2 : arg3
{
  [self forEach: (SEL)aSelector: arg1 : arg2];
}


-begin: aZone
{
  AVLTRSetIndex_c * newIndex;

  newIndex = [aZone allocIVars: [AVLTRSetIndex_c self]];
  newIndex->tree = aTree;
  //  newIndex->collection = self;
  [newIndex init];
  return newIndex;
}

- createIndex: (id <Zone>)aZone fromMember: anObject 
{
  raiseEvent(WarningMessage,"Not Implemented");
  return self;
}


- (void) drop
{
  avltr_destroy(aTree,NULL); //does not drop objects tree refers to
  [super drop];
}

- removeAll
{
  avltr_destroy(aTree,NULL);
  return self;
}


-  deleteAll
{
  avltr_free(aTree);  //drops objects in the tree and tree too
  return self;
}


//  - (void) mapAllocations: (mapalloc_t)mapalloc
//  {
//    mapObject (mapalloc, list);
//  }




// Super power insert. Inserts if object does not exist, replaces if object does.
// returns object being replaced if there is one.
- forcefulReplace: anObject
  {
    id value = avltr_replace (aTree, anObject );//uses integer keys;
    if (value != NULL) 
      return value;
    else return nil;
  }


-(void)  walk: (void (*)(void*,void*)) aFunction Param: (void *) PARAM
{
  avltr_walk(aTree , aFunction, NULL);
}


- traverse: (avltr_traverser *) travPtr
{
  id anObject;

  anObject = avltr_traverse (aTree, travPtr) ;
  
 return anObject;
}

- (avltr_tree *) getTree
{
  return aTree;
}


@end


@implementation AVLTRSetIndex_c

- next
{
  traverser =  avltr_next (tree, traverser);
  if (traverser != NULL)
    {
      currentObject = *traverser;
      position = Member;
    }
  else
    {
      position = End;
      currentObject = NULL;
    }
  offset ++ ;
  return currentObject ; //returns a null at the end of the tree
}

- prev
{
  int i;
  int currentOffset = offset;
  void * anObject;

  [self init];
  for (i=0; i < currentOffset; i++)
    {
      anObject = [self next];
    }
  printf("previousOffset was %d, new offset is %d \n",currentOffset, offset);
 
  return  anObject;
}

- get
{
  return  currentObject;
}

- replace: anObject
{
  void ** valuePtr; 
  void * removedObject = NULL;
  if ( (valuePtr = avltr_find(tree, anObject) ) )
    {
      void * anObject = *valuePtr;
      removedObject = avltr_replace (tree, anObject);
    }
  return removedObject;  //removed object
}

- remove
{
  id removed;
  //  int currentOffset = offset;
 
  removed = avltr_delete ( tree,  currentObject );
  offset = offset - 1 ;
  //following not needed for avltr?
//    [self init];
//    while ( offset < currentOffset-1 )
//      {
//        [self next];  //step up to object before removal
//      }
  return removed;
}


- init
{
  traverser = NULL;
  offset = -1;
  currentObject = NULL;
  return self;
}

- (id <Symbol>)getLoc
{
  if (offset == -1) return Start;
  else
    return position;
}

- (void)setLoc: (id <Symbol>)locSymbol
{
  if ( locSymbol == Start)
    [self init];
  if ( locSymbol == End)  //this is silly, nobody should ever do it. 
    while (avltr_next(tree, traverser ));
}

- (int)getOffset
{
  return offset ;
}

- setOffset: (unsigned)targetOffset
{
  [self init];
  do
    {
      [self next];
    } while ( offset < targetOffset );
  return  currentObject;
}

// I don't understand what this is for, but Set_Index has it...
//  - (void) mapAllocations: (mapalloc_t)mapalloc
//  {
//    mapObject (mapalloc, listIndex);
//  }



//Methods from "Index_any" that do not have meaning in a Set
- findNext: anObject
{
  raiseEvent (NotImplemented, nil);
  return self;
}

- findPrev: anObject
{
  raiseEvent (NotImplemented, nil);
  return self;
}


@end



@interface Agent: CreateDrop
{
  id <Array> population;
  unsigned personalNumber;
}
+ create: (id <Zone>)aZone setPopulation: (id <Array>)thePopulation setPIN: (unsigned)pin;

- print;

- (int) getPIN;

@end



@implementation Agent
+ create: (id <Zone>)aZone setPopulation: (id <Array>)thePopulation setPIN: (unsigned)pin
{
  Agent *obj = [self createBegin: aZone];
  obj->population = thePopulation;
  obj->personalNumber = pin;
  return [obj createEnd];
}

- print
{
  fprintf(stderr,"Hello, from Agent %d \n",personalNumber);
  return self;
}


- (int) getPIN
{
  return personalNumber;
}

@end

@interface ModelSwarm: Swarm
{
  id <Array> population;
  AVLTRSet * myTree1;
  AVLTRSet *  myTree2;

}
- buildObjects;
@end

@implementation ModelSwarm

//here is a user-specified comparison function. Note 3 args!
static int
compare_agent_position (const void *A, const void *B, void *PARAM)
{
  int a =  [(const id) A getPIN];
  int b =  [(const id) B getPIN];
  
  if (a  < b )
    return -1;

  return a> b;
}

static void
print_node ( void *A, void *PARAM)
{
  id a = (id) A;
  [a print];
}


- buildObjects
{
  unsigned i;
  id anAgent;

  [super buildObjects];
  population = [Array create: globalZone setCount: COUNT];

  myTree1 = [AVLTRSet createBegin: self ];
  [myTree1 setCompareIDs];
  myTree1= [myTree1 createEnd]; 

  myTree2 = [ AVLTRSet createBegin: self];
  [myTree2 setCompareFunction: compare_agent_position ] ; 
  myTree2 = [myTree2 createEnd] ; //[AVLtree create

  for (i = 0; i < COUNT; i++)
    {
      BOOL returnValue1;
      BOOL returnValue2;
      anAgent= [Agent create: self setPopulation: population setPIN: i];
      [population atOffset: i put: anAgent];

      returnValue1 = [myTree1 add: anAgent];//uses ID keys

      returnValue2 = [myTree2 add: anAgent];//retrieves node or inserts if key not in tree already  this amounts to a "set"
      printf("In creation loop, count %i \n", i);
      [[myTree1 at: anAgent] print];
    }

  {
    avltr_tree * tree1 = [myTree1 getTree];
    printf ("MyTree1 has %d \n \n", avltr_count(tree1));
    avltr_walk ( tree1, print_node, NULL); 

  }

   return self;
}

- (void)test
{
   int i;
   id anAgent=nil;
   id index1;
   id index2;
  

   printf("Now, use the wrapper around avltr_walk to march through the tree1\n");
   printf("This is supposed to start with the smallest key and move on up.\n");
   
   [myTree1 walk: print_node Param: NULL];
   
   printf("here is the object at the first offset in myTree2 \n");
   anAgent = [population atOffset: 1];
   [[myTree2 at: anAgent] print];

   printf("myTree1 for the agent that is in population offset 3 \n");
   anAgent = [population atOffset: 3];
   [[myTree1 at: anAgent] print];

   printf("Now do same with forEach and print \n");
   [myTree1 forEach: M(print)];


  anAgent = nil;
  printf("Now, go forwards through the tree1 with a for loop that uses   \n");
  printf("at: aKey, where the value of the agent itself from [population atOffset:i] as the key  \n");

  for (i = 0; i< COUNT; i++)
    {
      id outputAgent=nil;
      anAgent =  [population atOffset: i];
      outputAgent= [myTree1 at: anAgent];
    }

  printf("Now, go backwards through the tree2 with a for loop\n");

  for (i = 0; i< COUNT; i++)
    {
      id outputAgent = nil;
      anAgent = [population atOffset: COUNT-i-1];
      outputAgent = [myTree2 at: anAgent];
      [outputAgent print];
    }

    printf ("Now, grab the agent 5th (index value=4) from the tree1 by asking for it by name \n");
    anAgent=nil;
  
    anAgent = [myTree1 at: [population atOffset: 4]];
    [anAgent print];

    printf ("Create a swarm index for the trees \n");
    index1 = [myTree1 begin: self];
    index2 = [myTree2 begin: self];

    printf ("use index1 next 7 times, to step up through object 6 \n");
    for ( i = 0; i < 7; i ++ )
      {
	anAgent = [index1 next];
	[anAgent print];
      }

    printf (" Now delete the 5th agent from the tree1 and walk it\n");
    [myTree1 removeKey: [population atOffset: 4]];

    [myTree1 walk: print_node Param: NULL];

    printf ("Observe that the 5th object still exists \n"); 
    printf ("but it is no longer pointed to by an element in the AVLtree \n");

    printf ("now confirm the index is still valid: it should begin at agent 7, who is next \n");
    for ( anAgent = [index1 next]; [index1 getLoc]==Member; anAgent = [index1 next])
      {
	int offset;
	offset = [index1 getOffset];
	printf ("Offset reported by index1 is %d \n", offset);
	[anAgent print];
      }

    printf ("Now tell the index to go to offset 3, then step 5 times to see what it says \n");
    [index1 setOffset: 3];
    for (i = 0; i < 5; i ++)
      {
	int offset;
	offset = [index1 getOffset];
	printf("index1 currently positioned on offset %d and the agent at that positions say: \n", offset);
	[[index1 get] print];
	[index1 next];
      }

    printf ("Now test to make sure nothing happens if we walk off the end\n");
    while ( (anAgent = [index1 next]) )
      {
	printf("current offset is %d \n", [index1 getOffset]);
	[[index1 get] print];
      }
    printf ("If you saw anything, there is something wrong \n");

    printf ("Now, lets remove an object by repositioning the index at offset 2, then walk the collection");
    [index1 setOffset: 2];
    [index1 remove];
    [index1 setLoc: Start];
    
    for ( anAgent = [index1 next]; [index1 getLoc]==Member; anAgent = [index1 next])
      {
	printf("current offset is %d \n", [index1 getOffset]);
	[[index1 get] print];
      }

    printf("Now test index prev. The index should be at End, or offset = %d ", [index1 getOffset]);

    for (i = 0; i < 5; i ++)
      {
	int offset;
	offset = [index1 getOffset];
	[[index1 prev] print];
	printf("index1 currently positioned on offset %d, which should be the last \n", offset);
      }



//    printf ("What happens if you drop an agent before removing it from the tree? \n");
//    printf ("Go into the source code and uncomment the next 3 lines after this \n");
//    printf ("comment if you want to see a segmentation violation \n");
//    //printf ("lets drop the 6th agent, then do the walk\n");
//    //[[population atOffset: 5] drop];
//    //[myTree1 walk: print_node Param: NULL];

//    anAgent = nil;
//    printf("traverse \n");
//    while ( (anAgent=[myTree1 traverse: &trav]) != NULL)
//      [anAgent print];



 //     for (anAgent = [index1 next]; [index1 getLoc]==Member; anAgent= [index1 next])
//        {
//          [anAgent print];
//        }
//    printf("No  lets use the index to delete an item and find out who is left");
//    printf("This gets the  object at offset 5 (that's the 6th object)  in the tree: \n");

//    anAgent = [index1 setOffset: 5];
//    [anAgent print];

//    printf("And removes it and now we see that object is gone: \n");

//    [index1 remove];

//    [index1 setLoc:  [population atOffset: 5]];
  
//    for (anAgent = [index1 next]; [index1 getLoc]==Member; anAgent= [index1 next])
//      {
//        [anAgent print];
//      }

}

@end


int
main (int argc, const char **argv)
{
  initSwarmBatch (argc, argv);
  
  {
    id modelSwarm = [ModelSwarm create: globalZone];

    [modelSwarm buildObjects];
    [modelSwarm test];
  }
  return 0;
}

/*
Local Variables:
compile-command: "$SWARMHOME/bin/libtool-swarm --mode=link gcc -D_GNU_SOURCE \
  -DAPPNAME=avlusage4 -o avlusage4 -Wall -Werror -g -Wno-import -I$SWARMHOME/include \
  -I$SWARMHOME/include/swarm -L$SWARMHOME/lib/swarm avlusage4.m   -lswarm -lobjc" 
End:
*/