/* 
 * Sor.java
 * Object-ekből álló, tetszőleges hosszúra növő FIFO megvalósítás
 * by pts@fazekas.hu at Sat Apr  7 12:10:32 CEST 2001
 * további doksi: a README-ben és e file legkülső class-ának fejkommentjében
 *
 * Kincskereső Kisgömböc (C) Early May 2001 by eNTitánok (Rév Szilvia,
 * Szabó Péter <pts@inf.bme.hu>, Szurdi Miklós, Weizengruber Attila).
 *
 * 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 2 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, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

package eNTitanok.util;

/**
 * Egy generikus (Object-ekből álló), tetszőleges hosszúra növő sor (queue,
 * FIFO) megvalósítás. A sor elejéről lehet olvasni és a végéhez lehet
 * hozzáfűzni. Thread safe (nem teszteltük).
 */
public class Sor {
  /**
   * A minimális kapacitás.
   */
  public static final int MIN_HOSSZ=16;
  protected Object t[];
  /**
   * Az elsőként belerakott, kiolvasásra váró elem indexe.
   */
  protected int elso;
  /**
   * Az index, ahová a következő beszúrás történhet.
   */
  protected int uj;
  /**
   * Egy üres sort hoz létre, 16 kezdőkapacitással.
   */
  public Sor() { this(16); }
  /**
   * Egy adott kezdőkapacitású, üres sort hoz létre.
   */
  public Sor(int kezdomeret) {
    t=new Object[Math.min(kezdomeret,MIN_HOSSZ)];
    elso=uj=0;
  }

  public Sor klonoz() {
    Sor masik=new Sor();
    for (int i=elso;i<uj;i++) masik.vegehezFuz(t[i]);
    return masik;
  }
  
  /**
   * @return Pontosan akkor <code>true</code>, ha a sor üres, azaz nincs benne
   * senki.
   */
  public synchronized boolean isUres() { return elso==uj; }
  /**
   * @return a sorbanálló elemek száma.
   */
  public synchronized int length() { return uj-elso; }
  /**
   * Ha a sor legfeljebb a kapacitás negyedét tölti ki, összenyomja a felére.
   */
  protected synchronized void osszenyom() {
    if ((uj-elso)<=t.length/4 && t.length>=MIN_HOSSZ*2) {
      Object ujt[]=new Object[t.length/2];
      System.arraycopy(t, elso, ujt, 0, uj-elso);
      t=ujt; uj-=elso; elso=0;
    }
  }
  /**
   * Helyet csinál még <code>mennyinek</code> új elemnek.
   */
  protected synchronized void helyetCsinal(int mennyinek) {
    if (t.length-uj<mennyinek) {
      int ujhossz=t.length;
      while (ujhossz-(uj-elso)<mennyinek) ujhossz*=2;
      Object ujt[]=ujhossz==t.length?t:new Object[ujhossz];
      System.arraycopy(t, elso, ujt, 0, uj-elso);
      t=ujt; uj-=elso; elso=0;
    }
  } /// helyetCsinal()
  /**
   * @return a sor elején álló elem
   */
  public synchronized Object elso() { return uj==elso?null:t[elso]; }
  /**
   * Törli a sor elején álló elemet.
   * @return az épp törölt elem
   */
  public synchronized Object elsoTorol() {
    if (uj==elso) return null;
    Object o=t[elso++];
    osszenyom();
    return o;
  }
  /**
   * @return a sor végén álló elem
   */
  public synchronized Object utolso() { return uj==elso?null:t[uj-1]; }
  /**
   * Törli a sor végén álló elemet. Bár ezt a klasszikus <I>sor</I>
   * adatszerkezettől nem követeljük meg, itt megvalósítottuk.
   * @return az épp törölt elem
   */
  public synchronized Object utolsoTorol() {
    if (uj==elso) return null;
    Object o=t[--uj];
    osszenyom();
    return o;
  }
  /**
   * Paraméteret a sor végéhez fűzi új elemként.
   */
  public synchronized void vegehezFuz(Object ujelem) {
    helyetCsinal(1);
    t[uj++]=ujelem;
  }
  /**
   * Paraméteret a sor végéhez fűzi új elemként. Hibát okoz, ha `ujelem==null'.
   */
  public synchronized void vegehezFuzNemNull(Object ujelem) {
    if (ujelem==null) throw new NullPointerException();
    helyetCsinal(1);
    t[uj++]=ujelem;
  }
} /// class Sor