home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Tools / Languages / Python 1.1 / Objects / listobject.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-29  |  13.6 KB  |  745 lines  |  [TEXT/KAHL]
  1. /***********************************************************
  2. Copyright 1991, 1992, 1993, 1994 by Stichting Mathematisch Centrum,
  3. Amsterdam, The Netherlands.
  4.  
  5.                         All Rights Reserved
  6.  
  7. Permission to use, copy, modify, and distribute this software and its 
  8. documentation for any purpose and without fee is hereby granted, 
  9. provided that the above copyright notice appear in all copies and that
  10. both that copyright notice and this permission notice appear in 
  11. supporting documentation, and that the names of Stichting Mathematisch
  12. Centrum or CWI not be used in advertising or publicity pertaining to
  13. distribution of the software without specific, written prior permission.
  14.  
  15. STICHTING MATHEMATISCH CENTRUM DISCLAIMS ALL WARRANTIES WITH REGARD TO
  16. THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
  17. FITNESS, IN NO EVENT SHALL STICHTING MATHEMATISCH CENTRUM BE LIABLE
  18. FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  19. WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  20. ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
  21. OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  22.  
  23. ******************************************************************/
  24.  
  25. /* List object implementation */
  26.  
  27. #include "allobjects.h"
  28. #include "modsupport.h"
  29. #include "ceval.h"
  30. #ifdef STDC_HEADERS
  31. #include <stddef.h>
  32. #else
  33. #include <sys/types.h>        /* For size_t */
  34. #endif
  35.  
  36. object *
  37. newlistobject(size)
  38.     int size;
  39. {
  40.     int i;
  41.     listobject *op;
  42.     size_t nbytes;
  43.     if (size < 0) {
  44.         err_badcall();
  45.         return NULL;
  46.     }
  47.     nbytes = size * sizeof(object *);
  48.     /* Check for overflow */
  49.     if (nbytes / sizeof(object *) != size) {
  50.         return err_nomem();
  51.     }
  52.     op = (listobject *) malloc(sizeof(listobject));
  53.     if (op == NULL) {
  54.         return err_nomem();
  55.     }
  56.     if (size <= 0) {
  57.         op->ob_item = NULL;
  58.     }
  59.     else {
  60.         op->ob_item = (object **) malloc(nbytes);
  61.         if (op->ob_item == NULL) {
  62.             free((ANY *)op);
  63.             return err_nomem();
  64.         }
  65.     }
  66.     op->ob_type = &Listtype;
  67.     op->ob_size = size;
  68.     for (i = 0; i < size; i++)
  69.         op->ob_item[i] = NULL;
  70.     NEWREF(op);
  71.     return (object *) op;
  72. }
  73.  
  74. int
  75. getlistsize(op)
  76.     object *op;
  77. {
  78.     if (!is_listobject(op)) {
  79.         err_badcall();
  80.         return -1;
  81.     }
  82.     else
  83.         return ((listobject *)op) -> ob_size;
  84. }
  85.  
  86. object *
  87. getlistitem(op, i)
  88.     object *op;
  89.     int i;
  90. {
  91.     if (!is_listobject(op)) {
  92.         err_badcall();
  93.         return NULL;
  94.     }
  95.     if (i < 0 || i >= ((listobject *)op) -> ob_size) {
  96.         err_setstr(IndexError, "list index out of range");
  97.         return NULL;
  98.     }
  99.     return ((listobject *)op) -> ob_item[i];
  100. }
  101.  
  102. int
  103. setlistitem(op, i, newitem)
  104.     register object *op;
  105.     register int i;
  106.     register object *newitem;
  107. {
  108.     register object *olditem;
  109.     if (!is_listobject(op)) {
  110.         XDECREF(newitem);
  111.         err_badcall();
  112.         return -1;
  113.     }
  114.     if (i < 0 || i >= ((listobject *)op) -> ob_size) {
  115.         XDECREF(newitem);
  116.         err_setstr(IndexError, "list assignment index out of range");
  117.         return -1;
  118.     }
  119.     olditem = ((listobject *)op) -> ob_item[i];
  120.     ((listobject *)op) -> ob_item[i] = newitem;
  121.     XDECREF(olditem);
  122.     return 0;
  123. }
  124.  
  125. static int
  126. ins1(self, where, v)
  127.     listobject *self;
  128.     int where;
  129.     object *v;
  130. {
  131.     int i;
  132.     object **items;
  133.     if (v == NULL) {
  134.         err_badcall();
  135.         return -1;
  136.     }
  137.     items = self->ob_item;
  138.     RESIZE(items, object *, self->ob_size+1);
  139.     if (items == NULL) {
  140.         err_nomem();
  141.         return -1;
  142.     }
  143.     if (where < 0)
  144.         where = 0;
  145.     if (where > self->ob_size)
  146.         where = self->ob_size;
  147.     for (i = self->ob_size; --i >= where; )
  148.         items[i+1] = items[i];
  149.     INCREF(v);
  150.     items[where] = v;
  151.     self->ob_item = items;
  152.     self->ob_size++;
  153.     return 0;
  154. }
  155.  
  156. int
  157. inslistitem(op, where, newitem)
  158.     object *op;
  159.     int where;
  160.     object *newitem;
  161. {
  162.     if (!is_listobject(op)) {
  163.         err_badcall();
  164.         return -1;
  165.     }
  166.     return ins1((listobject *)op, where, newitem);
  167. }
  168.  
  169. int
  170. addlistitem(op, newitem)
  171.     object *op;
  172.     object *newitem;
  173. {
  174.     if (!is_listobject(op)) {
  175.         err_badcall();
  176.         return -1;
  177.     }
  178.     return ins1((listobject *)op,
  179.         (int) ((listobject *)op)->ob_size, newitem);
  180. }
  181.  
  182. /* Methods */
  183.  
  184. static void
  185. list_dealloc(op)
  186.     listobject *op;
  187. {
  188.     int i;
  189.     for (i = 0; i < op->ob_size; i++) {
  190.         XDECREF(op->ob_item[i]);
  191.     }
  192.     if (op->ob_item != NULL)
  193.         free((ANY *)op->ob_item);
  194.     free((ANY *)op);
  195. }
  196.  
  197. static int
  198. list_print(op, fp, flags)
  199.     listobject *op;
  200.     FILE *fp;
  201.     int flags;
  202. {
  203.     int i;
  204.     fprintf(fp, "[");
  205.     for (i = 0; i < op->ob_size; i++) {
  206.         if (i > 0)
  207.             fprintf(fp, ", ");
  208.         if (printobject(op->ob_item[i], fp, 0) != 0)
  209.             return -1;
  210.     }
  211.     fprintf(fp, "]");
  212.     return 0;
  213. }
  214.  
  215. static object *
  216. list_repr(v)
  217.     listobject *v;
  218. {
  219.     object *s, *comma;
  220.     int i;
  221.     s = newstringobject("[");
  222.     comma = newstringobject(", ");
  223.     for (i = 0; i < v->ob_size && s != NULL; i++) {
  224.         if (i > 0)
  225.             joinstring(&s, comma);
  226.         joinstring_decref(&s, reprobject(v->ob_item[i]));
  227.     }
  228.     XDECREF(comma);
  229.     joinstring_decref(&s, newstringobject("]"));
  230.     return s;
  231. }
  232.  
  233. static int
  234. list_compare(v, w)
  235.     listobject *v, *w;
  236. {
  237.     int len = (v->ob_size < w->ob_size) ? v->ob_size : w->ob_size;
  238.     int i;
  239.     for (i = 0; i < len; i++) {
  240.         int cmp = cmpobject(v->ob_item[i], w->ob_item[i]);
  241.         if (cmp != 0)
  242.             return cmp;
  243.     }
  244.     return v->ob_size - w->ob_size;
  245. }
  246.  
  247. static int
  248. list_length(a)
  249.     listobject *a;
  250. {
  251.     return a->ob_size;
  252. }
  253.  
  254. static object *
  255. list_item(a, i)
  256.     listobject *a;
  257.     int i;
  258. {
  259.     if (i < 0 || i >= a->ob_size) {
  260.         err_setstr(IndexError, "list index out of range");
  261.         return NULL;
  262.     }
  263.     INCREF(a->ob_item[i]);
  264.     return a->ob_item[i];
  265. }
  266.  
  267. static object *
  268. list_slice(a, ilow, ihigh)
  269.     listobject *a;
  270.     int ilow, ihigh;
  271. {
  272.     listobject *np;
  273.     int i;
  274.     if (ilow < 0)
  275.         ilow = 0;
  276.     else if (ilow > a->ob_size)
  277.         ilow = a->ob_size;
  278.     if (ihigh < 0)
  279.         ihigh = 0;
  280.     if (ihigh < ilow)
  281.         ihigh = ilow;
  282.     else if (ihigh > a->ob_size)
  283.         ihigh = a->ob_size;
  284.     np = (listobject *) newlistobject(ihigh - ilow);
  285.     if (np == NULL)
  286.         return NULL;
  287.     for (i = ilow; i < ihigh; i++) {
  288.         object *v = a->ob_item[i];
  289.         INCREF(v);
  290.         np->ob_item[i - ilow] = v;
  291.     }
  292.     return (object *)np;
  293. }
  294.  
  295. object *
  296. getlistslice(a, ilow, ihigh)
  297.     object *a;
  298.     int ilow, ihigh;
  299. {
  300.     if (!is_listobject(a)) {
  301.         err_badcall();
  302.         return NULL;
  303.     }
  304.     return list_slice((listobject *)a, ilow, ihigh);
  305. }
  306.  
  307. static object *
  308. list_concat(a, bb)
  309.     listobject *a;
  310.     object *bb;
  311. {
  312.     int size;
  313.     int i;
  314.     listobject *np;
  315.     if (!is_listobject(bb)) {
  316.         err_badarg();
  317.         return NULL;
  318.     }
  319. #define b ((listobject *)bb)
  320.     size = a->ob_size + b->ob_size;
  321.     np = (listobject *) newlistobject(size);
  322.     if (np == NULL) {
  323.         return NULL;
  324.     }
  325.     for (i = 0; i < a->ob_size; i++) {
  326.         object *v = a->ob_item[i];
  327.         INCREF(v);
  328.         np->ob_item[i] = v;
  329.     }
  330.     for (i = 0; i < b->ob_size; i++) {
  331.         object *v = b->ob_item[i];
  332.         INCREF(v);
  333.         np->ob_item[i + a->ob_size] = v;
  334.     }
  335.     return (object *)np;
  336. #undef b
  337. }
  338.  
  339. static object *
  340. list_repeat(a, n)
  341.     listobject *a;
  342.     int n;
  343. {
  344.     int i, j;
  345.     int size;
  346.     listobject *np;
  347.     object **p;
  348.     if (n < 0)
  349.         n = 0;
  350.     size = a->ob_size * n;
  351.     np = (listobject *) newlistobject(size);
  352.     if (np == NULL)
  353.         return NULL;
  354.     p = np->ob_item;
  355.     for (i = 0; i < n; i++) {
  356.         for (j = 0; j < a->ob_size; j++) {
  357.             *p = a->ob_item[j];
  358.             INCREF(*p);
  359.             p++;
  360.         }
  361.     }
  362.     return (object *) np;
  363. }
  364.  
  365. static int
  366. list_ass_slice(a, ilow, ihigh, v)
  367.     listobject *a;
  368.     int ilow, ihigh;
  369.     object *v;
  370. {
  371.     object **item;
  372.     int n; /* Size of replacement list */
  373.     int d; /* Change in size */
  374.     int k; /* Loop index */
  375. #define b ((listobject *)v)
  376.     if (v == NULL)
  377.         n = 0;
  378.     else if (is_listobject(v)) {
  379.         n = b->ob_size;
  380.         if (a == b) {
  381.             /* Special case "a[i:j] = a" -- copy b first */
  382.             int ret;
  383.             v = list_slice(b, 0, n);
  384.             ret = list_ass_slice(a, ilow, ihigh, v);
  385.             DECREF(v);
  386.             return ret;
  387.         }
  388.     }
  389.     else {
  390.         err_badarg();
  391.         return -1;
  392.     }
  393.     if (ilow < 0)
  394.         ilow = 0;
  395.     else if (ilow > a->ob_size)
  396.         ilow = a->ob_size;
  397.     if (ihigh < 0)
  398.         ihigh = 0;
  399.     if (ihigh < ilow)
  400.         ihigh = ilow;
  401.     else if (ihigh > a->ob_size)
  402.         ihigh = a->ob_size;
  403.     item = a->ob_item;
  404.     d = n - (ihigh-ilow);
  405.     if (d <= 0) { /* Delete -d items; XDECREF ihigh-ilow items */
  406.         for (k = ilow; k < ihigh; k++)
  407.             XDECREF(item[k]);
  408.         if (d < 0) {
  409.             for (/*k = ihigh*/; k < a->ob_size; k++)
  410.                 item[k+d] = item[k];
  411.             a->ob_size += d;
  412.             RESIZE(item, object *, a->ob_size); /* Can't fail */
  413.             a->ob_item = item;
  414.         }
  415.     }
  416.     else { /* Insert d items; XDECREF ihigh-ilow items */
  417.         RESIZE(item, object *, a->ob_size + d);
  418.         if (item == NULL) {
  419.             err_nomem();
  420.             return -1;
  421.         }
  422.         for (k = a->ob_size; --k >= ihigh; )
  423.             item[k+d] = item[k];
  424.         for (/*k = ihigh-1*/; k >= ilow; --k)
  425.             XDECREF(item[k]);
  426.         a->ob_item = item;
  427.         a->ob_size += d;
  428.     }
  429.     for (k = 0; k < n; k++, ilow++) {
  430.         object *w = b->ob_item[k];
  431.         XINCREF(w);
  432.         item[ilow] = w;
  433.     }
  434.     return 0;
  435. #undef b
  436. }
  437.  
  438. int
  439. setlistslice(a, ilow, ihigh, v)
  440.     object *a;
  441.     int ilow, ihigh;
  442.     object *v;
  443. {
  444.     if (!is_listobject(a)) {
  445.         err_badcall();
  446.         return -1;
  447.     }
  448.     return list_ass_slice((listobject *)a, ilow, ihigh, v);
  449. }
  450.  
  451. static int
  452. list_ass_item(a, i, v)
  453.     listobject *a;
  454.     int i;
  455.     object *v;
  456. {
  457.     if (i < 0 || i >= a->ob_size) {
  458.         err_setstr(IndexError, "list assignment index out of range");
  459.         return -1;
  460.     }
  461.     if (v == NULL)
  462.         return list_ass_slice(a, i, i+1, v);
  463.     INCREF(v);
  464.     DECREF(a->ob_item[i]);
  465.     a->ob_item[i] = v;
  466.     return 0;
  467. }
  468.  
  469. static object *
  470. ins(self, where, v)
  471.     listobject *self;
  472.     int where;
  473.     object *v;
  474. {
  475.     if (ins1(self, where, v) != 0)
  476.         return NULL;
  477.     INCREF(None);
  478.     return None;
  479. }
  480.  
  481. static object *
  482. listinsert(self, args)
  483.     listobject *self;
  484.     object *args;
  485. {
  486.     int i;
  487.     object *v;
  488.     if (!getargs(args, "(iO)", &i, &v))
  489.         return NULL;
  490.     return ins(self, i, v);
  491. }
  492.  
  493. static object *
  494. listappend(self, args)
  495.     listobject *self;
  496.     object *args;
  497. {
  498.     object *v;
  499.     if (!getargs(args, "O", &v))
  500.         return NULL;
  501.     return ins(self, (int) self->ob_size, v);
  502. }
  503.  
  504. static object *comparefunc;
  505.  
  506. static int
  507. cmp(v, w)
  508.     const ANY *v, *w;
  509. {
  510.     object *t, *res;
  511.     long i;
  512.  
  513.     if (err_occurred())
  514.         return 0;
  515.  
  516.     if (comparefunc == NULL)
  517.         return cmpobject(* (object **) v, * (object **) w);
  518.  
  519.     /* Call the user-supplied comparison function */
  520.     t = mkvalue("OO", * (object **) v, * (object **) w);
  521.     if (t == NULL)
  522.         return 0;
  523.     res = call_object(comparefunc, t);
  524.     DECREF(t);
  525.     if (res == NULL)
  526.         return 0;
  527.     if (!is_intobject(res)) {
  528.         err_setstr(TypeError, "comparison function should return int");
  529.         i = 0;
  530.     }
  531.     else {
  532.         i = getintvalue(res);
  533.         if (i < 0)
  534.             i = -1;
  535.         else if (i > 0)
  536.             i = 1;
  537.     }
  538.     DECREF(res);
  539.     return (int) i;
  540. }
  541.  
  542. static object *
  543. listsort(self, args)
  544.     listobject *self;
  545.     object *args;
  546. {
  547.     object *save_comparefunc;
  548.     if (self->ob_size <= 1) {
  549.         INCREF(None);
  550.         return None;
  551.     }
  552.     save_comparefunc = comparefunc;
  553.     comparefunc = args;
  554.     if (comparefunc != NULL) {
  555.         /* Test the comparison function for obvious errors */
  556.         (void) cmp((ANY *)&self->ob_item[0], (ANY *)&self->ob_item[1]);
  557.         if (err_occurred()) {
  558.             comparefunc = save_comparefunc;
  559.             return NULL;
  560.         }
  561.     }
  562.     qsort((char *)self->ob_item,
  563.                 (int) self->ob_size, sizeof(object *), cmp);
  564.     comparefunc = save_comparefunc;
  565.     if (err_occurred())
  566.         return NULL;
  567.     INCREF(None);
  568.     return None;
  569. }
  570.  
  571. static object *
  572. listreverse(self, args)
  573.     listobject *self;
  574.     object *args;
  575. {
  576.     register object **p, **q;
  577.     register object *tmp;
  578.     
  579.     if (args != NULL) {
  580.         err_badarg();
  581.         return NULL;
  582.     }
  583.  
  584.     if (self->ob_size > 1) {
  585.         for (p = self->ob_item, q = self->ob_item + self->ob_size - 1;
  586.                         p < q; p++, q--) {
  587.             tmp = *p;
  588.             *p = *q;
  589.             *q = tmp;
  590.         }
  591.     }
  592.     
  593.     INCREF(None);
  594.     return None;
  595. }
  596.  
  597. int
  598. sortlist(v)
  599.     object *v;
  600. {
  601.     if (v == NULL || !is_listobject(v)) {
  602.         err_badcall();
  603.         return -1;
  604.     }
  605.     v = listsort((listobject *)v, (object *)NULL);
  606.     if (v == NULL)
  607.         return -1;
  608.     DECREF(v);
  609.     return 0;
  610. }
  611.  
  612. object *
  613. listtuple(v)
  614.     object *v;
  615. {
  616.     object *w;
  617.     object **p;
  618.     int n;
  619.     if (v == NULL || !is_listobject(v)) {
  620.         err_badcall();
  621.         return NULL;
  622.     }
  623.     n = ((listobject *)v)->ob_size;
  624.     w = newtupleobject(n);
  625.     if (w == NULL)
  626.         return NULL;
  627.     p = ((tupleobject *)w)->ob_item;
  628.     memcpy((ANY *)p,
  629.            (ANY *)((listobject *)v)->ob_item,
  630.            n*sizeof(object *));
  631.     while (--n >= 0) {
  632.         INCREF(*p);
  633.         p++;
  634.     }
  635.     return w;
  636. }
  637.  
  638. static object *
  639. listindex(self, args)
  640.     listobject *self;
  641.     object *args;
  642. {
  643.     int i;
  644.     
  645.     if (args == NULL) {
  646.         err_badarg();
  647.         return NULL;
  648.     }
  649.     for (i = 0; i < self->ob_size; i++) {
  650.         if (cmpobject(self->ob_item[i], args) == 0)
  651.             return newintobject((long)i);
  652.     }
  653.     err_setstr(ValueError, "list.index(x): x not in list");
  654.     return NULL;
  655. }
  656.  
  657. static object *
  658. listcount(self, args)
  659.     listobject *self;
  660.     object *args;
  661. {
  662.     int count = 0;
  663.     int i;
  664.     
  665.     if (args == NULL) {
  666.         err_badarg();
  667.         return NULL;
  668.     }
  669.     for (i = 0; i < self->ob_size; i++) {
  670.         if (cmpobject(self->ob_item[i], args) == 0)
  671.             count++;
  672.     }
  673.     return newintobject((long)count);
  674. }
  675.  
  676. static object *
  677. listremove(self, args)
  678.     listobject *self;
  679.     object *args;
  680. {
  681.     int i;
  682.     
  683.     if (args == NULL) {
  684.         err_badarg();
  685.         return NULL;
  686.     }
  687.     for (i = 0; i < self->ob_size; i++) {
  688.         if (cmpobject(self->ob_item[i], args) == 0) {
  689.             if (list_ass_slice(self, i, i+1, (object *)NULL) != 0)
  690.                 return NULL;
  691.             INCREF(None);
  692.             return None;
  693.         }
  694.             
  695.     }
  696.     err_setstr(ValueError, "list.remove(x): x not in list");
  697.     return NULL;
  698. }
  699.  
  700. static struct methodlist list_methods[] = {
  701.     {"append",    (method)listappend},
  702.     {"count",    (method)listcount},
  703.     {"index",    (method)listindex},
  704.     {"insert",    (method)listinsert},
  705.     {"sort",    (method)listsort},
  706.     {"remove",    (method)listremove},
  707.     {"reverse",    (method)listreverse},
  708.     {NULL,        NULL}        /* sentinel */
  709. };
  710.  
  711. static object *
  712. list_getattr(f, name)
  713.     listobject *f;
  714.     char *name;
  715. {
  716.     return findmethod(list_methods, (object *)f, name);
  717. }
  718.  
  719. static sequence_methods list_as_sequence = {
  720.     (inquiry)list_length, /*sq_length*/
  721.     (binaryfunc)list_concat, /*sq_concat*/
  722.     (intargfunc)list_repeat, /*sq_repeat*/
  723.     (intargfunc)list_item, /*sq_item*/
  724.     (intintargfunc)list_slice, /*sq_slice*/
  725.     (intobjargproc)list_ass_item, /*sq_ass_item*/
  726.     (intintobjargproc)list_ass_slice, /*sq_ass_slice*/
  727. };
  728.  
  729. typeobject Listtype = {
  730.     OB_HEAD_INIT(&Typetype)
  731.     0,
  732.     "list",
  733.     sizeof(listobject),
  734.     0,
  735.     (destructor)list_dealloc, /*tp_dealloc*/
  736.     (printfunc)list_print, /*tp_print*/
  737.     (getattrfunc)list_getattr, /*tp_getattr*/
  738.     0,        /*tp_setattr*/
  739.     (cmpfunc)list_compare, /*tp_compare*/
  740.     (reprfunc)list_repr, /*tp_repr*/
  741.     0,        /*tp_as_number*/
  742.     &list_as_sequence,    /*tp_as_sequence*/
  743.     0,        /*tp_as_mapping*/
  744. };
  745.