#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 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 isLeaf;                 /* True if no direct child nodes */
  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 nRow;                  /* Number of rows */
  int railMap[GR_MAX_RAIL];  /* Rail order mapping */
  int nHash;                 /* Number of slots in apHash[] */
  GraphRow **apHash;         /* Hash table of rows */
};

#endif

/*
** Malloc for zeroed space.  Panic if unable to provide the
** requested space.

  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->apHash);
  free(p);
}

/*
** Insert a row into the hash table.  If there is already another
** row with the same rid, the other row is replaced.
*/
static void hashInsert(GraphContext *p, GraphRow *pRow){
  int h;
  h = pRow->rid % p->nHash;
  while( p->apHash[h] && p->apHash[h]->rid!=pRow->rid ){
    h++;
    if( h>=p->nHash ) h = 0;
  }
  p->apHash[h] = pRow;
}

/*
** Look up the row with rid.
*/
static GraphRow *hashFind(GraphContext *p, int rid){
  int h = rid % p->nHash;
  while( p->apHash[h] && p->apHash[h]->rid!=rid ){
    h++;
    if( h>=p->nHash ) h = 0;
  }
  return p->apHash[h];
}

/*
** 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){

  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.
*/
int graph_add_row(
  GraphContext *p,     /* The context to which the row is added */
  int rid,             /* RID for the check-in */

  int nParent,         /* Number of parents */
  int *aParent,        /* Array of parents */
  const char *zBranch  /* Branch for this check-in */
){
  GraphRow *pRow;

  if( p->nErr ) return 0;
  if( nParent>GR_MAX_PARENT ){ p->nErr++; return 0; }
  pRow = (GraphRow*)safeMalloc( sizeof(GraphRow) );
  pRow->rid = rid;

  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;
  p->nRow++;
  pRow->idx = p->nRow;
  return pRow->idx;
}

/*
** Return the index of a rail currently not in use for any row between
** top and bottom, inclusive.  
*/
static int findFreeRail(

}

/*
** Compute the complete graph
*/
void graph_finish(GraphContext *p, int omitDescenders){
  GraphRow *pRow, *pDesc;


  int i;

  u32 mask;
  u32 inUse;

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

  /* Initialize all rows */


  p->nHash = p->nRow*2 + 1;
  p->apHash = safeMalloc( sizeof(p->apHash[0])*p->nHash );
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    if( pRow->pNext ) pRow->pNext->pPrev = pRow;

    pRow->iRail = -1;
    pRow->mergeOut = -1;
    hashInsert(p, pRow);
  }
  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( hashFind(p, pRow->aParent[i])==0 ){
        pRow->aParent[i] = pRow->aParent[--pRow->nParent];
        i--;
      }
    }
  }

  /* Figure out which nodes have no direct children (children on
  ** the same rail).  Mark such nodes is isLeaf.
  */
  memset(p->apHash, 0, sizeof(p->apHash[0])*p->nHash);
  for(pRow=p->pLast; pRow; pRow=pRow->pPrev) pRow->isLeaf = 1;
  for(pRow=p->pLast; pRow; pRow=pRow->pPrev){
    GraphRow *pParent;
    hashInsert(p, pRow);
    if( pRow->nParent>0
     && (pParent = hashFind(p, pRow->aParent[0]))!=0
     && pRow->zBranch==pParent->zBranch
    ){
      pParent->isLeaf = 0;
    }
  }

  /* 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 || hashFind(p,pRow->aParent[0])==0 ){
      if( omitDescenders ){
        pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, 0, 0);
      }else{
        pRow->iRail = ++p->mxRail;
      }
      mask = 1<<(pRow->iRail);
      if( omitDescenders ){

  */
  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];

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

        }
      }
      pRow->mergeIn |= 1<<pDesc->mergeOut;
    }
  }

  /*
  ** Find the maximum rail number.
  */














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

}