list.h

来自「VC视频对象的跟踪提取原代码（vc视频监控源码）」· C头文件 代码 · 共 425 行

/////////////////////////////////////////////////////////////////////////////////////////
//                                                                                     //
//  List.h                                                                             //
//                                                                                     //
//   A container class implementing a general (2-way) linked list of some type         //
//                                                                                     //
//   HISTORY: used to be ingeniously defined by amb using preprocessor directives      //
//            to avoid template problems of early template implementations in C++      //
//            compilers                                                                //
//                                                                                     //
//   template implementation by nts on Sat Nov 10 18:49:37 GMT 2001 from amb's list.h  //
//                                                                                     //
//   NB: our compiler does not support the `export' keyword fully yet so all code,     //
//        both interface and implementation, are contained in this .h file,            //
//                                                                                     //
/////////////////////////////////////////////////////////////////////////////////////////

#ifndef __LIST_H__
#define __LIST_H__

#include <iostream>
#include <cassert>

using namespace std;


namespace ReadingPeopleTracker
{

/////////////////////////////////////////////////////////////////////////////////
////////////////////////////////    Interface   /////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////

//  List<type>      used to be  list(type)  eg Profilelist
//  ListNode<type>  used to be  item(type)  eg Profileitem

// the keyword 'export' is not implemented in GCC 2.95.x and will be ignored
template <class type>
class ListNode   // used to be  class item(type)
{
public:
    type *dat;
    ListNode *prev;
    ListNode *next;
    
    ListNode ()
	{
	    bool this_is_recommended = false;
	    assert (this_is_recommended == true);  // do not use ListNode's copy constructor
	}
    
    ListNode (type *d, ListNode *p = NULL, ListNode *n = NULL)
	{
	    dat = d;
	    prev = p;
	    next = n;
	}
};

// the keyword 'export' is not implemented in GCC 2.95.x and will be ignored
template <class type>
class List
{
public:
    ListNode<type> *first;
    ListNode<type> *last;
    unsigned int no_items;
    ListNode<type> *current;
    
    List()
	{
	    first = last = current = NULL;
	    no_items = 0;
	}
    
    ~List()
	{
	    destroy_all();
	}
    
    List<type> &operator= (List<type> &original);
    List *duplicate();
    
    type *operator[](const unsigned int i) const;
    ListNode<type> *find(type *item) const;
    
    type *add(type *new_item);
    type *add_a_copy(type *new_item);
    type *add()  { return add (new type); }
    
    void concat(List *l2);
    
    type *remove(ListNode<type> *item);
    type *remove(type *item )  { return remove (find(item)); }
    type *remove(unsigned int i)  { return remove ((*this)[i]); }
    type *pop()  { return remove(last); }
    
    void destroy(ListNode<type> *item);
    void destroy(type *item ) { destroy (find(item)); }
    void destroy(unsigned int i) { destroy ((*this)[i]); }
    
    void insert_before(ListNode<type> *item, type *datum);
    void insert_at(unsigned int i, type *datum)
	{ insert_before((*this)[i], datum); }
    void insert_before(type *item, type *datum)
	{ insert_before(find(item), datum); }
    
    void delete_all();
    void destroy_all();
    
    void close();
    void open();
    
    ListNode<type> *start()  { return current = first; }
    ListNode<type> *forward()  { return current = current->next; }
    ListNode<type> *back()  { return current = current->prev; }
    bool current_ok()  { return current != NULL; }
    
    type *get_current()  { return current->dat; }
    type *get_first()  { return first->dat; }
    type *get_last()  { return last->dat; }
    
    type *to_vector();
};

template <class type>
ostream &operator<<(ostream &out_strm, const List<type> &l);

template <class type>
istream &operator>>(istream &in_strm, List<type> &l);



/////////////////////////////////////////////////////////////////////////////////
//////////////////////////////    Implementation   //////////////////////////////
/////////////////////////////////////////////////////////////////////////////////


template <class type>
List<type> &List<type>::operator= (List<type> &original)
{
    destroy_all();  // make room for data
    
    ListNode<type> *curr;
    
    for (curr = original.first; curr != NULL; curr = curr->next)
    {
	add_a_copy(curr->dat);
    }

    assert(no_items == original.no_items);
    
    current = NULL;

    return *this;
}


template <class type>
List<type> *List<type>::duplicate()
{
    List *list_copy = new List;
    ListNode<type> *curr;

    for (curr = first; curr != NULL; curr = curr->next)
	list_copy->add_a_copy(curr->dat);

    return list_copy;
}

template <class type>
type *List<type>::operator[] (const unsigned int i) const
{
    assert (i < no_items);

    unsigned int count;

    ListNode<type> *curr = first;
    
    for (count = 0; count < i; count++)
	curr = curr->next;

    return curr->dat;
}

template <class type>
ListNode<type> *List<type>::find(type *item_dat) const
{
    ListNode<type> *curr = first;

    while ((curr != NULL) && (curr->dat != item_dat))
	curr = curr->next;

    return curr;
}

template <class type>
type *List<type>::add(type *new_item_dat)
{
    ListNode<type> *new_item;
    if (no_items == 0)
    {
	assert (first == NULL);
	assert (last == NULL);
	new_item = new ListNode<type> (new_item_dat, NULL, NULL);
	first = last = new_item;
	no_items = 1;
    }
    else
    {
	new_item = new ListNode<type> (new_item_dat, last, NULL);
	last->next = new_item;
	no_items++;
	last = new_item;
    }
    return new_item->dat;
}

template <class type>
type *List<type>::add_a_copy(type *new_item_dat)
{
    type *copy_item_dat = new type;
    *copy_item_dat = *new_item_dat;
    return add(copy_item_dat);
}

template <class type>
void List<type>::concat(List<type> *l2)
{
    if (no_items == 0)
    {
	assert(first == NULL);

	if (l2->no_items > 0)
	{
	    first = l2->first;
	    last = l2->last;
	    no_items = l2->no_items;
	}
	else
	    assert(l2->first == NULL);
    }
    else
    {
	assert(last->next == NULL);  // fails if close() was called or list error
    
	if (l2->no_items > 0)
	{
	    last->next = l2->first;
	    l2->first->prev = last;
	    last = l2->last;
	    no_items += l2->no_items;
	}
	else
	    assert(l2->first == NULL);
    }
    
    l2->first = l2->last = NULL;  // remove data from l2 list
    l2->no_items = 0;
}


template <class type>
type *List<type>::remove(ListNode<type> *item)
{
    if (item == NULL)
	return NULL;

    type *rdat = item->dat;  // keep a pointer to return it

    if (no_items == 1)
    {
	assert (first == last);
	assert (item == first);
	
	delete item;
	first = last = current = NULL;
	no_items = 0;
	return rdat;
    }
    
    if (item->prev != NULL)
    {
	assert (item != first);
	item->prev->next = item->next;
    }
    
    if (item->next != NULL)
    {
	assert (item != last);
	item->next->prev = item->prev;
    } 

    if (item == first)
	first = item->next;

    if (item == last)
	last = item->prev;

    delete item;
    no_items--;
    return rdat;
}

template <class type>
void List<type>::destroy(ListNode<type> *item)
{
    // let remove(...) remove and delete the item, keeping item->dat
    type *rdat = remove(item);  // keep a pointer to the data item->dat

    if (rdat != NULL)
	delete rdat;
}

template <class type>
void List<type>::insert_before(ListNode<type> *item, type *datum)
{
    ListNode<type> *new_item = new ListNode<type> (datum, item->prev, item);
    if (item->prev != NULL) item->prev->next = new_item;
    if (item == first) first = new_item;
    item->prev = new_item;
    no_items++;
}

template <class type>
void List<type>::delete_all()
{
    while (no_items > 0)
	remove(last);

    first = last = current = NULL;
}

template <class type>
void List<type>::destroy_all()
{
    while (no_items > 0)
	destroy(last);

    first = last = current = NULL;
}

template <class type>
void List<type>::close()
{
    if (no_items > 0)
    {
	last->next = first;
	first->prev = last;
    }
}

template <class type>
void List<type>::open()
{
    if (no_items > 0)
    {
	last->next = first->prev = NULL;
    }
}

template <class type>
type *List<type>::to_vector()
{
    type *res = new type[no_items];
    ListNode<type> *curr = first;

    for (unsigned int j = 0; j < no_items; j++)
    {
	res[j] = *(curr->dat);
	curr = curr->next;
    }

    return res;
}

template <class type>
ostream &operator<<(ostream &out_strm, List<type> &l)
{
    ListNode<type> *curr = l.first;
    out_strm << "list_length = " << l.no_items << "\n";
    for (unsigned int j = 0; j < l.no_items; j++)
    {
	out_strm << (*(curr->dat)) << endl;
	curr = curr->next;
    }
    return out_strm;
}

template <class type>
istream &operator>>(istream &in_strm, List<type> &l)
{
    l.destroy_all();  // make room for data

    unsigned int nitems;
    char dummy [256];
    strcpy(dummy,"dummy");
    while ((in_strm.eof() == false) &&
	   ((strlen(dummy) == 0) ||
	    (strncmp(dummy, "list_length",12) != 0))) in_strm >> dummy;

    if (in_strm.eof() == false)
    {
	in_strm.ignore(256, '=');
	in_strm >> nitems;
	type *newdata;
	for (unsigned int j = 0; j < nitems; j++)
	{
	    newdata = new type;
	    in_strm >> (*newdata);
	    l.add(newdata);
	}
    }
    else
    {
	l.first = l.last = NULL;
	l.no_items = 0;
    }
    return in_strm;
}

} // namespace ReadingPeopleTracker

#endif