mpdm_a.c

   1 /*
   2
   3     MPDM - Minimum Profit Data Manager
   4     Copyright (C) 2003/2007 Angel Ortega <angel@triptico.com>
   5
   6     mpdm_a.c - Array management
   7
   8     This program is free software; you can redistribute it and/or
   9     modify it under the terms of the GNU General Public License
  10     as published by the Free Software Foundation; either version 2
  11     of the License, or (at your option) any later version.
  12
  13     This program is distributed in the hope that it will be useful,
  14     but WITHOUT ANY WARRANTY; without even the implied warranty of
  15     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16     GNU General Public License for more details.
  17
  18     You should have received a copy of the GNU General Public License
  19     along with this program; if not, write to the Free Software
  20     Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  21
  22     http://www.triptico.com
  23
  24 */
  25
  26 #include "config.h"
  27
  28 #include <stdio.h>
  29 #include <stdlib.h>
  30 #include <string.h>
  31 #include <wchar.h>
  32
  33 #include "mpdm.h"
  34
  35
  36 /*******************
  37         Data
  38 ********************/
  39
  40 /* sorting callback code */
  41 static mpdm_t sort_cb = NULL;
  42
  43
  44 /*******************
  45         Code
  46 ********************/
  47
  48 mpdm_t mpdm_new_a(int flags, int size)
  49 /* creates a new array value */
  50 {
  51         mpdm_t v;
  52
  53         /* creates and expands */
  54         if((v = mpdm_new(flags|MPDM_MULTIPLE, NULL, 0)) != NULL)
  55                 mpdm_expand(v, 0, size);
  56
  57         return(v);
  58 }
  59
  60
  61 static int wrap_offset(mpdm_t a, int offset)
  62 /* manages negative offsets */
  63 {
  64         if(offset < 0) offset = mpdm_size(a) + offset;
  65
  66         return(offset);
  67 }
  68
  69
  70 mpdm_t mpdm_aclone(mpdm_t v)
  71 /* clones a multiple value */
  72 {
  73         mpdm_t w;
  74         int n;
  75
  76         /* creates a similar value */
  77         w = mpdm_new_a(v->flags, v->size);
  78
  79         /* fills each element with duplicates of the original */
  80         for(n=0;n < w->size;n++)
  81                 mpdm_aset(w, mpdm_clone(mpdm_aget(v, n)), n);
  82
  83         return(w);
  84 }
  85
  86
  87 /* interface */
  88
  89 /**
  90  * mpdm_expand - Expands an array.
  91  * @a: the array
  92  * @offset: insertion offset
  93  * @num: number of elements to insert
  94  *
  95  * Expands an array value, inserting @num elements (initialized
  96  * to NULL) at the specified @offset.
  97  * [Arrays]
  98  */
  99 mpdm_t mpdm_expand(mpdm_t a, int offset, int num)
 100 {
 101         int n;
 102         mpdm_t * p;
 103
 104         /* sanity checks */
 105         if(num <= 0) return(a);
 106
 107         /* add size */
 108         a->size += num;
 109
 110         /* expand, or fail */
 111         if((p = (mpdm_t *) realloc(a->data, a->size * sizeof(mpdm_t))) == NULL)
 112                 return(NULL);
 113
 114         /* moves up from top of the array */
 115         for(n = a->size - 1;n >= offset + num;n--)
 116                 p[n] = p[n - num];
 117
 118         /* fills the new space with blanks */
 119         for(;n >= offset;n--)
 120                 p[n] = NULL;
 121
 122         a->data = p;
 123
 124         return(a);
 125 }
 126
 127
 128 /**
 129  * mpdm_collapse - Collapses an array.
 130  * @a: the array
 131  * @offset: deletion offset
 132  * @num: number of elements to collapse
 133  *
 134  * Collapses an array value, deleting @num elements at
 135  * the specified @offset.
 136  * [Arrays]
 137  */
 138 mpdm_t mpdm_collapse(mpdm_t a, int offset, int num)
 139 {
 140         int n;
 141         mpdm_t * p;
 142
 143         /* sanity checks */
 144         if(num <= 0) return(a);
 145
 146         /* don't try to delete beyond the limit */
 147         if(offset + num > a->size)
 148                 num = a->size - offset;
 149
 150         p = (mpdm_t *) a->data;
 151
 152         /* unrefs the about-to-be-deleted elements */
 153         for(n = offset;n < offset + num;n++)
 154                 mpdm_unref(p[n]);
 155
 156         /* array is now shorter */
 157         a->size -= num;
 158
 159         /* moves down the elements */
 160         for(n = offset;n < a->size;n++)
 161                 p[n] = p[n + num];
 162
 163         /* finally shrinks the memory block */
 164         if((a->data = realloc(p, a->size * sizeof(mpdm_t))) == NULL)
 165                 return(NULL);
 166
 167         return(a);
 168 }
 169
 170
 171 /**
 172  * mpdm_aset - Sets the value of an array's element.
 173  * @a: the array
 174  * @e: the element to be assigned
 175  * @offset: the subscript of the element
 176  *
 177  * Sets the element of the array @a at @offset to be the @e value.
 178  * Returns the previous element.
 179  * [Arrays]
 180  */
 181 mpdm_t mpdm_aset(mpdm_t a, mpdm_t e, int offset)
 182 {
 183         mpdm_t v;
 184         mpdm_t * p;
 185
 186         offset = wrap_offset(a, offset);
 187
 188         /* boundary checks */
 189         if(offset < 0)
 190                 return(NULL);
 191
 192         /* if the array is shorter than offset, expand to make room for it */
 193         if(offset >= mpdm_size(a))
 194                 if(mpdm_expand(a, mpdm_size(a), offset - mpdm_size(a) + 1) == NULL)
 195                         return(NULL);
 196
 197         p = (mpdm_t *)a->data;
 198
 199         /* assigns and references */
 200         v = mpdm_unref(p[offset]);
 201         p[offset] = mpdm_ref(e);
 202
 203         return(v);
 204 }
 205
 206
 207 /**
 208  * mpdm_aget - Gets an element of an array.
 209  * @a: the array
 210  * @offset: the subscript of the element
 211  *
 212  * Returns the element at @offset of the array @a.
 213  * [Arrays]
 214  */
 215 mpdm_t mpdm_aget(mpdm_t a, int offset)
 216 {
 217         mpdm_t * p;
 218
 219         offset = wrap_offset(a, offset);
 220
 221         /* boundary checks */
 222         if(offset < 0 || offset >= mpdm_size(a))
 223                 return(NULL);
 224
 225         p = (mpdm_t *) a->data;
 226
 227         return(p[offset]);
 228 }
 229
 230
 231 /**
 232  * mpdm_ins - Insert an element in an array.
 233  * @a: the array
 234  * @e: the element to be inserted
 235  * @offset: subscript where the element is going to be inserted
 236  *
 237  * Inserts the @e value in the @a array at @offset.
 238  * Further elements are pushed up, so the array increases its size
 239  * by one. Returns the inserted element.
 240  * [Arrays]
 241  */
 242 mpdm_t mpdm_ins(mpdm_t a, mpdm_t e, int offset)
 243 {
 244         offset = wrap_offset(a, offset);
 245
 246         /* open room and set value */
 247         if(mpdm_expand(a, offset, 1))
 248                 mpdm_aset(a, e, offset);
 249
 250         return(e);
 251 }
 252
 253
 254 /**
 255  * mpdm_adel - Deletes an element of an array.
 256  * @a: the array
 257  * @offset: subscript of the element to be deleted
 258  *
 259  * Deletes the element at @offset of the @a array. The array
 260  * is shrinked by one. If @offset is negative, is counted from
 261  * the end of the array (so a value of -1 means delete the
 262  * last element of the array).
 263  *
 264  * Returns the deleted element.
 265  * [Arrays]
 266  */
 267 mpdm_t mpdm_adel(mpdm_t a, int offset)
 268 {
 269         mpdm_t v;
 270
 271         if(a == NULL || mpdm_size(a) == 0)
 272                 return(NULL);
 273
 274         offset = wrap_offset(a, offset);
 275
 276         /* gets current value */
 277         v = mpdm_aget(a, offset);
 278
 279         /* shrinks the array */
 280         mpdm_collapse(a, offset, 1);
 281
 282         return(v);
 283 }
 284
 285
 286 /**
 287  * mpdm_shift - Extracts the first element of an array.
 288  * @a: the array
 289  *
 290  * Extracts the first element of the array. The array
 291  * is shrinked by one.
 292  *
 293  * Returns the deleted element.
 294  * [Arrays]
 295  */
 296 mpdm_t mpdm_shift(mpdm_t a)
 297 {
 298         return(mpdm_adel(a, 0));
 299 }
 300
 301
 302 /**
 303  * mpdm_push - Pushes a value into an array.
 304  * @a: the array
 305  * @e: the value
 306  *
 307  * Pushes a value into an array (i.e. inserts at the end).
 308  * [Arrays]
 309  */
 310 mpdm_t mpdm_push(mpdm_t a, mpdm_t e)
 311 {
 312         /* inserts at the end */
 313         return(mpdm_ins(a, e, mpdm_size(a)));
 314 }
 315
 316
 317 /**
 318  * mpdm_pop - Pops a value from an array.
 319  * @a: the array
 320  *
 321  * Pops a value from the array (i.e. deletes from the end
 322  * and returns it).
 323  * [Arrays]
 324  */
 325 mpdm_t mpdm_pop(mpdm_t a)
 326 {
 327         /* deletes from the end */
 328         return(mpdm_adel(a, -1));
 329 }
 330
 331
 332 /**
 333  * mpdm_queue - Implements a queue in an array.
 334  * @a: the array
 335  * @e: the element to be pushed
 336  * @size: maximum size of array
 337  *
 338  * Pushes the @e element into the @a array. If the array already has
 339  * @size elements, the first (oldest) element is deleted from the
 340  * queue and returned.
 341  *
 342  * Returns the deleted element, or NULL if the array doesn't have
 343  * @size elements yet.
 344  * [Arrays]
 345  */
 346 mpdm_t mpdm_queue(mpdm_t a, mpdm_t e, int size)
 347 {
 348         mpdm_t v=NULL;
 349
 350         /* zero size is nonsense */
 351         if(size == 0)
 352                 return(NULL);
 353
 354         /* loop until a has the desired size */
 355         while(mpdm_size(a) > size - 1)
 356                 v = mpdm_shift(a);
 357
 358         mpdm_push(a, e);
 359         return(v);
 360 }
 361
 362
 363 /**
 364  * mpdm_seek - Seeks a value in an array (sequential).
 365  * @a: the array
 366  * @k: the key
 367  * @step: number of elements to step
 368  *
 369  * Seeks sequentially the value @k in the @a array in
 370  * increments of @step. A complete search should use a step of 1.
 371  * Returns the offset of the element if found, or -1 otherwise.
 372  * [Arrays]
 373  */
 374 int mpdm_seek(mpdm_t a, mpdm_t k, int step)
 375 {
 376         int n;
 377
 378         /* avoid stupid steps */
 379         if(step <= 0) step = 1;
 380
 381         for(n=0;n < mpdm_size(a);n += step)
 382         {
 383                 mpdm_t v = mpdm_aget(a, n);
 384
 385                 if(mpdm_cmp(v, k) == 0)
 386                         return(n);
 387         }
 388
 389         return(-1);
 390 }
 391
 392
 393 /**
 394  * mpdm_seek_s - Seeks a value in an array (sequential, string version).
 395  * @a: the array
 396  * @k: the key
 397  * @step: number of elements to step
 398  *
 399  * Seeks sequentially the value @k in the @a array in
 400  * increments of @step. A complete search should use a step of 1.
 401  * Returns the offset of the element if found, or -1 otherwise.
 402  * [Arrays]
 403  */
 404 int mpdm_seek_s(mpdm_t a, wchar_t * k, int step)
 405 {
 406         return(mpdm_seek(a, MPDM_LS(k), step));
 407 }
 408
 409
 410 /**
 411  * mpdm_bseek - Seeks a value in an array (binary).
 412  * @a: the ordered array
 413  * @k: the key
 414  * @step: number of elements to step
 415  * @pos: the position where the element should be, if it's not found
 416  *
 417  * Seeks the value @k in the @a array in increments of @step.
 418  * The array should be sorted to work correctly. A complete search
 419  * should use a step of 1.
 420  *
 421  * If the element is found, returns the offset of the element
 422  * as a positive number; otherwise, -1 is returned and the position
 423  * where the element should be is stored in @pos. You can set @pos
 424  * to NULL if you don't mind.
 425  * [Arrays]
 426  */
 427 int mpdm_bseek(mpdm_t a, mpdm_t k, int step, int * pos)
 428 {
 429         int b, t, n, c;
 430
 431         /* avoid stupid steps */
 432         if(step <= 0) step = 1;
 433
 434         b=0; t = (mpdm_size(a) - 1) / step;
 435
 436         while(t >= b)
 437         {
 438                 mpdm_t v;
 439
 440                 n = (b + t) / 2;
 441                 if((v = mpdm_aget(a, n * step)) == NULL)
 442                         break;
 443
 444                 c = mpdm_cmp(k, v);
 445
 446                 if(c == 0)
 447                         return(n * step);
 448                 else
 449                 if(c < 0)
 450                         t = n - 1;
 451                 else
 452                         b = n + 1;
 453         }
 454
 455         if(pos != NULL) *pos = b * step;
 456         return(-1);
 457 }
 458
 459
 460 /**
 461  * mpdm_bseek_s - Seeks a value in an array (binary, string version).
 462  * @a: the ordered array
 463  * @k: the key
 464  * @step: number of elements to step
 465  * @pos: the position where the element should be, if it's not found
 466  *
 467  * Seeks the value @k in the @a array in increments of @step.
 468  * The array should be sorted to work correctly. A complete search
 469  * should use a step of 1.
 470  *
 471  * If the element is found, returns the offset of the element
 472  * as a positive number; otherwise, -1 is returned and the position
 473  * where the element should be is stored in @pos. You can set @pos
 474  * to NULL if you don't mind.
 475  * [Arrays]
 476  */
 477 int mpdm_bseek_s(mpdm_t a, wchar_t * k, int step, int * pos)
 478 {
 479         return(mpdm_bseek(a, MPDM_LS(k), step, pos));
 480 }
 481
 482
 483 static int sort_cmp(const void * s1, const void * s2)
 484 /* qsort help function */
 485 {
 486         int ret = 0;
 487
 488         /* if callback is NULL, use basic value comparisons */
 489         if(sort_cb == NULL)
 490                 ret = mpdm_cmp(*(mpdm_t *)s1, *(mpdm_t *)s2);
 491         else
 492         {
 493                 /* executes the callback and converts to integer */
 494                 ret = mpdm_ival(mpdm_exec_2(sort_cb,
 495                         (mpdm_t) * ((mpdm_t *)s1),
 496                         (mpdm_t) * ((mpdm_t *)s2)));
 497         }
 498
 499         return(ret);
 500 }
 501
 502
 503 /**
 504  * mpdm_sort - Sorts an array.
 505  * @a: the array
 506  * @step: increment step
 507  *
 508  * Sorts the array. @step is the number of elements to group together.
 509  *
 510  * Returns the sorted array (the original one is left untouched).
 511  * [Arrays]
 512  */
 513 mpdm_t mpdm_sort(mpdm_t a, int step)
 514 {
 515         return(mpdm_sort_cb(a, step, NULL));
 516 }
 517
 518
 519 /**
 520  * mpdm_sort_cb - Sorts an array with a special sorting function.
 521  * @a: the array
 522  * @step: increment step
 523  * @asort_cb: sorting function
 524  *
 525  * Sorts the array. @step is the number of elements to group together.
 526  * For each pair of elements being sorted, the executable mpdm_t value
 527  * @sort_cb is called with an array containing the two elements as
 528  * argument. It must return a signed numerical mpdm_t value indicating
 529  * the sorting order.
 530  *
 531  * Returns the sorted array (the original one is left untouched).
 532  * [Arrays]
 533  */
 534 mpdm_t mpdm_sort_cb(mpdm_t a, int step, mpdm_t cb)
 535 {
 536         if(a == NULL) return(NULL);
 537
 538         /* creates a copy to be sorted */
 539         a = mpdm_clone(a);
 540
 541         sort_cb = cb;
 542
 543         /* references the array and the code, as the latter
 544            can include anything (including sweeping) */
 545         mpdm_ref(a);
 546         mpdm_ref(sort_cb);
 547
 548         qsort(a->data, mpdm_size(a) / step,
 549                 sizeof(mpdm_t) * step, sort_cmp);
 550
 551         /* unreferences */
 552         mpdm_unref(sort_cb);
 553         mpdm_unref(a);
 554
 555         sort_cb = NULL;
 556
 557         return(a);
 558 }
 559
 560
 561 /**
 562  * mpdm_split - Separates a string into an array of pieces.
 563  * @s: the separator
 564  * @v: the value to be separated
 565  *
 566  * Separates the @v string value into an array of pieces, using @s
 567  * as a separator.
 568  *
 569  * If the separator is NULL, the string is splitted by characters.
 570  *
 571  * If the string does not contain the separator, an array holding
 572  * the complete string is returned.
 573  * [Arrays]
 574  * [Strings]
 575  */
 576 mpdm_t mpdm_split(mpdm_t s, mpdm_t v)
 577 {
 578         mpdm_t w;
 579         wchar_t * ptr;
 580         wchar_t * sptr;
 581
 582         /* nothing to split? */
 583         if(v == NULL) return(NULL);
 584
 585         w = MPDM_A(0);
 586
 587         /* NULL separator? special case: split string in characters */
 588         if(s == NULL)
 589         {
 590                 for(ptr = mpdm_string(v);ptr && *ptr != '\0';ptr++)
 591                         mpdm_push(w, MPDM_NS(ptr, 1));
 592
 593                 return(w);
 594         }
 595
 596         /* travels the string finding separators and creating new values */
 597         for(ptr = v->data;
 598                 *ptr != L'\0' && (sptr = wcsstr(ptr, s->data)) != NULL;
 599                 ptr = sptr + mpdm_size(s))
 600                 mpdm_push(w, MPDM_NS(ptr, sptr - ptr));
 601
 602         /* add last part */
 603         mpdm_push(w, MPDM_S(ptr));
 604
 605         return(w);
 606 }
 607
 608
 609 /**
 610  * mpdm_join - Joins all elements of an array into one.
 611  * @s: joiner string
 612  * @a: array to be joined
 613  *
 614  * Joins all elements from @a into one string, using @s as a glue.
 615  * [Arrays]
 616  * [Strings]
 617  */
 618 mpdm_t mpdm_join(mpdm_t s, mpdm_t a)
 619 {
 620         int n;
 621         wchar_t * ptr = NULL;
 622         int l = 0;
 623
 624         /* adds the first string */
 625         ptr = mpdm_pokev(ptr, &l, mpdm_aget(a, 0));
 626
 627         for(n = 1;n < mpdm_size(a);n++)
 628         {
 629                 /* add separator */
 630                 ptr = mpdm_pokev(ptr, &l, s);
 631
 632                 /* add element */
 633                 ptr = mpdm_pokev(ptr, &l, mpdm_aget(a, n));
 634         }
 635
 636         if(ptr == NULL)
 637                 return(NULL);
 638
 639         ptr = mpdm_poke(ptr, &l, L"", 1, sizeof(wchar_t));
 640         return(MPDM_ENS(ptr, l - 1));
 641 }