/*
   XBN Java:  Generically useful, non-GUI Java code.
   http://sourceforge.net/projects/xbnjava

   Copyright (C) 1997-2003, Jeff Epstein
   All rights reserved.

   Modifications: No

   Redistribution in binary form, with or without modifications, are permitted provided that the following conditions are met:

      * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
      * If modifications are made to source code then this license should indicate that fact in the "Modifications" section above.
      * Neither the author, nor the contributors may be used to endorse or promote products derived from this software without specific prior written permission.

   THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

   [NOTE:  This license contains NO advertising clause.]
 */
package xbn.array;
   import xbn.XBNObject;

/**
   <P>Data necessary to do a binary search with.</P>

   <P><CODE><I><B>Source code:</B> &nbsp;<A HREF="../../../CODE/xbn/array/BinarySearchData.java">BinarySearchData.java</A>. &nbsp;<B>Example code:</B> &nbsp;<A HREF="../../xbn_examples/array/XmplBinarySearchData_asc.html">XmplBinarySearchData_asc.java</A>, <A HREF="../../xbn_examples/array/XmplBinarySearchData_desc.html">XmplBinarySearchData_desc.java</A>. &nbsp;<B>Unit tests:</B> &nbsp;xbn_junit.array.<A HREF="../../../CODE/xbn_junit/array/JUTUtilArray.java">JUTUtilArray.java</A>.</I></CODE></P>

   <P>Specifically, referring to the array-being-searched:  The minimum, middle and maximum bounds, and sort-order direction.  See <A HREF="~JD~utila~EJD~">UtilArray</A>.<A HREF="~JD~utila#getMiddleIdx(i,i,b)~EJD~">getMiddleIdx</A>.</P>

   <P>This object only works when you are searching an array that is ordered.  Unique-ness is not required, but is more efficient.</P>

   @version  0.9b
   @author  Jeff Epstein, <A HREF="http://sourceforge.net/projects/xbnjava">http://sourceforge.net/projects/xbnjava</A>.
 **/
public class BinarySearchData extends XBNObject  {
   private UtilArray uArray = new UtilArray();

   private int iLength = -1;
   private int iLeft = -1;
   private int iRight = -1;
   private int iMiddle = -1;
   private boolean bOrderDirAscDesc = false;

   /**
      <P>Create a BinarySearchData.</P>

      @param i_arrayLength  The length of the array to be searched.  May not be less than one.
      @param  b_arrayOrderDirAscDesc  What direction is the array-to-be-searched ordered?  If true, then ascending.  If false, descending.
    **/
   public BinarySearchData(int i_arrayLength, boolean b_arrayOrderDirAscDesc)  {
      if(i_arrayLength < 1)  {
         throwAX("constructor:  i_arrayLength (" + i_arrayLength + ") is less than one.");
      }
      iLength = i_arrayLength;
      bOrderDirAscDesc = b_arrayOrderDirAscDesc;
      reset();
   }

   /**
      <P>Get the left-most index that has not yet been searched.</P>

      <P>When this object is originally created, or <A HREF="#reset()">reset</A>, this is set to 0.</P>
    **/
   public final int getIdxLeft()  {
      return iLeft;
   }

   /**
      <P>Get the next array index to analyze.</P>

      <P>When this object is originally created, or <A HREF="#reset()">reset</A>, this is set to <CODE>[<A HREF="~JD~utila~EJD~">UtilArray</A>].<A HREF="~JD~utila#getMiddleIdx(i,i)~EJD~">getMiddleIdx</A>(getMiddleIdx(<A HREF="#getIdxLeft()">getIdxLeft</A>(), <A HREF="#getIdxRight()">getIdxRight</A>()))</CODE>.</P>
    **/
   public final int getIdxMiddle()  {
      return iMiddle;
   }

   /**
      <P>Get the right-most index that has not yet been searched.</P>

      <P>When this object is originally created, or <A HREF="#reset()">reset</A>, this is set to <CODE>(<A HREF="#getLength()">getLength</A>() - 1)</CODE>.</P>
    **/
   public final int getIdxRight()  {
      return iRight;
   }

   /**
      <P>How long is the array that is being searched?</P>

      @return  <B>i_arrayLength</B>  Exactly as provided to the <A HREF="~JD~bsd(i,b)~EJD~">constructor</A>.
    **/
   public final int getLength()  {
      return iLength;
   }

   /**
      <P>Reset the internally-held data, to search the array again.  This initializes this object to a state equal to that when it was originally created.</P>

      <P>The <A HREF="#getIdxLeft()">left index</A> is set to 0.
      <BR>The <A HREF="#getIdxMiddle()">middle index</A> is set to <CODE>[<A HREF="~JD~utila~EJD~">UtilArray</A>].<A HREF="~JD~utila#getMiddleIdx(i,i)~EJD~">getMiddleIdx</A>(getMiddleIdx(<A HREF="#getIdxLeft()">getIdxLeft</A>(), <A HREF="#getIdxRight()">getIdxRight</A>()))</CODE>.
      <BR>The <A HREF="#getIdxRight()">right index</A> is set to <CODE>(getLength() - 1)</CODE>.  </P>
    **/
   public final void reset()  {
      iLeft = 0;
      iRight = (getLength() - 1);
      iMiddle = uArray.getMiddleIdx(getIdxLeft(), getIdxRight());
   }

   /**
      <P>Is the array-being-searched ordered ascending or descending?</P>

      @return  <B>b_arrayOrderDirAscDesc</B>  Exactly as provided to the <A HREF="~JD~bsd(i,b)~EJD~">constructor</A>.
    **/
   public final boolean getOrderDirAscDesc()  {
      return bOrderDirAscDesc;
   }

   /**
      <P>Set the indexes for the next search.  Do not call this function when the search item was found to be <I>equal</I> to an element of the array (there's no need for a "next search"!).</P>

      @param  b_siLessOrGreaterThanAE  Was the search item less or greater than the array element just compared against?  If true, the search item was found to be less than the array element.  If false, the search item was found to be greater than the array element.
    **/
   public final void prepareForNextSearch(boolean b_siLessOrGreaterThanAE)  {
      int iMiddlePrev = getIdxMiddle();

      //In all the following comments, when it says "if rounded
      //down...".  This class *always* rounds down, it's just
      //hypothetical information.

      if(b_siLessOrGreaterThanAE)  {
         if(getOrderDirAscDesc())  {
            //The search item is less than a[getIndexMiddle()],
            //and the array is ordered ascending.
            //
            //For example:
            //		Array:              [5, 10, 15, 20]
            //		Search item:        9
            //    left/middle/right:  0/1/3
            //
            //The search item (9) is less than element 1 (10).
            //Therefore, we know that elements 1, 2 and 3 cannot
            //contain the item (because order is ascending),
            //so make the right bound equal to the array index
            //*before* the one just searched:  Element 0.
            iRight = iMiddle - 1;
            //Now, left/middle/right equals 0/1/0.  After
            //calling getMiddleIdx(), below, the middle will
            //be set to 0.

         }  else  {
            //The search item is less than a[getIndexMiddle()],
            //and the array is ordered descending.
            //
            //For example:
            //		Array:              [20, 15, 10, 5]
            //		Search item:        9
            //    left/middle/right:  0/1/3
            //
            //The search item (9) is less than element 1 (15).
            //Therefore, we know that elements 0 and 1 cannot
            //contain the item (because order is descending),
            //so make the left bound equal to the array index
            //*after* the one just searched:  Element 2.
            iLeft = iMiddle + 1;
            //Now, left/middle/right equals 2/1/3.  After
            //calling getMiddleIdx(), below, the middle will
            //be set to 2 (if round down.  3 if up).
         }

      }  else  {
         if(getOrderDirAscDesc())  {
            //The search item is greater than a[getIndexMiddle()],
            //and the array is ordered ascending.
            //
            //For example:
            //		Array:              [5, 10, 15, 20]
            //		Search item:        16
            //    left/middle/right:  0/1/3
            //
            //The search item (16) is greater than element 1 (10).
            //Therefore, we know that elements 0 and 1 cannot
            //contain the item (because order is ascending),
            //so make the left bound equal to the array index
            //*after* the one just searched:  Element 2.
            iLeft = iMiddle + 1;
            //Now, left/middle/right equals 2/1/3.  After
            //calling getMiddleIdx(), below, the middle will
            //be set to 2 (if round down.  3 if up).

         }  else  {
            //The search item is greater than a[getIndexMiddle()],
            //and the array is ordered descending.
            //
            //For example:
            //		Array:              [20, 15, 10, 5]
            //		Search item:        16
            //    left/middle/right:  0/1/3
            //
            //The search item (16) is greater than element 1 (15).
            //Therefore, we know that elements 1, 2 and 3 cannot
            //contain the item (because order is descending),
            //so make the right bound equal to the array index
            //*before* the one just searched:  Element 0.
            iRight = iMiddle - 1;
            //Now, left/middle/right equals 0/1/0.  After
            //calling getMiddleIdx(), below, the middle will
            //be set to 0.
         }
      }

      iMiddle = uArray.getMiddleIdx(iLeft, iRight);

      if(iMiddle == iMiddlePrev)  {
         //This middle index was already searched.  Once (and
         //if) the left and right are set to be only one apart,
         //getMiddleIdx() cannot squeeze it further (so left
         //and right are the same).
         //
         //(...as I read this comment a year later:  Huh?!)

         if(iLeft != iRight)  {
            if(iMiddle == iRight)  {
               iMiddle = iLeft;
               iRight = iLeft;
            }  else  {
               iMiddle = iRight;
               iLeft = iRight;
            }
         }  else  {
            //It is as squeezed as possible (left equals right).
            //The search is over ("...you were with me all the
            //while...").
            iMiddle = -1;
         }
      }
   }

   /**
      <P>Get some information about this BinarySearchData.</P>
    **/
   public final String toString()  {
      return this.getClass().getName() + ":  getIdxLeft()=" + getIdxLeft() + ", getIdxLeft()=" + getIdxLeft() + ", getIdxLeft()=" + getIdxLeft() + ", getLength()=" + getLength() + ", getOrderDirAscDesc()=" + getOrderDirAscDesc();
   }
}