/*
** Copyright (c) 2010 D. Richard Hipp
**
** This program is free software; you can redistribute it and/or
** modify it under the terms of the GNU General Public
** License version 2 as published by the Free Software Foundation.
**
** 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
** General Public License for more details.
** 
** You should have received a copy of the GNU General Public
** License along with this library; if not, write to the
** Free Software Foundation, Inc., 59 Temple Place - Suite 330,
** Boston, MA  02111-1307, USA.
**
** Author contact information:
**   drh@hwaci.com
**   http://www.hwaci.com/drh/
**
*******************************************************************************
**
** This file contains code to compute a revision history graph.
*/
#include "config.h"
#include "graph.h"
#include <assert.h>

#if INTERFACE

#define GR_MAX_PARENT 10
#define GR_MAX_RAIL   32

/* The graph appears vertically beside a timeline.  Each row in the
** timeline corresponds to a row in the graph.
*/
struct GraphRow {
  int rid;                    /* The rid for the check-in */
  int isLeaf;                 /* True if the check-in is an open leaf */
  int nParent;                /* Number of parents */
  int aParent[GR_MAX_PARENT]; /* Array of parents.  0 element is primary .*/
  char *zBranch;              /* Branch name */

  GraphRow *pNext;            /* Next row down in the list of all rows */
  GraphRow *pPrev;            /* Previous row */
  
  int idx;                    /* Row index.  First is 1.  0 used for "none" */
  int iRail;                  /* Which rail this check-in appears on. 0-based.*/
  int aiRaiser[GR_MAX_RAIL];  /* Raisers from this node to a higher row. */
  int bDescender;             /* Raiser from bottom of graph to here. */
  u32 mergeIn;                /* Merge in from other rails */
  int mergeOut;               /* Merge out to this rail */
  int mergeUpto;              /* Draw the merge rail up to this level */

  u32 railInUse;              /* Mask of occupied rails */
};

/* Context while building a graph
*/
struct GraphContext {
  int nErr;             /* Number of errors encountered */
  int mxRail;           /* Number of rails required to render the graph */
  GraphRow *pFirst;     /* First row in the list */
  GraphRow *pLast;      /* Last row in the list */
  int nBranch;          /* Number of distinct branches */
  char **azBranch;      /* Names of the branches */
  int railMap[GR_MAX_RAIL];  /* Rail order mapping */
};

#endif

/*
** Malloc for zeroed space.  Panic if unable to provide the
** requested space.
*/
void *safeMalloc(int nByte){
  void *p = malloc(nByte);
  if( p==0 ) fossil_panic("out of memory");
  memset(p, 0, nByte);
  return p;
}

/*
** Create and initialize a GraphContext
*/
GraphContext *graph_init(void){
  return (GraphContext*)safeMalloc( sizeof(GraphContext) );
}

/*
** Destroy a GraphContext;
*/
void graph_free(GraphContext *p){
  int i;
  GraphRow *pRow;
  while( p->pFirst ){
    pRow = p->pFirst;
    p->pFirst = pRow->pNext;
    free(pRow);
  }
  for(i=0; i<p->nBranch; i++) free(p->azBranch[i]);
  free(p->azBranch);
  free(p);
}

/*
** Return the canonical pointer for a given branch name.
** Multiple calls to this routine with equivalent strings
** will return the same pointer.
*/
static char *persistBranchName(GraphContext *p, const char *zBranch){
  int i;
  for(i=0; i<p->nBranch; i++){
    if( strcmp(zBranch, p->azBranch[i])==0 ) return p->azBranch[i];
  }
  p->nBranch++;
  p->azBranch = realloc(p->azBranch, sizeof(char*)*p->nBranch);
  if( p->azBranch==0 ) fossil_panic("out of memory");
  p->azBranch[p->nBranch-1] = mprintf("%s", zBranch);
  return p->azBranch[p->nBranch-1];
}

/*
** Add a new row t the graph context.  Rows are added from top to bottom.
*/
void graph_add_row(
  GraphContext *p,     /* The context to which the row is added */
  int rid,             /* RID for the check-in */
  int isLeaf,          /* True if the check-in is an leaf */
  int nParent,         /* Number of parents */
  int *aParent,        /* Array of parents */
  const char *zBranch  /* Branch for this check-in */
){
  GraphRow *pRow;

  if( p->nErr ) return;
  if( nParent>GR_MAX_PARENT ){ p->nErr++; return; }
  pRow = (GraphRow*)safeMalloc( sizeof(GraphRow) );
  pRow->rid = rid;
  pRow->isLeaf = isLeaf;
  pRow->nParent = nParent;
  pRow->zBranch = persistBranchName(p, zBranch);
  memcpy(pRow->aParent, aParent, sizeof(aParent[0])*nParent);
  if( p->pFirst==0 ){
    p->pFirst = pRow;
  }else{
    p->pLast->pNext = pRow;
  }
  p->pLast = pRow;
}

/*
** Return the index of a rail currently not in use for any row between
** top and bottom, inclusive.  
*/
static int findFreeRail(
  GraphContext *p,         /* The graph context */
  int top, int btm,        /* Span of rows for which the rail is needed */
  u32 inUseMask,           /* Mask or rails already in use */
  int iNearto              /* Find rail nearest to this rail */
){
  GraphRow *pRow;
  int i;
  int iBest = 0;
  int iBestDist = 9999;
  for(pRow=p->pFirst; pRow && pRow->idx<top; pRow=pRow->pNext){}
  while( pRow && pRow->idx<=btm ){
    inUseMask |= pRow->railInUse;
    pRow = pRow->pNext;
  }
  for(i=0; i<32; i++){
    if( (inUseMask & (1<<i))==0 ){
      int dist;
      if( iNearto<=0 ) return i;
      dist = i - iNearto;
      if( dist<0 ) dist = -dist;
      if( dist<iBestDist ){
        iBestDist = dist;
        iBest = i;
      }
    }
  }
  if( iBestDist>1000 ) p->nErr++;
  return iBest;
}

/*
** Compute the complete graph
*/
void graph_finish(GraphContext *p, int omitDescenders){
  GraphRow *pRow, *pDesc;
  Bag allRids;
  int i;
  int nRow;
  u32 mask;
  u32 inUse;

  if( p==0 || p->pFirst==0 || p->nErr ) return;

  /* Initialize all rows */
  bag_init(&allRids);
  nRow = 0;
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    if( pRow->pNext ) pRow->pNext->pPrev = pRow;
    pRow->idx = ++nRow;
    pRow->iRail = -1;
    pRow->mergeOut = -1;
    bag_insert(&allRids, pRow->rid);
  }
  p->mxRail = -1;

  /* Purge merge-parents that are out-of-graph
  */
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    for(i=1; i<pRow->nParent; i++){
      if( !bag_find(&allRids, pRow->aParent[i]) ){
        pRow->aParent[i] = pRow->aParent[--pRow->nParent];
        i--;
      }
    }
  }

  /* Identify rows where the primary parent is off screen.  Assign
  ** each to a rail and draw descenders to the bottom of the screen.
  */
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    if( pRow->nParent==0 || !bag_find(&allRids,pRow->aParent[0]) ){
      if( omitDescenders ){
        pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, 0, 0);
      }else{
        pRow->iRail = ++p->mxRail;
      }
      mask = 1<<(pRow->iRail);
      if( omitDescenders ){
        pRow->railInUse |= mask;
        if( pRow->pNext ) pRow->pNext->railInUse |= mask;
      }else{
        pRow->bDescender = pRow->nParent>0;
        for(pDesc=pRow; pDesc; pDesc=pDesc->pNext){
          pDesc->railInUse |= mask;
        }
      }
    }
  }

  /* Assign rails to all rows that are still unassigned.
  ** The first primary child of a row goes on the same rail as
  ** that row.
  */
  inUse = (1<<(p->mxRail+1))-1;
  for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
    int parentRid;
    if( pRow->iRail>=0 ) continue;
    assert( pRow->nParent>0 );
    parentRid = pRow->aParent[0];
    assert( bag_find(&allRids, parentRid) );
    for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid; pDesc=pDesc->pNext){}
    if( pDesc==0 ){
      /* Time skew */
      pRow->iRail = ++p->mxRail;
      pRow->railInUse = 1<<pRow->iRail;
      continue;
    }
    if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
      pRow->iRail = pDesc->iRail;
    }else{
      pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse, 0);
    }
    pDesc->aiRaiser[pRow->iRail] = pRow->idx;
    mask = 1<<pRow->iRail;
    if( pRow->isLeaf ){
      inUse &= ~mask;
    }else{
      inUse |= mask;
    }
    for(pDesc = pRow; ; pDesc=pDesc->pNext){
      assert( pDesc!=0 );
      pDesc->railInUse |= mask;
      if( pDesc->rid==parentRid ) break;
    }
  }

  /*
  ** Insert merge rails and merge arrows
  */
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    for(i=1; i<pRow->nParent; i++){
      int parentRid = pRow->aParent[i];
      for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
          pDesc=pDesc->pNext){}
      if( pDesc==0 ) continue;
      if( pDesc->mergeOut<0 ){
        int iTarget = (pRow->iRail + pDesc->iRail)/2;
        pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
        pDesc->mergeUpto = pRow->idx;
        mask = 1<<pDesc->mergeOut;
        pDesc->railInUse |= mask;
        for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
             pDesc=pDesc->pNext){
          pDesc->railInUse |= mask;
        }
      }
      pRow->mergeIn |= 1<<pDesc->mergeOut;
    }
  }

  /*
  ** Sort the rail numbers
  */
#if 0
  p->mxRail = -1;
  mask = 0;
  for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
    if( (mask & (1<<pRow->iRail))==0 ){
      p->railMap[pRow->iRail] = ++p->mxRail;
      mask |= 1<<pRow->iRail;
    }
    if( pRow->mergeOut>=0 && (mask & (1<<pRow->mergeOut))==0 ){
      p->railMap[pRow->mergeOut] = ++p->mxRail;
      mask |= 1<<pRow->mergeOut;
    }
  }
#else
  for(i=0; i<GR_MAX_RAIL; i++) p->railMap[i] = i;
  p->mxRail = 0;
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    if( pRow->iRail>p->mxRail ) p->mxRail = pRow->iRail;
    if( pRow->mergeOut>p->mxRail ) p->mxRail = pRow->mergeOut;
  }
#endif
}