Bag

Torba (razred Bag) je poljubna zbirka objektov, ki lahko vsebuje duplikate.

bag = “torba” = multiset = množica z duplikati

Prikaz razširitve razreda AbstractCollection

Postopen prikaz vsebine razreda Bag

Za predstavitev objektov bomo uporabili tabelo:

import java.util.*;
public class Bag extends AbstractCollection
{
  private Object[] objects;
  private int size = 0;
  private static final int CAPACITY = 16;

Metode

• private void resize()

skrita metoda

uporablja se znotraj razreda, ko je treba tabelo povečati

• public Bag()

konstruktor

naredi prazno torbo

• public Bag(int)

konstruktor

naredi torbo z določeno kapaciteto

• public Bag(Object[])

naredi torbo iz tabele objektov

• public Bag(Collection)

naredi torbo iz zbirke

• public boolean add(Object)

dodajanje objektov

• public boolean addAll(Collection)

dodajanje zbirke

• public void clear()

praznenje

• public boolean contains(Object)

če vsebuje nek objekt vrne true

• public boolean containsAll(Collection)

če vsebuje vse objekte vrne true

• private static int frequency(Collection, Object)

prešteje koliko pojavitev nekega objekta se pojavi v tej torbi

Implementacija:

private static int frequency(Collection c, Object o) {
  int st=0;
  for( Iterator it = c.iterator(); it.hasNext(); )  //dokler imamo objekte
    if o.equals(it.next()) //ce je objekt enak naslednjemu
      ++st;                //povecamo stevec
  return st;
}

• public boolean equals(Object)

preveri če sta objekta enaka

Implementacija:

public boolean equals(Object o)
{
  if (this == o)
    return true;   //dva ista objekta sta vedno tudi enaka
 
  if (this.getClass() != o.getClass())
    return false;  //enaka objekta imata isti razred
 
  if (this.hashCode() != o.hashCode())
    return false;  //enaka objekta imata isti hash
 
  Collection c = (Collection) o;
  if (this.size() != c.size())
    return false;  //enaka objekta imata enake velikosti
 
  if (!this.containsAll(c))
    return false;  //enaka objekta vsebujeta vse elemente drug drugega
 
  if (!c.containsAll(this))
    return false;  //enaka objekta vsebujeta vse elemente drug drugega
 
  for(int i = 0; i < size; i++) {
    Object x = objects[i];
    if (frequency(c,x)!= frequency(this,x))
      return false;
  }
 
  return true;
 
}

• public int hashCode()

določi celo število, ki predstavlja objekt

Implementacija:

public int hashCode() {
  int code=0;
  for(int i=0; i < size; i++)
    code+= objects[i].hashCode();  //sestejemo hashcode vseh objektov
  return code;
}

• public boolean isEmpty()

• public boolean remove(Object)

• public boolean removeAll(Object)

• public boolean removeAll(Collection)

• public boolean retainAll(Collection)

• public int size()

• public Object[] toArray()

• public Object[] toArray(Object[])

• public String toString()

Implementacija nekaterih metod

import java.util.*;
 
public class Bag extends AbstractCollection 
{
  private Object[] objects;
  private int size = 0; 
  private static final int CAPACITY = 16;
 
  private void resize() 
  {
    Object[] temp=objects;
    objects = new Object[temp.length+CAPACITY];
    for(int i=0; i<size; i++)
      objects[i]=temp[i];
  }
 
  public Bag() 
  {
    objects = new Object[CAPACITY];
  }
 
  public Bag(Object[] objects) 
  {
    this.objects = new Object[objects.length+CAPACITY];
    for(int i=0; i<objects.length; i++)
      this.objects[size++] = objects[i];
  }
 
  public boolean add(Object object) 
  {
    if (size == objects.length)
      resize();
    objects[size++] = object;
    return true;
  }
 
  public boolean addAll(Collection collection) 
  {
    while (size + collection.size() > objects.length)
      resize();
    for (Iterator it=collection.iterator(); it.hasNext(); )
      objects[size++]=it.next();
    return true;
  }
 
  public void clear() 
  {
    for(int i=0; i<size; i++)
      objects[i] = null;
    size=0;
  }
 
  public boolean contains(Object object) 
  {
    for(int i=0; i<size; i++)
      if(object.equals(objects[i]))
        return true;
    return false;
  }
 
  public boolean containsAll (Collection collection) 
  {
    for (Iterator it=collection.iterator(); it.hasNext(); )
      if (!this.contains(it.next())) 
        return false;
    return true;    
  }
 
  public boolean isEmpty() 
  {
    return size==0;
  }
 
  private class BagIterator implements Iterator 
  {
    private int cursor=0;
 
    public boolean hasNext() 
    {
      return cursor<size;
    }
 
    public Object next() 
    {
      if (cursor >= size) 
        return null;
      return objects[cursor++];
    }
 
    public void remove() 
    {
      objects[--cursor] = objects[--size];
      objects[size]=null;
    }
  }
 
  public Iterator iterator() 
  {
    return new BagIterator();
  }
 
 
/*
  public Iterator iterator() 
  {
    return new Iterator() 
    {
      private int cursor=0;
      public boolean hasNext() 
      {
        return cursor<size;
      }
 
      public Object next() 
      {
        if (cursor >= size) 
          return null;
        return objects[cursor++];
      }
 
      public void remove() 
      {
        objects[--cursor] = objects[--size];
        objects[size]=null;
      }
    };
  }
 
*/
  public boolean remove(Object object) 
  {
    for(int i=0; i<size; i++)
      if (object.equals(objects[i])) 
      {
        objects[i] = objects[--size];
        objects[size]=null;
        return true;
      }
    return false;
  }
 
  public boolean removeAll(Object object) 
  {   boolean modified=false;
    for(int i=0; i<size; i++)
      if (object.equals(objects[i])) 
      {
        objects[i--] = objects[--size];
        objects[size]=null;
        modified=true;
      }
    return modified;
  }
 
  public boolean removeAll(Collection collection) 
  {
    boolean modified = false;
    for(Iterator it = collection.iterator(); it.hasNext();)
      if (this.removeAll(it.next())) // ali remove()
           modified=true;
    return modified;
  }
 
  public boolean retainAll(Collection collection) 
  {
    boolean modified = false;
    for (int i=0; i<size; i++)
      if (!collection.contains(objects[i])) 
      {
        remove(objects[i]);
        modified = true;
      }
    return modified;
  }
 
  public int size() 
  {
    return size;
  }
 
  public Object[] toArray() 
  {
    Object[] objects = new Object[size];
    for (int i=0; i<size; i++)
      objects[i] = this.objects[i];
    return objects;
  }
 
  public String toString() 
  {
    String s = "{ ";
    if (size>0)
      s+=this.objects[0];
    for (int i=1; i<size; i++)
      s+=", "+this.objects[i];
    return s+" }";
  }
}

Primer uporabe

import java.util.Iterator;
 
public class TestBag
{ 
  public static void main(String[] args)
    { 
      String[] hrana = { "sladoled", "mleko", "jogurt", "kruh",
                         "salama", "sok" , "cokolada", "slive",
                         "sok", "salama", "mleko", "vino",
                         "banane", "cebula", "mleko", "sok", "solata" };
 
      Bag torba = new Bag(hrana);
 
      System.out.println(torba.toString());
 
      izpisi(torba);
 
      torba.add("torta");
 
      izpisi(torba);
 
      if (torba.removeAll("salama")) 
        izpisi(torba);
      else 
        System.out.println("Objekta \"salama\" ni v moji torbi.");
 
      Iterator it = torba.iterator();
 
      while (it.hasNext())
      { 
        String s = (String)it.next();
          System.out.println("\ts = \""+s+"\"");
         if (s.charAt(0) == 's')
          { 
            it.remove();
            System.out.println("\tObjekt \""+s+"\" je odstranjen iz moje torbe.");
        }
       }
 
      izpisi(torba);
  }
 
  private static void izpisi(Bag b)
  { 
   System.out.println();
     System.out.println("Moja torba:");
   System.out.println("***********");
 
   System.out.println("Velikost = " + b.size());
 
    Object[] objects = b.toArray();
 
    for (int i=0; i<objects.length; i++)
        System.out.println("\tobjekt[" + i + "] = " + objects[i]);
 
    if (b.contains("sok"))
        System.out.println("\tMoja torba vsebuje objekt \"sok\"");
    else 
      System.out.println("\tMoja torba ne vsebuje objekta \"sok\"");
 
  String[] hrana = { "sladoled", "mleko", "jogurt", "kruh",
                     "salama", "sok" , "cokolada", "slive" };
 
    Bag ob = new Bag(hrana);
 
    if (ob.containsAll(b))
        System.out.println("\tOsnovna torba vsebuje mojo torbo");
    else 
      System.out.println("\tOsnovna torba ne vsebuje mojo torbe");
 
    if (b.containsAll(ob))
        System.out.println("\tMoja torba vsebuje osnovno torbo");
    else 
      System.out.println("\tMoja torba ne vsebuje osnovne torbe");
 
    if (b.equals(ob))
        System.out.println("\tMoja torba je enaka osnovni torbi");
    else 
      System.out.println("\tMoja torba ni enaka osnovni torbi");
 
    if (ob.equals(b))
        System.out.println("\tOsnovna torba je enaka moji torbi");
    else 
      System.out.println("\tOsnovna torba ni enaka moji torbi");
 
    /*  
    if (b.retainAll(ob))
    {
      System.out.println("Po b.retainAll(ob):");
      System.out.println(b.toString());
    }
 
    if (b.removeAll(ob))
    {
      System.out.println("Po b.removeAll(ob):");
      System.out.println(b.toString());
    }  
 
    */
  }
}