list.cpp

数据挖掘中的经典算法Apriori实现

//implementation of list class
#include <stdio.h>
#include "items.h"
#include "list.h"

list::list()
{
	head=tail=current=(ListNode *)NULL;
    number = 0;
    current_index = -1;
}
list::~list()
{
    clear();
}
//   Add an item to the list.
void list::add(items *item)
{
	ListNode *node = (ListNode *)new ListNode;
	node->next = (ListNode *)NULL;
	node->pre = tail;
	node->item = item;
    
    if (tail != (ListNode *)NULL)
    {
    	tail->next = node;
    	tail = node;
    }
    else
    	head = tail = node;

    number++;
}


//   Adds the specified item to the the scrolling list at the 
//   position indicated by the index.
//
void list::add(int position,items *item)
{
    ListNode *ln = head;
    
    for (int i = 0; i < position && ln; i++, ln = ln->next)
    	;
    
    if (!ln)
    {
        // if position is greater than the current scope, 
        // append the object to the list
        add(item);
    }
	else
    {
        ListNode *node;
		
		node = (ListNode *)new ListNode;
    
        node->next = (ListNode *)NULL;
        node->pre = (ListNode *)NULL;
		node->item = item;
        
    	if (ln == head)   //node is the first listnode
	    {
	        node->next = head;
    	    node->next->pre = node;
	        head = node;
    	}
	    else
    	{
	        node->next = ln;
	        node->pre = ln->pre;
    	    node->pre->next = node;
	        node->next->pre = node;
    	}
        
        if(current_index >= position)
            current_index++;
        
        number++;
    }
    
    return;
}

// Append plist to the current list
void list::add(list *plist)
{
	items *pitem;
	for(int i = 0; i < plist->size(); i++)
	{
		pitem = plist->get(i);
		add(pitem->clone());
	}

	return;
}
//*********************************************************************
// void list::clear()
//   Removes all nodes from this list, and the objects as well.
//
void list::clear()
{
    ListNode *node;
    
    while (head)
    {
    	node = head;
    	head = head->next;
		delete node->item;
    	delete node;
    }
    
    head = tail = current = (ListNode *)NULL;
    number = 0;
    current_index = -1;
}
//*********************************************************************
// void list::dump()
//   dump all the content in the link list.
//
void list::dump()
{
    for(ListNode *node = head; node != (ListNode *)NULL; node = node->next)
		node->item->dump();
}



//*********************************************************************
// List *List::clone()
//   Return a deep copy of the list.
//
list *list::clone()
{
    list	*lt = new list();
    ListNode *node;

    for(node = head; node != (ListNode *)NULL; node = node->next)
		lt->add(node->item->clone());
        
    return lt;
}

//*********************************************************************
//
//   Gets the item associated with the specified index.
//
items *list::get(int index)
{
    if (index < 0 || index >= number)
        return (items *)NULL;

    // if we want to retrieve exact the current node or the node next to current
    if (current_index == index)
		return current->item;
    if (current && current_index >= 0 && index == current_index + 1)
    {
    	current = current->next;
	    if (!current)
    	{
	        current_index = -1;
    	    return (items *)NULL;
	    }
    	current_index = index;
		return current->item;
    }

    ListNode *temp = head;
    
    for (int i = 0; temp && i < index; i++)
    	temp = temp->next;

    if (temp)
    {
    	current_index = index;
	    current = temp;
		return temp->item;
    }
    
   	return (items *)NULL;
}
//*********************************************************************
//
//    Searches for the first occurence of the given argument, 
//    testing for equality using the equals method.
//
int list::indexOf(items *obj)
{
    ListNode *temp = head;
    int			index = 0;

	while (temp && obj->compare(temp->item) != 0)  //not equal!
    {
    	temp = temp->next;
	    index++;
    }
    
    if (index >= number)
    	return -1;
    else
    	return index;
}
//*********************************************************************
// 
//   Remove the item at the specified position from this scrolling list.
//
void list::remove(int position)
{
    if (position < 0 || position >= number)
        return;
    
    ListNode *node;
    
    if (current_index == position)
        node = current;
    else if (current && current_index >= 0 && position == current_index + 1)
    	node = current->next;
    else
    {
        node = head;
    
        for (int i = 0; node && i < position; i++)
         	node = node->next;
    }
    
    if(node)
        remove(node);

    return;    
}
//*********************************************************************
// 
//   Removes the first occurrence of an item from the list.
//
void list::remove(items *item)
{
    
    for(ListNode *node = head; node != (ListNode *)NULL; node = node->next)
    {
		if (item->compare(node->item) == 0)
    	{
            remove(node);
            break;
    	}
    }
    
    return;
}
//*********************************************************************
// 
//   Remove the node from this scrolling list.
//
void list::remove(ListNode *node)
{
    
    if (head == tail)
    {
        // if only one node in the list
        head = tail = (ListNode *)NULL;
    }
    else if (head == node)
    {
        head = head->next;
		head->pre = (ListNode *)NULL;
    }
    else if (tail == node)
    {
        tail = tail->pre;
        tail->next = (ListNode *)NULL;
    }
    else
    {
        node->next->pre = node->pre;
        node->pre->next = node->next;
    }

	delete node->item;          //note here 
    delete node;
    
    number--;
    
    // we should keep the current correctly, but ...
    current_index = -1;
    current = (ListNode *)NULL;
    
    return;
}

//*********************************************************************
// 
//   Replaces the item at the specified index in the scrolling list with the new object.
//
void list::set(int position,items *item)
{
    ListNode *temp = head;
    
    //
    // First make sure that there is something there!
    //
    while (number < position + 1)
    	add((items *)NULL);                            //空的也添加

    //
    // Now find the listnode to put the new object in
    //
    for (int i = 0; temp && i < position; i++)
    	temp = temp->next;

	if(temp->item != (items *)NULL)
		delete temp->item;
    
	temp->item=item;
    
    current = temp;
    current_index = position;
    
    return;
}