/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 
/* vim: set ts=2 et sw=2 tw=80: */
/*
   Copyright (c) 2014 D. Richard Hipp
  
   This program is free software; you can redistribute it and/or
   modify it under the terms of the Simplified BSD License (also
   known as the "2-Clause License" or "FreeBSD License".)
  
   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.
  
   Author contact information:
     drh@hwaci.com
     http://www.hwaci.com/drh/
  
  *****************************************************************************
   This file contains routines related to working with the filesystem.
*/
#include "fossil-scm/fossil-internal.h"
#include "fossil-scm/fossil-path.h"
#include <assert.h>

/* Only for debugging */
#include <stdio.h>
#define MARKER(pfexp)                                               \
  do{ printf("MARKER: %s:%d:%s():\t",__FILE__,__LINE__,__func__);   \
    printf pfexp;                                                   \
  } while(0)


static const fsl_path_node fsl_path_node_empty = {0,0,0,0,0,{0},0};
const fsl_path fsl_path_empty = fsl_path_empty_m;

void fsl_path_clear(fsl_path *path){
  fsl_path_node * p;
  while(path->pAll){
    p = path->pAll;
    path->pAll = p->pAll;
    fsl_free(p);
  }
  fsl_id_bag_clear(&path->seen);
  *path = fsl_path_empty;
}

fsl_path_node * fsl_path_first(fsl_path *p){
  return p->pStart;
}

fsl_path_node * fsl_path_last(fsl_path *p){
  return p->pEnd;
}

int fsl_path_length(fsl_path const * p){
  return p->nStep;
}

fsl_path_node * fsl_path_next(fsl_path_node *p){
  return p->u.pTo;
}

fsl_path_node * fsl_path_midpoint(fsl_path * path){
  if( path->nStep<2 ) return 0;
  else{
    fsl_path_node *p;
    int i;
    int const max = path->nStep/2;
    for(p=path->pEnd, i=0; p && i<max; p=p->pFrom, i++){}
    return p;
  }
}


/**
   Reconstructs path from path->pStart to path->pEnd, reversing its
   order by fiddling with the u->pTo fields. 

   Unfortunately does not reverse after the initial creation/reversal
   :/.
*/
void fsl_path_reverse(fsl_path * path);
void fsl_path_reverse(fsl_path * path){
  fsl_path_node *p;
  assert( path->pEnd!=0 );
  for(p=path->pEnd; p && p->pFrom; p = p->pFrom){
    p->pFrom->u.pTo = p;
  }
  path->pEnd->u.pTo = 0;
  assert( p==path->pStart );
}

/**
   Adds a new node to path and returns it. Returns 0 on allocation error.
   path must not be 0. rid must be greater than 0. pFrom may be 0. If
   pFrom is not 0 then isParent must be true if pFrom is a parent of
   rid.

   On success, sets the returned node as path->pCurrent, sets its
   pFrom to the given pFrom, and sets rc->u.pPeer to the prior
   path->pCurrent value.
*/
static fsl_path_node * fsl_path_new_node(fsl_path * path, fsl_id_t rid,
                                         fsl_path_node * pFrom, char isParent){
  fsl_path_node * rc = 0;
  assert(path);
  assert(rid>0);
  if(0 != fsl_id_bag_insert(&path->seen, rid)) return 0;
  rc = (fsl_path_node*)fsl_malloc(sizeof(fsl_path_node));
  if(!rc){
    fsl_id_bag_remove(&path->seen, rid);
    return 0;
  }
  *rc = fsl_path_node_empty;
  rc->rid = rid;
  rc->fromIsParent = pFrom ? isParent : 0;
  rc->pFrom = pFrom;
  rc->u.pPeer = path->pCurrent;
  path->pCurrent = rc;
  rc->pAll = path->pAll;
  path->pAll = rc;
  return rc;
}

int fsl_path_shortest( fsl_cx * f, fsl_path * path,
                       fsl_id_t iFrom, fsl_id_t iTo,
                       char directOnly, char oneWayOnly ){
  fsl_stmt s = fsl_stmt_empty;
  fsl_db * db = fsl_needs_repo(f);
  int rc = 0;
  fsl_path_node * pPrev;
  fsl_path_node * p;
  assert(db);
  if(!db) return FSL_RC_NOT_A_REPO;
  else if(iFrom<=0){
    return fsl_cx_err_set(f, FSL_RC_RANGE,
                          "Invalid 'from' RID: %d", (int)iFrom);
  }else if(iTo<=0){
    /*
      Possible TODO: if iTo==0, use... what? Checkout? Tip of current
      checkout branch? Trunk? The multitude of options make it impossible
      to decide :/.      
    */
    return fsl_cx_err_set(f, FSL_RC_RANGE,
                          "Invalid 'to' RID: %d", (int)iTo);
  }

  fsl_path_clear(path);
  path->pStart = fsl_path_new_node(path, iFrom, 0, 0);
  if(!path->pStart){
    return fsl_cx_err_set(f, FSL_RC_OOM, 0);
  }
  if( iTo == iFrom ){
    path->pEnd = path->pStart;
    return 0;
  }

  if( oneWayOnly ){
    if(directOnly){
      rc = fsl_db_prepare(db, &s,
                          "SELECT cid, 1 FROM plink WHERE pid=?1 AND isprim");
    }else{
      rc = fsl_db_prepare(db, &s,
                          "SELECT cid, 1 FROM plink WHERE pid=?1");
    }
  }else if( directOnly ){
    rc = fsl_db_prepare(db, &s,
                        "SELECT cid, 1 FROM plink WHERE pid=?1 AND isprim "
                        "UNION ALL "
                        "SELECT pid, 0 FROM plink WHERE cid=?1 AND isprim");
  }else{
    rc = fsl_db_prepare(db, &s,
                        "SELECT cid, 1 FROM plink WHERE pid=?1 "
                        "UNION ALL "
                        "SELECT pid, 0 FROM plink WHERE cid=?1");
  }
  if(rc){
    fsl_cx_uplift_db_error(f, db);
    assert(f->error.code);
    goto end;
  }

  while(path->pCurrent){
    ++path->nStep;
    pPrev = path->pCurrent;
    path->pCurrent = 0;
    while( pPrev ){
      rc = fsl_stmt_bind_id(&s, 1, pPrev->rid);
      assert(0==rc);
      while( FSL_RC_STEP_ROW == fsl_stmt_step(&s) ){
        fsl_id_t const cid = fsl_stmt_g_id(&s, 0);
        int const isParent = fsl_stmt_g_int32(&s, 1);
        assert((cid>0) && "fsl_id_bag_find() asserts this.");
        if( fsl_id_bag_contains(&path->seen, cid) ) continue;
        p = fsl_path_new_node(path, cid, pPrev, isParent ? 1 : 0);
        if(!p){
          rc = fsl_cx_err_set(f, FSL_RC_OOM, 0);
          goto end;
        }
        if( cid == iTo ){
          fsl_stmt_finalize(&s);
          path->pEnd = p;
          fsl_path_reverse( path );
          return 0;
        }
      }
      fsl_stmt_reset(&s);
      pPrev = pPrev->u.pPeer;
    }
  }
  end:
  fsl_stmt_finalize(&s);
  fsl_path_clear(path);
  return rc;
}


#undef MARKER