# == Synopsis
#
# Library to support Cartagena play
# 
# == Author
# Neil Smith
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# 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 program.  If not, see <http://www.gnu.org/licenses/>.
#
# == Change history
# Version 1.0::  11 Jun 2008  
#                * Initial build
#         1.1::  5 Dec 2008
# =>             * Now tracks played cards when generating new games

# Symbols
$SYMBOLS = [:bottle, :dagger, :gun, :hat, :keys, :skull]

# The number of cards of each symbol in the deck
$CARDS_PER_SYMBOL = 17

# The number of cards initiall dealt to each player
$INITIAL_CARDS_PER_PLAYER = 3

# Maximum number of pieces on a position
$MAX_PIECES_PER_POSITION = 3

# Number of actions that can be taken by each player in sequence
$MAX_MOVES_PER_TURN = 3

# Errors for a game

# Moves can only be [1..6] spaces
class InvalidMoveError < StandardError
end

# Game is won when only one player has uncaptured pieces
class GameWonNotice < StandardError
end

# A position on the board.
class Position
  attr_accessor :symbol
  attr_accessor :contains
  
  def initialize(symbol)
    @symbol = symbol
    @contains = []
  end
end

# A tile that makes up the board.  Each tile has two sides, each with six
# positions.  Tiles can be either way up, and either way round.
class Tile
  attr_reader :exposed, :front, :back
  
  def initialize(front, back)
    @front = front.collect {|s| Position.new(s)}
    @back = back.collect {|s| Position.new(s)}
    @exposed = @front
    @exposed_side = :front
  end
  
  def flip!
    if @exposed_side == :front
      @exposed = @back
      @exposed_side = :back
    else
      @exposed = @front
      @exposed_side = :front
    end
  end
  
  def reverse!
    @exposed = @exposed.reverse
  end
end


# The game board
class Board

  attr_accessor :positions
  attr_reader :tiles

  # A laborious procedure to create all the positions and tie them all together
  def initialize(tiles_used)
    # A hash of all positions, indexed by position names
    @tiles = [Tile.new([:hat, :keys, :gun, :bottle, :skull, :dagger], 
        [:hat, :keys, :gun, :bottle, :skull, :dagger]),
      Tile.new([:gun, :hat, :dagger, :skull, :bottle, :keys],
        [:gun, :hat, :dagger, :skull, :bottle, :keys]),
      Tile.new([:skull, :gun, :bottle, :keys, :dagger, :hat],
        [:skull, :gun, :bottle, :keys, :dagger, :hat]),
      Tile.new([:dagger, :bottle, :keys, :gun, :hat, :skull],
        [:dagger, :bottle, :keys, :gun, :hat, :skull]),
      Tile.new([:keys, :dagger, :skull, :hat, :gun, :bottle],
        [:keys, :dagger, :skull, :hat, :gun, :bottle]),
      Tile.new([:bottle, :skull, :hat, :dagger, :keys, :gun],
        [:bottle, :skull, :hat, :dagger, :keys, :gun])                 
    ].shuffle[0...tiles_used]
    @tiles = @tiles.each do |t|
      if rand < 0.5
        t.reverse!
      else
        t
      end
    end

    @positions = [Position.new(:cell)]
    @tiles.each {|t| t.exposed.each {|p| @positions << p}}
    @positions << Position.new(:boat)
  end # def

  def to_s
    layout
  end
  
  def to_str
    to_s
  end
  
  
  # For each position, show its name and what it touches
  def layout
    out_string = ""
    @positions.each {|position| out_string << "#{position.symbol}\n"}
    out_string
  end

end


# Each piece on the board is an object
class Piece
  attr_reader :player, :number
  attr_accessor :position

  def initialize(position, player, number)
    @position = position
    @player = player
    @number = number
  end

  def to_s
    "#{@player}:#{@number}"
  end
  
  def to_str
    to_s
  end

  def show(convert_to_zero_based_player_number = false)
    if convert_to_zero_based_player_number
      "#{@player + 1}:#{@number}"   
    else
      "#{@player}:#{@number}"  
    end
  end
  
  def move_to(new_position)
    @position = new_position
  end

end


# A move in a game
class Move
  attr_reader :piece, :origin, :destination, :card_played
  
  def initialize(piece, origin, destination, card_played = :unspecified)
    @piece = piece
    @origin = origin
    @destination = destination
    @card_played = card_played
  end

  def show(board, convert_to_zero_based_player_number = false)
    if @card_played == :unspecified
      "#{@piece.show(convert_to_zero_based_player_number)}: #{board.positions.index(@origin)} -> #{board.positions.index(@destination)}"
    else
      "#{@piece.show(convert_to_zero_based_player_number)}: #{board.positions.index(@origin)} -> #{board.positions.index(@destination)} (#{@card_played})"
    end
  end
  
  def format(board, convert_to_zero_based_player_number = false)
    display_player_number = if convert_to_zero_based_player_number then
      @piece.player + 1
    else
      @piece.player
    end
    if @card_played ==:unspecified
      "#{display_player_number} #{board.positions.index(@origin)} #{board.positions.index(@destination)}"
    else
      "#{display_player_number} #{board.positions.index(@origin)} #{board.positions.index(@destination)} #{@card_played}"
    end
  end
  
  # Write a move to a string
  # Note the inverse, String#to_move, is defined below
  def to_s
    "#{@piece.player} #{@origin.to_s}  #{@destination.to_s} #{@card_played}"
  end
  
  def to_str
    to_s
  end
  
end



# A class to record each of the states previously found in a game.  
# Note that this is a deep copy of the pieces and what they've captured, so 
# you'll need to convert back
class GameState
  attr_accessor :move, :player, :board, :pieces_before_move, :deck_before_move, 
    :players_cards_before_move, :moves_by_current_player
  #    this_game_state = GameState.new(move, player, @board, @pieces, @deck, @players_cards)
  
  
  def initialize(move, player, board, pieces, deck, players_cards, moves_by_current_player)
    @move, @player, @board, @pieces_before_move, @deck_before_move, 
      @players_cards_before_move, @moves_by_current_player = 
      copy_game_state(move, player, board, pieces, deck, players_cards, 
      moves_by_current_player)
  end
  
  #  def ==(other)
  #    @move.to_s == other.move.to_s and
  #      @player == other.player and
  #      @piece_after_move == other.pieces_after_move
  #  end
  
  def copy_game_state(move, player, board, pieces, deck, players_cards, moves_by_current_player)
    copy_player = player
    moving_player = move.piece.player

    copy_board = board.dup
    copy_board.positions = board.positions.collect {|pos| pos.dup}
    copy_board.positions.each {|pos| pos.contains = []}

    copy_pieces = pieces.collect do |players_pieces|
      players_pieces.collect do |piece|
        new_piece_position = copy_board.positions[board.positions.index(piece.position)]
        new_piece = Piece.new(new_piece_position, piece.player, piece.number)
        new_piece_position.contains << new_piece
        new_piece
      end
    end

    piece_index = pieces[moving_player].index(move.piece)
    origin_index = board.positions.index(move.origin)
    destination_index = board.positions.index(move.destination)
    copy_move = Move.new(copy_pieces[moving_player][piece_index], 
      copy_board.positions[origin_index], 
      copy_board.positions[destination_index])
    
    copy_deck = deck.dup
    copy_players_cards = players_cards.collect {|p| p.dup}
    copy_moves_by_current_player = moves_by_current_player

    return copy_move, copy_player, copy_board, copy_pieces, copy_deck, copy_players_cards, copy_moves_by_current_player
  end
  
end


# A game of Cartagena.  It keeps a history of all previous states.  
class Game

  attr_reader :history
  attr_accessor :current_player
  attr_reader :players
  attr_accessor :players_cards
  attr_accessor :moves_by_current_player
  attr_reader :board
  attr_reader :pieces
  attr_reader :cards
  attr_accessor :deck

  # Create a new game
  def initialize(players = 5, number_of_tiles = 6, pieces_each = 6)
    @board = Board.new(number_of_tiles)
    @history = []
    @pieces = []
    @players = [].fill(0, players) {|i| i}
    @players_cards = []
    @current_player = 0
    @moves_by_current_player = 0
    @cards = []
    1.upto($CARDS_PER_SYMBOL) {|x| @cards.concat($SYMBOLS)}
    @deck = @cards.shuffle
    @players.each do |p|
      @pieces[p] = []
      0.upto(pieces_each - 1) do |count|
        piece = Piece.new(@board.positions[0], p, count)
        @pieces[p][count] = piece
        @board.positions[0].contains << piece
      end
      @players_cards[p] = []
      deal_cards!($INITIAL_CARDS_PER_PLAYER, p)
    end
  end

  # Deal some cards to a player.  Remove them from the deck.  Refill the deck
  # if necessary
  def deal_cards!(number_of_cards, player = @current_player)
    1.upto(number_of_cards) do
      if @deck.empty?
        @deck = @cards
        @players_cards.each do |p|
          p.each do |c|
            @deck.delete_at(@deck.index(c))
          end
        end
        @deck = @deck.shuffle
      end
      @players_cards[player] << @deck.pop
    end
  end
  
  # Check that a move is valid.  Throw an exception if it's invalid
  def validate_move(move, player = @current_player)
    # Check the move is a valid one
    raise(InvalidMoveError, "Move #{move}: Player #{player} does not exist") unless @players.include?(player)
    raise(InvalidMoveError, "Move #{move}: None of player #{player}'s pieces on position #{move.origin}") unless move.origin.contains.find {|pc| pc.player == player}
    raise(InvalidMoveError, "Move #{move}: Origin and destination are the same") if move.origin == move.destination
  
    origin_position      = @board.positions.index(move.origin)
    destination_position = @board.positions.index(move.destination)
    # Is this move an advance or a retreat?
    if destination_position > origin_position
      # Advancing a piece
      if move.destination == @board.positions[-1] # A move into the boat
        raise(InvalidMoveError, "Move #{move}: Move into boat and card unspecified") if move.destination == @board.positions[-1] and move.card_played == :unspecified
        unless @players_cards[player].find {|c| c == move.card_played}
          raise(InvalidMoveError, "Player #{player} does not have a card to move a piece into the boat")
        end
      else
        if move.card_played != :unspecified and move.destination.symbol != move.card_played
          raise(InvalidMoveError, "Player #{player} trying to move to #{move.destination}, a #{move.destination.symbol} square with a a #{move.card_played} card")
        end
        unless @players_cards[player].find {|c| c == move.destination.symbol}
          raise(InvalidMoveError, "Player #{player} does not have a card to move a piece to a #{move.destination.symbol} square")
        end
        # Check target square is vacant
        raise(InvalidMoveError, "Advance move #{move}: destination occupied") unless move.destination.contains.empty?
      end
      # Check all the intervening squares with this symbol are occupied
      intervening_empty_position = @board.positions[origin_position...destination_position].index_find do |p| 
        p.symbol == move.destination.symbol and 
          p.contains.empty?
      end
      raise(InvalidMoveError, "Advance move #{move}: location #{intervening_empty_position} is empty") if intervening_empty_position
    else
      # Retreating a piece
      # Check target position has one or two pieces already on it
      destination_count = move.destination.contains.length
      raise(InvalidMoveError, "Retreat move #{move}: destination has no pieces already on it") if destination_count == 0
      raise(InvalidMoveError, "Retreat move #{move}: destination has too many (#{destination_count}) pieces already on it") if destination_count >= $MAX_PIECES_PER_POSITION
      # Check none of the intervening squares have any pieces on them
      # puts "Checking positions #{destination_position} to #{origin_position}"      
      intervening_target_position = @board.positions[(destination_position + 1)...origin_position].index_find do |p| 
        # puts "Examining postition #{p} at location #{@board.positions.index(p)} which contains #{p.contains.length} pieces"        
        p.contains.length > 0 and 
          p.contains.length < $MAX_PIECES_PER_POSITION
      end
      raise(InvalidMoveError, "Retreat move #{move.show(@board)}: location #{intervening_target_position} is a viable target") if intervening_target_position
    end
  end
  
  # Apply a single move to a game.  
  def apply_move!(move, player = @current_player, validate = true)
    
    validate_move(move, player) if validate

    raise(InvalidMoveError, "Too many consecutive moves by #{@current_player}: has taken #{@moves_by_current_player} and validate is #{validate}") if validate and player == @current_player and @moves_by_current_player >= $MAX_MOVES_PER_TURN
       
    # Record the old state
    this_game_state = GameState.new(move, @current_player, @board, @pieces, @deck, @players_cards, @moves_by_current_player)
    @history << this_game_state
    
    # Apply this move
    move.origin.contains.delete move.piece
    move.destination.contains << move.piece
    move.piece.position = move.destination

    if player == @current_player
      @moves_by_current_player += 1
    else
      @current_player = player
      @moves_by_current_player = 1
    end
   
    # Update cards
    if @board.positions.index(move.destination) > @board.positions.index(move.origin)
      # Advance move
      if validate
        card_to_remove = if move.card_played != :unspecified
          move.card_played
        else
          move.destination.symbol
        end
        if @players_cards[player].include?(card_to_remove)
          @players_cards[player].delete_at(@players_cards[player].index(card_to_remove))
        end
      end
    else
      # Retreat move
      deal_cards!(move.destination.contains.length - 1, player)
    end
    
    # If this player has all their pieces in the boat, declare a win.
    if @pieces[player].all? {|pc| pc.position == @board.positions[-1]}
      raise(GameWonNotice, "Game won by #{player}")
    end
  end
  
  # Undo a move 
  def undo_move!
    state_to_restore = @history[-1]
    move, @current_player, @board, @pieces, @deck, @players_cards, 
      @moves_by_current_player = 
      state_to_restore.copy_game_state(state_to_restore.move, 
      state_to_restore.player, 
      state_to_restore.board, 
      state_to_restore.pieces_before_move, 
      state_to_restore.deck_before_move, 
      state_to_restore.players_cards_before_move, 
      state_to_restore.moves_by_current_player)
    @history.pop    
  end
    
  # Apply a list of moves in order
  def apply_moves!(moves)
    moves.each do |move| 
      @current_player = move.piece.player
      apply_move!(move, @current_player)
      next_player! if @moves_by_current_player >= $MOVES_PER_TURN
    end
  end


  # Set the current player to be the next player
  def next_player!
    if @current_player == @players[-1]
      @current_player = @players[0]
    else
      @current_player = @players[@players.index(@current_player) + 1]
    end
    @moves_by_current_player = 0
    @current_player
  end

  
  def reset_current_player(new_current_player)
    @current_player = new_current_player
    @moves_by_current_player = 0
  end

  
  # Return an array of all possible moves from this state, given the active player
  def possible_moves(player = @current_player)
    moves = []
    @pieces[player].each do |piece|
      # Do a forward move for each card held
      unless piece.position == @board.positions[-1]
        @players_cards[player].each do |card|
          destination = @board.positions[@board.positions.index(piece.position)..-1].find do |pos|
            (pos.symbol == card and pos.contains == []) or
              pos.symbol == :boat
          end
          # puts "Player #{player}, card #{card}, piece #{piece.number} at position #{@board.positions.index(piece.position)} to #{@board.positions.index(destination)}, a #{destination.symbol}"        
          moves << Move.new(piece, piece.position, destination, card)
        end
      end
      # Do a reverse move for the piece
      unless piece.position == board.positions[0]
        destination = @board.positions[1...@board.positions.index(piece.position)].reverse.find do |pos|
          pos.contains.length == 1 or pos.contains.length == 2
        end
        if destination
          # puts "Player #{player}, piece #{piece.number} at position #{@board.positions.index(piece.position)} retreats to #{@board.positions.index(destination)}, a #{destination.symbol} containing #{destination.contains.length} pieces"
          moves << Move.new(piece, piece.position, destination)
        end
      end
    end
    # moves.each {|m| puts m.show(@board)}    
    moves
  end

  def build_state_string
    outstr = "Current player = #{@current_player}\n"
    0.upto((@board.positions.length)-1) do |i|
      outstr << "#{i}: #{@board.positions[i].symbol}: "
      @board.positions[i].contains.each do |piece|
        outstr << "P#{piece.player}:#{piece.number} "
      end
      outstr << "\n"
    end
    0.upto((@players.length)-1) do |i|
      outstr << "Player #{i} holds " << (@players_cards[i].sort_by {|c| c.to_s}).join(', ') << "\n"
    end
    outstr << "Deck holds " << @deck.join(', ') << "\n"
    outstr
  end
  
  # Show the state of the board
  def show_state
    puts build_state_string
  end

  def to_s
    show_state
  end
  
  def to_str
    to_s
  end
  

  def set_testing_game!
    srand 1234
    @board = nil
    initialize(5, 6, 6)
    board_symbols = [:cell, :gun, :keys, :dagger, :hat, :skull, :bottle,
      :keys, :dagger, :skull, :hat, :gun, :bottle, 
      :dagger, :bottle, :keys, :gun, :hat, :skull, 
      :dagger, :skull, :bottle, :gun, :keys, :hat, 
      :hat, :dagger, :keys, :bottle, :gun, :skull, 
      :keys, :bottle, :skull, :dagger, :hat, :gun, :boat]
    board_symbols.each_index do |i|
        @board.positions[i].symbol = board_symbols[i]
      end
      
    @players_cards[0] = [:gun,    :hat,   :skull]
    @players_cards[1] = [:bottle, :keys,  :keys]
    @players_cards[2] = [:bottle, :hat,   :keys]
    @players_cards[3] = [:bottle, :skull, :skull]
    @players_cards[4] = [:bottle, :gun,   :gun]
    
    @deck = [:hat, :dagger, :hat, :hat, :skull, :bottle, :bottle, :bottle, :dagger, 
      :keys, :hat, :dagger, :skull, :skull, :dagger, :gun, :skull, :gun, 
      :gun, :skull, :keys, :keys, :gun, :hat, :dagger, :keys, :dagger,
      :hat, :gun, :skull, :keys, :gun, :skull, :gun, :hat, :gun, :dagger,
      :gun, :gun, :hat, :hat, :bottle, :gun, :dagger, :hat, :skull, :dagger,
      :bottle, :hat, :skull, :gun, :bottle, :keys, :hat, :bottle, :keys,
      :dagger, :bottle, :bottle, :dagger, :keys, :dagger, :dagger, :dagger,
      :skull, :hat, :dagger, :dagger, :hat, :keys, :skull, :bottle, :skull,
      :keys, :bottle, :keys, :bottle, :gun, :keys, :hat, :keys, :dagger,
      :gun, :skull, :keys, :bottle, :skull]
    
  end
  
  # Given a set of lines from an input file, turn them into a Game object and 
  # a set of Move objects.
  # Note the multiple return values.
  # Class method
  def Game.read_game(gamelines)
    gamelines.each {|l| l.chomp!}
    game = Game.new(gamelines[0].to_i, 6, 6)
    
    # create the board
    2.upto(38) do |i|
      game.board.positions[i-1] = Position.new(gamelines[i].to_sym)
    end
    
    # read all the moves so far
    moves = []
    i = 39
    current_player_moves = 0
    current_player = 0
    player_card_counts = game.players_cards.map {|p| $INITIAL_CARDS_PER_PLAYER}
    unused_cards = game.cards.map {|c| c}
    while gamelines[i].in_move_format?
      move = gamelines[i].to_move(game, true)
      if move.piece.player == current_player
        current_player_moves += 1
      else
        current_player = move.piece.player
        current_player_moves = 1
      end
      # if move is an advance move, decrement the cards held by the player and remove the card from unused cards
      #   throw an error if an advance move is made when all the cards of that type have been used
      #   if unused_cards becomes empty, restock it.  
      if game.board.positions.index(move.destination) > game.board.positions.index(move.origin)
        raise(InvalidMoveError, "Game reading: Player #{move.piece.player} attempting an advance move with no cards in hand.  Move is #{gamelines[i]} on line #{i}") if player_card_counts[move.piece.player] == 0
        card_used = move.destination.symbol
        if card_used == :boat
          card_used = move.card_played
        end
        raise(InvalidMoveError, "Attempting to move into boat without a card specified") if card_used == :unspecified
        raise(InvalidMoveError, "Game reading: Player #{move.piece.player} attempting an advance move to a #{move.destination.symbol} place when all those cards have been used. Move is #{gamelines[i]} on line #{i}") unless unused_cards.include? card_used
        player_card_counts[current_player] -= 1
        unused_cards.delete_at(unused_cards.index(card_used))
      # if move is a retreat move, increment the cards held by the player
      else
        player_card_counts[current_player] += move.destination.contains.length
        if unused_cards.length == player_card_counts.inject {|sum, n| sum + n }
          unused_cards = game.cards.map {|c| c}
        end
      end
      game.apply_move!(move, move.piece.player, false)
      moves << move
      i = i + 1
    end
    
    # note the current player
    game.current_player = gamelines[i].to_i - 1
    if game.current_player == current_player
      game.moves_by_current_player = current_player_moves
    else
      game.moves_by_current_player = 0
    end
    current_player = game.current_player
    
    # read the cards
    game.players_cards = game.players_cards.map {|c| []}
    (i+1).upto(gamelines.length - 1) do |j|
      game.players_cards[game.current_player] << gamelines[j].to_sym
      raise(InvalidMoveError, "Player #{game.current_player} given a #{gamelines[j]} card, but none left in deck") unless unused_cards.index(gamelines[j].to_sym)
      unused_cards.delete_at(unused_cards.index(gamelines[j].to_sym))
    end
    raise(InvalidMoveError, "Player #{game.current_player} given #{game.players_cards[game.current_player].length} cards, but should have #{player_card_counts[game.current_player]} cards from play") if game.players_cards[game.current_player].length != player_card_counts[game.current_player]
    
    # Update the game deck
    game.deck = unused_cards.shuffle
    player_card_counts[game.current_player] = 0
    player_card_counts.each_index do |player|
      if player_card_counts[player] > 0
        game.deal_cards!(player_card_counts[player], player)
      end
    end
    return game, moves
  end

end
  

# Extension to String class to convert a move-description string into a Move object.  
# This is the inverse of the Move#to_s method
class String
  def in_move_format?
    elements = split
    return ((elements.length == 3 or elements.length == 4) and
        elements[0].to_i > 0 and elements[0].to_i < 6 and
        elements[1].to_i >= 0 and elements[1].to_i <= 37 and
        elements[2].to_i >= 0 and elements[2].to_i <= 37)
  end
  
  def to_move(game, convert_to_zero_based_player_number = false)
    move_elements = self.downcase.split
    player = move_elements[0].to_i
    player = player - 1 if convert_to_zero_based_player_number
    origin_index = move_elements[1].to_i
    destination_index = move_elements[2].to_i
    raise(InvalidMoveError, "Invalid origin #{origin_index} in move read") unless origin_index >= 0 and origin_index < game.board.positions.length
    raise(InvalidMoveError, "Invalid destination #{destination_index} in move read") unless destination_index > 0 and destination_index <= game.board.positions.length
    raise(InvalidMoveError, "Player #{player} does not have a piece on position #{origin_index} in move read") unless game.board.positions[origin_index].contains.any? {|p| p.player == player}
    piece = game.board.positions[origin_index].contains.find {|p| p.player == player}
    piece_name = piece.number
    if destination_index > origin_index
      if move_elements.length == 4 
        card_used = move_elements[3].chomp.to_sym
        raise(InvalidMoveError, "Card used (#{card_used}) does not match destination space (#{game.board.positions[destination_index].symbol})") unless card_used == game.board.positions[destination_index].symbol or destination_index == game.board.positions.length - 1
        Move.new(game.pieces[player][piece_name], 
                 game.board.positions[origin_index], 
                 game.board.positions[destination_index],
                 card_used)
      else
        card_used = :unspecified
        raise(InvalidMoveError, "Move to boat without specifying card used") if destination_index == game.board.positions.length + 1
        Move.new(game.pieces[player][piece_name], 
                 game.board.positions[origin_index], 
                 game.board.positions[destination_index])
      end
    else
      Move.new(game.pieces[player][piece_name], 
        game.board.positions[origin_index], 
        game.board.positions[destination_index])
    end
  end
end


# Read a game description file and convert it into a Game object and set of Move objects.
# Note that Game.read_game method returns multiple values, so this one does too.
class IO
  def IO.read_game(filename)
    gamelines = IO.readlines(filename)
    return Game.read_game(gamelines)
  end
end

# Extension to the Array class to include the Array#shuffle function
class Array
  def shuffle
    sort_by { rand }
  end
  
  def index_find(&block)
    found = find(&block)
    if found
      index found
    else
      found
    end
  end
end