Loading...
Searching...
No Matches
ftmpl_list.cc
Go to the documentation of this file.
/* emacs edit mode for this file is -*- C++ -*- */
#include "factory/templates/ftmpl_list.h"
template <class T>
ListItem<T>::ListItem( const ListItem<T>& i )
{
next = i.next;
prev = i.prev;
item = i.item;
}
template <class T>
ListItem<T>::ListItem( const T& t, ListItem<T>* n, ListItem<T>* p )
{
next = n;
prev = p;
item = new T( t );
}
template <class T>
ListItem<T>::ListItem( T* t, ListItem<T>* n, ListItem<T>* p )
{
next = n;
prev = p;
item = t;
}
template <class T>
ListItem<T>::~ListItem()
{
delete item;
}
template <class T>
ListItem<T>& ListItem<T>::operator=( const ListItem<T>& i )
{
if ( this != &i )
{
next = i.next;
prev = i.prev;
item = i.item;
}
return *this;
}
template <class T>
ListItem<T>* ListItem<T>::getNext()
{
return next;
}
template <class T>
ListItem<T>* ListItem<T>::getPrev()
{
return prev;
}
template <class T>
T& ListItem<T>::getItem()
{
return *item;
}
#ifndef NOSTREAMIO
template <class T>
void ListItem<T>::print( OSTREAM & os )
{
if ( item )
os << *item;
else
os << "(no item)";
}
#endif /* NOSTREAMIO */
template <class T>
List<T>::List()
{
first = last = 0;
_length = 0;
}
template <class T>
List<T>::List( const List<T>& l )
{
ListItem<T>* cur = l.last;
if ( cur )
{
first = new ListItem<T>( *(cur->item), 0, 0 );
last = first;
cur = cur->prev;
while ( cur )
{
first = new ListItem<T>( *(cur->item), first, 0 );
first->next->prev = first;
cur = cur->prev;
}
_length = l._length;
}
else
{
first = last = 0;
_length = 0;
}
}
template <class T>
List<T>::List( const T& t )
{
first = last = new ListItem<T>( t, 0, 0 );
_length = 1;
}
template <class T>
List<T>::~List()
{
ListItem<T> *dummy;
while ( first )
{
dummy = first;
first = first->next;
delete dummy;
}
}
template <class T>
List<T>& List<T>::operator=( const List<T>& l )
{
if ( this != &l )
{
ListItem<T> *dummy;
while ( first )
{
dummy = first;
first = first->next;
delete dummy;
}
ListItem<T>* cur = l.last;
if ( cur )
{
first = new ListItem<T>( *(cur->item), 0, 0 );
last = first;
cur = cur->prev;
while ( cur )
{
first = new ListItem<T>( *(cur->item), first, 0 );
first->next->prev = first;
cur = cur->prev;
}
_length = l._length;
}
else
{
first = last = 0;
_length = 0;
}
_length = l._length;
}
return *this;
}
template <class T>
int operator== ( const List<T>& l1, const List<T>& l2 )
{
if (l1.length() != l2.length())
return 0;
ListIterator<T> iter2= l2;
for (ListIterator<T> iter1= l1; iter1.hasItem(); iter1++)
{
if (!(iter1.getItem() == iter2.getItem()))
return 0;
iter2++;
}
return 1;
}
template <class T>
void List<T>::insert ( const T& t )
{
first = new ListItem<T>( t, first, 0 );
if ( last )
first->next->prev = first;
last = ( last ) ? last : first;
_length++;
}
template <class T>
void List<T>::insert ( const T& t, int (*cmpf)( const T&, const T& ) )
{
if ( ! first || cmpf( *first->item, t ) > 0 )
insert( t );
else if ( cmpf( *last->item, t ) < 0 )
append( t );
else
{
ListItem<T> * cursor = first;
int c;
while ( (c = cmpf( *cursor->item, t )) < 0 )
cursor = cursor->next;
if ( c == 0 )
*cursor->item = t;
else
{
cursor = cursor->prev;
cursor->next = new ListItem<T>( t, cursor->next, cursor );
cursor->next->next->prev = cursor->next;
_length++;
}
}
}
template <class T>
void List<T>::insert ( const T& t, int (*cmpf)( const T&, const T& ), void (*insf)( T&, const T& ) )
{
if ( ! first || cmpf( *first->item, t ) > 0 )
insert( t );
else if ( cmpf( *last->item, t ) < 0 )
append( t );
else
{
ListItem<T> * cursor = first;
int c;
while ( (c = cmpf( *cursor->item, t )) < 0 )
cursor = cursor->next;
if ( c == 0 )
insf( *cursor->item, t );
else
{
cursor = cursor->prev;
cursor->next = new ListItem<T>( t, cursor->next, cursor );
cursor->next->next->prev = cursor->next;
_length++;
}
}
}
template <class T>
void List<T>::append ( const T& t )
{
last = new ListItem<T>( t, 0, last );
if ( first )
last->prev->next = last;
first = ( first ) ? first : last;
_length++;
}
template <class T>
int List<T>::isEmpty() const
{
return ( first == 0 );
}
template <class T>
int List<T>::length() const
{
return _length;
}
template <class T>
T List<T>::getFirst() const
{
ASSERT( first, "List: no item available" );
return first->getItem();
}
template <class T>
void List<T>::removeFirst()
{
if ( first )
{
_length--;
if ( first == last )
{
delete first;
first = last = 0;
}
else
{
ListItem<T> *dummy = first;
first->next->prev = 0;
first = first->next;
delete dummy;
}
}
}
template <class T>
T List<T>::getLast() const
{
ASSERT( first, "List: no item available" );
return last->getItem();
}
template <class T>
void List<T>::removeLast()
{
if ( last )
{
_length--;
if ( first == last )
{
delete last;
first = last = 0;
}
else
{
ListItem<T> *dummy = last;
last->prev->next = 0;
last = last->prev;
delete dummy;
}
}
}
template <class T>
void List<T>::sort( int (*swapit) ( const T&, const T& ) )
{
if ( first != last )
{
int swap;
do
{
swap = 0;
ListItem<T> *cur = first;
while ( cur->next )
{
if ( swapit( *(cur->item), *(cur->next->item) ) )
{
T* dummy = cur->item;
cur->item = cur->next->item;
cur->next->item = dummy;
swap = 1;
}
cur = cur->next;
}
} while (swap);
}
}
#ifndef NOSTREAMIO
template <class T>
void List<T>::print ( OSTREAM & os ) const
{
ListItem<T> *cur = first;
os << "( ";
while ( cur )
{
cur->print( os );
if ( (cur = cur->getNext()) )
os << ", ";
}
os << " )";
}
#endif /* NOSTREAMIO */
template <class T>
ListIterator<T>::ListIterator()
{
theList = 0;
current = 0;
}
template <class T>
ListIterator<T>::ListIterator ( const ListIterator<T> & i )
{
theList = i.theList;
current = i.current;
}
template <class T>
ListIterator<T>::ListIterator ( const List<T> & l )
{
theList = (List<T>*)&l;
current = l.first;
}
template <class T>
ListIterator<T>::~ListIterator() { }
template <class T>
ListIterator<T>& ListIterator<T>::operator= ( const ListIterator<T> & I )
{
if ( this != &I )
{
theList = I.theList;
current = I.current;
}
return *this;
}
template <class T>
ListIterator<T>& ListIterator<T>::operator= ( const List<T> & l )
{
theList = (List<T>*)&l;
current = l.first;
return *this;
}
template <class T>
T& ListIterator<T>::getItem () const
{
ASSERT( current, "ListIterator: no item available" );
return current->getItem();
}
template <class T>
int ListIterator<T>::hasItem ()
{
return current != 0;
}
template <class T>
void ListIterator<T>::operator++ ()
{
if ( current )
current = current->next;
}
template <class T>
void ListIterator<T>::operator-- ()
{
if ( current )
current = current->prev;
}
template <class T>
void ListIterator<T>::operator++ ( int )
{
if ( current )
current = current->next;
}
template <class T>
void ListIterator<T>::operator-- ( int )
{
if ( current )
current = current->prev;
}
template <class T>
void ListIterator<T>::firstItem ()
{
current = theList->first;
}
template <class T>
void ListIterator<T>::lastItem ()
{
current = theList->last;
}
template <class T>
void ListIterator<T>::insert ( const T & t )
{
if ( current )
{
if ( ! current->prev )
theList->insert( t );
else
{
current->prev = new ListItem<T>( t, current, current->prev );
current->prev->prev->next = current->prev;
theList->_length++;
}
}
}
template <class T>
void ListIterator<T>::append ( const T & t )
{
if ( current )
{
if ( ! current->next )
theList->append( t );
else
{
current->next = new ListItem<T>( t, current->next, current );
current->next->next->prev = current->next;
theList->_length++;
}
}
}
template <class T>
void ListIterator<T>::remove ( int moveright )
{
if ( current )
{
ListItem <T>*dummynext = current->next, *dummyprev = current->prev;
if ( current->prev )
{
current->prev->next = current->next;
if ( current->next )
current->next->prev = current->prev;
else
theList->last = current->prev;
delete current;
current = ( moveright ) ? dummynext : dummyprev;
}
else
{
if ( current->next )
current->next->prev = 0;
theList->first = current->next;
delete current;
current = ( moveright ) ? dummynext : dummyprev;
}
theList->_length--;
}
}
#ifndef NOSTREAMIO
template <class T>
OSTREAM& operator<<( OSTREAM & os, const List<T> & l )
{
l.print( os );
return os;
}
#endif /* NOSTREAMIO */
template <class T>
List<T> Union ( const List<T> & F, const List<T> & G )
{
List<T> L = G;
ListIterator<T> i, j;
T f;
bool iselt;
for ( i = F; i.hasItem(); i++ )
{
f = i.getItem();
iselt = false;
j = G;
while ( ( ! iselt ) && j.hasItem() )
{
iselt = f == j.getItem();
j++;
}
if ( ! iselt )
L.append( f );
}
return L;
}
template <class T>
List<T> Union ( const List<T> & F, const List<T> & G, int (*cmpf)( const T&, const T& ), void (*insf)( T&, const T& ) )
{
List<T> L = G;
ListIterator<T> i;
for ( i = F; i.hasItem(); ++i )
L.insert( i.getItem(), cmpf, insf );
return L;
}
template <class T>
List<T> Union ( const List<T> & F, const List<T> & G, int (*ecmpf)( const T&, const T& ))
{
List<T> L = G;
ListIterator<T> i, j;
T f;
bool iselt;
for ( i = F; i.hasItem(); i++ )
{
f = i.getItem();
iselt = false;
j = G;
while ( ( ! iselt ) && j.hasItem() )
{
iselt = ecmpf (f, j.getItem());
j++;
}
if ( ! iselt )
L.append( f );
}
return L;
}
template <class T>
List<T> Difference ( const List<T> & F, const List<T> & G )
{
List<T> L;
ListIterator<T> i, j;
T f;
int found;
for ( i = F; i.hasItem(); ++i )
{
f = i.getItem();
found = 0;
for ( j = G; j.hasItem() && (!found); ++j )
found = f == j.getItem();
if ( ! found )
L.append( f );
}
return L;
}
template <class T>
List<T> Difference ( const List<T> & F, const List<T> & G, int (*ecmpf)( const T&, const T& ))
{
List<T> L;
ListIterator<T> i, j;
T f;
int found;
for ( i = F; i.hasItem(); ++i )
{
f = i.getItem();
found = 0;
for ( j = G; j.hasItem() && (!found); ++j )
found = ecmpf (f, j.getItem());
if ( ! found )
L.append( f );
}
return L;
}
template <class T>
List<T> Difference ( const List<T> & F, const T & G, int (*ecmpf)( const T&, const T& ))
{
List<T> L;
ListIterator<T> i;
int found;
for ( i = F; i.hasItem(); ++i )
{
found = ecmpf (G, i.getItem());
if ( ! found )
L.append( i.getItem() );
}
return L;
}
template <class T>
List<T> Difference ( const List<T> & F, const T & G)
{
List<T> L;
ListIterator<T> i;
int found;
for ( i = F; i.hasItem(); ++i )
{
found = G == i.getItem();
if ( ! found )
L.append( i.getItem() );
}
return L;
}
template <class T>
T prod ( const List<T> & F )
{
ListIterator<T> i;
T p = 1;
for ( i = F; i.hasItem(); i++ )
p *= i.getItem();
return p;
}
template <class T>
bool find (const List<T> & F, const T& t)
{
if (F.length() == 0) return false;
ListIterator<T> J= F;
while (J.hasItem())
{
if (J.getItem() == t)
return true;
J++;
}
return false;
}
template <class T>
bool find (const List<T> & F, const T& t, int (*ecmpf)( const T&, const T& ))
{
if (F.length() == 0) return false;
ListIterator<T> J= F;
while (J.hasItem())
{
if (ecmpf (J.getItem(), t))
return true;
J++;
}
return false;
}
swap
#define swap(_i, _j)
l
int l
Definition cfEzgcd.cc:100
i
int i
Definition cfEzgcd.cc:132
p
int p
Definition cfModGcd.cc:4086
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
f
FILE * f
Definition checklibs.c:9
ListItem
Definition ftmpl_list.h:29
ListItem::getNext
ListItem< T > * getNext()
Definition ftmpl_list.cc:53
ListItem::getItem
T & getItem()
Definition ftmpl_list.cc:67
ListItem::next
ListItem * next
Definition ftmpl_list.h:31
ListItem::~ListItem
~ListItem()
Definition ftmpl_list.cc:33
ListItem::prev
ListItem * prev
Definition ftmpl_list.h:32
ListItem::item
T * item
Definition ftmpl_list.h:33
ListItem::operator=
ListItem< T > & operator=(const ListItem< T > &)
Definition ftmpl_list.cc:40
ListItem::ListItem
ListItem(const ListItem< T > &)
Definition ftmpl_list.cc:6
ListItem::print
void print(OSTREAM &)
Definition ftmpl_list.cc:74
ListItem::getPrev
ListItem< T > * getPrev()
Definition ftmpl_list.cc:60
ListIterator
Definition ftmpl_list.h:87
ListIterator::lastItem
void lastItem()
Definition ftmpl_list.cc:485
ListIterator::firstItem
void firstItem()
Definition ftmpl_list.cc:478
ListIterator::ListIterator
ListIterator()
Definition ftmpl_list.cc:382
ListIterator::remove
void remove(int moveright)
Definition ftmpl_list.cc:526
ListIterator::operator--
void operator--()
Definition ftmpl_list.cc:454
ListIterator::operator=
ListIterator< T > & operator=(const ListIterator< T > &)
Definition ftmpl_list.cc:410
ListIterator::theList
List< T > * theList
Definition ftmpl_list.h:89
ListIterator::append
void append(const T &)
Definition ftmpl_list.cc:509
ListIterator::~ListIterator
~ListIterator()
Definition ftmpl_list.cc:406
ListIterator::operator++
void operator++()
Definition ftmpl_list.cc:446
ListIterator::hasItem
int hasItem()
Definition ftmpl_list.cc:439
ListIterator::getItem
T & getItem() const
Definition ftmpl_list.cc:431
ListIterator::current
ListItem< T > * current
Definition ftmpl_list.h:90
ListIterator::insert
void insert(const T &)
Definition ftmpl_list.cc:492
List
Definition ftmpl_list.h:52
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
List::first
ListItem< T > * first
Definition ftmpl_list.h:54
List::~List
~List()
Definition ftmpl_list.cc:127
List::removeFirst
void removeFirst()
Definition ftmpl_list.cc:287
List::sort
void sort(int(*)(const T &, const T &))
Definition ftmpl_list.cc:339
List::List
List()
Definition ftmpl_list.cc:86
List::operator=
List< T > & operator=(const List< T > &)
Definition ftmpl_list.cc:140
List::length
int length() const
Definition ftmpl_list.cc:273
List::append
void append(const T &)
Definition ftmpl_list.cc:256
List::getLast
T getLast() const
Definition ftmpl_list.cc:309
List::insert
void insert(const T &)
Definition ftmpl_list.cc:193
List::_length
int _length
Definition ftmpl_list.h:56
List::isEmpty
int isEmpty() const
Definition ftmpl_list.cc:267
List::last
ListItem< T > * last
Definition ftmpl_list.h:55
List::print
void print(OSTREAM &) const
Definition ftmpl_list.cc:366
List::removeLast
void removeLast()
Definition ftmpl_list.cc:317
insert
result insert(CFAFactor(LcF, 1, 1))
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition facAlgFuncUtil.cc:32
found
bool found
Definition facFactorize.cc:55
j
int j
Definition facHensel.cc:110
prod
fq_nmod_poly_t prod
Definition facHensel.cc:100
operator==
int operator==(const List< T > &l1, const List< T > &l2)
Definition ftmpl_list.cc:176
find
bool find(const List< T > &F, const T &t)
Definition ftmpl_list.cc:700
Union
List< T > Union(const List< T > &F, const List< T > &G)
Definition ftmpl_list.cc:563
Difference
List< T > Difference(const List< T > &F, const List< T > &G)
Definition ftmpl_list.cc:622
operator<<
OSTREAM & operator<<(OSTREAM &os, const List< T > &l)
Definition ftmpl_list.cc:555
ftmpl_list.h
OSTREAM
#define OSTREAM
Definition ftmpl_list.h:9
T
STATIC_VAR jList * T
Definition janet.cc:30
G
STATIC_VAR TreeM * G
Definition janet.cc:31