itemset.java

数据挖掘的工具代码（包含fp-tree,appriory

/*

ARMiner - Association Rules Miner
Copyright (C) 2000  UMass/Boston - Computer Science Department


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


The ARMiner Server was written by Dana Cristofor and Laurentiu
Cristofor.

The ARMiner Client was written by Abdelmajid Karatihy, Xiaoyong Kuang,
and Lung-Tsung Li.


The ARMiner package is currently maintained by Laurentiu Cristofor
([e-mail]).

*/

import java.util.Vector;

/*

  Maintenance log started on November 30th, 2000

  Dec. 5th, 2001    - fixed an error in add method

  Nov. 30th, 2000   - added pruneDuplicates method
                    - added doesIntersect method

*/

/**

   Itemset.java<P>

   An itemset is an ordered list of integers that identify items
   coupled with a float value representing the support of the itemset
   as a percentage.<P>
   
*/
/*
  
   This file is a part of the ARMiner project.
   
   (P)1999-2000 by ARMiner Server Team:

   Dana Cristofor
   Laurentiu Cristofor

*/

public class Itemset implements java.io.Serializable
{
  private static final int SIZE_INCR = 7;

  /** 
   * The capacity of the itemset.
   *
   * @serial
   */
  private int capacity;

  /** 
   * The number of items in the itemset.
   *
   * @serial
   */
  private int size;

  /** 
   * The itemset.
   *
   * @serial
   */
  private int[] set;

  /** 
   * The support of the itemset.
   *
   * @serial
   */
  private float support;

  /** 
   * The weight of the itemset.
   *
   * @serial
   */
  private long weight;

  /** 
   * The mark of the itemset.
   *
   * @serial
   */
  private boolean mark; // this can be used to mark the itemset for
  // various purposes

  /** 
   * Internal index used for cycling through the itemset's items.
   *
   * @serial
   */
  private int index;

  /**
   * Creates a new empty itemset.
   */
  public Itemset()
  {
    capacity = SIZE_INCR;
    set = new int[capacity];
    size = 0;
    support = 0;
    weight = 0;
    mark = false;
    index = 0;
  }

  /**
   * Create a new empty itemset of specified capacity.
   *
   * @param c   the capacity of the itemset
   * @exception IllegalArgumentException   <code>c</code> is negative or zero
   */
  public Itemset(int c)
  {
    if (c < 1)
      throw new IllegalArgumentException("constructor requires positive argument value");

    capacity = c;
    set = new int[capacity];
    size = 0;
    support = 0;
    weight = 0;
    mark = false;
    index = 0;
  }

  /**
   * Create a new itemset by copying a given one.
   *
   * @param itemset   the itemset to be copied
   * @exception IllegalArgumentException   <code>itemset</code> is null
   */
  public Itemset(Itemset itemset)
  {
    if (itemset == null)
      throw new IllegalArgumentException("constructor requires an itemset as argument");

    capacity = itemset.capacity;
    set = new int[capacity];
    size = itemset.size;
    support = itemset.support;
    weight = itemset.weight;
    mark = itemset.mark;
    for (int i = 0; i < size; i++)
      set[i] = itemset.set[i];
    index = 0;
  }

  /**
   * Return support of itemset.
   */
  public float getSupport()
  {
    return support;
  }

  /**
   * Return weight of itemset.
   */
  public long getWeight()
  {
    return weight;
  }

  /**
   * Return i-th item in set.
   *
   * @param i   the index of the item to get
   * @exception IndexOutOfBoundsException   <code>i</code> is an invalid index
   * @return   the <code>i</code>-th item
   */
  public int getItem(int i)
  {
    if (i < 0 || i >= size)
      throw new IndexOutOfBoundsException("invalid index");

    return set[i];
  }

  /**
   * Return first item in set.
   *
   * @exception IndexOutOfBoundsException   there is no first item
   * @return   first item
   */
  public int getFirstItem()
  {
    index = 0;

    if (index < 0 || index >= size)
      throw new IndexOutOfBoundsException("no first item");

    return set[index++];
  }

  /**
   * Return next item in set.
   *
   * @exception IndexOutOfBoundsException   there is no next item
   * @return   next item
   */
  public int getNextItem()
  {
    if (index < 0 || index >= size)
      throw new IndexOutOfBoundsException("no next item");

    return set[index++];
  }

  /**
   * Return true if there are more items in the itemset. You can call
   * this method to find out whether you can call getNext without
   * raising an exception.
   *
   * @return   true if there are more items, false if not
   */
  public boolean hasMoreItems() 
  { 
    if (index < 0 || index >= size) 
      return false; 
    else 
      return true; 
  }
  
  /**
   * Return size of itemset.
   *
   * @return   size of itemset
   */
  public int size()
  {
    return size;
  }

  /**
   * Return true if this itemset has items in common
   * with <code>itemset</code>.
   *
   * @param itemset   the itemset with which we compare
   * @exception IllegalArgumentException   <code>itemset</code> is null
   * @return   true if <code>itemset</code> contains items of this 
   * itemset, false otherwise.
   */
  public boolean doesIntersect(Itemset itemset)
  {
    if (itemset == null)
      throw new IllegalArgumentException("subtract() requires an itemset as argument");

    Itemset result = new Itemset(capacity);
    int i = 0;
    int j = 0;
    for ( ; i < size && j < itemset.size; )
      {
	// if elements are equal, return true
	if (set[i] == itemset.set[j])
	  return true;
	// if the element in this Itemset is bigger then
	// we need to move to the next item in itemset.
	else if (set[i] > itemset.set[j])
	  j++;
	// the element in this Itemset does not appear
	// in itemset so we need to add it to result
	else
	  i++;
      }

    return false;
  }

  /**
   * Return a new Itemset that contains only those items that do not
   * appear in <code>itemset</code>.
   *
   * @param itemset   the itemset whose items we want to subtract
   * @exception IllegalArgumentException   <code>itemset</code> is null
   * @return   an Itemset containing only those items of this Itemset that
   * do not appear in <code>itemset</code>.
   */
  public Itemset subtract(Itemset itemset)
  {
    if (itemset == null)
      throw new IllegalArgumentException("subtract() requires an itemset as argument");

    Itemset result = new Itemset(capacity);
    int i = 0;
    int j = 0;
    for ( ; i < size && j < itemset.size; )
      {
	// if elements are equal, move to next ones
	if (set[i] == itemset.set[j])
	  {
	    i++;
	    j++;
	  }
	// if the element in this Itemset is bigger then
	// we need to move to the next item in itemset.
	else if (set[i] > itemset.set[j])
	  j++;
	// the element in this Itemset does not appear
	// in itemset so we need to add it to result
	else
	  result.set[result.size++] = set[i++];
      }

    // copy any remaining items from this Itemset 
    while (i < size)
      result.set[result.size++] = set[i++];

    // NOTE: the size of the resulting itemset
    // has been automatically updated
    return result;
  }

  /**
   * Return a new Itemset that contains all those items that appear
   * in this Itemset and in <code>itemset</code>.
   *
   * @param itemset   the itemset whose items we want to add
   * @exception IllegalArgumentException   <code>itemset</code> is null
   * @return   an Itemset containing all those items that appear
   * in this Itemset and in <code>itemset</code>.
   */
  public Itemset add(Itemset itemset)
  {
    if (itemset == null)
      throw new IllegalArgumentException("add() requires an itemset as argument");

    Itemset result = new Itemset(capacity);
    int i = 0;
    int j = 0;
    for ( ; i < size && j < itemset.size; )
      {
	// if elements are equal, copy then move to next ones
	if (set[i] == itemset.set[j])
	  {
	    result.set[result.size++] = set[i++];
	    j++;
	  }
	// if the element in this Itemset is bigger then
	// we need to copy from itemset then move to the next item.
	else if (set[i] > itemset.set[j])
	  result.set[result.size++] = itemset.set[j++];
	// else we need to copy from this Itemset
	else
	  result.set[result.size++] = set[i++];
      }

    // copy any remaining items from this Itemset 
    while (i < size)
      result.set[result.size++] = set[i++];
    // copy any remaining items from itemset 
    while (j < itemset.size)
      result.set[result.size++] = itemset.set[j++];

    // NOTE: the size of the resulting itemset
    // has been automatically updated
    return result;
  }

  /**
   * Add a new item to the itemset.
   *
   * @param item   the item to be added
   * @exception IllegalArgumentException   <code>item</code> is <= 0
   * @return   true if item was added, false if it wasn't added (was
   * already there!)
   */
  public boolean addItem(int item)
  {
    if (item <= 0)
      throw new IllegalArgumentException("negative or zero value for item not allowed");

    if (size == 0)
      set[0] = item;
    else
      {
	// look for place to insert item
	int index;
	for (index = 0; index < size && item > set[index]; index++)
	  ;

	// if item was already in itemset then return
	if (index < size && item == set[index])
	  return false;

	// if set is full then allocate new array
	if (size == capacity)
	  {
	    capacity = size + SIZE_INCR;
	    int[] a = new int[capacity];

	    int i;
	    for (i = 0; i < index; i++)
	      a[i] = set[i];
	    a[i] = item;
	    for ( ; i < size; i++)
	      a[i + 1] = set[i];

	    set = a;
	  }
	// otherwise make place and insert new item
	else
	  {
	    int i;
	    for (i = size; i > index; i--)
	      set[i] = set[i - 1];

	    set[i] = item;