xref: /386bsd/usr/include/nonstd/gnu/g++/gen/List.ccP (revision a2142627) 
1// This may look like C code, but it is really -*- C++ -*-
2/*
3Copyright (C) 1988 Free Software Foundation
4    written by Doug Lea (dl@rocky.oswego.edu)
5
6This file is part of GNU CC.
7
8GNU CC is distributed in the hope that it will be useful,
9but WITHOUT ANY WARRANTY.  No author or distributor
10accepts responsibility to anyone for the consequences of using it
11or for whether it serves any particular purpose or works at all,
12unless he says so in writing.  Refer to the GNU CC General Public
13License for full details.
14
15Everyone is granted permission to copy, modify and redistribute
16GNU CC, but only under the conditions described in the
17GNU CC General Public License.   A copy of this license is
18supposed to have been given to you along with GNU CC so you
19can know your rights and responsibilities.  It should be in a
20file named COPYING.  Among other things, the copyright notice
21and this notice must be preserved on all copies.
22*/
23
24#ifdef __GNUG__
25#pragma implementation
26#endif
27#include <builtin.h>
28#include "<T>.List.h"
29
30<T>ListNode Nil<T>ListNode;
31
32class init_Nil<T>ListNode
33{
34public:
35  inline init_Nil<T>ListNode()
36  {
37    Nil<T>ListNode.tl = &Nil<T>ListNode;
38    Nil<T>ListNode.ref = -1;
39  }
40};
41
42static init_Nil<T>ListNode Nil<T>ListNode_initializer;
43
44<T>List& <T>List::operator = (<T>List& a)
45{
46  reference(a.P);
47  dereference(P);
48  P = a.P;
49  return *this;
50}
51
52<T> <T>List::pop()
53{
54  <T> res = P->hd;
55  <T>ListNode* tail = P->tl;
56  reference(tail);
57  dereference(P);
58  P = tail;
59  return res;
60}
61
62void <T>List::set_tail(<T>List& a)
63{
64  reference(a.P);
65  dereference(P->tl);
66  P->tl = a.P;
67}
68
69<T>List <T>List::nth(int n)
70{
71  for (<T>ListNode* p = P; n-- > 0; p = p->tl);
72  reference(p);
73  return <T>List(p);
74}
75
76<T>List <T>List::last()
77{
78  <T>ListNode* p = P;
79  if (p != &Nil<T>ListNode) while (p->tl != &Nil<T>ListNode) p = p->tl;
80  reference(p);
81  return <T>List(p);
82}
83
84void <T>List::append(<T>List& l)
85{
86  <T>ListNode* p = P;
87  <T>ListNode* a = l.P;
88  reference(a);
89  if (p != &Nil<T>ListNode)
90  {
91    while (p->tl != &Nil<T>ListNode) p = p->tl;
92    p->tl = a;
93  }
94  else
95    P = a;
96}
97
98int <T>List::length()
99{
100  int l = 0;
101  for (<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl) ++l;
102  return l;
103}
104
105<T>&  <T>List::operator [] (int n)
106{
107  for (<T>ListNode* p = P; n-- > 0; p = p->tl);
108  return (p->hd);
109}
110
111int operator == (<T>List& x, <T>List& y)
112{
113  <T>ListNode* a = x.P;
114  <T>ListNode* b = y.P;
115
116  for (;;)
117  {
118    if (a == &Nil<T>ListNode)
119      return b == &Nil<T>ListNode;
120    else if (b == &Nil<T>ListNode)
121      return 0;
122    else if (a->hd == b->hd)
123    {
124      a = a->tl;
125      b = b->tl;
126    }
127    else
128      return 0;
129  }
130}
131
132
133void <T>List::apply(<T>Procedure f)
134{
135  for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
136    (*f)((p->hd));
137}
138
139void <T>List::subst(<T&> old, <T&> repl)
140{
141  for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
142    if (p->hd == old)
143      p->hd = repl;
144}
145
146<T> <T>List::reduce(<T>Combiner f, <T&> base)
147{
148  <T> r = base;
149  for(<T>ListNode* p = P; p != &Nil<T>ListNode; p = p->tl)
150    r = (*f)(r, (p->hd));
151  return r;
152}
153
154int <T>List::position(<T&> targ)
155{
156  int l = 0;
157  <T>ListNode* p = P;
158  for (;;)
159  {
160    if (p == &Nil<T>ListNode)
161      return -1;
162    else if (p->hd == targ)
163      return l;
164    else
165    {
166      ++l;
167      p = p->tl;
168    }
169  }
170}
171
172int <T>List::contains(<T&> targ)
173{
174  <T>ListNode* p = P;
175  for (;;)
176  {
177    if (p == &Nil<T>ListNode)
178      return 0;
179    else if (p->hd == targ)
180      return 1;
181    else
182      p = p->tl;
183  }
184}
185
186<T>List <T>List::find(<T&> targ)
187{
188  for (<T>ListNode* p = P; p != &Nil<T>ListNode && !(p->hd == targ); p=p->tl);
189  reference(p);
190  return <T>List(p);
191}
192
193Pix <T>List::seek(<T&> targ)
194{
195  <T>ListNode* p = P;
196  for (;;)
197  {
198    if (p == &Nil<T>ListNode)
199      return 0;
200    else if (p->hd == targ)
201      return Pix(p);
202    else
203      p = p->tl;
204  }
205}
206
207int <T>List::owns(Pix i)
208{
209  <T>ListNode* p = P;
210  for (;;)
211  {
212    if (p == &Nil<T>ListNode)
213      return 0;
214    else if (Pix(p) == i)
215      return 1;
216    else
217      p = p->tl;
218  }
219}
220
221<T>List <T>List::find(<T>List& target)
222{
223  <T>ListNode* targ = target.P;
224  if (targ == &Nil<T>ListNode)
225    return <T>List(targ);
226
227  <T>ListNode* p = P;
228  while (p != &Nil<T>ListNode)
229  {
230    if (p->hd == targ->hd)
231    {
232      <T>ListNode* a = p->tl;
233      <T>ListNode* t = targ->tl;
234      for(;;)
235      {
236        if (t == &Nil<T>ListNode)
237        {
238          reference(p);
239          return <T>List(p);
240        }
241        else if (a == &Nil<T>ListNode || !(a->hd == t->hd))
242          break;
243        else
244        {
245          a = a->tl;
246          t = t->tl;
247        }
248      }
249    }
250    p = p->tl;
251  }
252  return <T>List(&Nil<T>ListNode);
253}
254
255int <T>List::contains(<T>List& target)
256{
257  <T>ListNode* targ = target.P;
258  if (targ == &Nil<T>ListNode)
259    return 0;
260
261  <T>ListNode* p = P;
262  while (p != &Nil<T>ListNode)
263  {
264    if (p->hd == targ->hd)
265    {
266      <T>ListNode* a = p->tl;
267      <T>ListNode* t = targ->tl;
268      for(;;)
269      {
270        if (t == &Nil<T>ListNode)
271          return 1;
272        else if (a == &Nil<T>ListNode || !(a->hd == t->hd))
273          break;
274        else
275        {
276          a = a->tl;
277          t = t->tl;
278        }
279      }
280    }
281    p = p->tl;
282  }
283  return 0;
284}
285
286void <T>List::del(<T&> targ)
287{
288  <T>ListNode* h = P;
289
290  for (;;)
291  {
292    if (h == &Nil<T>ListNode)
293    {
294      P = h;
295      return;
296    }
297    else if (h->hd == targ)
298    {
299      <T>ListNode* nxt = h->tl;
300      reference(nxt);
301      dereference(h);
302      h = nxt;
303    }
304    else
305      break;
306  }
307
308  <T>ListNode* trail = h;
309  <T>ListNode* p = h->tl;
310  while (p != &Nil<T>ListNode)
311  {
312    if (p->hd == targ)
313    {
314      <T>ListNode* nxt = p->tl;
315      reference(nxt);
316      dereference(p);
317      trail->tl = nxt;
318      p = nxt;
319    }
320    else
321    {
322      trail = p;
323      p = p->tl;
324    }
325  }
326  P = h;
327}
328
329void <T>List::del(<T>Predicate f)
330{
331  <T>ListNode* h = P;
332  for (;;)
333  {
334    if (h == &Nil<T>ListNode)
335    {
336      P = h;
337      return;
338    }
339    else if ((*f)(h->hd))
340    {
341      <T>ListNode* nxt = h->tl;
342      reference(nxt);
343      dereference(h);
344      h = nxt;
345    }
346    else
347      break;
348  }
349
350  <T>ListNode* trail = h;
351  <T>ListNode* p = h->tl;
352  while (p != &Nil<T>ListNode)
353  {
354    if ((*f)(p->hd))
355    {
356      <T>ListNode* nxt = p->tl;
357      reference(nxt);
358      dereference(p);
359      trail->tl = nxt;
360      p = nxt;
361    }
362    else
363    {
364      trail = p;
365      p = p->tl;
366    }
367  }
368  P = h;
369}
370
371void <T>List::select(<T>Predicate f)
372{
373  <T>ListNode* h = P;
374  for (;;)
375  {
376    if (h == &Nil<T>ListNode)
377    {
378      P = h;
379      return;
380    }
381    else if (!(*f)(h->hd))
382    {
383      <T>ListNode* nxt = h->tl;
384      reference(nxt);
385      dereference(h);
386      h = nxt;
387    }
388    else
389      break;
390  }
391  <T>ListNode* trail = h;
392  <T>ListNode* p = h->tl;
393  while (p != &Nil<T>ListNode)
394  {
395    if (!(*f)(p->hd))
396    {
397      <T>ListNode* nxt = p->tl;
398      reference(nxt);
399      dereference(p);
400      trail->tl = nxt;
401      p = nxt;
402    }
403    else
404    {
405      trail = p;
406      p = p->tl;
407    }
408  }
409  P = h;
410}
411
412void <T>List::reverse()
413{
414  <T>ListNode* l = &Nil<T>ListNode;
415  <T>ListNode* p = P;
416  while (p != &Nil<T>ListNode)
417  {
418    <T>ListNode* nxt = p->tl;
419    p->tl = l;
420    l = p;
421    p = nxt;
422  }
423  P = l;
424}
425
426
427<T>List copy(<T>List& x)
428{
429  <T>ListNode* a = x.P;
430  if (a == &Nil<T>ListNode)
431    return <T>List(a);
432  else
433  {
434    <T>ListNode* h = new<T>ListNode(a->hd);
435    <T>ListNode* trail = h;
436    for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
437    {
438      <T>ListNode* n = new<T>ListNode(a->hd);
439      trail->tl = n;
440      trail = n;
441    }
442    trail->tl = &Nil<T>ListNode;
443    return <T>List(h);
444  }
445}
446
447
448<T>List subst(<T&> old, <T&> repl, <T>List& x)
449{
450  <T>ListNode* a = x.P;
451  if (a == &Nil<T>ListNode)
452    return <T>List(a);
453  else
454  {
455    <T>ListNode* h = new <T>ListNode;
456    h->ref = 1;
457    if (a->hd == old)
458      h->hd = repl;
459    else
460      h->hd = a->hd;
461    <T>ListNode* trail = h;
462    for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
463    {
464      <T>ListNode* n = new <T>ListNode;
465      n->ref = 1;
466      if (a->hd == old)
467        n->hd = repl;
468      else
469        n->hd = a->hd;
470      trail->tl = n;
471      trail = n;
472    }
473    trail->tl = &Nil<T>ListNode;
474    return <T>List(h);
475  }
476}
477
478<T>List combine(<T>Combiner f, <T>List& x, <T>List& y)
479{
480  <T>ListNode* a = x.P;
481  <T>ListNode* b = y.P;
482  if (a == &Nil<T>ListNode || b == &Nil<T>ListNode)
483    return <T>List(&Nil<T>ListNode);
484  else
485  {
486    <T>ListNode* h = new<T>ListNode((*f)(a->hd, b->hd));
487    <T>ListNode* trail = h;
488    a = a->tl;
489    b = b->tl;
490    while (a != &Nil<T>ListNode && b != &Nil<T>ListNode)
491    {
492      <T>ListNode* n = new<T>ListNode((*f)(a->hd, b->hd));
493      trail->tl = n;
494      trail = n;
495      a = a->tl;
496      b = b->tl;
497    }
498    trail->tl = &Nil<T>ListNode;
499    return <T>List(h);
500  }
501}
502
503<T>List reverse(<T>List& x)
504{
505  <T>ListNode* a = x.P;
506  if (a == &Nil<T>ListNode)
507    return <T>List(a);
508  else
509  {
510    <T>ListNode* l = new<T>ListNode(a->hd);
511    l->tl = &Nil<T>ListNode;
512    for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
513    {
514      <T>ListNode* n = new<T>ListNode(a->hd);
515      n->tl = l;
516      l = n;
517    }
518    return <T>List(l);
519  }
520}
521
522<T>List append(<T>List& x, <T>List& y)
523{
524  <T>ListNode* a = x.P;
525  <T>ListNode* b = y.P;
526  reference(b);
527  if (a != &Nil<T>ListNode)
528  {
529    <T>ListNode* h = new<T>ListNode(a->hd);
530    <T>ListNode* trail = h;
531    for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
532    {
533      <T>ListNode* n = new<T>ListNode(a->hd);
534      trail->tl = n;
535      trail = n;
536    }
537    trail->tl = b;
538    return <T>List(h);
539  }
540  else
541    return <T>List(b);
542}
543
544void <T>List::prepend(<T>List& y)
545{
546  <T>ListNode* b = y.P;
547  if (b != &Nil<T>ListNode)
548  {
549    <T>ListNode* h = new<T>ListNode(b->hd);
550    <T>ListNode* trail = h;
551    for(b = b->tl; b != &Nil<T>ListNode; b = b->tl)
552    {
553      <T>ListNode* n = new<T>ListNode(b->hd);
554      trail->tl = n;
555      trail = n;
556    }
557    trail->tl = P;
558    P = h;
559  }
560}
561
562<T>List concat(<T>List& x, <T>List& y)
563{
564  <T>ListNode* a = x.P;
565  <T>ListNode* b = y.P;
566  if (a != &Nil<T>ListNode)
567  {
568    <T>ListNode* h = new<T>ListNode(a->hd);
569    <T>ListNode* trail = h;
570    for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
571    {
572      <T>ListNode* n = new<T>ListNode(a->hd);
573      trail->tl = n;
574      trail = n;
575    };
576    for(;b != &Nil<T>ListNode; b = b->tl)
577    {
578      <T>ListNode* n = new<T>ListNode(b->hd);
579      trail->tl = n;
580      trail = n;
581    }
582    trail->tl = &Nil<T>ListNode;
583    return <T>List(h);
584  }
585  else if (b != &Nil<T>ListNode)
586  {
587    <T>ListNode* h = new<T>ListNode(b->hd);
588    <T>ListNode* trail = h;
589    for(b = b->tl; b != &Nil<T>ListNode; b = b->tl)
590    {
591      <T>ListNode* n = new<T>ListNode(b->hd);
592      trail->tl = n;
593      trail = n;
594    }
595    trail->tl = &Nil<T>ListNode;
596    return <T>List(h);
597  }
598  else
599    return <T>List(&Nil<T>ListNode);
600}
601
602<T>List select(<T>Predicate f, <T>List& x)
603{
604  <T>ListNode* a = x.P;
605  <T>ListNode* h = &Nil<T>ListNode;
606  while (a != &Nil<T>ListNode)
607  {
608    if ((*f)(a->hd))
609    {
610      h = new<T>ListNode(a->hd);
611      <T>ListNode* trail = h;
612      for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
613      {
614        if ((*f)(a->hd))
615        {
616          <T>ListNode* n = new<T>ListNode(a->hd);
617          trail->tl = n;
618          trail = n;
619        }
620      }
621      trail->tl = &Nil<T>ListNode;
622      break;
623    }
624    else
625      a = a->tl;
626  }
627  return <T>List(h);
628}
629
630<T>List remove(<T>Predicate f, <T>List& x)
631{
632  <T>ListNode* a = x.P;
633  <T>ListNode* h = &Nil<T>ListNode;
634  while (a != &Nil<T>ListNode)
635  {
636    if (!(*f)(a->hd))
637    {
638      h = new<T>ListNode(a->hd);
639      <T>ListNode* trail = h;
640      for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
641      {
642        if (!(*f)(a->hd))
643        {
644          <T>ListNode* n = new<T>ListNode(a->hd);
645          trail->tl = n;
646          trail = n;
647        }
648      }
649      trail->tl = &Nil<T>ListNode;
650      break;
651    }
652    else
653      a = a->tl;
654  }
655  return <T>List(h);
656}
657
658<T>List remove(<T&> targ, <T>List& x)
659{
660  <T>ListNode* a = x.P;
661  <T>ListNode* h = &Nil<T>ListNode;
662  while (a != &Nil<T>ListNode)
663  {
664    if (!(a->hd == targ))
665    {
666      h = new<T>ListNode(a->hd);
667      <T>ListNode* trail = h;
668      for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
669      {
670        if (!(a->hd == targ))
671        {
672          <T>ListNode* n = new<T>ListNode(a->hd);
673          trail->tl = n;
674          trail = n;
675        }
676      }
677      trail->tl = &Nil<T>ListNode;
678      break;
679    }
680    else
681      a = a->tl;
682  }
683  return <T>List(h);
684}
685
686<T>List map(<T>Mapper f, <T>List& x)
687{
688  <T>ListNode* a = x.P;
689  <T>ListNode* h = &Nil<T>ListNode;
690  if (a != &Nil<T>ListNode)
691  {
692    h = new<T>ListNode((*f)(a->hd));
693    <T>ListNode* trail = h;
694    for(a = a->tl; a != &Nil<T>ListNode; a = a->tl)
695    {
696      <T>ListNode* n = new<T>ListNode((*f)(a->hd));
697      trail->tl = n;
698      trail = n;
699    }
700    trail->tl = &Nil<T>ListNode;
701  }
702  return <T>List(h);
703}
704
705
706<T>List merge(<T>List& x, <T>List& y, <T>Comparator f)
707{
708  <T>ListNode* a = x.P;
709  <T>ListNode* b = y.P;
710
711  if (a == &Nil<T>ListNode)
712  {
713    if (b == &Nil<T>ListNode)
714      return <T>List(&Nil<T>ListNode);
715    else
716      return copy(y);
717  }
718  else if (b == &Nil<T>ListNode)
719    return copy(x);
720
721  <T>ListNode* h = new <T>ListNode;
722  h->ref = 1;
723  if ((*f)(a->hd, b->hd) <= 0)
724  {
725    h->hd = a->hd;
726    a = a->tl;
727  }
728  else
729  {
730    h->hd = b->hd;
731    b = b->tl;
732  }
733
734  <T>ListNode* r = h;
735
736  for(;;)
737  {
738    if (a == &Nil<T>ListNode)
739    {
740      while (b != &Nil<T>ListNode)
741      {
742        <T>ListNode* n = new <T>ListNode;
743        n->ref = 1;
744        n->hd = b->hd;
745        r->tl = n;
746        r = n;
747        b = b->tl;
748      }
749      r->tl = &Nil<T>ListNode;
750      return <T>List(h);
751    }
752    else if (b == &Nil<T>ListNode)
753    {
754      while (a != &Nil<T>ListNode)
755      {
756        <T>ListNode* n = new <T>ListNode;
757        n->ref = 1;
758        n->hd = a->hd;
759        r->tl = n;
760        r = n;
761        a = a->tl;
762      }
763      r->tl = &Nil<T>ListNode;
764      return <T>List(h);
765    }
766    else if ((*f)(a->hd, b->hd) <= 0)
767    {
768      <T>ListNode* n = new <T>ListNode;
769      n->ref = 1;
770      n->hd = a->hd;
771      r->tl = n;
772      r = n;
773      a = a->tl;
774    }
775    else
776    {
777      <T>ListNode* n = new <T>ListNode;
778      n->ref = 1;
779      n->hd = b->hd;
780      r->tl = n;
781      r = n;
782      b = b->tl;
783    }
784  }
785}
786
787void <T>List::sort(<T>Comparator f)
788{
789  // strategy: place runs in queue, merge runs until done
790  // This is often very fast
791
792  if (P == &Nil<T>ListNode || P->tl == &Nil<T>ListNode)
793    return;
794
795  int qlen = 250;   // guess a good queue size, realloc if necessary
796
797  <T>ListNode** queue = (<T>ListNode**)malloc(qlen * sizeof(<T>ListNode*));
798
799  <T>ListNode* h = P;
800  <T>ListNode* a = h;
801  <T>ListNode* b = a->tl;
802  int qin = 0;
803
804  while (b != &Nil<T>ListNode)
805  {
806    if ((*f)(a->hd, b->hd) > 0)
807    {
808      if (h == a)               // minor optimization: ensure runlen >= 2
809      {
810        h = b;
811        a->tl = b->tl;
812        b->tl = a;
813        b = a->tl;
814      }
815      else
816      {
817        if (qin >= qlen)
818        {
819          qlen *= 2;
820          queue = (<T>ListNode**)realloc(queue, qlen * sizeof(<T>ListNode*));
821        }
822        queue[qin++] = h;
823        a->tl = &Nil<T>ListNode;
824        h = a = b;
825        b = b->tl;
826      }
827    }
828    else
829    {
830      a = b;
831      b = b->tl;
832    }
833  }
834
835  int count = qin;
836  queue[qin] = h;
837  if (++qin >= qlen) qin = 0;
838  int qout = 0;
839
840  while (count-- > 0)
841  {
842    a = queue[qout];
843    if (++qout >= qlen) qout = 0;
844    b = queue[qout];
845    if (++qout >= qlen) qout = 0;
846
847    if ((*f)(a->hd, b->hd) <= 0)
848    {
849      h = a;
850      a = a->tl;
851    }
852    else
853    {
854      h = b;
855      b = b->tl;
856    }
857    queue[qin] = h;
858    if (++qin >= qlen) qin = 0;
859
860    for (;;)
861    {
862      if (a == &Nil<T>ListNode)
863      {
864        h->tl = b;
865        break;
866      }
867      else if (b == &Nil<T>ListNode)
868      {
869        h->tl = a;
870        break;
871      }
872      else if ((*f)(a->hd, b->hd) <= 0)
873      {
874        h->tl = a;
875        h = a;
876        a = a->tl;
877      }
878      else
879      {
880        h->tl = b;
881        h = b;
882        b = b->tl;
883      }
884    }
885  }
886  P = queue[qout];
887  free(queue);
888}
889
890int <T>List::list_length()
891{
892  <T>ListNode* fast = P;
893  if (fast == &Nil<T>ListNode)
894    return 0;
895
896  <T>ListNode* slow = fast->tl;
897  if (slow == &Nil<T>ListNode)
898    return 1;
899
900  fast = slow->tl;
901  int n = 2;
902
903  for (;;)
904  {
905    if (fast == &Nil<T>ListNode)
906      return n;
907    else if (fast->tl == &Nil<T>ListNode)
908      return n+1;
909    else if (fast == slow)
910      return -1;
911    else
912    {
913      n += 2;
914      fast = fast->tl->tl;
915      slow = slow->tl;
916    }
917  }
918}
919
920void <T>List::error(const char* msg)
921{
922  (*lib_error_handler)("List", msg);
923}
924
925int <T>List::OK()
926{
927  int v = P != 0;               // have a node
928  // check that all nodes OK, even if circular:
929
930  <T>ListNode* fast = P;
931  if (fast != &Nil<T>ListNode)
932  {
933    v &= fast->ref != 0;
934    <T>ListNode* slow = fast->tl;
935    v &= slow->ref != 0;
936    if (v && slow != &Nil<T>ListNode)
937    {
938      fast = slow->tl;
939      v &= fast->ref != 0;
940      while (v)
941      {
942        if (fast == &Nil<T>ListNode)
943          break;
944        else if (fast->tl == &Nil<T>ListNode)
945          break;
946        else if (fast == slow)
947          break;
948        else
949        {
950          v &= fast->ref != 0 && slow->ref != 0;
951          fast = fast->tl->tl;
952          slow = slow->tl;
953        }
954      }
955    }
956  }
957  if (!v) error ("invariant failure");
958  return v;
959}
960