MolLib/IntGroup.c

   1 /*
   2    IntGroup.c
   3    Created by Toshi Nagata, 2000.12.3.
   4
   5    Copyright (c) 2000-2008 Toshi Nagata.
   6
   7  This program is free software; you can redistribute it and/or modify
   8  it under the terms of the GNU General Public License as published by
   9  the Free Software Foundation version 2 of the License.
  10
  11  This program is distributed in the hope that it will be useful,
  12  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  GNU General Public License for more details.
  15  */
  16
  17 #include "IntGroup.h"
  18
  19 #include <stdio.h>              /*  for fprintf() in IntGroupDump()  */
  20 #include <stdlib.h>             /*  for malloc(), realloc(), and free()  */
  21 #include <string.h>             /*  for memmove()  */
  22 #include <limits.h>             /*  for INT_MAX  */
  23 #include <stdarg.h>
  24
  25 #ifdef __MWERKS__
  26 #pragma mark ====== Private definitions ======
  27 #endif
  28
  29 struct IntGroup {
  30         int                     refCount;       /*  the reference count  */
  31         int                     num;            /*  the number of entries  */
  32         int *           entries;        /*  entries[2*n]: begin point, entries[2*n+1]: end point */
  33 };
  34
  35 typedef short IntGroupOperation;
  36 enum {
  37         kIntGroupIntersect,
  38         kIntGroupConvolute,
  39         kIntGroupDeconvolute
  40 };
  41
  42 #ifdef __MWERKS__
  43 #pragma mark ====== Private (static) functions ======
  44 #endif
  45
  46 /* --------------------------------------
  47         ･ IntGroupCalcRequiredStorage
  48    -------------------------------------- */
  49 static int
  50 IntGroupCalcRequiredStorage(int inLength)
  51 {
  52         return ((inLength * 2 + 3) / 4) * 4 * sizeof(int);
  53 }
  54
  55 /* --------------------------------------
  56         ･ IntGroupAdjustStorage
  57    -------------------------------------- */
  58 static IntGroupStatus
  59 IntGroupAdjustStorage(IntGroup *psRef, int inLength)
  60 {
  61         int theOldSize, theNewSize;
  62
  63         theOldSize = IntGroupCalcRequiredStorage(psRef->num);
  64         theNewSize = IntGroupCalcRequiredStorage(inLength);
  65         if (theOldSize == theNewSize)
  66                 return 0;
  67
  68         if (theOldSize == 0 && theNewSize != 0) {
  69                 psRef->entries = (int *)malloc(theNewSize);
  70                 if (psRef->entries == NULL)
  71                         return kIntGroupStatusOutOfMemory;
  72         } else if (theOldSize != 0 && theNewSize == 0) {
  73                 free(psRef->entries);
  74                 psRef->entries = NULL;
  75         } else {
  76                 int *ptr = (int *)realloc(psRef->entries, theNewSize);
  77                 if (ptr == NULL)
  78                         return kIntGroupStatusOutOfMemory;
  79                 psRef->entries = ptr;
  80         }
  81         return kIntGroupStatusNoError;
  82 }
  83
  84 /* --------------------------------------
  85         ･ IntGroupInsertAnEntry
  86    -------------------------------------- */
  87 static IntGroupStatus
  88 IntGroupInsertAnEntry(IntGroup *psRef, int inIndex, int inBeginPt, int inEndPt)
  89 {
  90         IntGroupStatus result;
  91         int moveAmount;
  92         result = IntGroupAdjustStorage(psRef, psRef->num + 1);
  93         if (result != kIntGroupStatusNoError)
  94                 return result;  /* out of memory */
  95         moveAmount = (psRef->num - inIndex) * 2 * sizeof(int);
  96         if (moveAmount > 0)
  97                 memmove(&(psRef->entries[inIndex * 2 + 2]), &(psRef->entries[inIndex * 2]), moveAmount);
  98         psRef->entries[inIndex * 2] = inBeginPt;
  99         psRef->entries[inIndex * 2 + 1] = inEndPt;
 100         psRef->num++;
 101         return kIntGroupStatusNoError;
 102 }
 103
 104 /* --------------------------------------
 105         ･ IntGroupDeleteEntries
 106    -------------------------------------- */
 107 static IntGroupStatus
 108 IntGroupDeleteEntries(IntGroup *psRef, int inStartIndex, int inEndIndex)
 109 {
 110         IntGroupStatus result;
 111         int moveAmount;
 112         if (inStartIndex > inEndIndex)
 113                 return 0;       /*  do nothing  */
 114         moveAmount = sizeof(int) * 2 * (psRef->num - inEndIndex - 1);
 115         if (moveAmount > 0)
 116                 memmove(&(psRef->entries[inStartIndex * 2]), &(psRef->entries[inEndIndex * 2 + 2]), moveAmount);
 117         result = IntGroupAdjustStorage(psRef, psRef->num - (inEndIndex - inStartIndex + 1));
 118         if (result == kIntGroupStatusNoError)
 119                 psRef->num -= inEndIndex - inStartIndex + 1;
 120         return result;
 121 }
 122
 123 #ifdef __MWERKS__
 124 #pragma mark ====== New/Retain/Release ======
 125 #endif
 126
 127 /* --------------------------------------
 128         ･ IntGroupNew
 129    -------------------------------------- */
 130 IntGroup *
 131 IntGroupNew(void)
 132 {
 133         IntGroup *psRef = (IntGroup *)malloc(sizeof(*psRef));
 134         if (psRef == NULL)
 135                 return NULL;    /* out of memory */
 136         psRef->entries = NULL;
 137         psRef->num = 0;
 138         psRef->refCount = 1;
 139         return psRef;
 140 }
 141
 142 /* --------------------------------------
 143         ･ IntGroupNewFromIntGroup
 144    -------------------------------------- */
 145 IntGroup *
 146 IntGroupNewFromIntGroup(const IntGroup *src)
 147 {
 148         IntGroup *dst = IntGroupNew();
 149         if (dst == NULL)
 150                 return NULL;
 151         if (IntGroupCopy(dst, src) != kIntGroupStatusNoError) {
 152                 IntGroupRelease(dst);
 153                 return NULL;
 154         }
 155         return dst;
 156 }
 157
 158 /* --------------------------------------
 159         ･ IntGroupNewWithPoints
 160    -------------------------------------- */
 161 IntGroup *
 162 IntGroupNewWithPoints(int start, ...)
 163 {
 164         va_list ap;
 165         int length;
 166         IntGroup *psRef = IntGroupNew();
 167         if (psRef == NULL)
 168                 return NULL;
 169         va_start(ap, start);
 170         while (start >= 0) {
 171                 length = va_arg(ap, int);
 172                 if (IntGroupAdd(psRef, start, length) != 0) {
 173                         IntGroupRelease(psRef);
 174                         return NULL;
 175                 }
 176                 start = va_arg(ap, int);
 177         }
 178         va_end(ap);
 179         return psRef;
 180 }
 181
 182 /* --------------------------------------
 183         ･ IntGroupRetain
 184    -------------------------------------- */
 185 void
 186 IntGroupRetain(IntGroup *psRef)
 187 {
 188         if (psRef == NULL)
 189                 return;
 190         psRef->refCount++;
 191 }
 192
 193 /* --------------------------------------
 194         ･ IntGroupRelease
 195    -------------------------------------- */
 196 void
 197 IntGroupRelease(IntGroup *psRef)
 198 {
 199         if (psRef == NULL)
 200                 return;
 201         if (--psRef->refCount == 0) {
 202                 IntGroupClear(psRef);
 203                 free(psRef);
 204         }
 205 }
 206
 207 #ifdef __MWERKS__
 208 #pragma mark ====== Clear/Copy ======
 209 #endif
 210 /* --------------------------------------
 211         ･ IntGroupClear
 212    -------------------------------------- */
 213 void
 214 IntGroupClear(IntGroup *psRef)
 215 {
 216         if (psRef == NULL)
 217                 return;
 218         if (psRef->entries != NULL) {
 219                 free(psRef->entries);
 220                 psRef->entries = NULL;
 221         }
 222         psRef->num = 0;
 223 }
 224
 225 /* --------------------------------------
 226         ･ IntGroupCopy
 227    -------------------------------------- */
 228 IntGroupStatus
 229 IntGroupCopy(IntGroup *psRef1, const IntGroup *psRef2)
 230 {
 231         IntGroupStatus sts;
 232         if (psRef1 == NULL || psRef2 == NULL)
 233                 return kIntGroupStatusNoError;
 234         sts = IntGroupAdjustStorage(psRef1, psRef2->num);
 235         if (sts == kIntGroupStatusNoError) {
 236                 memmove(psRef1->entries, psRef2->entries, psRef2->num * 2 * sizeof(int));
 237         psRef1->num = psRef2->num;
 238     }
 239         return sts;
 240 }
 241
 242 #ifdef __MWERKS__
 243 #pragma mark ====== Point Manipulations ======
 244 #endif
 245
 246 /* --------------------------------------
 247         ･ IntGroupLookup
 248    -------------------------------------- */
 249 int
 250 IntGroupLookup(const IntGroup *psRef, int inPoint, int *outIndex)
 251 {
 252         int i;
 253         if (psRef == NULL)
 254                 return 0;
 255         for (i = 0; i < psRef->num; i++) {
 256                 if (inPoint < psRef->entries[i*2]) {
 257                         if (outIndex != NULL)
 258                             *outIndex = i;
 259                         return 0;
 260                 } else if (inPoint < psRef->entries[i*2+1]) {
 261                         if (outIndex != NULL)
 262                             *outIndex = i;
 263                         return 1;
 264                 }
 265         }
 266         if (outIndex != NULL)
 267                 *outIndex = psRef->num;
 268         return 0;
 269 }
 270
 271 /* --------------------------------------
 272         ･ IntGroupIsEqual
 273    -------------------------------------- */
 274 int
 275 IntGroupIsEqual(const IntGroup *psRef1, const IntGroup *psRef2)
 276 {
 277         int i;
 278         if (psRef1 == NULL || psRef2 == NULL)
 279                 return (psRef1 == psRef2);
 280         if (psRef1->num != psRef2->num)
 281                 return 0;
 282         for (i = 0; i < psRef1->num * 2; i++) {
 283                 if (psRef1->entries[i] != psRef2->entries[i])
 284                         return 0;
 285         }
 286         return 1;
 287 }
 288
 289 /* --------------------------------------
 290         ･ IntGroupGetCount
 291    -------------------------------------- */
 292 int
 293 IntGroupGetCount(const IntGroup *psRef)
 294 {
 295         int i, n;
 296         if (psRef == NULL)
 297                 return 0;
 298         n = 0;
 299         for (i = 0; i < psRef->num; i++)
 300                 n += psRef->entries[i*2+1] - psRef->entries[i*2];
 301         return n;
 302 }
 303
 304 /* --------------------------------------
 305         ･ IntGroupGetIntervalCount
 306    -------------------------------------- */
 307 int
 308 IntGroupGetIntervalCount(const IntGroup *psRef)
 309 {
 310         if (psRef == NULL)
 311                 return 0;
 312         return psRef->num;
 313 }
 314
 315 /* --------------------------------------
 316         ･ IntGroupAdd
 317    -------------------------------------- */
 318 IntGroupStatus
 319 IntGroupAdd(IntGroup *psRef, int inStart, int inCount)
 320 {
 321         int theBeginIndex, theEndIndex;
 322         int theBeginFlag, theEndFlag;
 323
 324         if (psRef == NULL)
 325                 return kIntGroupStatusNoError;
 326
 327         /*  inStart, inStart+inCount が位置指定の中でどこにあるか探す  */
 328         theBeginFlag = IntGroupLookup(psRef, inStart, &theBeginIndex);
 329         theEndFlag = IntGroupLookup(psRef, inStart + inCount, &theEndIndex);
 330
 331         if (theBeginFlag) {
 332                 /*  psRef->entries[theBeginIndex*2] <= inStart < psRef->entries[theBeginIndex*2+1]  */
 333                 if (theEndFlag) {
 334                         /*  psRef->entries[theEndIndex*2] <= inStart + inCount
 335                             < psRef->entries[theEndIndex*2+1]  */
 336                         if (theBeginIndex < theEndIndex) {
 337                                 psRef->entries[theBeginIndex*2+1] = psRef->entries[theEndIndex*2+1];
 338                                 return IntGroupDeleteEntries(psRef, theBeginIndex + 1, theEndIndex);
 339                         } else return 0;
 340                 } else {
 341                         /*  psRef->entries[(theEndIndex-1)*2+1] <= inStart + inCount
 342                             < psRef->entries[theEndIndex*2]  */
 343                         psRef->entries[theBeginIndex*2+1] = inStart + inCount;
 344                         return IntGroupDeleteEntries(psRef, theBeginIndex + 1, theEndIndex - 1);
 345                 }
 346         } else {
 347                 /*  psRef->entries[(theBeginIndex-1)*2+1] <= inStart < psRef->entries[theBeginIndex*2]  */
 348                 int thePoint = 0;
 349                 if (theBeginIndex > 0 && psRef->entries[(theBeginIndex-1)*2+1] == inStart) {
 350                         /*  １つ前のブロックとくっついてしまう  */
 351                         theBeginIndex--;
 352                 } else if (theBeginIndex < psRef->num) {
 353                         thePoint = psRef->entries[theBeginIndex*2];     /*  あとで必要かもしれない  */
 354                         psRef->entries[theBeginIndex*2] = inStart;
 355                 }
 356                 if (theEndFlag) {
 357                         /*  psRef->entries[theEndIndex*2] <= inStart + inCount
 358                             < psRef->entries[theEndIndex*2+1]  */
 359                         psRef->entries[theBeginIndex*2+1] = psRef->entries[theEndIndex*2+1];
 360                         return IntGroupDeleteEntries(psRef, theBeginIndex + 1, theEndIndex);
 361                 } else {
 362                         /*  psRef->entries[(theEndIndex-1)*2+1] <= inStart + inCount
 363                             < psRef->entries[theEndIndex*2]  */
 364                         if (theBeginIndex == theEndIndex) {
 365                                 if (theBeginIndex < psRef->num)
 366                                         psRef->entries[theBeginIndex*2] = thePoint;     /*  元に戻す  */
 367                                 return IntGroupInsertAnEntry(psRef, theBeginIndex, inStart, inStart + inCount);
 368                         } else {
 369                                 psRef->entries[theBeginIndex*2+1] = inStart + inCount;
 370                                 return IntGroupDeleteEntries(psRef, theBeginIndex + 1, theEndIndex - 1);
 371                         }
 372                 }
 373         }
 374
 375 }
 376
 377 /* --------------------------------------
 378         ･ IntGroupRemove
 379    -------------------------------------- */
 380 IntGroupStatus
 381 IntGroupRemove(IntGroup *psRef, int inStart, int inCount)
 382 {
 383         int theBeginIndex, theEndIndex;
 384         int theBeginFlag, theEndFlag;
 385
 386         if (psRef == NULL)
 387                 return kIntGroupStatusNoError;
 388
 389         /*  inStart, inStart+inCount が位置指定の中でどこにあるか探す  */
 390         theBeginFlag = IntGroupLookup(psRef, inStart, &theBeginIndex);
 391         theEndFlag = IntGroupLookup(psRef, inStart + inCount, &theEndIndex);
 392
 393         if (theBeginFlag) {
 394                 /*  psRef->entries[theBeginIndex*2] <= inStart < psRef->entries[theBeginIndex*2+1]  */
 395                 int thePoint = psRef->entries[theBeginIndex*2];
 396                 if (theEndFlag) {
 397                         /*  psRef->entries[theEndIndex*2] <= inStart + inCount
 398                             < psRef->entries[theEndIndex*2+1]  */
 399                         psRef->entries[theEndIndex*2] = inStart + inCount;
 400                         if (theBeginIndex == theEndIndex) {
 401                                 if (thePoint == inStart)
 402                                         return 0;
 403                                 else
 404                                         return IntGroupInsertAnEntry(psRef, theBeginIndex, thePoint, inStart);
 405                         } else {
 406                                 if (thePoint == inStart)
 407                                         theBeginIndex--;
 408                                 else
 409                                         psRef->entries[theBeginIndex*2+1] = inStart;
 410                                 return IntGroupDeleteEntries(psRef, theBeginIndex + 1, theEndIndex - 1);
 411                         }
 412                 } else {
 413                         /*  psRef->entries[(theEndIndex-1)*2+1] <= inStart + inCount
 414                             < psRef->entries[theEndIndex*2]  */
 415                         if (thePoint == inStart)
 416                                 theBeginIndex--;
 417                         else
 418                                 psRef->entries[theBeginIndex*2+1] = inStart;
 419                         return IntGroupDeleteEntries(psRef, theBeginIndex + 1, theEndIndex - 1);
 420                 }
 421         } else {
 422                 /*  psRef->entries[(theBeginIndex-1)*2+1] <= inStart < psRef->entries[theBeginIndex*2]  */
 423                 if (theEndFlag) {
 424                         /*  psRef->entries[theEndIndex*2] <= inStart + inCount
 425                             < psRef->entries[theEndIndex*2+1]  */
 426                         psRef->entries[theEndIndex*2] = inStart + inCount;
 427                         return IntGroupDeleteEntries(psRef, theBeginIndex, theEndIndex - 1);
 428                 } else {
 429                         /*  psRef->entries[(theEndIndex-1)*2+1] <= inStart + inCount
 430                             < psRef->entries[theEndIndex*2]  */
 431                         return IntGroupDeleteEntries(psRef, theBeginIndex, theEndIndex - 1);
 432                 }
 433         }
 434 }
 435
 436 /* --------------------------------------
 437         ･ IntGroupReverse
 438    -------------------------------------- */
 439 IntGroupStatus
 440 IntGroupReverse(IntGroup *psRef, int inStart, int inCount)
 441 {
 442         int theBeginIndex, theEndIndex, theIndex;
 443         int theBeginFlag, theEndFlag;
 444         IntGroupStatus result;
 445
 446         if (psRef == NULL)
 447                 return kIntGroupStatusNoError;
 448
 449         /*  inStart, inStart+inCount が位置指定の中でどこにあるか探す  */
 450         theBeginFlag = IntGroupLookup(psRef, inStart, &theBeginIndex);
 451         theEndFlag = IntGroupLookup(psRef, inStart + inCount, &theEndIndex);
 452
 453         if (theBeginFlag) {
 454                 /*  psRef->entries[theBeginIndex*2] <= inStart < psRef->entries[theBeginIndex*2+1]  */
 455                 if (psRef->entries[theBeginIndex*2] < inStart) {
 456                         result = IntGroupInsertAnEntry(psRef, theBeginIndex, psRef->entries[theBeginIndex*2], inStart);
 457                         if (result != 0)
 458                                 return result;
 459                         theBeginIndex++;
 460                         theEndIndex++;
 461                 }
 462         } else {
 463                 /*  psRef->entries[(theBeginIndex-1)*2+1] <= inStart < psRef->entries[theBeginIndex*2]  */
 464                 int thePoint;
 465                 if (theBeginIndex == theEndIndex && !theEndFlag)
 466                         thePoint = inStart + inCount;   /* theBeginIndex == mNumberOfEntries の場合を含む  */
 467                 else
 468                         thePoint = psRef->entries[theBeginIndex*2];
 469                 result = IntGroupInsertAnEntry(psRef, theBeginIndex, inStart, thePoint);
 470                 if (result != 0)
 471                         return result;
 472                 theBeginIndex++;
 473                 theEndIndex++;
 474         }
 475
 476         if (theEndFlag) {
 477                 /*  psRef->entries[theEndIndex*2] <= inStart + inCount
 478                     < psRef->entries[theEndIndex*2+1] */
 479                 for (theIndex = theBeginIndex; theIndex < theEndIndex; theIndex++) {
 480                         psRef->entries[theIndex*2] = psRef->entries[theIndex*2+1];
 481                         psRef->entries[theIndex*2+1] = psRef->entries[(theIndex+1)*2];
 482                 }
 483                 psRef->entries[theEndIndex*2] = inStart + inCount;
 484                 if (theEndIndex > 0 && psRef->entries[(theEndIndex-1)*2+1] == inStart + inCount) {
 485                         /*  １つ前のブロックとくっついてしまう  */
 486                         psRef->entries[(theEndIndex-1)*2+1] = psRef->entries[theEndIndex*2+1];
 487                         return IntGroupDeleteEntries(psRef, theEndIndex, theEndIndex);
 488                 }
 489         } else {
 490                 /*  psRef->entries[(theEndIndex-1)*2+1] <= inStart + inCount
 491                     < psRef->entries[theEndIndex*2]  */
 492                 for (theIndex = theBeginIndex; theIndex < theEndIndex - 1; theIndex++) {
 493                         psRef->entries[theIndex*2] = psRef->entries[theIndex*2+1];
 494                         psRef->entries[theIndex*2+1] = psRef->entries[(theIndex+1)*2];
 495                 }
 496                 if (theIndex == theEndIndex - 1) {
 497                         if (psRef->entries[theIndex*2+1] == inStart + inCount)
 498                                 return IntGroupDeleteEntries(psRef, theIndex, theIndex);
 499                         else {
 500                                 psRef->entries[theIndex*2] = psRef->entries[theIndex*2+1];
 501                                 psRef->entries[theIndex*2+1] = inStart + inCount;
 502                         }
 503                 }
 504         }
 505         return 0;
 506 }
 507
 508 /* --------------------------------------
 509  ･ IntGroupAddIntGroup
 510  -------------------------------------- */
 511 IntGroupStatus
 512 IntGroupAddIntGroup(IntGroup *psRef1, const IntGroup *psRef2)
 513 {
 514         int i, n1, n2, result;
 515         if (psRef1 == NULL || psRef2 == NULL)
 516                 return 0;
 517         for (i = 0; (n1 = IntGroupGetStartPoint(psRef2, i)) >= 0; i++) {
 518                 n2 = IntGroupGetInterval(psRef2, i);
 519                 if ((result = IntGroupAdd(psRef1, n1, n2)) != 0)
 520                         return result;
 521         }
 522         return 0;
 523 }
 524
 525 /* --------------------------------------
 526  ･ IntGroupRemoveIntGroup
 527  -------------------------------------- */
 528 IntGroupStatus
 529 IntGroupRemoveIntGroup(IntGroup *psRef1, const IntGroup *psRef2)
 530 {
 531         int i, n1, n2, result;
 532         if (psRef1 == NULL || psRef2 == NULL)
 533                 return 0;
 534         for (i = 0; (n1 = IntGroupGetStartPoint(psRef2, i)) >= 0; i++) {
 535                 n2 = IntGroupGetInterval(psRef2, i);
 536                 if ((result = IntGroupRemove(psRef1, n1, n2)) != 0)
 537                         return result;
 538         }
 539         return 0;
 540 }
 541
 542 /* --------------------------------------
 543  ･ IntGroupReverseIntGroup
 544  -------------------------------------- */
 545 IntGroupStatus
 546 IntGroupReverseIntGroup(IntGroup *psRef1, const IntGroup *psRef2)
 547 {
 548         int i, n1, n2, result;
 549         if (psRef1 == NULL || psRef2 == NULL)
 550                 return 0;
 551         for (i = 0; (n1 = IntGroupGetStartPoint(psRef2, i)) >= 0; i++) {
 552                 n2 = IntGroupGetInterval(psRef2, i);
 553                 if ((result = IntGroupReverse(psRef1, n1, n2)) != 0)
 554                         return result;
 555         }
 556         return 0;
 557 }
 558
 559 /* --------------------------------------
 560         ･ IntGroupGetStartPoint
 561    -------------------------------------- */
 562 int
 563 IntGroupGetStartPoint(const IntGroup *psRef, int inIndex)
 564 {
 565         if (psRef == NULL || inIndex < 0 || inIndex >= psRef->num)
 566                 return -1;
 567         else return psRef->entries[inIndex*2];
 568 }
 569
 570 /* --------------------------------------
 571         ･ IntGroupGetEndPoint
 572    -------------------------------------- */
 573 int
 574 IntGroupGetEndPoint(const IntGroup *psRef, int inIndex)
 575 {
 576         if (psRef == NULL || inIndex < 0 || inIndex >= psRef->num)
 577                 return -1;
 578         else return psRef->entries[inIndex*2+1];
 579 }
 580
 581 /* --------------------------------------
 582         ･ IntGroupGetInterval
 583    -------------------------------------- */
 584 int
 585 IntGroupGetInterval(const IntGroup *psRef, int inIndex)
 586 {
 587         if (psRef == NULL || inIndex < 0 || inIndex >= psRef->num)
 588                 return -1;
 589         else return psRef->entries[inIndex*2+1] - psRef->entries[inIndex*2];
 590 }
 591
 592 /* --------------------------------------
 593         ･ IntGroupGetNthPoint
 594    -------------------------------------- */
 595 int
 596 IntGroupGetNthPoint(const IntGroup *psRef, int inCount)
 597 {
 598         int i, n, dn;
 599         if (psRef == NULL || inCount < 0)
 600                 return -1;
 601         n = 0;
 602         for (i = 0; i < psRef->num; i++) {
 603                 dn = psRef->entries[i*2+1] - psRef->entries[i*2];
 604                 if (inCount < n + dn) {
 605                         /*  The inCount-th point is in this interval  */
 606                         return psRef->entries[i*2] + inCount - n;
 607                 }
 608                 n += dn;
 609         }
 610         /*  No such point  */
 611         return -1;
 612 }
 613
 614 /* --------------------------------------
 615         ･ IntGroupLookupPoint
 616    -------------------------------------- */
 617 int
 618 IntGroupLookupPoint(const IntGroup *psRef, int inPoint)
 619 {
 620         int i, n;
 621         if (psRef == NULL || inPoint < 0)
 622                 return -1;
 623         n = 0;
 624         for (i = 0; i < psRef->num; i++) {
 625                 if (inPoint >= psRef->entries[i*2] && inPoint < psRef->entries[i*2+1]) {
 626                         return n + inPoint - psRef->entries[i*2];
 627                 }
 628                 n += psRef->entries[i*2+1] - psRef->entries[i*2];
 629         }
 630         /*  No such point  */
 631         return -1;
 632 }
 633
 634 #ifdef __MWERKS__
 635 #pragma mark ====== Binary Operations ======
 636 #endif
 637
 638 /* --------------------------------------
 639         ･ IntGroupMyIntersect
 640    -------------------------------------- */
 641 static IntGroupStatus
 642 IntGroupMyIntersect(
 643         IntGroupOperation inCode,
 644         const IntGroup *psRef1,
 645         const IntGroup *psRef2,
 646         IntGroup *psRef3)
 647 {
 648         int base = 0;
 649         int i, j, offset1, offset2, where;
 650         int theBeginIndex, theEndIndex;
 651         int theBeginFlag, theEndFlag;
 652         const int *ptr;
 653         IntGroupStatus result = kIntGroupStatusNoError;
 654
 655         IntGroupClear(psRef3);
 656         offset1 = offset2 = 0;
 657         where = 0;
 658
 659         for (i = 0; result == 0 && i < psRef2->num; i++) {
 660
 661                 int beginPt, endPt;
 662                 int newBeginPt, newEndPt;
 663
 664                 ptr = &(psRef2->entries[i * 2]);
 665                 switch (inCode) {
 666                         case kIntGroupIntersect:
 667                                 break;  /* offset1 = offset2 = 0  */
 668                         case kIntGroupConvolute:
 669                                 offset1 = base - ptr[0];
 670                                 offset2 = -offset1;
 671                                 break;
 672                         case kIntGroupDeconvolute:
 673                                 offset2 = base - ptr[0];
 674                                 break;
 675                 }
 676                 beginPt = ptr[0] + offset1;
 677                 endPt = ptr[1] + offset1;
 678                 theBeginFlag = IntGroupLookup(psRef1, beginPt, &theBeginIndex);
 679                 theEndFlag = IntGroupLookup(psRef1, endPt, &theEndIndex);
 680
 681                 if (theBeginIndex == psRef1->num)
 682                         break;  /*  もう加えるべき区間はない  */
 683
 684                 if (theBeginFlag) {
 685                         newBeginPt = beginPt + offset2;
 686                 } else {
 687                         newBeginPt = psRef1->entries[theBeginIndex * 2] + offset2;
 688                 }
 689                 if (theEndFlag && theBeginIndex == theEndIndex) {
 690                         newEndPt = endPt + offset2;
 691                 } else if (!theEndFlag && theBeginIndex == theEndIndex) {
 692                         newEndPt = newBeginPt;  /* null interval */
 693                 } else {
 694                         newEndPt = psRef1->entries[theBeginIndex * 2 + 1] + offset2;
 695                 }
 696                 /*  直前の区間と連続していないかどうかチェック  */
 697                 if (where > 0 && newBeginPt == psRef3->entries[where * 2 - 1]) {
 698                         psRef3->entries[where * 2 - 1] = newEndPt;
 699                 } else if (newBeginPt < newEndPt) {
 700                         result = IntGroupInsertAnEntry(psRef3, where++, newBeginPt, newEndPt);
 701                 }
 702                 if (result == kIntGroupStatusNoError) {
 703                         for (j = theBeginIndex + 1; j < theEndIndex; j++) {
 704                                 result = IntGroupInsertAnEntry(psRef3,
 705                                                                         where++,
 706                                                                         psRef1->entries[j * 2] + offset2,
 707                                                                         psRef1->entries[j * 2 + 1] + offset2);
 708                                 if (result != kIntGroupStatusNoError)
 709                                         break;
 710                         }
 711                 }
 712                 if (result == kIntGroupStatusNoError) {
 713                         if (theEndFlag && theBeginIndex < theEndIndex
 714                         && psRef1->entries[theEndIndex * 2] < endPt)
 715                                 result = IntGroupInsertAnEntry(psRef3,
 716                                                                         where++,
 717                                                                         psRef1->entries[theEndIndex * 2] + offset2,
 718                                                                         endPt + offset2);
 719                 }
 720
 721                 base += ptr[1] - ptr[0];
 722         }
 723
 724         /*  *****   debug   *****  */
 725 /*
 726         FILE *fp;
 727         fp = ::fopen("intersect.out", "at");
 728         switch (inCode) {
 729                 case code_Intersect: ::fprintf(fp, "Intersect:\n"); break;
 730                 case code_Convolute: ::fprintf(fp, "Convolute:\n"); break;
 731                 case code_Deconvolute: ::fprintf(fp, "Deconvolute:\n"); break;
 732         }
 733         for (i = 0; i < psRef1.mNumberOfEntries; i++) {
 734                 ::fprintf(fp, "%c%ld %ld", (i == 0 ? '(' : ' '),
 735                         (int)psRef1.mEntries[i].beginPt,
 736                         (int)psRef1.mEntries[i].endPt);
 737         }
 738         ::fprintf(fp, ")\n");
 739         for (i = 0; i < psRef2.mNumberOfEntries; i++) {
 740                 ::fprintf(fp, "%c%ld %ld", (i == 0 ? '(' : ' '),
 741                         (int)psRef2.mEntries[i].beginPt,
 742                         (int)psRef2.mEntries[i].endPt);
 743         }
 744         ::fprintf(fp, ")\n");
 745         for (i = 0; i < psRef3.mNumberOfEntries; i++) {
 746                 ::fprintf(fp, "%c%ld %ld", (i == 0 ? '(' : ' '),
 747                         (int)psRef3.mEntries[i].beginPt,
 748                         (int)psRef3.mEntries[i].endPt);
 749         }
 750         ::fprintf(fp, ")\n");
 751         ::fclose(fp);
 752 */
 753         /*  *********************  */
 754
 755         return result;
 756 }
 757
 758 /* --------------------------------------
 759         ･ IntGroupUnion
 760    -------------------------------------- */
 761 IntGroupStatus
 762 IntGroupUnion(const IntGroup *psRef1, const IntGroup *psRef2, IntGroup *psRef3)
 763 {
 764         int i, startPt;
 765         IntGroupStatus result;
 766         result = IntGroupCopy(psRef3, psRef2);
 767         if (result != kIntGroupStatusNoError)
 768                 return result;
 769         for (i = 0; i < psRef1->num; i++) {
 770                 startPt = psRef1->entries[i*2];
 771                 result = IntGroupAdd(psRef3, startPt, psRef1->entries[i*2+1] - startPt);
 772                 if (result != kIntGroupStatusNoError)
 773                         return result;
 774         }
 775         return kIntGroupStatusNoError;
 776 }
 777
 778 /* --------------------------------------
 779         ･ IntGroupIntersect
 780    -------------------------------------- */
 781 IntGroupStatus
 782 IntGroupIntersect(const IntGroup *psRef1, const IntGroup *psRef2, IntGroup *psRef3)
 783 {
 784         return IntGroupMyIntersect(kIntGroupIntersect, psRef1, psRef2, psRef3);
 785 }
 786
 787 /* --------------------------------------
 788         ･ IntGroupXor
 789    -------------------------------------- */
 790 IntGroupStatus
 791 IntGroupXor(const IntGroup *psRef1, const IntGroup *psRef2, IntGroup *psRef3)
 792 {
 793     IntGroupStatus result;
 794     int i, startPt;
 795     result = IntGroupCopy(psRef3, psRef1);
 796     if (result != kIntGroupStatusNoError)
 797         return result;
 798     for (i = 0; i < psRef2->num; i++) {
 799         startPt = psRef2->entries[i*2];
 800         result = IntGroupReverse(psRef3, startPt, psRef2->entries[i*2+1] - startPt);
 801         if (result != kIntGroupStatusNoError)
 802             return result;
 803     }
 804     return kIntGroupStatusNoError;
 805 }
 806
 807 /* --------------------------------------
 808         ･ IntGroupConvolute
 809    -------------------------------------- */
 810 IntGroupStatus
 811 IntGroupConvolute(const IntGroup *psRef1, const IntGroup *psRef2, IntGroup *psRef3)
 812 {
 813         return IntGroupMyIntersect(kIntGroupConvolute, psRef1, psRef2, psRef3);
 814 }
 815
 816 /* --------------------------------------
 817         ･ IntGroupDeconvolute
 818    -------------------------------------- */
 819 IntGroupStatus
 820 IntGroupDeconvolute(const IntGroup *psRef1, const IntGroup *psRef2, IntGroup *psRef3)
 821 {
 822         return IntGroupMyIntersect(kIntGroupDeconvolute, psRef1, psRef2, psRef3);
 823 }
 824
 825 /* --------------------------------------
 826         ･ IntGroupDifference
 827    -------------------------------------- */
 828 IntGroupStatus
 829 IntGroupDifference(const IntGroup *psRef1, const IntGroup *psRef2, IntGroup *psRef3)
 830 {
 831     IntGroupStatus result;
 832     int i, startPt;
 833     result = IntGroupCopy(psRef3, psRef1);
 834     if (result != kIntGroupStatusNoError)
 835         return result;
 836     for (i = 0; i < psRef2->num; i++) {
 837         startPt = psRef2->entries[i*2];
 838         result = IntGroupRemove(psRef3, startPt, psRef2->entries[i*2+1] - startPt);
 839         if (result != kIntGroupStatusNoError)
 840             return result;
 841     }
 842     return kIntGroupStatusNoError;
 843 }
 844
 845 /* --------------------------------------
 846         ･ IntGroupNegate
 847    -------------------------------------- */
 848 IntGroupStatus
 849 IntGroupNegate(const IntGroup *psRef1, IntGroup *psRef2)
 850 {
 851         int i;
 852
 853         IntGroupCopy(psRef2, psRef1);
 854         if (psRef1->num == 0) {
 855                 //  空集合
 856                 return IntGroupInsertAnEntry(psRef2, 0, 0, INT_MAX);
 857         }
 858
 859         if (psRef1->entries[0] == 0) {
 860                 for (i = 0; i < psRef1->num - 1; i++) {
 861                         psRef2->entries[i*2] = psRef1->entries[i*2+1];
 862                         psRef2->entries[i*2+1] = psRef1->entries[(i+1)*2];
 863                 }
 864                 if (psRef1->entries[i*2+1] != INT_MAX) {
 865                         psRef2->entries[i*2] = psRef1->entries[i*2+1];
 866                         psRef2->entries[i*2+1] = INT_MAX;
 867                 } else return IntGroupDeleteEntries(psRef2, i, i);
 868         } else {
 869                 psRef2->entries[0] = 0;
 870                 psRef2->entries[1] = psRef1->entries[0];
 871                 for (i = 1; i < psRef1->num; i++) {
 872                         psRef2->entries[i*2] = psRef1->entries[(i-1)*2+1];
 873                         psRef2->entries[i*2+1] = psRef1->entries[i*2];
 874                 }
 875                 if (psRef1->entries[(i-1)*2+1] != INT_MAX) {
 876                         return IntGroupInsertAnEntry(psRef2, i, psRef1->entries[(i-1)*2+1], INT_MAX);
 877                 }
 878         }
 879         return kIntGroupStatusNoError;
 880 }
 881
 882 /* --------------------------------------
 883         ･ IntGroupOffset
 884    -------------------------------------- */
 885 IntGroupStatus
 886 IntGroupOffset(IntGroup *psRef, int offset)
 887 {
 888         int i;
 889         if (psRef == NULL || psRef->num == 0)
 890                 return kIntGroupStatusNoError;
 891         if (psRef->entries[0] + offset < 0)
 892                 return kIntGroupStatusOutOfRange;  /*  Negative number is not allowed  */
 893         for (i = 0; i < psRef->num; i++) {
 894                 psRef->entries[i*2] += offset;
 895                 psRef->entries[i*2+1] += offset;
 896         }
 897         return kIntGroupStatusNoError;
 898 }
 899
 900 #ifdef __MWERKS__
 901 #pragma mark ====== Debugging ======
 902 #endif
 903
 904 /* --------------------------------------
 905         ･ IntGroupDump
 906    -------------------------------------- */
 907 void
 908 IntGroupDump(const IntGroup *pset)
 909 {
 910     int i, n, m;
 911     fprintf(stderr, "IntGroup[%p]: ", pset);
 912     for (i = 0; i < pset->num; i++) {
 913         n = pset->entries[i*2];
 914         m = pset->entries[i*2+1];
 915         fprintf(stderr, "%d", n);
 916         if (m > n + 1)
 917             fprintf(stderr, "-%d", m-1);
 918         if (i < pset->num - 1)
 919             fprintf(stderr, ",");
 920     }
 921     fprintf(stderr, "\n");
 922 }
 923
 924 #pragma mark ====== Iterators ======
 925
 926 /* --------------------------------------
 927         ･ IntGroupIteratorNew
 928    -------------------------------------- */
 929 IntGroupIterator *
 930 IntGroupIteratorNew(IntGroup *psRef)
 931 {
 932         IntGroupIterator *piRef = (IntGroupIterator *)malloc(sizeof(*piRef));
 933         if (piRef == NULL)
 934                 return NULL;    /* out of memory */
 935         IntGroupIteratorInit(psRef, piRef);
 936         piRef->refCount = 1;
 937         return piRef;
 938 }
 939
 940 /* --------------------------------------
 941         ･ IntGroupIteratorInit
 942    -------------------------------------- */
 943 IntGroupIterator *
 944 IntGroupIteratorInit(IntGroup *psRef, IntGroupIterator *piRef)
 945 {
 946         piRef->intGroup = psRef;
 947         IntGroupRetain(psRef);
 948         piRef->index = -1;
 949         piRef->position = -1;
 950         piRef->refCount = -1;
 951         return piRef;
 952 }
 953
 954 /* --------------------------------------
 955         ･ IntGroupIteratorRetain
 956    -------------------------------------- */
 957 void
 958 IntGroupIteratorRetain(IntGroupIterator *piRef)
 959 {
 960         if (piRef == NULL)
 961                 return;
 962         else if (piRef->refCount < 0)
 963                 piRef->refCount--;
 964         else
 965                 piRef->refCount++;
 966 }
 967
 968 /* --------------------------------------
 969         ･ IntGroupIteratorRelease
 970    -------------------------------------- */
 971 void
 972 IntGroupIteratorRelease(IntGroupIterator *piRef)
 973 {
 974         if (piRef == NULL)
 975                 return;
 976         else if (piRef->refCount < 0) {
 977                 if (++piRef->refCount == 0)
 978                         IntGroupRelease(piRef->intGroup);
 979         } else {
 980                 if (--piRef->refCount == 0) {
 981                         IntGroupRelease(piRef->intGroup);
 982                         free(piRef);
 983                 }
 984         }
 985 }
 986
 987 void
 988 IntGroupIteratorReset(IntGroupIterator *piRef)
 989 {
 990     if (piRef == NULL)
 991         return;
 992     piRef->index = -1;
 993     piRef->position = -1;
 994 }
 995
 996 void
 997 IntGroupIteratorResetAtLast(IntGroupIterator *piRef)
 998 {
 999     if (piRef == NULL || piRef->intGroup == NULL)
1000         return;
1001     piRef->index = piRef->intGroup->num - 1;
1002     if (piRef->index >= 0)
1003         piRef->position = piRef->intGroup->entries[piRef->intGroup->num * 2 - 1];
1004     else piRef->position = -1;
1005 }
1006
1007 int
1008 IntGroupIteratorNext(IntGroupIterator *piRef)
1009 {
1010     if (piRef == NULL || piRef->intGroup == NULL || piRef->intGroup->num == 0 || piRef->index >= piRef->intGroup->num)
1011         return -1;
1012     if (piRef->position < 0) {
1013         piRef->index = 0;
1014         piRef->position = piRef->intGroup->entries[0];
1015         return piRef->position;
1016     } else {
1017         piRef->position++;
1018         if (piRef->intGroup->entries[piRef->index * 2 + 1] > piRef->position)
1019             return piRef->position;
1020         if (piRef->index == piRef->intGroup->num - 1) {
1021             piRef->index = piRef->intGroup->num;
1022             return -1;
1023         } else {
1024             piRef->index++;
1025             piRef->position = piRef->intGroup->entries[piRef->index * 2];
1026             return piRef->position;
1027         }
1028     }
1029 }
1030
1031 int
1032 IntGroupIteratorLast(IntGroupIterator *piRef)
1033 {
1034     if (piRef == NULL || piRef->intGroup == NULL || piRef->intGroup->num == 0 || piRef->index < 0)
1035         return -1;
1036     piRef->position--;
1037     if (piRef->intGroup->entries[piRef->index * 2] <= piRef->position)
1038         return piRef->position;
1039     if (piRef->index == 0) {
1040         piRef->index = -1;
1041         piRef->position = -1;
1042         return -1;
1043     } else {
1044         piRef->index--;
1045         piRef->position = piRef->intGroup->entries[piRef->index * 2 + 1] - 1;
1046         return piRef->position;
1047     }
1048 }