/**
 * This module contains strategies for working on lists using indexes.
 * An indexed list works similarly to an array in that every element of
 * the list is associated with in an integer index, and the first 
 * element has index 1.
 * 
 * Adding the indices to a list is done by add-indices.
 *
 */
module collection/list/index
imports 
  collection/list/cons 
  strategy/traversal/simple

strategies

 /**
  * Get the n-th element of a list.
  * The first element has index 1.
  *
  * @type (Int, List(a)) -> a
  * @inc test-index
  */
  index =
    ?(i, <id>); index(|i)

strategies

  /**
   * Get the i-th element of a list.
   * The first element has index 1.
   *
   * @type List(a) -> a   
   */    
  index(|i) =
    at-index(?t | <dec> i); !t

strategies

  /**
   * Get index of element in list.
   *
   * @type (a, List(a)) -> Int
   */
  get-index = 
    Gind0 ; rec x(Gind1 <+ Gind2 ; x)
 
  
  /** @internal */
  Gind0  : (x, ys) -> (1, x, ys)
  
  /** @internal */
  Gind1  : (n, x, [x | xs]) -> n
  
  /** @internal */
  Gind2  : (n, y, [x | xs]) -> (<add> (n, 1), y, xs)

  get-index0(s) = at-suffix([s | id]; ![]); length

strategies

  /**
   * Change element in list.
   * The first element has index 0.
   *
   * @type (Int, a, List(a)) -> List(a)
   * @inc  test-set-index
   */
  set-index =
    ?(i, x, xs)
    ; <at-index(!x)> (i, xs)

  /**
   * Apply s at the specified index
   * The first element has index 0.
   *
   * @type (Int, List(a)) -> List(a)
   */
  at-index(s) =
    ?(i, <id>)
    ; at-index(s | i)
    
  /**
   * Apply s at the specified index i.
   * The first element has index 0.
   *
   * @type List(a)) -> List(a)
   */
  at-index(s | i) =
    let next(|j) =
          if !j => i then
            [s | id]
          else
            [id | next(|<inc> j)]
          end
     in next(|0)
    end

  /**
   * Apply s to the list containing the elements
   * from index i onwards from the original list.
   * The first element has index 0.
   * 
   * @type List(a) -> List(a)
   */
  at-index-tail(s|i) =
    let next(|j) =
      if !j => i then
        s
      else
        [id | next(|<inc> j)]
      end
    in next(|0)
    end

strategies

  /**
   * Insert element in list.
   *
   * @type (Int, a, List(a)) -> List(a)
   * @inc test-insert
   */
  insert =
    Ins0; rec x(Ins1 <+ Ins2(x))

  /** @internal */
  Ins0:    (i, x, ys) -> (0, i, x, ys)
  
  /** @internal */
  Ins1:    (i, i, x, xs) -> [x | xs]
  
  /** @internal */
  Ins2(r): (n, i, x, [y | ys]) -> [y | <r>(<add> (n, 1), i, x, ys)]


strategies

  /**
   * Map a strategy over a list where the strategy takes the index as a term argument.
   *
   * @param Strategy to apply to all the elements of the list.
   * @param The first index (e.g. 0 or 1)
   * @type  List(a) -> List(b)
   */
  nmap(s : Int * a -> b | i) =
    [] + [s(|i) | nmap(s | <inc> i)]
    
  /**
   * Apply strategies that require some knowledge of the index of an element 
   * to the elements of the list.
   *
   * The index of the first element is 1.
   *
   * @param Int * a -> b
   * @type  List(a) -> List(b)
   * @inc  test4a
   * @inc  test4b
   */
  map-with-index(s) =
    let apply(|i) = <s> (i, <id>)
     in nmap(apply | 1)
    end

  /**
   * Adds indices to the elements of a list.
   * The index of the first element is 1.
   *
   * Example: <add-indices> [1,2,3] => [(1,1),(2,2),(3,3)]
   *
   * @type List(a) -> List((Int, a))
   * @inc test5
   */
  add-indices = 
    map-with-index(id)