//Paul Johnson Sept. 14, 2000
//avl_tree based set class for swarm.
//Comparison function must be set between createBegin and createEnd 

#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> //for the AVLtree

#include <misc/avl.h>


#define COUNT 10



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

//@interface AVLSet: Collection_any

@interface AVLSet: SwarmObject

{
  avl_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;

- copy: aZone;

- (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: (avl_traverser *) travPtr;

@end


@interface AVLSetIndex_c: Index_any <KeyedCollectionIndex>
{

  int offset;
  avl_traverser trav;
  id currentObject;
@public
   avl_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 AVLSet

//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  
{
  AVLSet * 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 = avl_create ( compareFunc, NULL);
  return self;
}

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

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

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

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

//by default,use IDs to compare. 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
{
  AVLSet * obj; 
  obj = [super createBegin: aZone];
  obj->aTree = avl_create (comparFunc, param);
  return obj;
}

PHASE(Using)

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

- copy: aZone
{
  AVLSet *newSet;
  newSet = [aZone copyIVars: self];
  newSet->aTree = avl_copy (aTree,NULL);
  return newSet;
}

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

- (unsigned) getCount
{
  return (unsigned)  avl_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 = avl_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 = avl_find(aTree, anObject) ))
    {
      avl_replace (aTree, anObject);
    }
  return value; //have to worry about NULL being different from nil?
}


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

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


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


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

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

- (void)forEach: (SEL)aSelector
{
  id anObject;
   avl_traverser trav = {0};
   while (( anObject = avl_traverse (aTree, &trav)) != NULL) 
     [anObject perform: aSelector];
}

- (void)forEach: (SEL)aSelector : arg1
{
  id anObject;
   avl_traverser trav = {0};
   while (( anObject = avl_traverse (aTree, &trav)) != NULL )
     [anObject perform: aSelector with: arg1];
}

- (void)forEach: (SEL)aSelector : arg1 : arg2
{ 
  id anObject;
   avl_traverser trav = {0};
   while (( anObject = avl_traverse (aTree, &trav)) != NULL )
     [anObject perform: aSelector with: arg1 with: arg2];
}

- (void)forEach: (SEL)aSelector : arg1 : arg2 : arg3
{
  id anObject;
   avl_traverser trav = {0};
   while (( anObject = avl_traverse (aTree, &trav)) != NULL )
     [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
{
  AVLSetIndex_c * newIndex;

  newIndex = [aZone allocIVars: [AVLSetIndex_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
{
  avl_destroy(aTree,NULL); //does not drop objects tree refers to
  [super drop];
}

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


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



// 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 = avl_replace (aTree, anObject );//uses integer keys;
    if (value != NULL) 
      return value;
    else return nil;
  }


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


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

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


@end



@implementation AVLSetIndex_c
- next
{
  currentObject =  avl_traverse (tree, &trav);
  offset ++;
  return  currentObject ; //returns a null at the end of the tree
}

//sorry, I don't see a way to make an avltree walk backwards!
- prev
{
  int i;
  int currentOffset = offset;
  void * anObject = NULL;

  [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 * value;
  if (( value = avl_find(tree, anObject) ))
    {
      avl_replace (tree, anObject);
    }
  return value;  //removed object
}

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


- init
{
  avl_traverser newtrav = {0};
  trav = newtrav ;
  offset = -1;
  currentObject = nil;
  return self;
}

- (id <Symbol>)getLoc
{
  if (offset == -1) return Start;
  else if (currentObject != NULL) 
    {
      fprintf (stderr,"Member! offset= %d",offset);
      return Member;
    }
  else if (offset >= avl_count(tree))
    {
      return End;
    }
  else
    raiseEvent(WarningMessage,"Invalid AVLSet position");
  return End;
}

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

- (int)getOffset
{
  return offset ;
}

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

//I don't know what this does!
//  - (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
{
  printf("Hello, from Agent %d \n",personalNumber);
  return self;
}


- (int) getPIN
{
  return personalNumber;
}

@end

@interface ModelSwarm: Swarm
{
  id <Array> population;
  AVLSet * myTree1;
  AVLSet *  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 = [AVLSet createBegin: self ];
  [myTree1 setCompareIDs];
  myTree1= [myTree1 createEnd]; 

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

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

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

      [myTree2 add: anAgent];//retrieves node or inserts if key not in tree already
    }	                         //this amounts to a "set"
   return self;
}

- (void)test
{
  int i;
  //  int j;
  id anAgent=nil;
  avl_traverser trav = {0};
  id index1;
  id index2;
  

  printf("Now, use the avl_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("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];
      [outputAgent print];
    }

  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];
    }

  anAgent = nil;
  printf("Now, grab the agent 5th from the tree2 by asking for it by name \n");
  anAgent = [myTree2 at: [population atOffset: 4]];
  [anAgent 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 (" 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 ("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];

  printf ("Create a swarm index for the trees \n");


  index1 = [myTree1 begin: self];
  index2 = [myTree2 begin: self];
  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=avlusage3 -o avlusage3 -Wall -Werror -g -Wno-import -I$SWARMHOME/include \
  -I$SWARMHOME/include/swarm -L$SWARMHOME/lib/swarm avlusage3.m  -lswarm -lobjc" 
End:
*/