SortertAnsattSamling.java [Last ned]

import static java.lang.System.*;
 
 
/*
 *  Klasse for representasjon av en sortert samling
 *  av Ansatt-objekt. Klassen har metoder for
 *  søk, innsetting og sletting.
 *
 */
public class SortertAnsattSamling {
 
  private Ansatt[] tabell;
  private int      nesteLedige;
 
 
  public SortertAnsattSamling(int antall) {
    tabell = new Ansatt[antall];
    nesteLedige = 0;
  }
 
 
  // Finner ansatt, gitt ansattnummer.
  // Returnerer null hvis objektet ikke finnes.
  public Ansatt finn(int ansNr) {
    int pos = finnPos(ansNr);
    if (pos >= 0) // funnet!
      return tabell[pos];
    else
      return null;
  }
 
 
 
  // Setter inn en ansatt sortert. Returnerer false
  // hvis en ansatt med samme ansattnummer finnes,
  // eller det ikke er ledig plass, og true ellers.
  public boolean settInn(Ansatt a) {
    int pos = finnPos(a.getAnsNr());
 
    boolean ny = false;
    if (pos<0)
      ny = true;
    else if (pos == 0 && nesteLedige > 0)
      ny = (a.getAnsNr() != tabell[0].getAnsNr());
 
    if ( ny && nesteLedige < tabell.length ) {
      pos = (-pos)-1;
      for (int i=nesteLedige; i>pos; i--)
        tabell[i] = tabell[i-1];
      tabell[pos] = a;
      nesteLedige++;
      return true;
    }
    else
      return false;
  }
 
 
  // Sletter en ansatt, gitt ansattnummer. Returnerer
  // false hvis objektet ikke finnes, true ellers.
  // Sørger for å beholde ansattsamlingen sortert.
  public boolean slett(int ansNr) {
    int pos = finnPos(ansNr);
 
    boolean finnes = true;
    if (pos<0)
      finnes = false;
    else if (pos == 0 && nesteLedige > 0)
      finnes = (ansNr == tabell[0].getAnsNr());
 
    if (finnes) {
      for (int i=pos; i<nesteLedige-1; i++)
        tabell[i] = tabell[i+1];      
      nesteLedige--;
      return true;
    }
    else
      return false;
  }
 
 
  public String toString() {
    String svar = "";
    for (int i=0; i<nesteLedige; i++)
      svar += tabell[i].toString() + "\n";
 
    return svar;
  }
 
 
  // Finner posisjonen til et Ansatt-objekt, gitt et
  // ansattnr. Hvis objektet ikke finnes, returnerer
  // metoden en negativ verdi pos, som er slik at et
  // evt. nytt objekt med dette ansattnummeret skal
  // inn på posisjon -pos-1.
  //
  // Antar at tabellen er sortert mhp ansattnummer,
  // og kan dermed bruke binærsøk.
  private int finnPos(int ansNr) {
 
    boolean funnet = false;
    int nedre = 0;
    int øvre = nesteLedige-1;
    int pos = 0;
 
    while (!funnet && nedre<=øvre) {
      pos = (nedre+øvre) / 2;
 
      if ( tabell[pos].getAnsNr() == ansNr )
        funnet = true;
      else if (tabell[pos].getAnsNr() < ansNr)
        nedre = pos+1;
      else
        øvre = pos-1;
    }
 
    if ( funnet )
      return pos;
    else {
      if (nesteLedige == 0) // tom tabell
        return -1;
      else {
        if (tabell[pos].getAnsNr() < ansNr)
          pos++;
        // Nytt objekt skal inn i posisjon pos.
        // Dette blir kodet som posisjon -(pos+1).
        return -(pos+1);
      }
    }
  }
 
}
Kildekode blir vist ved hjelp av GeSHi.