/*
   File:        part.c
   Author:      Andrew W. Moore
   Created:     Sun Sep 13 18:03:42 EDT 1992
   Description: Partition sets of kdspaces, hides kdtree and partigame

   Copyright (C) 1992, Andrew W. Moore
*/

#include <stdio.h>
#include <math.h>
#include "ambs.h"      /* Very basic operations */
#include "amma.h"      /* Fast, non-fragmenting, memory management */
#include "amar.h"      /* Trivial Array Operations */
#include "maxdim.h"    /* The MAX_DIM declaration */
#include "gpro.h"      /* Graphics projections kd->2d space */
#include "hype.h"      /* Hyper-rectangles from ../kdtr */
#include "kdtr.h"      /* kd-trees from ../kdtr */
#include "pg.h"        /* PartiGame things. From ../pg */
#include "part.h"      /* PARTitions and TESSalations */

/* NOTICE.. this file knows that we are using kdtrees and partigames.
   Its descendants (files which use functions defined defined here) will
   not know, however.
*/

#define KDNODE(pt) ((kdnode *) ((pt) -> geom_data))
#define STATE(pt) ((state *) ((pt) -> game_data))
#define ACTIONS(ne) ((actions *) ((ne) -> game_data))
#define KDTREE(te,i) ((kdtree *) (((te) -> geom_data)[i]))
#define PGAME(te) ((pgame *) ((te) -> game_data))
#define PART(kdn) ((part *) ((kdn) -> data))

int part_id(pt)
part *pt;
{
  state *st = STATE(pt);
  if ( st == NULL )
    return(-77);
  else
    return(st->state_id);
}

bool is_part_cost_finite(pt)
part *pt;
{
  return(is_winner(&(STATE(pt)->cost)));
}

float part_cost(pt)
part *pt;
{
  return(cost_to_float(&(STATE(pt)->cost)));
}

void fprintf_part_list(s,ptl)
FILE *s;
part_list *ptl;
{
  for ( ; ptl != NULL ; ptl = ptl -> next )
    fprintf(s,"%d%s",part_id(ptl->part),(ptl->next == NULL) ? "" : " ");
}

void fprintf_part(s,m,pt,ts)
FILE *s;
char *m;
part *pt;
tess *ts;
{
  if ( Verbosity > 20.0 )
    printf("ADDRESS OF (%s) = 0x%lX\n",m,(long) pt);

  if ( pt == NULL )
    fprintf(s,"%s (part *) NULL\n",m);
  else
  {
    char buff[100];
    int dim = KDTREE(ts,pt->tess_id)->dim;
    hype *hy = create_hype(dim);
    hype_of_kdnode(KDNODE(pt),hy);

    fprintf(s,"%s %s and has tess_id %d\n",m,
            (pt->is_garbage) ? "is garbage" :
            (pt->neighs_valid) ? "has valid neighs" :
            "has invalid neighs",
            pt->tess_id
           );
    fprintf(s,"%s->neighs = ",m);
    if ( pt -> neighs == NULL )
      fprintf(s,"(neighs *) NULL\n");
    else
    {
      neighs *ne;
      for ( ne = pt -> neighs ; ne != NULL ; ne = ne -> next )
      {
        part_list *ou;
        fprintf(s,"%d(",part_id(ne->neigh));
        for ( ou = ne -> outcomes ; ou != NULL ; ou = ou -> next )
          fprintf(s,"%d%s",part_id(ou->part),(ou->next==NULL)?"":",");
        fprintf(s,") ");
      }
      printf("\n");
    }
    sprintf(buff,"%s -> hype =",m);
    fprintf_hype(s,buff,hy,"\n");
    sprintf(buff,"%s -> state",m);
    if ( STATE(pt) == NULL )
      fprintf(s,"%s = <NULL GAME STATE>\n",buff);
    else
      fprint_state(s,buff,STATE(pt),3);
    free_hype(hy);
  }
}

void fprint_all_parts(s,m,ptl,ts)
FILE *s;
char *m;
part_list *ptl;
tess *ts;
{
  int i = 0;
  char buff[100];
  for ( ; ptl != NULL ; ptl = ptl -> next )
  {
    sprintf(buff,"%s[%d]",m,i);
    fprintf_part(s,buff,ptl->part,ts);
    i++;
  }
}

/* PART_LIST operations */

part_list *add_to_part_list(pt,ptl)
part *pt;
part_list *ptl;
{
  part_list *new = AM_MALLOC(part_list);
  new -> part = pt;
  new -> next = ptl;
  return(new);
}

void free_part_list_node(ptl)
part_list *ptl;
{
  am_free((char *) ptl,sizeof(part_list));
}

void free_part_list(ptl)
part_list *ptl;
{
  while ( ptl != NULL )
  {
    part_list *next = ptl -> next;
    free_part_list_node(ptl);
    ptl = next;
  }
}

bool is_in_part_list(ptl,pt)
part_list *ptl;
part *pt;
{
  bool result = FALSE;
  for ( ; ptl != NULL && !result ; ptl = ptl -> next )
    result = EQUAL_PARTS(ptl->part,pt);
  return(result);
}

/* NEIGHS operations */

neighs *add_to_neighs(pt,ne)
part *pt;
neighs *ne;
{
  neighs *new = AM_MALLOC(neighs);
  new -> neigh = pt;
  new -> outcomes = NULL;
  new -> game_data = NULL;
  new -> next = ne;
  return(new);
}

void free_neighs_node(ne)
neighs *ne;
{
  free_part_list(ne->outcomes);
  am_free((char *) ne,sizeof(neighs));
}

void free_neighs(ne)
neighs *ne;
{
  while ( ne != NULL )
  {
    neighs *next = ne -> next;
    free_neighs_node(ne);
    ne = next;
  }
}

neighs *find_neigh(ne,pt)
neighs *ne;
part *pt;
{
  neighs *result = NULL;
  for ( ; result == NULL && ne != NULL ; ne = ne -> next )
    if ( EQUAL_PARTS(pt,ne->neigh) )
      result = ne;

  return(result);
}

/* PART ops */

void init_part(ts,tess_id,pt,kdn)
tess *ts;
int tess_id;
part *pt;
kdnode *kdn;
/*
   PRE:   part's memory is there, and kdn and tess_id work.
   POST: Part now
   refers to its position within the tess and is included in ts->all_parts.
   Game_data is NULL. Neighbours are NULL, which, if this is the only
   part in the geom_data, is valid.
*/
{
  pt -> tess_id = tess_id;
  pt -> geom_data = (char *) kdn;
  kdn -> data = (char *) pt;
  pt -> game_data = NULL;
  pt -> neighs = NULL;
  pt -> is_garbage = FALSE;
  pt -> neighs_valid = TRUE;
  pt -> is_garbage = FALSE;
  ts -> all_parts = add_to_part_list(pt,ts->all_parts);
  pt -> experience_data = NULL;
  pt -> histos_data = NULL;
}

/* SPLIT_SPEC operations.
   split_spec are somewhat tedious representations of the set of
   partitions to be split, and how they are to be split.
*/

bool is_in_split_spec(sps,pt)
split_spec *sps;
part *pt;
{
  bool result = FALSE;
  for ( ; !result && sps != NULL ; sps = sps -> next )
    result = EQUAL_PARTS(pt,sps->part);
  return(result);
}

split_spec *add_to_split_spec(pt,split,pivot,sps)
part *pt;
int split;
float pivot;
split_spec *sps;
{
  split_spec *new = AM_MALLOC(split_spec);
  if ( is_in_split_spec(sps,pt) )
    my_error("add_to_split_spec: part already there");

  new -> part = pt;
  new -> split = split;
  new -> pivot = pivot;
  new -> next = sps;
  return(new);
}

void free_split_spec(sps)
split_spec *sps;
{
  while ( sps != NULL )
  {
    split_spec *next = sps -> next;
    am_free((char *) sps,sizeof(split_spec));
    sps = next;
  }
}

void fprint_split_spec_node(s,m,sps,ts)
FILE *s;
char *m;
split_spec *sps;
tess *ts;
{
  char buff[100];
  fprintf(s,"%s -> split = %d, %s -> pivot = %g\n",m,sps->split,m,sps->pivot);
  sprintf(buff,"%s -> part",m);
  fprintf_part(s,buff,sps->part,ts);
}

void fprint_split_spec(s,m,sps,ts)
FILE *s;
char *m;
split_spec *sps;
tess *ts;
{
  char buff[100];
  int i = 0;
  for ( ; sps != NULL ; sps = sps -> next )
  {
    sprintf(buff,"%s[%d]",m,i);
    fprint_split_spec_node(s,buff,sps,ts);
    i++;
  }
}

void init_tess(ts,size)
tess *ts;
int size;
/*
   Sets up geom_data array memory, but all its geom_datas are NULL and need
   to be created with make_geom_data (below). Creates an empty partigame
   with a NULL goal state. Sets validity flags suitably negatively.
*/
{
  int i;
  pgame *pg = AM_MALLOC(pgame);
  ts -> size = size;
  ts -> geom_data = AM_MALLOC_ARRAY(char_ptr,size);
  for ( i = 0 ; i < size ; i++ )
    ts -> geom_data[i] = NULL;

  init_pgame(pg);
  ts -> game_data = (char *) pg;
  ts -> all_parts = NULL;
  ts -> game_tree_valid = FALSE;
  ts -> game_scores_valid = FALSE;
}
  
void make_geom_data(ts,tess_id,dim,middle,scales)
tess *ts;
int tess_id;
int dim;
float *middle;
float *scales;
/*
   The ts->geom_data[tess_id] field is filled in with a valid geom_data
   (a kdtree) which is itself connected to a valid part which itself 
   refers to its position within the tess and is included in all_parts.
   Furthermore, this wonderful new part even has a state created for it in the
   partigame (game_data). Neighbours are, I must say though,
   undefined, both for parts and for game states.

   dim, middle and scales together describe a euclidian space and the
   bit of it we find cool.
*/  
{
  kdtree *kd = AM_MALLOC(kdtree);
  part *pt = AM_MALLOC(part);
  init_kdtree(kd,dim,middle,scales);
  init_part(ts,tess_id,pt,kd->root);
  if ( tess_id < 0 || tess_id >= ts->size || ts->geom_data[tess_id] != NULL )
    my_error("make_geom_data. Bleagh.");
  ts -> geom_data[tess_id] = (char *) kd;
}

/* MAJOR OPERATIONS */

part *part_search(te,tess_id,farr)
tess *te;
int tess_id;
float *farr;
{
  kdtree *kd = KDTREE(te,tess_id);
  if ( kd == NULL )
    my_error("part_search: null geom_data");
  else
  {
    kdnode *kdn = leaf_search(kd,farr);
    return(PART(kdn));
  }
}

/* PERFORMING THE SPLITS */

void remove_garbage_outcomes(ne)
neighs *ne;
{
  part_list *last = NULL;
  part_list *ptl = ne->outcomes;
  ne->outcomes = NULL;
  while ( ptl != NULL )
  {
    part_list *next = ptl -> next;
    if ( ptl -> part -> is_garbage )
      free_part_list_node(ptl);
    else
    {
      if ( last == NULL )
      {
        ne->outcomes = ptl;
        last = ptl;
      }
      else
      {
        last -> next = ptl;
        last = ptl;
      }
      ptl->next = NULL;
    }
    ptl = next;
  }
}

void purge_all_neighs(pt)
part *pt;
             /* PRE: pt is a garbage node.
                POST: All neighs, and all neigh outcomes are removed and NULLed
             */
{
  if ( !pt->is_garbage )
    my_error("purge_all_neighs: Non garbage pt");
  else
  {
    free_neighs(pt->neighs); /* This also frees all outcome partlist nodes */
    pt -> neighs = NULL;
  }
}

void purge_garbage_references(ts,pt)
tess *ts;
part *pt;
             /* IF ptl->part IS A GARBAGE NODE IT IS IGNORED. ELSE...
                
                If ptl->part has a garbage node among any of its
                neighs, then that neigh node is removed, and the
                neighs_valid field of ptl->part is set FALSE.

                If ptl->part has a garbage node among any of the
                outcomes of a neigh that is itself not garbage, then
                the reference to that outcome is removed.
             */
{
  if ( pt->is_garbage )
    my_error("purge_refs() garbage pt");
  else
  {
    neighs *last = NULL;
    neighs *ne = pt->neighs;
    if ( Verbosity > 40.0 ) fprintf_part(stdout,"pt-b4-pgrefs",pt,ts);
    pt->neighs = NULL;

    while ( ne != NULL )
    {
      neighs *next = ne -> next;
      if ( Verbosity > 40.0 ) 
        fprintf_part(stdout,"Considered-neigh",ne->neigh,ts);
      if ( ne->neigh->is_garbage )
      {
        if ( Verbosity > 40.0 ) printf("Is garbage\n");
        pt->neighs_valid = FALSE;
        free_neighs_node(ne);
      }
      else
      {
        if ( Verbosity > 40.0 ) printf("Isn't garbage\n");
        if ( last == NULL )
        {
          pt->neighs = ne;
          last = ne;
        }
        else
        {
          last -> next = ne;
          last = ne;
        }
        last -> next = NULL;

        remove_garbage_outcomes(ne);
      }

      if ( Verbosity > 40.0 ) fprintf_part(stdout,"pt-during-pgrefs",pt,ts);
      ne = next;
    }
    if ( Verbosity > 40.0 ) fprintf_part(stdout,"pt-after-pgrefs",pt,ts);
  }
}

void split_part(ts,sps)
tess *ts;
split_spec *sps;
        /*
           Allocates the memory of a second part.
           The two new part memory nodes are changed so that their (now
           valid) geom_datas are
           are split according to sps's specifications. Both parts have
           NULL game_data (Note that there's no need to deallocate game_data
           memory... that's up to free_game_structure())
           Both game states are thus invalid, but that'll be dealt with later.
           Both parts will also have NULL neighs. (The one that was there
           before will have deallocated it neigh's memory)
           The parts are both added onto ts->all_states. (Note that the
           original part memory should not have been in ts->all_states
           prior to this call)

           The new parts are not garbage, but their neighs are not valid.
        */
{
  kdnode *kdn = KDNODE(sps->part);
  part *pt1 = sps->part;
  part *pt2 = AM_MALLOC(part);
  int tess_id = sps -> part ->tess_id;

  split_node(kdn,sps->split,sps->pivot);

  init_part(ts,tess_id,pt1,kdn->left);
  init_part(ts,tess_id,pt2,kdn->right);

  pt1 -> is_garbage = FALSE;
  pt1 -> neighs_valid = FALSE;
  pt2 -> is_garbage = FALSE;
  pt2 -> neighs_valid = FALSE;
}

void recompute_neighs(ts,pt)
tess *ts;
part *pt;
       /*
          First we find all the neighboring parts (helped by our geom_data
          of course). Then we check how this compares with our current set
          of neighbors. Algorithm logic dictates that all our old, same tess,
          neighbors
          still be new neighbors (if we weren't garbage we don't change our
          position or size and none of our old_neighs set were garbage or they
          wouldn't still be here. Therefore they too are in the same position
          and size so they must still be neighbors.

          Anyway, we may have some new neighbors, which we formally add into
          our neighs field, along with NULL outcomes.

          That's just about all we do, actually.
       */
{
  int dim = KDTREE(ts,pt->tess_id)->dim;
  kdnode_list *adj_ks = adjacent_leaves(KDNODE(pt),dim);
  kdnode_list *ks;
  neighs *ns;

  for ( ns = pt->neighs ; ns != NULL ; ns = ns -> next )
  {
    bool ns_okay = ns->neigh->tess_id != pt->tess_id;
    for ( ks = adj_ks ; !ns_okay && ks != NULL ; ks = ks -> next )
      ns_okay = EQ_PTR(PART(ks->kdnode),ns->neigh);
    if ( !ns_okay )
    {
      int i = 0;
      printf("recompute_neighs(). An old neighbor is not a new neighbor\n");
      fprintf_part(stderr,"pt-to-be-recomped",pt,ts);
      fprintf_part(stderr,"old-neigh-part",ns->neigh,ts);
      for ( ks = adj_ks ; ks != NULL ; ks = ks -> next )
      {
        char buff[100];
        sprintf(buff,"adj_ks[%d]",i);
        i++;
        fprintf_part(stderr,buff,PART(ks->kdnode),ts);
      }
      while ( !input_bool("Ready to continue?> ") )
        printf("Fair enough\n");
    }
  }

  if ( pt -> is_garbage )
  {
    fprintf_part(stderr,"pt",pt,ts);
    my_error("recompute_neighs() garbage part");
  }

  for ( ks = adj_ks ; ks != NULL ; ks = ks -> next )
  {
    part *neigh_pt = PART(ks -> kdnode);
    if ( find_neigh(pt->neighs,neigh_pt) == NULL )
      pt->neighs = add_to_neighs(neigh_pt,pt->neighs);
  }

  pt->neighs_valid = TRUE;
  free_kdnode_list(adj_ks);
}

void perform_splits(ts,all_splits)
tess *ts;
split_spec *all_splits;
{
  part_list *ptl;
  split_spec *sps;
  int ptl_number = 0;

  if ( Verbosity > 35.0 )
  {
    fprint_all_parts(stdout,"presplit-ptl",ts->all_parts,ts);
    printf("Lets see all_splits..\n");
    fprint_split_spec(stdout,"presplit-sps",all_splits,ts);
  }

  if ( Verbosity > 30.0 ) printf("will free game structure\n");
  free_game_structure(ts);
  if ( Verbosity > 30.0 ) printf("have freed game structure\n");

  ts -> game_scores_valid = FALSE;
  ts -> game_tree_valid = FALSE;

  if ( Verbosity > 30.0 ) printf("will kill all game data refs\n");
  for ( ptl = ts -> all_parts ; ptl != NULL ; ptl = ptl -> next )
  {
    neighs *ne;
    ptl->part->game_data = NULL;
    for ( ne = ptl -> part -> neighs ; ne != NULL ; ne = ne -> next )
      ne->game_data = NULL;
  }

  if ( Verbosity > 30.0 ) printf("will agree all splits are garbage\n");
  for ( sps = all_splits ; sps != NULL ; sps = sps -> next )
    sps -> part -> is_garbage = TRUE;

  ptl = ts -> all_parts;
  ts -> all_parts = NULL;

  if ( Verbosity > 35.0 )
  {
    fprint_all_parts(stdout,"gameless-ptl",ptl,ts);
    fprint_split_spec(stdout,"gameless-sps",all_splits,ts);
  }

  ptl_number = 0;

  if ( Verbosity > 30.0 ) printf("will remove garbage and refs\n");
  while ( ptl != NULL )
  {
    part_list *next = ptl -> next;
    if ( Verbosity > 40.0 ) printf("Dealing with ptl[%d]\n",ptl_number);
    ptl_number++;
    if ( ptl -> part -> is_garbage )
    {
      if ( Verbosity > 40.0 ) printf("It's garbage\n");
      purge_all_neighs(ptl->part);
      free_part_list_node(ptl);
      if ( Verbosity > 40.0 ) printf("and has been dealt with\n");
    }
    else
    {
      if ( Verbosity > 40.0 ) printf("Its not garbage.. purge refs\n");    
      purge_garbage_references(ts,ptl -> part);
      if ( Verbosity > 40.0 ) printf("refs purged\n");
             /* IF ptl->part IS A GARBAGE NODE IT IS IGNORED. ELSE...
                
                If ptl->part has a garbage node among any of its
                neighs, then that neigh node is removed, and the
                neighs_valid field of ptl->part is set FALSE.

                If ptl->part has a garbage node among any of the
                outcomes of a neigh that is itself not garbage, then
                the reference to that outcome is removed.
             */
      ptl -> next = ts -> all_parts;
      ts -> all_parts = ptl;
    }
    ptl = next;
  }

  if ( Verbosity > 35.0 )
    fprint_all_parts(stdout,"nonsplit-ptl",ts->all_parts,ts);

  if ( Verbosity > 30.0 ) printf("Will split individual parts\n");
  for ( sps = all_splits ; sps != NULL ; sps = sps -> next )
    split_part(ts,sps);
        /*
           Allocates the memory of a second part.
           The two new part memory nodes are changed so that their (now
           valid) geom_datas are
           are split according to sps's specifications. Both parts have
           NULL game_data (Note that there's no need to deallocate game_data
           memory... that's up to free_game_structure())
           Both game states are thus invalid, but that'll be dealt with later.
           Both parts will also have NULL neighs. (The one that was there
           before will have deallocated it neigh's memory)
           The parts are both added onto ts->all_states. (Note that the
           original part memory should not have been in ts->all_states
           prior to this call)

           The new parts are not garbage, but their neighs are not valid.
        */
/* At this point there should be no garbage nodes, and all parts in existence
   should be in ts->all_parts
*/

  if ( Verbosity > 35.0 )
    fprint_all_parts(stdout,"postsplit-ptl",ts->all_parts,ts);

  if ( Verbosity > 30.0 ) printf("Will recompute neighs\n");
  for ( ptl = ts -> all_parts ; ptl != NULL ; ptl = ptl -> next )
  {
    if ( !ptl->part->neighs_valid )
      recompute_neighs(ts,ptl->part);
       /*
          First we find all the neighboring parts (helped by our geom_data
          of course). Then we check how this compares with our current set
          of neighbors. Algorithm logic dictates that all our old neighbors
          still be new neighbors (if we weren't garbage we don't change our
          position or size and none of our old_neighs set were garbage or they
          wouldn't still be here. Therefore they too are in the same position
          and size so they must still be neighbors.

          Anyway, we may have some new neighbors, which we formally add into
          our neighs field, along with NULL outcomes.

          That's just about all we do, actually.
       */
  }

  if ( Verbosity > 30.0 ) printf("Have finished performing splits\n");
/* At this point there should be garbage nodes and no invalid neighbors.
   The world is at peace.
*/
  if ( Verbosity > 35.0 )
    fprint_all_parts(stdout,"postall-ptl",ts->all_parts,ts);

}

void build_game_structure(ts)
tess *ts;
/*
    Pre: The should be no unnecessary memory in ts's game data. It should
         have been removed with something like free_game_data(), or else
         never have existed.

         Also, all states should have NULL game datas, and all neighs
         should have NULL game datas.
*/
{
  pgame *pg = PGAME(ts);
  part_list *ptl;

  if ( ts -> game_tree_valid || ts -> game_scores_valid )
    my_error("build_game_structure() Can't start with valid tree");

  if ( pg == NULL )
    my_error("build game structure(), game_data NULL");

  if ( pg -> states != NULL || pg -> goal != NULL || pg -> number_states > 0 )
    my_error("build game structure non-empty game or goal.");

  for ( ptl = ts -> all_parts ; ptl != NULL ; ptl = ptl -> next )
  {
    state *st = add_state_to_pgame(pg,(char *) ptl -> part);
    if ( STATE(ptl -> part) != NULL ) my_error("build_game_s(): snn");
    ptl -> part -> game_data = (char *) st;
  }
    
  for ( ptl = ts -> all_parts ; ptl != NULL ; ptl = ptl -> next )
  {
    state *st = STATE(ptl->part);
    neighs *nes;

    for ( nes = ptl -> part -> neighs ; nes != NULL ; nes = nes -> next )
    {
      part_list *ou = nes -> outcomes;
      actions *acs = add_action_to_state(st,(char *) nes);

      if ( nes -> game_data != NULL ) my_error("build_game_s(): ann");
      nes -> game_data = (char *) acs;

      if ( ou == NULL ) /* Then we assume that aiming for that neighbor
                           will get us there */
      {
        maybe_include_action_outcome(acs,STATE(nes->neigh));
      }
      else
      {
        for ( ; ou != NULL ; ou = ou -> next )
          maybe_include_action_outcome(acs,STATE(ou->part));
      }
    }
  }

  pred_finder(pg);

  ts -> game_tree_valid = TRUE;
}

void free_game_structure(ts)
tess *ts;
{
  pgame *pg = PGAME(ts);
  free_pgame_contents(pg);
  init_pgame(pg);
  ts -> game_scores_valid = FALSE;
  ts -> game_tree_valid = FALSE;
}

void part_and_game_observe(ts,source_part,aim_part,actual_part)
tess *ts;
part *source_part;
part *aim_part;
part *actual_part;
/*
   PRE:  Game tree is valid, its scores may or may not be.
         aim_part is a valid neighbor of source_part.
   POST: The outcomes of the "aim_part" neighbor of "dest_part" is,
         if necessary, updated to included actual_part.
         Game_tree agrees with the new outcomes, which means part's
         game_data will be changed if part is changed. If this happens
         then ts's scores_valid flag is turned off.

         There's a tedious detail. If the outcome list had originally been
         empty and we add an outcome as the neighbor itself, then the
         game_data should not change, because by default an empty outcome
         corresponds to assuming that when the neighbor is aimed for it
         is achieved. 
*/
{
  neighs *ne = find_neigh(source_part->neighs,aim_part);

  if ( !ts->game_tree_valid )
    my_error("observe needs valid game tree");

  if ( ne == NULL )
    my_error("observe: NON NEIGH");
  
  if ( !is_in_part_list(ne->outcomes,actual_part) )
  {
    bool outcomes_had_been_empty = ne->outcomes == NULL;
    bool default_assumption_wrong = !EQUAL_PARTS(aim_part,actual_part) &&
                                    outcomes_had_been_empty;

    ne->outcomes = add_to_part_list(actual_part,ne->outcomes);

    if ( !outcomes_had_been_empty || default_assumption_wrong )
    {
      actions *ac = ACTIONS(ne);
      if ( ac == NULL ) my_error("Observe discovers neigh with no game_data");
      ts -> game_scores_valid = FALSE;
      if ( default_assumption_wrong )
        remove_outcome_and_pred(STATE(source_part),ac,STATE(aim_part));
      new_outcome_and_pred(STATE(source_part),ac,STATE(actual_part));
    }
  }
}

float old_middle_pivot(ts,pt,comp)
tess *ts;
part *pt;
int comp;
/*
   Finds the middle of the component "comp" of the space occupied by part.
   Now what, I hear you ask if things are infinite or semi-infinite in that
   direction?. Good point I reply. Hah, so you're flummoxed you sneer. No not
   at all I reply with a calm smile. We use the "middle" and "spread" fields
   of the pt->tess_id'th kdtree to let us know whats happening.

     If pt is finite in that comp then no problem.
     If it's semi infinite in that comp, we split half a "scales[comp]"
     distance away from the bounded end.
     If it's fully infinite we split at "middle[comp]".
*/
{
  kdtree *kd = KDTREE(ts,pt->tess_id);
  hype *hy = create_hype(kd->dim);
  bool lo_bounded,hi_bounded;
  float result;

  hype_of_kdnode(KDNODE(pt),hy);
  lo_bounded = hype_has_limit(hy,comp,LO);
  hi_bounded = hype_has_limit(hy,comp,HI);

  if ( lo_bounded && hi_bounded )
    result = ( hype_ref(hy,comp,LO) + hype_ref(hy,comp,HI) ) / 2.0;
  else if ( lo_bounded )
    result = ( hype_ref(hy,comp,LO) + kd->scales[comp]/2.0 );
  else if ( hi_bounded )    
    result = ( hype_ref(hy,comp,HI) - kd->scales[comp]/2.0 );
  else
    result = kd->middle[comp];

  free_hype(hy);
  return(result);
}

float middle_pivot(ts,pt,comp)
tess *ts;
part *pt;
int comp;
/*
   Finds the middle of the component "comp" of the space occupied by part.
   Now what, I hear you ask if things are infinite or semi-infinite in that
   direction?. Good point I reply. Hah, so you're flummoxed you sneer. No not
   at all I reply with a calm smile. We use the "middle" and "spread" fields
   of the pt->tess_id'th kdtree to let us know whats happening.

   We just clip with middle and scales.
*/
{
  kdtree *kd = KDTREE(ts,pt->tess_id);
  hype *hy = create_hype(kd->dim);
  float lo_val,hi_val;

  hype_of_kdnode(KDNODE(pt),hy);

  lo_val = ( hype_has_limit(hy,comp,LO) ) ? 
           hype_ref(hy,comp,LO) : 
           kd->middle[comp] - kd->scales[comp];

  hi_val = ( hype_has_limit(hy,comp,HI) ) ? 
           hype_ref(hy,comp,HI) : 
           kd->middle[comp] + kd->scales[comp];

  free_hype(hy);
  return( (lo_val + hi_val) / 2.0 );
}

void solve_game(ts,goal_pt)
tess *ts;
part *goal_pt;
{
  pgame *pg = PGAME(ts);
  if ( ts -> game_scores_valid )
    my_error("solve_game() doesn't need to be solved");
  if ( !ts->game_tree_valid )
    my_error("solve_game() game tree not valid");

  if ( pg == NULL )
    my_error("solve game: NULL pg");

  if ( pg -> goal == NULL )
    set_goal(pg,STATE(goal_pt));
  else if ( part_id(goal_pt) != pg->goal->state_id )
    my_error("solve_game(): wrong goal");

  solve_pgame(PGAME(ts));
  ts -> game_scores_valid = TRUE;
}

void gp_draw_geom_data(gp,ts,tess_id)
gproj *gp;
tess *ts;
int tess_id;
{
  kdtree *kd = KDTREE(ts,tess_id);
  part_list *ptl;

  if ( Verbosity > 20.0 )
    gp_clear(gp);
  gp_draw_kdtree(gp,kd);
  
  if ( Verbosity > 20.0 )
    for ( ptl = ts -> all_parts ; ptl != NULL ; ptl = ptl -> next )
  {
    {
      if ( ptl -> part -> tess_id == tess_id )
      {
        char buff[100];
        char cost_string[100];
        if ( is_part_cost_finite(ptl->part) )
          sprintf(cost_string,"%g",part_cost(ptl->part));
        else
          sprintf(cost_string,"X");

        sprintf(buff,"%c%d=%s",
                'a' + (char) tess_id,part_id(ptl->part),
                cost_string
               );
        gp_draw_string(gp,
                       middle_pivot(ts,ptl->part,gp->x.comp),
                       middle_pivot(ts,ptl->part,gp->y.comp),
                       buff
                      );
      }
    }
  }
}    

void add_extra_neigh(pt,neigh_pt)
part *pt,*neigh_pt;
{
  if ( find_neigh(pt->neighs,neigh_pt) == NULL )
    pt -> neighs = add_to_neighs(neigh_pt,pt->neighs);
}

void fprint_game(s,ts)
FILE *s;
tess *ts;
{
  fprint_pgame(s,"pg",PGAME(ts),3);
}

void find_outcome_cost(ne,co)
neighs *ne;
cost *co;
{
  if ( ne -> outcomes == NULL )
    copy_cost(&(STATE(ne->neigh)->cost),co);
  else
  {
    part_list *ptl;
    copy_cost(&(STATE(ne->outcomes->part)->cost),co);
    for ( ptl = ne -> outcomes -> next ; ptl != NULL ; ptl = ptl -> next )
      if ( less_cost(co,&(STATE(ptl->part)->cost)) )
        copy_cost(&(STATE(ptl->part)->cost),co);
  }
}

neighs *best_neigh(p)
part *p;
/*
   Returns the best neighbor in the game to aim for.
   If no neighbor works, then returns NULL.
*/
{
  neighs *ne;
  neighs *best_ne = NULL;
  cost lowest_cost;

  set_loser_cost(&lowest_cost);

  for ( ne = p -> neighs ; ne != NULL ; ne = ne -> next )
  {
    cost ne_cost;
    if ( Verbosity > 20.0 )
    {
      printf("Considering part with state:\n");
      fprint_state(stdout,"state",STATE(ne->neigh),3);
    }

    find_outcome_cost(ne,&ne_cost);
    if ( Verbosity > 20.0 )
    {
      if ( is_winner(&ne_cost) )
        printf("Its cost is %g\n",cost_to_float(&ne_cost));
      else
        printf("Its infinite cost\n");
    }

    if ( less_cost(&ne_cost,&lowest_cost) )
    {
      copy_cost(&ne_cost,&lowest_cost);
      best_ne = ne;
    }
  }

  return(best_ne);
}

void draw_filled_part(gp,ts,tess_id,p)
gproj *gp;
tess *ts;
int tess_id;
part *p;
{
  hype *hy = create_hype(KDTREE(ts,tess_id)->dim);
  hype_of_kdnode(KDNODE(p),hy);
  gp_draw_hype(gp,hy);
  free_hype(hy);
}

void draw_filled_part_list(gp,ts,tess_id,ptl)
gproj *gp;
tess *ts;
int tess_id;
part_list *ptl;
{
  for ( ; ptl != NULL ; ptl = ptl -> next )
    draw_filled_part(gp,ts,tess_id,ptl->part);
}

bool is_safely_in_part(pt,pt_middle,pt_dim,farr)
part *pt;
float *pt_middle;
int pt_dim;
float *farr;
{
  bool result;
  hype *hy = create_hype(pt_dim);
  hype_of_kdnode(KDNODE(pt),hy);
  if ( Verbosity > 20.0 )
    fprintf_hype(stdout,"hype-before-shrinking",hy,"\n");
  shrink_hype(hy,0.5,pt_middle);
  if ( Verbosity > 20.0 )
    fprintf_hype(stdout,"hype-after-shrinking",hy,"\n");
  result = is_inside_hype(hy,farr);
  free_hype(hy);
  return(result);
}

bool worst_neigh_infinite(p)
part *p;
/*
    Returns TRUE iff there's at least one neigh, and all
    neighs have infinite cost.
*/
{
  neighs *ne;
  bool result;

  if ( p -> neighs == NULL )
    result = TRUE;
  else
  {
    result = FALSE;
    for ( ne = p -> neighs ; !result && ne != NULL ; ne = ne -> next )
    {
      cost *ne_cost = &(STATE(ne->neigh)->cost);
      result = !is_winner(ne_cost);
    }
  }
  
  return(result);
}

bool best_neigh_finite(p)
part *p;
/*
    Returns TRUE if all
    neighs have finite cost.
*/
{
  neighs *ne;
  bool result = FALSE;

  for ( ne = p -> neighs ; !result && ne != NULL ; ne = ne -> next )
  {
    cost *ne_cost = &(STATE(ne->neigh)->cost);
    if ( is_winner(ne_cost) ) result = TRUE;
  }
  return(result);
}

bool is_eligable(pt,tess_id)
part *pt;
int tess_id;
{
  bool result;
  if ( pt -> tess_id != tess_id )
    result = FALSE;
  else
  {
    cost *my_cost = &(STATE(pt)->cost);
    if ( is_winner(my_cost) )
      result = worst_neigh_infinite(pt);
    else
      result = best_neigh_finite(pt);
  }

  return(result);
}

float volume_of_part(ts,pt)
tess *ts;
part *pt;
{
  kdtree *kd = KDTREE(ts,pt->tess_id);
  hype *hy = create_hype(kd->dim);
  float result;

  hype_of_kdnode(KDNODE(pt),hy);
  clip_hype_with_m_and_s(hy,kd->middle,kd->scales);
  result = hype_volume(hy,kd->scales);
  return(result);
}

part_list *get_eligables(ts,tess_id)
tess *ts;
int tess_id;
{
  part_list *result = NULL;
  part_list *ptl;

  for ( ptl = ts -> all_parts ; ptl != NULL ; ptl = ptl -> next )
  {
    if ( is_eligable(ptl->part,tess_id) )
      result = add_to_part_list(ptl->part,result);
  }

  return(result);
}

float largest_volume(ts,ptl)
tess *ts;
part_list *ptl;
{
  float result;

  if ( ptl == NULL )
    my_error("largest volume: empty part list");
  else
  {
    part_list *ipl;
    result = volume_of_part(ts,ptl->part);

    for ( ipl = ptl -> next ; ipl != NULL ; ipl = ipl -> next )
    {
      float vol = volume_of_part(ts,ipl->part);
      result = real_max(vol,result);
    }
  }

  return(result);
}

part_list *filter_out_low_volumes(ts,base_ptl,v)
tess *ts;
part_list *base_ptl;
float v;
/*
    Return list of parts in part list with volume greater than v.
    Free ptl nodes memory
    Allocate memory for new result list.
*/
{
  part_list *result = NULL;
  part_list *ptl;

  for ( ptl = base_ptl ; ptl != NULL ; ptl = ptl -> next )
  {
    if ( volume_of_part(ts,ptl->part) > v )
      result = add_to_part_list(ptl->part,result);
  }

  free_part_list(base_ptl);

  return(result);
}

void split_middle_of_longest(ts,pt,res_comp,res_pivot)
tess *ts;
part *pt;
int *res_comp;
float *res_pivot;
{
  kdtree *kd = KDTREE(ts,pt->tess_id);
  if ( kd -> dim == 0 )
    my_error("split middle kd->dim zero");
  else
  {
    int i;
    hype *hy = create_hype(kd->dim);
    float longest_scaled_length = 0.0;

    hype_of_kdnode(KDNODE(pt),hy);
    clip_hype_with_m_and_s(hy,kd->middle,kd->scales);

    for ( i = 0 ; i < kd -> dim ; i++ )
    {
      float scaled_length = (hype_ref(hy,i,HI) - hype_ref(hy,i,LO)) /
                            kd -> scales[i];
      if ( scaled_length >= longest_scaled_length )
      {
        longest_scaled_length = scaled_length;
        *res_comp = i;
        *res_pivot = (hype_ref(hy,i,LO) + hype_ref(hy,i,HI)) / 2.0;
      }
    }
  
    free_hype(hy);
  }
}

split_spec *split_spec_from_longest(ts,ptl)
tess *ts;
part_list *ptl;
{
  split_spec *result = NULL;
  for ( ; ptl != NULL ; ptl = ptl -> next )
  {
    int comp;
    float pivot;
    split_middle_of_longest(ts,ptl->part,&comp,&pivot);
    result = add_to_split_spec(ptl->part,comp,pivot,result);
  }
  return(result);
}

void hype_of_part(pt,hy)
part *pt;
hype *hy;
/*
   PRE: hype dimesnion must be that of part. It's contents are irrelevant.
   POST: part's region (smallest encoling hyperrect) is in hy.
*/
{
  set_hype_infinite(hy);
  hype_of_kdnode(KDNODE(pt),hy);
}

part_list *get_biggest_eligables(gp,ts,tess_id)
gproj *gp;
tess *ts;
int tess_id;
{
  float big_volume;
  part_list *ptl = get_eligables(ts,tess_id);

  if ( Verbosity > 20.0 )
  {
    printf("All eligables: ");
    fprintf_part_list(stdout,ptl);
    printf("\n");
  }

  big_volume = largest_volume(ts,ptl);
  if ( Verbosity > 20.0 )
    printf("largest scaled volume is %g\n",big_volume);

  ptl = filter_out_low_volumes(ts,ptl,0.99 * big_volume);

  if ( Verbosity > 20.0 )
  {
    printf("Filtered eligables: ");
    fprintf_part_list(stdout,ptl);
    printf("\n");
    draw_filled_part_list(gp,ts,tess_id,ptl);
/*
    {
      float dumx,dumy;
      (void) ag_get_xy(&dumx,&dumy);
    }
*/
  }

  return(ptl);
}

void m_and_s_of_part(ts,pt,middle,scales)
tess *ts;
part *pt;
float *middle,*scales;
/*
    mid and scales contains at least ts->dimension entries.
*/
{
  kdtree *kd = KDTREE(ts,pt->tess_id);
  hype *hy = create_hype(kd->dim);
  hype_of_part(pt,hy);
  clip_hype_with_m_and_s(hy,kd->middle,kd->scales);
  m_and_s_from_hype(hy,middle,scales);
  if ( Verbosity > 23.0 ) fprintf_hype(stdout,"hype-of-part",hy,"\n");
  free_hype(hy);
}

part *find_closest_part(ts,ptl,farr)
tess *ts;
part_list *ptl;
float *farr;
/*
   PRE: all parts in ptl have same tess_id, ptl must be non-null,
        and farr has as many elements as the dimesnion of the parts.

   POST: The member of ptl with middle closest to farr is returned.
*/
{
  if ( ptl == NULL )
    my_error("iwyvb");
  else
  {
    int tess_id = ptl->part->tess_id;
    kdtree *kd = KDTREE(ts,tess_id);
    float least_dsqd = 0.0;
    part *closest = NULL;
    float middle[MAX_DIM];
    float scales[MAX_DIM];
 
    if ( Verbosity > 23.0 )
    {
      fprintf_floats(stdout,"Finding closest part to ",farr,kd->dim,"\n");
      fprint_all_parts(stdout,"ptl",ptl,ts);
    }
    for ( ; ptl != NULL ; ptl = ptl -> next )
    {
      float dsqd;
      part *pt = ptl -> part;
      if ( pt -> tess_id != tess_id )
        my_error("wuoibcv iuw");
      m_and_s_of_part(ts,ptl->part,middle,scales);
      dsqd = floats_scaled_dsqd(middle,farr,kd->scales,kd->dim);
      if ( Verbosity > 23.0 )
      {
        printf("dsqd of part %d is %g\n",part_id(pt),dsqd);
        fprintf_floats(stdout,"Its middle is ",middle,kd->dim,"\n");
      }

      if ( closest == NULL || dsqd < least_dsqd )
      {
        closest = pt;
        least_dsqd = dsqd;
      }
    }
  
    if ( Verbosity > 23.0 )
      fprintf_part(stdout,"closest",closest,ts);
    return(closest);
  }
}
    
int number_partitions(ts)
tess *ts;
{
  int result = 0;
  int i;
  for ( i = 0 ; i < ts -> size ; i++ )
    result += kdtree_size(KDTREE(ts,i));

  return(result);
}

void print_partition_info(ts,run_mode)
tess *ts;
int run_mode;
{
  printf("Tree Leaves vs depth: ");
  partition_depth_histogram(KDTREE(ts,run_mode));
}

int random_long_dimension(hy,scales,dim)
hype *hy;
float *scales;
int dim;
/*
   Find all those directions is hy which are at least 99% as long
   (in the scaled metric) as the longest. Return a random one of the
   longest.
*/
{
  float slens[MAX_DIM];
  int i;
  int num_long = 0;
  float longest = 0.0;
  int result = -1;

  for ( i = 0 ; i < dim ; i++ )
  {
    bool lo_lim = hype_has_limit(hy,i,LO);
    bool hi_lim = hype_has_limit(hy,i,HI);
    if ( lo_lim && hi_lim )
      slens[i] = (hype_ref(hy,i,HI) - hype_ref(hy,i,LO)) / scales[i];
    else if ( lo_lim || hi_lim )
      slens[i] = 1e20;
    else
      slens[i] = 2e20;

    if ( i == 0 || longest < slens[i] )
      longest = slens[i];
  }

  for ( i = 0 ; i < dim ; i++ )
    if ( slens[i] > 0.99 * longest ) num_long++;

  num_long = int_random(num_long);

  for ( i = 0 ; result < 0 && i < dim ; i++ )
    if ( slens[i] > 0.99 * longest )
    {
      if ( num_long == 0 )
        result = i;
      else
        num_long -= 1;
    }

  return(result);
}

/* Split spec from schedule uses the depth of the thing being split
   and a string called a schedule string. We split in the middle
   of the scheule_string[depth MOD N] dimension where N = length of schedule.

   For example, schedule string "1323" means

    Split dimension 1 at top level
          dimension 3 at level 2
          dimension 2 at level 3
          dimension 3 at level 4
          dimension 1 at level 5
             .
             .
    
*/

void split_middle_from_schedule(ts,pt,sched,res_comp,res_pivot)
tess *ts;
part *pt;
char *sched;
int *res_comp;
float *res_pivot;
{
  kdtree *kd = KDTREE(ts,pt->tess_id);
  if ( kd -> dim == 0 )
    my_error("split middle kd->dim zero");
  else
  {
    int depth = kdnode_depth(KDNODE(pt));
    int i = (int) (sched[depth % strlen(sched)] - '0');
    hype *hy = create_hype(kd->dim);

    hype_of_kdnode(KDNODE(pt),hy);
    clip_hype_with_m_and_s(hy,kd->middle,kd->scales);

    if ( eq_string(sched,"random") )
      i = random_long_dimension(hy,kd->scales,kd->dim);

    *res_comp = i;
    *res_pivot = (hype_ref(hy,i,LO) + hype_ref(hy,i,HI)) / 2.0;
    free_hype(hy);
  }
}

split_spec *split_spec_from_schedule(ts,ptl,sched)
tess *ts;
part_list *ptl;
char *sched;
{
  split_spec *result = NULL;
  for ( ; ptl != NULL ; ptl = ptl -> next )
  {
    int comp;
    float pivot;
    split_middle_from_schedule(ts,ptl->part,sched,&comp,&pivot);
    result = add_to_split_spec(ptl->part,comp,pivot,result);
  }
  return(result);
}