/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 
/* vim: set ts=2 et sw=2 tw=80: */
#if !defined(NET_FOSSIL_SCM_FSL_PATH_H_INCLUDED)
#define NET_FOSSIL_SCM_FSL_PATH_H_INCLUDED
/*
   Copyright (c) 2013 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 declares public APIs relating to generating hash values
   hashing.
*/

#include "fossil-internal.h" /* MUST come first b/c of config macros */

#if defined(__cplusplus)
extern "C" {
#endif

  typedef struct fsl_path_node fsl_path_node;
  typedef struct fsl_path fsl_path;


  /**

     Holds information for a single node in a path of checkin versions.

     @see fsl_path
  */
  struct fsl_path_node {
    /** ID for this node */
    fsl_id_t rid;
    /** True if pFrom is the parent of rid */
    char fromIsParent;
    /** True if primary side of common ancestor */
    char isPrimary;
    /* HISTORICAL: Abbreviate output in "fossil bisect ls" */
    char isHidden;
    /** Node this one came from. */
    fsl_path_node *pFrom;
    union {
      /** List of nodes of the same generation */
      fsl_path_node *pPeer;
      /** Next on path from beginning to end */
      fsl_path_node *pTo;
    } u;
    /** List of all nodes */
    fsl_path_node *pAll;
  };

  /**
     A utility type for collecting "paths" between two checkin versions.
  */
  struct fsl_path{
    /** Current generation of nodes */
    fsl_path_node *pCurrent;
    /** All nodes */
    fsl_path_node *pAll;
    /** Nodes seen before */
    fsl_id_bag seen;
    /** Number of steps from first to last. */
    int nStep;
    /** Earliest node in the path. */
    fsl_path_node *pStart;
    /** Common ancestor of pStart and pEnd */
    fsl_path_node *pPivot;
    /** Most recent node in the path. */
    fsl_path_node *pEnd;
  };

  /**
     An empty-initialize fsl_path object, intended for const-copy
     initialization.
  */
#define fsl_path_empty_m {0,0,fsl_id_bag_empty_m,0,0,0,0}

  /**
     An empty-initialize fsl_path object, intended for copy
     initialization.
  */
  extern const fsl_path fsl_path_empty;


  /**
     Returns the first node in p's path.

     The returned node is owned by path may be invalidated by any APIs
     which manipulate path.
  */
  fsl_path_node * fsl_path_first(fsl_path *p);

  /**
     Returns the last node in p's path.

     The returned node is owned by path may be invalidated by any APIs
     which manipulate path.
  */
  fsl_path_node * fsl_path_last(fsl_path *p);

  /**
     Returns the next node p's path.

     The returned node is owned by path may be invalidated by any APIs
     which manipulate path.

     Intended to be used like this:

     @code
     for( p = fsl_path_first(path) ;
     p ;
     p = fsl_path_next(p)){
     ...
     }
     @endcode
  */
  fsl_path_node * fsl_path_next(fsl_path_node *p);

  /**
     Returns p's path length.
  */
  int fsl_path_length(fsl_path const * p);

  /**
     Frees all nodes in path (which must not be NULL) and resets all
     state in path. Does not free path.
  */
  void fsl_path_clear(fsl_path *path);

  /**
     Find the mid-point of the path.  If the path contains fewer than
     2 steps, returns 0. The returned node is owned by path may be
     invalidated by any APIs which manipulate path.
  */
  fsl_path_node * fsl_path_midpoint(fsl_path * path);


  /**
     Computes the shortest path from checkin versions iFrom to iTo
     (inclusive), storing the result state in path. If path has
     state before this is called, it is cleared by this call.

     iFrom and iTo must both be valid checkin version RIDs.

     If directOnly is true, then use only the "primary" links from
     parent to child.  In other words, ignore merges.

     On success, returns 0 and path->pStart will point to the
     beginning of the path (the iFrom node). If pStart is 0 then no
     path could be found but 0 is still returned.

     Elements of the path can be traversed like so:

     @code
     fsl_path path = fsl_path_empty;
     fsl_path_node * n = 0;
     int rc = fsl_path_shortest(f, &path, versionFrom, versionTo, 1, 0);
     if(rc) { ... error ... }
     for( n = fsl_path_first(&path); n; n = fsl_path_next(n) ){
       ...
     }
     fsl_path_clear(&path);
     @endcode

     On error, f's error state may be updated with a description of the
     problem.
  */
  int fsl_path_shortest( fsl_cx * f, fsl_path * path,
                         fsl_id_t iFrom, fsl_id_t iTo,
                         char directOnly, char oneWayOnly );



#if defined(__cplusplus)
} /*extern "C"*/
#endif
#endif
/* NET_FOSSIL_SCM_FSL_PATH_H_INCLUDED */
