edgelist.java

经典的货郎担问题解决办法

/*
** This code was written by Kent Paul Dolan.  See accompanying file
** TravellerDoc.html for status for your use.
*/

package com.well.www.user.xanthian.java.structures;

import com.coyotegulch.tools.*;
import com.coyotegulch.genetic.*;

import com.well.www.user.xanthian.java.genetic.*;
import com.well.www.user.xanthian.java.tools.*;
import com.well.www.user.xanthian.java.ui.*;

public class EdgeList extends Object
{
  private Edge[]  m_edgeList      = null;
  private boolean m_alreadySorted = false;

  public EdgeList( TravellerChromosome chromosome )
  {

      if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
      {
        System.out.println
        (
          "Entered EdgeList Constructor via chromosome"
        );
      }

    int genomeLength =  ValuatorControls.getNumberOfCities();

    m_edgeList = new Edge[genomeLength];

    for (int i = 0 ; i < genomeLength ; i++ )
    {
      m_edgeList[i]
        = new
          Edge
          (
            new Codon
            (
              chromosome.getCity
              (
                ( i - 1 + genomeLength ) % genomeLength
              )
            ),
            new Codon( chromosome.getCity(i) )
          );
    }

    m_alreadySorted = false;
  }

  public EdgeList( EdgeList that )
  {

      if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
      {
        System.out.println
        (
          "Entered EdgeList Constructor via anotherEdgeList"
        );
      }

    m_edgeList = new Edge[that.length()];
    for (int i = 0 ; i < that.length() ; i++ )
    {
      m_edgeList[i] = new Edge( that.getEdge(i) );
    }
    this.m_alreadySorted = that.isSorted();
  }

  public String toString()
  {
    StringBuffer b = new StringBuffer("");
    b.append("[");
    for ( int i = 0; i < this.length(); i++ )
    {
      if ( this.m_edgeList[i] != null )
      {
        b.append( ( ( i == 0 ) ? "" : "," ) + this.m_edgeList[i].toString() );
      }
    }
    b.append("]");
    return b.toString();
  }

  public Edge getEdge( int index )
  {

    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
    {
      System.out.println
      (
        "Entered EdgeList.getEdge(int index)"
        + index
      );
    }

    return this.m_edgeList[ index ];
  }

  public void setEdge( int index, Edge e )
  {
    m_edgeList[index] = new Edge( e );
  }

  public int length()
  {

    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
    {
      System.out.println
      (
        "Entered EdgeList.length()"
      );
    }

    return m_edgeList.length;
  }

  public boolean isSorted()
  {

    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
    {
      System.out.println
      (
        "Entered EdgeList.isSorted()"
      );
    }

    return this.m_alreadySorted;

  }

  public void sort()
  {

    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
    {
      System.out.println
      (
        "Entered EdgeList.sort()"
      );
    }

    if (! this.m_alreadySorted)
    {
      QuickSortAlgorithm.sort( this.m_edgeList );
      this.m_alreadySorted = true;
    }

  }

  public int findEdge( Edge e )
  {
    if ( this.m_alreadySorted )
    {

/*
** Use faster binary search.
*/

      // System.out.println( "findEdge finding edge by binary search" );
      int lo = 0;
      int hi = m_edgeList.length - 1;
      while ( lo != hi )
      {
        int mid = ( hi + lo ) / 2;
        int threeWay = e.compareTo( m_edgeList[mid] );
        if ( threeWay == Sortable.THIS_EQUAL_TO ) { return mid; }
        if ( threeWay == Sortable.THIS_LESS_THAN )
        {
          hi = mid;
        }
        else  // == Sortable.THIS_GREATER_THAN, the remaining case
        {
          lo = mid;
        }
      }

/*
** It is perfectly possible that we are being asked to find an edge we
** do not have.  If we drop through, return minus one as a "not found"
** marker response.
*/

      return -1;
    }
    else
    {

/*
** Use slower linear search.
*/

      // System.out.println( "findEdge finding edge by linear search" );

      for ( int i = 0; i < m_edgeList.length; i++ )
      {
        if ( Sortable.THIS_EQUAL_TO == e.compareTo( m_edgeList[i] ) )
        {
          return i;
        }
      }

/*
** It is perfectly possible that we are being asked to find an edge we
** do not have.  If we drop through, return minus one as a "not found"
** marker response.
*/

      return -1;

    }
  }

}