gt:     Vector<Option> newVector = new Vector<Option>(4);
context: /*
   *   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/>.
   */
  
  /*
   *    BestFirst.java
   *    Copyright (C) 1999-2012 University of Waikato, Hamilton, New Zealand
   *
   */
  
  package weka.attributeSelection;
  
  import java.io.Serializable;
  import java.util.ArrayList;
  import java.util.BitSet;
  import java.util.Enumeration;
  import java.util.Hashtable;
  import java.util.Vector;
  
  import weka.core.Instances;
  import weka.core.Option;
  import weka.core.OptionHandler;
  import weka.core.Range;
  import weka.core.RevisionHandler;
  import weka.core.RevisionUtils;
  import weka.core.SelectedTag;
  import weka.core.Tag;
  import weka.core.Utils;
  
  /**
   <!-- globalinfo-start --> 
   * BestFirst:<br/>
   * <br/>
   * Searches the space of attribute subsets by greedy hillclimbing augmented with
   * a backtracking facility. Setting the number of consecutive non-improving
   * nodes allowed controls the level of backtracking done. Best first may start
   * with the empty set of attributes and search forward, or start with the full
   * set of attributes and search backward, or start at any point and search in
   * both directions (by considering all possible single attribute additions and
   * deletions at a given point).<br/>
   * <p/>
   * <!-- globalinfo-end -->
   * 
   * <!-- options-start --> Valid options are:
   * <p/>
   * 
   * <pre>
   * -P &lt;start set&gt;
   *  Specify a starting set of attributes.
   *  Eg. 1,3,5-7.
   * </pre>
   * 
   * <pre>
   * -D &lt;0 = backward | 1 = forward | 2 = bi-directional&gt;
   *  Direction of search. (default = 1).
   * </pre>
   * 
   * <pre>
   * -N &lt;num&gt;
   *  Number of non-improving nodes to
   *  consider before terminating search.
   * </pre>
   * 
   * <pre>
   * -S &lt;num&gt;
   *  Size of lookup cache for evaluated subsets.
   *  Expressed as a multiple of the number of
   *  attributes in the data set. (default = 1)
   * </pre>
   * 
   <!-- options-end -->
   * 
   * @author Mark Hall (mhall@cs.waikato.ac.nz) Martin Guetlein (cashing merit of
   *         expanded nodes)
   * @version $Revision: 10396 $
   */
  public class BestFirst extends ASSearch implements OptionHandler,
    StartSetHandler {
  
    /** for serialization */
    static final long serialVersionUID = 7841338689536821867L;
  
    // Inner classes
    /**
     * Class for a node in a linked list. Used in best first search.
     * 
     * @author Mark Hall (mhall@cs.waikato.ac.nz)
     **/
    public class Link2 implements Serializable, RevisionHandler {
  
      /** for serialization */
      static final long serialVersionUID = -8236598311516351420L;
  
      /* BitSet group; */
      Object[] m_data;
      double m_merit;
  
      /**
       * Constructor
       */
      public Link2(Object[] data, double mer) {
        // group = (BitSet)gr.clone();
        m_data = data;
        m_merit = mer;
      }
  
      /** Get a group */
      public Object[] getData() {
        return m_data;
      }
  
      @Override
      public String toString() {
        return ("Node: " + m_data.toString() + "  " + m_merit);
      }
  
      /**
       * Returns the revision string.
       * 
       * @return the revision
       */
      @Override
      public String getRevision() {
        return RevisionUtils.extract("$Revision: 10396 $");
      }
    }
  
    /**
     * Class for handling a linked list. Used in best first search. Extends the
     * Vector class.
     * 
     * @author Mark Hall (mhall@cs.waikato.ac.nz)
     **/
    public class LinkedList2 extends ArrayList<Link2> {
  
      /** for serialization */
      static final long serialVersionUID = 3250538292330398929L;
  
      /** Max number of elements in the list */
      int m_MaxSize;
  
      // ================
      // Public methods
      // ================
      public LinkedList2(int sz) {
        super();
        m_MaxSize = sz;
      }
  
      /**
       * removes an element (Link) at a specific index from the list.
       * 
       * @param index the index of the element to be removed.
       **/
      public void removeLinkAt(int index) throws Exception {
  
        if ((index >= 0) && (index < size())) {
          remove(index);
        } else {
          throw new Exception("index out of range (removeLinkAt)");
        }
      }
  
      /**
       * returns the element (Link) at a specific index from the list.
       * 
       * @param index the index of the element to be returned.
       **/
      public Link2 getLinkAt(int index) throws Exception {
  
        if (size() == 0) {
          throw new Exception("List is empty (getLinkAt)");
        } else {
          if ((index >= 0) && (index < size())) {
            return ((get(index)));
          } else {
            throw new Exception("index out of range (getLinkAt)");
          }
        }
      }
  
      /**
       * adds an element (Link) to the list.
       * 
       * @param data the attribute set specification
       * @param mer the "merit" of this attribute set
       **/
      public void addToList(Object[] data, double mer) throws Exception {
        Link2 newL = new Link2(data, mer);
  
        if (size() == 0) {
          add(newL);
        } else {
          if (mer > (get(0)).m_merit) {
            if (size() == m_MaxSize) {
              removeLinkAt(m_MaxSize - 1);
            }
  
            // ----------
            add(0, newL);
          } else {
            int i = 0;
            int size = size();
            boolean done = false;
  
            // ------------
            // don't insert if list contains max elements an this
            // is worst than the last
            if ((size == m_MaxSize) && (mer <= get(size() - 1).m_merit)) {
  
            }
            // ---------------
            else {
              while ((!done) && (i < size)) {
                if (mer > (get(i)).m_merit) {
                  if (size == m_MaxSize) {
                    removeLinkAt(m_MaxSize - 1);
                  }
  
                  // ---------------------
                  add(i, newL);
                  done = true;
                } else {
                  if (i == size - 1) {
                    add(newL);
                    done = true;
                  } else {
                    i++;
                  }
                }
              }
            }
          }
        }
      }
  
      /**
       * Returns the revision string.
       * 
       * @return the revision
       */
      public String getRevision() {
        return RevisionUtils.extract("$Revision: 10396 $");
      }
    }
  
    // member variables
    /** maximum number of stale nodes before terminating search */
    protected int m_maxStale;
  
    /** 0 == backward search, 1 == forward search, 2 == bidirectional */
    protected int m_searchDirection;
  
    /** search direction: backward */
    protected static final int SELECTION_BACKWARD = 0;
    /** search direction: forward */
    protected static final int SELECTION_FORWARD = 1;
    /** search direction: bidirectional */
    protected static final int SELECTION_BIDIRECTIONAL = 2;
    /** search directions */
    public static final Tag[] TAGS_SELECTION = {
      new Tag(SELECTION_BACKWARD, "Backward"),
      new Tag(SELECTION_FORWARD, "Forward"),
      new Tag(SELECTION_BIDIRECTIONAL, "Bi-directional"), };
  
    /** holds an array of starting attributes */
    protected int[] m_starting;
  
    /** holds the start set for the search as a Range */
    protected Range m_startRange;
  
    /** does the data have a class */
    protected boolean m_hasClass;
  
    /** holds the class index */
    protected int m_classIndex;
  
    /** number of attributes in the data */
    protected int m_numAttribs;
  
    /** total number of subsets evaluated during a search */
    protected int m_totalEvals;
  
    /** for debugging */
    protected boolean m_debug;
  
    /** holds the merit of the best subset found */
    protected double m_bestMerit;
  
    /** holds the maximum size of the lookup cache for evaluated subsets */
    protected int m_cacheSize;
  
    /**
     * Returns a string describing this search method
     * 
     * @return a description of the search method suitable for displaying in the
     *         explorer/experimenter gui
     */
    public String globalInfo() {
      return "BestFirst:\n\n"
        + "Searches the space of attribute subsets by greedy hillclimbing "
        + "augmented with a backtracking facility. Setting the number of "
        + "consecutive non-improving nodes allowed controls the level of "
        + "backtracking done. Best first may start with the empty set of "
        + "attributes and search forward, or start with the full set of "
        + "attributes and search backward, or start at any point and search "
        + "in both directions (by considering all possible single attribute "
        + "additions and deletions at a given point).\n";
    }
  
    /**
     * Constructor
     */
    public BestFirst() {
      resetOptions();
    }
  
    /**
     * Returns an enumeration describing the available options.
     * 
     * @return an enumeration of all the available options.
     * 
     **/
    @Override
    public Enumeration<Option> listOptions() {
  