ftmpl_list.cc
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
4 
5 template <class T>
7 {
8  next = i.next;
9  prev = i.prev;
10  item = i.item;
11 }
12 
13 
14 template <class T>
16 {
17  next = n;
18  prev = p;
19  item = new T( t );
20 }
21 
22 
23 template <class T>
25 {
26  next = n;
27  prev = p;
28  item = t;
29 }
30 
31 
32 template <class T>
34 {
35  delete item;
36 }
37 
38 
39 template <class T>
41 {
42  if ( this != &i )
43  {
44  next = i.next;
45  prev = i.prev;
46  item = i.item;
47  }
48  return *this;
49 }
50 
51 
52 template <class T>
54 {
55  return next;
56 }
57 
58 
59 template <class T>
61 {
62  return prev;
63 }
64 
65 
66 template <class T>
68 {
69  return *item;
70 }
71 
72 #ifndef NOSTREAMIO
73 template <class T>
75 {
76  if ( item )
77  os << *item;
78  else
79  os << "(no item)";
80 }
81 #endif /* NOSTREAMIO */
82 
83 
84 
85 template <class T>
87 {
88  first = last = 0;
89  _length = 0;
90 }
91 
92 
93 template <class T>
95 {
96  ListItem<T>* cur = l.last;
97  if ( cur )
98  {
99  first = new ListItem<T>( *(cur->item), 0, 0 );
100  last = first;
101  cur = cur->prev;
102  while ( cur )
103  {
104  first = new ListItem<T>( *(cur->item), first, 0 );
105  first->next->prev = first;
106  cur = cur->prev;
107  }
108  _length = l._length;
109  }
110  else
111  {
112  first = last = 0;
113  _length = 0;
114  }
115 }
116 
117 
118 template <class T>
119 List<T>::List( const T& t )
120 {
121  first = last = new ListItem<T>( t, 0, 0 );
122  _length = 1;
123 }
124 
125 
126 template <class T>
128 {
129  ListItem<T> *dummy;
130  while ( first )
131  {
132  dummy = first;
133  first = first->next;
134  delete dummy;
135  }
136 }
137 
138 
139 template <class T>
141 {
142  if ( this != &l )
143  {
144  ListItem<T> *dummy;
145  while ( first )
146  {
147  dummy = first;
148  first = first->next;
149  delete dummy;
150  }
151  ListItem<T>* cur = l.last;
152  if ( cur )
153  {
154  first = new ListItem<T>( *(cur->item), 0, 0 );
155  last = first;
156  cur = cur->prev;
157  while ( cur )
158  {
159  first = new ListItem<T>( *(cur->item), first, 0 );
160  first->next->prev = first;
161  cur = cur->prev;
162  }
163  _length = l._length;
164  }
165  else
166  {
167  first = last = 0;
168  _length = 0;
169  }
170  _length = l._length;
171  }
172  return *this;
173 }
174 
175 template <class T>
176 int operator== ( const List<T>& l1, const List<T>& l2 )
177 {
178  if (l1.length() != l2.length())
179  return 0;
180  ListIterator<T> iter2= l2;
181  for (ListIterator<T> iter1= l1; iter1.hasItem(); iter1++)
182  {
183  if (!(iter1.getItem() == iter2.getItem()))
184  return 0;
185  iter2++;
186  }
187 
188  return 1;
189 }
190 
191 
192 template <class T>
193 void List<T>::insert ( const T& t )
194 {
195  first = new ListItem<T>( t, first, 0 );
196  if ( last )
197  first->next->prev = first;
198  last = ( last ) ? last : first;
199  _length++;
200 }
201 
202 
203 template <class T>
204 void List<T>::insert ( const T& t, int (*cmpf)( const T&, const T& ) )
205 {
206  if ( ! first || cmpf( *first->item, t ) > 0 )
207  insert( t );
208  else if ( cmpf( *last->item, t ) < 0 )
209  append( t );
210  else
211  {
212  ListItem<T> * cursor = first;
213  int c;
214  while ( (c = cmpf( *cursor->item, t )) < 0 )
215  cursor = cursor->next;
216  if ( c == 0 )
217  *cursor->item = t;
218  else
219  {
220  cursor = cursor->prev;
221  cursor->next = new ListItem<T>( t, cursor->next, cursor );
222  cursor->next->next->prev = cursor->next;
223  _length++;
224  }
225  }
226 }
227 
228 
229 template <class T>
230 void List<T>::insert ( const T& t, int (*cmpf)( const T&, const T& ), void (*insf)( T&, const T& ) )
231 {
232  if ( ! first || cmpf( *first->item, t ) > 0 )
233  insert( t );
234  else if ( cmpf( *last->item, t ) < 0 )
235  append( t );
236  else
237  {
238  ListItem<T> * cursor = first;
239  int c;
240  while ( (c = cmpf( *cursor->item, t )) < 0 )
241  cursor = cursor->next;
242  if ( c == 0 )
243  insf( *cursor->item, t );
244  else
245  {
246  cursor = cursor->prev;
247  cursor->next = new ListItem<T>( t, cursor->next, cursor );
248  cursor->next->next->prev = cursor->next;
249  _length++;
250  }
251  }
252 }
253 
254 
255 template <class T>
256 void List<T>::append ( const T& t )
257 {
258  last = new ListItem<T>( t, 0, last );
259  if ( first )
260  last->prev->next = last;
261  first = ( first ) ? first : last;
262  _length++;
263 }
264 
265 
266 template <class T>
267 int List<T>::isEmpty() const
268 {
269  return ( first == 0 );
270 }
271 
272 template <class T>
273 int List<T>::length() const
274 {
275  return _length;
276 }
277 
278 template <class T>
280 {
281  ASSERT( first, "List: no item available" );
282  return first->getItem();
283 }
284 
285 
286 template <class T>
288 {
289  if ( first )
290  {
291  _length--;
292  if ( first == last )
293  {
294  delete first;
295  first = last = 0;
296  }
297  else
298  {
299  ListItem<T> *dummy = first;
300  first->next->prev = 0;
301  first = first->next;
302  delete dummy;
303  }
304  }
305 }
306 
307 
308 template <class T>
310 {
311  ASSERT( first, "List: no item available" );
312  return last->getItem();
313 }
314 
315 
316 template <class T>
318 {
319  if ( last )
320  {
321  _length--;
322  if ( first == last )
323  {
324  delete last;
325  first = last = 0;
326  }
327  else
328  {
329  ListItem<T> *dummy = last;
330  last->prev->next = 0;
331  last = last->prev;
332  delete dummy;
333  }
334  }
335 }
336 
337 
338 template <class T>
339 void List<T>::sort( int (*swapit) ( const T&, const T& ) )
340 {
341  if ( first != last )
342  {
343  int swap;
344  do
345  {
346  swap = 0;
347  ListItem<T> *cur = first;
348  while ( cur->next )
349  {
350  if ( swapit( *(cur->item), *(cur->next->item) ) )
351  {
352  T* dummy = cur->item;
353  cur->item = cur->next->item;
354  cur->next->item = dummy;
355  swap = 1;
356  }
357  cur = cur->next;
358  }
359  } while (swap);
360  }
361 }
362 
363 
364 #ifndef NOSTREAMIO
365 template <class T>
366 void List<T>::print ( OSTREAM & os ) const
367 {
368  ListItem<T> *cur = first;
369  os << "( ";
370  while ( cur )
371  {
372  cur->print( os );
373  if ( (cur = cur->getNext()) )
374  os << ", ";
375  }
376  os << " )";
377 }
378 #endif /* NOSTREAMIO */
379 
380 
381 template <class T>
383 {
384  theList = 0;
385  current = 0;
386 }
387 
388 
389 template <class T>
391 {
392  theList = i.theList;
393  current = i.current;
394 }
395 
396 
397 template <class T>
399 {
400  theList = (List<T>*)&l;
401  current = l.first;
402 }
403 
404 
405 template <class T>
407 
408 
409 template <class T>
411 {
412  if ( this != &I )
413  {
414  theList = I.theList;
415  current = I.current;
416  }
417  return *this;
418 }
419 
420 
421 template <class T>
423 {
424  theList = (List<T>*)&l;
425  current = l.first;
426  return *this;
427 }
428 
429 
430 template <class T>
432 {
433  ASSERT( current, "ListIterator: no item available" );
434  return current->getItem();
435 }
436 
437 
438 template <class T>
440 {
441  return current != 0;
442 }
443 
444 
445 template <class T>
447 {
448  if ( current )
449  current = current->next;
450 }
451 
452 
453 template <class T>
455 {
456  if ( current )
457  current = current->prev;
458 }
459 
460 
461 template <class T>
463 {
464  if ( current )
465  current = current->next;
466 }
467 
468 
469 template <class T>
471 {
472  if ( current )
473  current = current->prev;
474 }
475 
476 
477 template <class T>
479 {
480  current = theList->first;
481 }
482 
483 
484 template <class T>
486 {
487  current = theList->last;
488 }
489 
490 
491 template <class T>
492 void ListIterator<T>::insert ( const T & t )
493 {
494  if ( current )
495  {
496  if ( ! current->prev )
497  theList->insert( t );
498  else
499  {
500  current->prev = new ListItem<T>( t, current, current->prev );
501  current->prev->prev->next = current->prev;
502  theList->_length++;
503  }
504  }
505 }
506 
507 
508 template <class T>
509 void ListIterator<T>::append ( const T & t )
510 {
511  if ( current )
512  {
513  if ( ! current->next )
514  theList->append( t );
515  else
516  {
517  current->next = new ListItem<T>( t, current->next, current );
518  current->next->next->prev = current->next;
519  theList->_length++;
520  }
521  }
522 }
523 
524 
525 template <class T>
526 void ListIterator<T>::remove ( int moveright )
527 {
528  if ( current )
529  {
530  ListItem <T>*dummynext = current->next, *dummyprev = current->prev;
531  if ( current->prev )
532  {
533  current->prev->next = current->next;
534  if ( current->next )
535  current->next->prev = current->prev;
536  else
537  theList->last = current->prev;
538  delete current;
539  current = ( moveright ) ? dummynext : dummyprev;
540  }
541  else
542  {
543  if ( current->next )
544  current->next->prev = 0;
545  theList->first = current->next;
546  delete current;
547  current = ( moveright ) ? dummynext : dummyprev;
548  }
549  theList->_length--;
550  }
551 }
552 
553 #ifndef NOSTREAMIO
554 template <class T>
555 OSTREAM& operator<<( OSTREAM & os, const List<T> & l )
556 {
557  l.print( os );
558  return os;
559 }
560 #endif /* NOSTREAMIO */
561 
562 template <class T>
563 List<T> Union ( const List<T> & F, const List<T> & G )
564 {
565  List<T> L = G;
567  T f;
568  bool iselt;
569 
570  for ( i = F; i.hasItem(); i++ )
571  {
572  f = i.getItem();
573  iselt = false;
574  j = G;
575  while ( ( ! iselt ) && j.hasItem() )
576  {
577  iselt = f == j.getItem();
578  j++;
579  }
580  if ( ! iselt )
581  L.append( f );
582  }
583  return L;
584 }
585 
586 template <class T>
587 List<T> Union ( const List<T> & F, const List<T> & G, int (*cmpf)( const T&, const T& ), void (*insf)( T&, const T& ) )
588 {
589  List<T> L = G;
591 
592  for ( i = F; i.hasItem(); ++i )
593  L.insert( i.getItem(), cmpf, insf );
594  return L;
595 }
596 
597 template <class T>
598 List<T> Union ( const List<T> & F, const List<T> & G, int (*ecmpf)( const T&, const T& ))
599 {
600  List<T> L = G;
602  T f;
603  bool iselt;
604 
605  for ( i = F; i.hasItem(); i++ )
606  {
607  f = i.getItem();
608  iselt = false;
609  j = G;
610  while ( ( ! iselt ) && j.hasItem() )
611  {
612  iselt = ecmpf (f, j.getItem());
613  j++;
614  }
615  if ( ! iselt )
616  L.append( f );
617  }
618  return L;
619 }
620 
621 template <class T>
622 List<T> Difference ( const List<T> & F, const List<T> & G )
623 {
624  List<T> L;
626  T f;
627  int found;
628  for ( i = F; i.hasItem(); ++i )
629  {
630  f = i.getItem();
631  found = 0;
632  for ( j = G; j.hasItem() && (!found); ++j )
633  found = f == j.getItem();
634  if ( ! found )
635  L.append( f );
636  }
637  return L;
638 }
639 
640 template <class T>
641 List<T> Difference ( const List<T> & F, const List<T> & G, int (*ecmpf)( const T&, const T& ))
642 {
643  List<T> L;
645  T f;
646  int found;
647  for ( i = F; i.hasItem(); ++i )
648  {
649  f = i.getItem();
650  found = 0;
651  for ( j = G; j.hasItem() && (!found); ++j )
652  found = ecmpf (f, j.getItem());
653  if ( ! found )
654  L.append( f );
655  }
656  return L;
657 }
658 
659 template <class T>
660 List<T> Difference ( const List<T> & F, const T & G, int (*ecmpf)( const T&, const T& ))
661 {
662  List<T> L;
664  int found;
665  for ( i = F; i.hasItem(); ++i )
666  {
667  found = ecmpf (G, i.getItem());
668  if ( ! found )
669  L.append( i.getItem() );
670  }
671  return L;
672 }
673 
674 template <class T>
675 List<T> Difference ( const List<T> & F, const T & G)
676 {
677  List<T> L;
679  int found;
680  for ( i = F; i.hasItem(); ++i )
681  {
682  found = G == i.getItem();
683  if ( ! found )
684  L.append( i.getItem() );
685  }
686  return L;
687 }
688 
689 template <class T>
690 T prod ( const List<T> & F )
691 {
693  T p = 1;
694  for ( i = F; i.hasItem(); i++ )
695  p = p * i.getItem();
696  return p;
697 }
698 
699 template <class T>
700 bool find (const List<T> & F, const T& t)
701 {
702  if (F.length() == 0) return false;
703  ListIterator<T> J= F;
704  while (J.hasItem())
705  {
706  if (J.getItem() == t)
707  return true;
708  J++;
709  }
710  return false;
711 }
712 
713 template <class T>
714 bool find (const List<T> & F, const T& t, int (*ecmpf)( const T&, const T& ))
715 {
716  if (F.length() == 0) return false;
717  ListIterator<T> J= F;
718  while (J.hasItem())
719  {
720  if (ecmpf (J.getItem(), t))
721  return true;
722  J++;
723  }
724  return false;
725 }
726 
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
ListItem * next
Definition: ftmpl_list.h:33
void remove(int moveright)
Definition: ftmpl_list.cc:526
ListIterator< T > & operator=(const ListIterator< T > &)
Definition: ftmpl_list.cc:410
int isEmpty() const
Definition: ftmpl_list.cc:267
ListItem< T > * getPrev()
Definition: ftmpl_list.cc:60
~List()
Definition: ftmpl_list.cc:127
T * item
Definition: ftmpl_list.h:35
return P p
Definition: myNF.cc:203
static poly last
Definition: hdegree.cc:1077
void lastItem()
Definition: ftmpl_list.cc:485
ListItem * prev
Definition: ftmpl_list.h:34
void firstItem()
Definition: ftmpl_list.cc:478
ListItem< T > & operator=(const ListItem< T > &)
Definition: ftmpl_list.cc:40
void insert(const T &)
Definition: ftmpl_list.cc:193
List< T > & operator=(const List< T > &)
Definition: ftmpl_list.cc:140
static TreeM * G
Definition: janet.cc:38
void removeFirst()
Definition: ftmpl_list.cc:287
bool found
Definition: facFactorize.cc:56
void operator--()
Definition: ftmpl_list.cc:454
T getFirst() const
Definition: ftmpl_list.cc:279
int _length
Definition: ftmpl_list.h:58
void append(const T &)
Definition: ftmpl_list.cc:509
int operator==(const List< T > &l1, const List< T > &l2)
Definition: ftmpl_list.cc:176
void removeLast()
Definition: ftmpl_list.cc:317
int j
Definition: myNF.cc:70
T prod(const List< T > &F)
Definition: ftmpl_list.cc:690
List< T > Union(const List< T > &F, const List< T > &G)
Definition: ftmpl_list.cc:563
ListItem< T > * first
Definition: ftmpl_list.h:56
T & getItem() const
Definition: ftmpl_list.cc:431
result insert(CFAFactor(LcF, 1, 1))
ListItem< T > * current
Definition: ftmpl_list.h:92
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:123
T getLast() const
Definition: ftmpl_list.cc:309
void print(OSTREAM &) const
Definition: ftmpl_list.cc:366
ListItem< T > * getNext()
Definition: ftmpl_list.cc:53
void insert(const T &)
Definition: ftmpl_list.cc:492
int length() const
Definition: ftmpl_list.cc:273
#define swap(_i, _j)
#define OSTREAM
Definition: canonicalform.h:16
bool find(const List< T > &F, const T &t)
Definition: ftmpl_list.cc:700
#define ASSERT(expression, message)
Definition: cf_assert.h:99
List()
Definition: ftmpl_list.cc:86
void operator++()
Definition: ftmpl_list.cc:446
void print(OSTREAM &)
Definition: ftmpl_list.cc:74
List< T > Difference(const List< T > &F, const List< T > &G)
Definition: ftmpl_list.cc:622
ListItem< T > * last
Definition: ftmpl_list.h:57
void append(const T &)
Definition: ftmpl_list.cc:256
static jList * T
Definition: janet.cc:37
int l
Definition: cfEzgcd.cc:94
ListItem(const ListItem< T > &)
Definition: ftmpl_list.cc:6
T & getItem()
Definition: ftmpl_list.cc:67
List< T > * theList
Definition: ftmpl_list.h:91
void sort(int(*)(const T &, const T &))
Definition: ftmpl_list.cc:339
ListNode * next
Definition: janet.h:31