/*
   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 java.util.Arrays;
   import java.util.Vector;

/**
   <P>A VectorWrapper for chars.</P>

   <P><CODE><I><B>Source code:</B> &nbsp;<A HREF="../../../CODE/xbn/array/VWChar.java">VWChar.java</A>. &nbsp;<B>Example code</B> &nbsp;See the similar example code for <A HREF="~JD~vwi~EJD~">VWInt</A>.</I></CODE></P>

   @version  0.9b
   @author  Jeff Epstein, <A HREF="http://sourceforge.net/projects/xbnjava">http://sourceforge.net/projects/xbnjava</A>.
 **/
public class VWChar extends VectorWrapper implements Cloneable  {
   private BinarySearchData bsd = null;
   /**
      <P>Create a VWChar with default settings.</P>

      <P>Equal to <CODE><A HREF="~JD~vw#vw()~EJD~">VectorWrapper</A>()</CODE></P>
    **/
   public VWChar()  {
      super();
   }

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

      <P>Equal to <CODE><A HREF="~JD~vw#vw(vctr)~EJD~">VectorWrapper</A>(v_ector)</CODE></P>

      <P>Note:  It is expected that this Vector contain only chars (contained in <A HREF="~JD~C~EJD~">Character</A> objects).</P>
    **/
   public VWChar(Vector v_ector)  {
      super(v_ector);
   }

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

      <P>Equal to <CODE><A HREF="~JD~vw#vw(b)~EJD~">VectorWrapper</A>(b_orderDirAscDesc)</CODE></P>
    **/
   public VWChar(boolean b_orderDirAscDesc)  {
      super(b_orderDirAscDesc);
   }

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

      <P>Equal to <CODE><A HREF="~JD~vw#vw(vctr,b)~EJD~">VectorWrapper</A>(v_ector, b_orderDirAscDesc)</CODE></P>

      <P>Note:  It is expected that this Vector contain only chars (contained in <A HREF="~JD~C~EJD~">Character</A> objects).</P>
    **/
   public VWChar(Vector v_ector, boolean b_orderDirAscDesc)  {
      super(v_ector, b_orderDirAscDesc);
   }


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

      <P>Equal to <CODE><A HREF="~JD~vw#vw(b,b)~EJD~">VectorWrapper</A>(b_addInOrder, b_orderDirAscDesc)</CODE></P>
    **/
   public VWChar(boolean b_addInOrder, boolean b_orderDirAscDesc)  {
      super(b_addInOrder, b_orderDirAscDesc);
   }


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

      <P>Equal to <CODE><A HREF="~JD~vw#vw(vctr,b,b)~EJD~">VectorWrapper</A>(v_ector, b_addInOrder, b_orderDisAscDesc)</CODE></P>

      <P>Note:  It is expected that this Vector contain only chars (contained in <A HREF="~JD~C~EJD~">Character</A> objects).</P>
    **/
   public VWChar(Vector v_ector, boolean b_addInOrder, boolean b_orderDirAscDesc)  {
      super(v_ector, b_addInOrder, b_orderDirAscDesc);
   }

   /**
      <P>Add a char.</P>

      @param  c_har  The char to add.
    **/
   public final void add(char c_har)  {
      if(!doAddInOrder())  {
         getVector().addElement(new Character(c_har));
         return;
      }
      //DO add in order.


      getVector().insertElementAt((new Character(c_har)), getInsertAddIdx(c_har));

      //We've just changed the size of the "array", so the bsd
      //is no longer valid.  This will be recreated in
      //getArrIdx().
      bsd = null;
   }

   /**
      <P>Get the index at which to insert the provided char.  This function is only meaningful when adding is ordered.  See <a href="~JD~vw~EJD~#doAddInOrder()">doAddInOrder</a>.</P>

      @param  c_har  The char you're about to insert.  May not be null.
      @return  If...<UL>
         <LI>...<a href="~JD~vw~EJD~#doAddInOrder()">adding is done in order</a>:  The array index at which c_har should be added to preserve the requested ordering.  Note that when there are one or more chars equaling c_har have already been added, then you'll get the array index of (randomly) one of those existing elements.</LI>
         <LI>...<a href="~JD~vw~EJD~#size()">size</a> equals zero:  <B>0</B></LI>
         <LI>...adding is not done in order:  <B>0</B></LI>
      </UL>
    **/
   public final int getInsertAddIdx(char c_har)  {
      return getArrIdx(c_har, false);
   }

   /**
      <P>Get the index at which the char actually exists.</P>

      @param  c_har  The char that may already exist in this VWInt.  May not be null.
      @return  <B>The array index</B> at which c_har exists.  Note that in the case of multiple instances of c_har, the first (when not adding in order) or random (when adding in order) one is returned.
      <BR><B>-1</B>  If no other char equalling c_har have yet been added.
    **/
   public final int getFoundIdx(char c_har)  {
      return getArrIdx(c_har, true);
   }

   /**
      <P>Was an char already added?</P>

      @param  c_har  The char who's existence you want to test.  May not be null.
      @return  <B>-1</B>  If no char equalling c_har exists.
      <BR><B>The array index</B> at which the char is found.
    **/
   public final boolean doesExist(char c_har)  {
      return (getFoundIdx(c_har) != -1);
   }

   /**
      <P>Add an array of chars.</P>

      @param  a_char  The char array to add.  May not be null.
    **/
   public final void addArray(char[] a_char)  {
      try  {
         for(int i = 0; i < a_char.length; i++)  {
            add(a_char[i]);
         }
      }  catch(NullPointerException npx)  {
         throwAX("addArray:  a_char is null.");
      }
   }

   /**
      <P>Add an array of chars, as protected by the provided APChar.</P>

      @param  ap_char  The APChar, whose protected array should be add, via <a href="~JD~addArray(c[])~EJD~">addArray</a>.  May not be null.
    **/
   public final void addAPChar(APChar ap_char)  {
      try  {
         addArray(ap_char.getAOChar());
      }  catch(NullPointerException npx)  {
         throwAX("addAPChar:  ap_char is null.");
      }
   }

   /**
      <P>Get a char from the vector, at the required array index.</P>

      @param  i_dx  The array index.  Must range 0..<CODE>[<A HREF="~JD~vw~EJD~#size()">size</A>() - 1]</CODE>, inclusive.
    **/
   public final char getChar(int i_dx)  {
      try  {
         return ((Character)getVector().elementAt(i_dx)).charValue();
      }  catch(ClassCastException ccx)  {
         throwAX("getChar:  Element i_dx (" + i_dx + ") is not a Character, which it must be.  It is actually a " + getVector().elementAt(i_dx).getClass().getName() + ".  It seems you provided an inaccurate Vector to the constructor.");
      }  catch(ArrayIndexOutOfBoundsException aioobx)  {
         throwAX("getChar:  i_dx (" + i_dx + ") is invalid.  size()=" + size() + ".");
      }

      //Never reached.  Required for compile.
      return ' ';
   }

   public final String getString(int i_dx)  {
      return (new Character(getChar(i_dx))).toString();
   }
   public final boolean isNull(int i_dx)  {
      return false;
   }

   public final char[] getAOChar()  {
      return getAOChar(false);
   }

   /**
      <P>Get the array of chars.  This array is composed of all those chars <A HREF="#add(char)">add</A>ed since this object was created, or since the last time this function was called.</P>

      @param  b_sort  If true, then sort the array <I>ascending</I> before returning it (this is redundant when both <a href="~JD~vw~EJD~#doAddInOrder()">doAddInOrder</a> and <a href="~JD~vw~EJD~#getOrderDirAscDesc()">getOrderDirAscDesc</a> equal true).  If false, then return the array as it currently exists.
      @return  An array of chars, as added to this VWChar.
    **/
   public final char[] getAOChar(boolean b_sort)  {
      char ac[] = new char[getVector().size()];

      if(ac.length == 0)  {
         return ac;
      }

      //The array is at least one element in length.

      for(int i = 0; i < getVector().size(); i++)  {
         try  {
            ac[i] = ((Character)(getVector().elementAt(i))).charValue();
         }  catch(ClassCastException ccx)  {
            throwAX("getAOChar:  Element " + i + " is not a Character, which it must be.  It is actually a " + getVector().elementAt(i).getClass().getName() + ".  It seems you provided an inaccurate Vector to the constructor.");
         }
      }

      if(b_sort)  {
         Arrays.sort(ac);
      }

      return ac;
   }


   //Cloning...START
      /**
         <P>Get a full (deep) copy of this VWChar.</P>

         @return  <CODE>(VWChar)<A HREF="#clone()">clone</A>()</CODE>
       **/
      public final VWChar getVWCClone()  {
         try  {
            return (VWChar)clone();
         }  catch(CloneNotSupportedException cnsx)  {
            throwAX("getVWCClone [SHOULD NEVER HAPPEN!]:  " + cnsx.toString());
         }

         //Never reached.  Required for compile.
         return null;
      }

      /**
         <P>Get a full (deep) copy of this VWChar as an Object.</P>
       **/
      protected final Object clone() throws CloneNotSupportedException  {
         VWChar accClone = new VWChar();
         for(int i = 0; i < size(); i++)  {
            accClone.add(getChar(i));
         }

         return accClone;
      }
   //Cloning...END

   /**
      b_onlyIfFound:  If true, then when c_har does not exist in the array, then return -1.  Otherwise, return the index at which to insert c_har.
    **/
   private final int getArrIdx(char c_har, boolean b_onlyIfFound)  {
      if(size() == 0)  {
         //There are no elements yet

         return b_onlyIfFound  ?
            -1  :
            0;
      }

      //There is at least one element.


      if(!doAddInOrder())  {
         //Adding is not done in order.  Binary searching is
         //pointless.

         if(b_onlyIfFound)  {
            //We only want to know the index at which c_har is
            //found.

            for(int i = 0; i < size(); i++)  {
               if(c_har == getChar(i))  {
                  return i;
               }
            }


         }  //ELSE:  We only want the array index at which to
            //       *insert*.  Since it's not ordered, just
            //       return zero.

         return b_onlyIfFound  ?
            -1  :
            0;
      }

      //Adding IS done in order.  Binary searching is
      //useful.

      if(bsd == null)  {
         //This is either (1) the first time using this
         //function, or this is (2) the first time using
         //this function since adding something.
         bsd = new BinarySearchData(size(), getOrderDirAscDesc());
      }

      bsd.reset();

      int iPrevMidIdx = -1;

      while(bsd.getIdxMiddle() != -1)  {
         int iMiddleIdx = bsd.getIdxMiddle();
         char cAtMiddle = getChar(bsd.getIdxMiddle());

         //Used only after the end of this while block.
         iPrevMidIdx = iMiddleIdx;


         if(c_har == cAtMiddle)  {
            //Found.  Duplicates (which are okay) are added at
            //the same point, pushing the duplicate to the right.
            return iMiddleIdx;
         }

         bsd.prepareForNextSearch(c_har < cAtMiddle);
      }
      //The char to be inserted does not currently exist in the
      //array.

      if(c_har < getChar(iPrevMidIdx))  {
         if(!getOrderDirAscDesc())  {
            //Insert c_har at the index right *after* the
            //element it is just-less than.
            iPrevMidIdx++;

         }  //ELSE:  The order is ascending, so insert it *at*
            //       the element c_har is just-less than.  This
            //       pushes the existing element one to the
            //       right.

      }  else  {
         //c_har is greater than the existing "middle" element.

         if(getOrderDirAscDesc())  {
            //Insert c_har at the index right *after* the
            //element it is just-greater than.
            iPrevMidIdx++;

         }  //ELSE:  The order is descending, so insert it *at*
            //       the element c_har is just-less than.  This
            //       pushes the existing element one to the
            //       right.
      }


      return  b_onlyIfFound  ?
         -1  :
         iPrevMidIdx;
   }
}