nodes: 0, module; 1, function_definition; 2, function_name:_prune_beam; 3, parameters; 4, type; 5, block; 6, typed_parameter; 7, typed_parameter; 8, typed_default_parameter; 9, generic_type; 10, expression_statement; 11, expression_statement; 12, for_statement; 13, expression_statement; 14, for_statement; 15, return_statement; 16, identifier:states; 17, type; 18, identifier:beam_size; 19, type; 20, identifier:sort_states; 21, type; 22, False; 23, identifier:List; 24, type_parameter; 25, comment:"""
          This method can be used to prune the set of unfinished states on a beam or finished states
          at the end of search. In the former case, the states need not be sorted because the all come
          from the same decoding step, which does the sorting. However, if the states are finished and
          this method is called at the end of the search, they need to be sorted because they come
          from different decoding steps.
          """; 26, assignment; 27, identifier:state; 28, identifier:states; 29, block; 30, assignment; 31, pattern_list; 32, call; 33, block; 34, identifier:pruned_states; 35, generic_type; 36, identifier:int; 37, identifier:bool; 38, type; 39, identifier:states_by_batch_index; 40, type; 41, call; 42, assert_statement; 43, expression_statement; 44, expression_statement; 45, identifier:pruned_states; 46, list; 47, identifier:_; 48, identifier:instance_states; 49, attribute; 50, argument_list; 51, if_statement; 52, for_statement; 53, identifier:List; 54, type_parameter; 55, identifier:State; 56, generic_type; 57, identifier:defaultdict; 58, argument_list; 59, comparison_operator:len(state.batch_indices) == 1; 60, assignment; 61, call; 62, identifier:states_by_batch_index; 63, identifier:items; 64, identifier:sort_states; 65, block; 66, identifier:state; 67, subscript; 68, block; 69, type; 70, identifier:Dict; 71, type_parameter; 72, identifier:list; 73, call; 74, integer:1; 75, identifier:batch_index; 76, subscript; 77, attribute; 78, argument_list; 79, expression_statement; 80, expression_statement; 81, expression_statement; 82, expression_statement; 83, identifier:instance_states; 84, slice; 85, expression_statement; 86, identifier:State; 87, type; 88, type; 89, identifier:len; 90, argument_list; 91, attribute; 92, integer:0; 93, subscript; 94, identifier:append; 95, identifier:state; 96, assignment; 97, assignment; 98, assignment; 99, assignment; 100, identifier:beam_size; 101, call; 102, identifier:int; 103, generic_type; 104, attribute; 105, identifier:state; 106, identifier:batch_indices; 107, identifier:states_by_batch_index; 108, identifier:batch_index; 109, identifier:scores; 110, call; 111, pattern_list; 112, call; 113, identifier:sorted_states; 114, list_comprehension; 115, identifier:instance_states; 116, identifier:sorted_states; 117, attribute; 118, argument_list; 119, identifier:List; 120, type_parameter; 121, identifier:state; 122, identifier:batch_indices; 123, attribute; 124, argument_list; 125, identifier:_; 126, identifier:sorted_indices; 127, attribute; 128, argument_list; 129, subscript; 130, for_in_clause; 131, identifier:pruned_states; 132, identifier:append; 133, identifier:state; 134, type; 135, identifier:torch; 136, identifier:cat; 137, list_comprehension; 138, identifier:scores; 139, identifier:sort; 140, unary_operator; 141, keyword_argument; 142, identifier:instance_states; 143, identifier:i; 144, identifier:i; 145, call; 146, identifier:State; 147, call; 148, for_in_clause; 149, integer:1; 150, identifier:descending; 151, True; 152, attribute; 153, argument_list; 154, attribute; 155, argument_list; 156, identifier:state; 157, identifier:instance_states; 158, call; 159, identifier:numpy; 160, subscript; 161, identifier:view; 162, unary_operator; 163, attribute; 164, argument_list; 165, attribute; 166, integer:0; 167, integer:1; 168, call; 169, identifier:cpu; 170, identifier:state; 171, identifier:score; 172, attribute; 173, argument_list; 174, identifier:sorted_indices; 175, identifier:detach
code: def _prune_beam(states: List[State],
                      beam_size: int,
                      sort_states: bool = False) -> List[State]:
          """
          This method can be used to prune the set of unfinished states on a beam or finished states
          at the end of search. In the former case, the states need not be sorted because the all come
          from the same decoding step, which does the sorting. However, if the states are finished and
          this method is called at the end of the search, they need to be sorted because they come
          from different decoding steps.
          """
          states_by_batch_index: Dict[int, List[State]] = defaultdict(list)
          for state in states:
              assert len(state.batch_indices) == 1
              batch_index = state.batch_indices[0]
              states_by_batch_index[batch_index].append(state)
          pruned_states = []
          for _, instance_states in states_by_batch_index.items():
              if sort_states:
                  scores = torch.cat([state.score[0].view(-1) for state in instance_states])
                  _, sorted_indices = scores.sort(-1, descending=True)
                  sorted_states = [instance_states[i] for i in sorted_indices.detach().cpu().numpy()]
                  instance_states = sorted_states
              for state in instance_states[:beam_size]:
                  pruned_states.append(state)
          return pruned_states