| /**************************************************************/ |
| /* ********************************************************** */ |
| /* * * */ |
| /* * PARTITION * */ |
| /* * * */ |
| /* * $Module: PARTITION * */ |
| /* * * */ |
| /* * Copyright (C) 1999, 2001 MPI fuer Informatik * */ |
| /* * * */ |
| /* * This program is free software; you can redistribute * */ |
| /* * it and/or modify it under the terms of the GNU * */ |
| /* * General Public License as published by the Free * */ |
| /* * Software Foundation; either version 2 of the License, * */ |
| /* * or (at your option) any later version. * */ |
| /* * * */ |
| /* * This program is distributed in the hope that it will * */ |
| /* * be useful, but WITHOUT ANY WARRANTY; without even * */ |
| /* * the implied warranty of MERCHANTABILITY or FITNESS * */ |
| /* * FOR A PARTICULAR PURPOSE. See the GNU General Public * */ |
| /* * License for more details. * */ |
| /* * * */ |
| /* * You should have received a copy of the GNU General * */ |
| /* * Public License along with this program; if not, write * */ |
| /* * to the Free Software Foundation, Inc., 59 Temple * */ |
| /* * Place, Suite 330, Boston, MA 02111-1307 USA * */ |
| /* * * */ |
| /* * * */ |
| /* $Revision$ * */ |
| /* $State$ * */ |
| /* $Date$ * */ |
| /* $Author$ * */ |
| /* * * */ |
| /* * Contact: * */ |
| /* * Christoph Weidenbach * */ |
| /* * MPI fuer Informatik * */ |
| /* * Stuhlsatzenhausweg 85 * */ |
| /* * 66123 Saarbruecken * */ |
| /* * Email: weidenb@mpi-sb.mpg.de * */ |
| /* * Germany * */ |
| /* * * */ |
| /* ********************************************************** */ |
| /**************************************************************/ |
| |
| |
| /**************************************************************/ |
| /* Include */ |
| /**************************************************************/ |
| |
| #include "partition.h" |
| |
| |
| /**************************************************************/ |
| /* Inline functions */ |
| /**************************************************************/ |
| |
| static __inline__ ECLASS part_GetClass(PARTITION p, ELEMENT e) |
| { |
| return p[e]; |
| } |
| |
| |
| static __inline__ PARTITION part_SetClass(PARTITION p, ELEMENT e, ECLASS c) |
| { |
| p[e] = c; |
| return p; |
| } |
| |
| |
| static __inline__ int part_GetClassSize(PARTITION p, ELEMENT e) |
| { |
| return p[p[part_CARD] + e]; |
| } |
| |
| |
| static __inline__ PARTITION part_SetClassSize(PARTITION p, ELEMENT e, int |
| classsize) |
| { |
| p[p[part_CARD] + e] = classsize; |
| return p; |
| } |
| |
| |
| static __inline__ int part_GetStamp(PARTITION p, ELEMENT e) |
| { |
| return p[-part_HEAD - 1 - e]; |
| } |
| |
| |
| static __inline__ PARTITION part_SetStamp(PARTITION p, ELEMENT e, int stamp) |
| { |
| p[-part_HEAD - 1 - e] = stamp; |
| return p; |
| } |
| |
| |
| static __inline__ BOOL part_Stamped(PARTITION p, ELEMENT e) |
| { |
| return part_GetStamp(p, e) == p[part_STAMPCOUNTER]; |
| } |
| |
| |
| static __inline__ ELEMENT part_DelayedInit(PARTITION p, ELEMENT e) |
| /*************************************************************** |
| RETURNS: the (now stamped) element |
| EFFECT: establishes the equivalence class {e} in p, thus |
| partially initializing p |
| ***************************************************************/ |
| { |
| if (!part_Stamped(p, e)) { |
| part_SetClass(p, e, -e - 1); /* representative e (>= 0) of {e} is coded */ |
| /* as -e - 1 (< 0) */ |
| part_SetClassSize(p, e, 1); |
| part_SetStamp(p, e, p[part_STAMPCOUNTER]); |
| } |
| return e; |
| } |
| |
| |
| /**************************************************************/ |
| /* Functions */ |
| /**************************************************************/ |
| |
| PARTITION part_Create(int size) |
| /**************************************************************** |
| RETURNS: the initial partition {{0}, {1}, {2}, ..., {size - 1}} |
| of the set {0, 1, 2, ..., size - 1} |
| ****************************************************************/ |
| { |
| PARTITION result; |
| |
| #ifdef CHECK |
| if (size < 0) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In part_Create: negative size %d.", size); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| result = (PARTITION) memory_Calloc(size * 3 + part_HEAD, sizeof(int)) |
| + size + part_HEAD; /* move pointer to the middle of the array */ |
| /* to allow negative indices */ |
| result[part_CARD] = size; |
| result[part_ALLOC] = size * 3 + part_HEAD; |
| result[part_STAMPCOUNTER] = 1; |
| return result; |
| } |
| |
| |
| PARTITION part_Init(PARTITION p, int size) |
| /**************************************************************** |
| RETURNS: the initial partition {{0}, {1}, {2}, ..., {size - 1}} |
| of the set {0, 1, 2, ..., size - 1} |
| EFFECT: stores the initial partition to p if it's big enough, |
| otherwise creates a new partition, therefore |
| CAUTION: must be called inside an assignment like: |
| p = part_Init(p, ...) |
| ****************************************************************/ |
| { |
| int alloc, i; |
| |
| #ifdef CHECK |
| if (size < 0) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In part_Init: negative size %d.", size); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| alloc = (p[part_ALLOC] - part_HEAD) / 3; |
| if (size > alloc) { |
| part_Free(p); |
| p = part_Create(size); |
| } |
| else { |
| p[part_CARD] = size; |
| p[part_STAMPCOUNTER]++; |
| |
| /* if a stamp overflow occurs, reinit stamps: */ |
| if (p[part_STAMPCOUNTER] <= 0) { |
| for (i = 0; i < alloc; i++) |
| part_SetStamp(p, i, 0); |
| p[part_STAMPCOUNTER] = 1; |
| } |
| |
| } |
| return p; |
| } |
| |
| |
| static ELEMENT part_NF(PARTITION p, ELEMENT e) |
| /*************************************************************** |
| RETURNS: the normal form element of the class [e]; this is an |
| element of [e] that sometimes differ from the |
| representative |
| EFFECT: makes the normal form to the direct parent of all |
| elements visited on the search path from e to this |
| normal form ("path compression") |
| ***************************************************************/ |
| { |
| ELEMENT nf, aux; |
| |
| #ifdef CHECK |
| if (!part_Element(p, e)) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In part_NF: %d not in partitioned set.", e); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| nf = e; |
| while (part_GetClass(p, part_DelayedInit(p, nf)) >= 0) |
| nf = part_GetClass(p, nf); |
| |
| /* path compression: */ |
| while (e != nf) { |
| aux = part_GetClass(p, e); |
| part_SetClass(p, e, nf); |
| e = aux; |
| } |
| |
| return nf; |
| } |
| |
| |
| ECLASS part_Find(PARTITION p, ELEMENT e) |
| /*************************************************************** |
| RETURNS: (the representative of) class [e] |
| ***************************************************************/ |
| { |
| |
| #ifdef CHECK |
| if (!part_Element(p, e)) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In part_Find: %d not in partitioned set.", e); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| return -part_GetClass(p, part_NF(p, e)) - 1; |
| /* representative e is coded as -e - 1 (cf. part_DelayedInit) */ |
| } |
| |
| |
| PARTITION part_Union(PARTITION p, ECLASS c1, ECLASS c2) |
| /*************************************************************** |
| RETURNS: the union of the classes |
| EFFECT: the representative of c1 is the representative of the |
| union |
| ***************************************************************/ |
| { |
| ELEMENT nf1, nf2, aux; |
| |
| #ifdef CHECK |
| if (!part_Element(p, c1)) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In part_Union: first class %d not in partitioned set.", |
| c1); |
| misc_FinishErrorReport(); |
| } |
| if (!part_Element(p, c2)) { |
| misc_StartErrorReport(); |
| misc_ErrorReport |
| ("\n In part_Union: second class %d not in partitioned set.", c2); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| nf1 = part_NF(p, c1); |
| nf2 = part_NF(p, c2); |
| if (nf1 != nf2) { |
| |
| /* make [nf1] the bigger (or at least not smaller) class: */ |
| if (part_GetClassSize(p, nf1) < part_GetClassSize(p, nf2)) { |
| aux = nf1; |
| nf1 = nf2; |
| nf2 = aux; |
| part_SetClass(p, nf1, part_GetClass(p, nf2)); |
| part_SetClass(p, -part_GetClass(p, nf2) - 1, nf1); |
| } |
| |
| part_SetClass(p, nf2, nf1); |
| part_SetClassSize(p, nf1, |
| part_GetClassSize(p, nf1) + part_GetClassSize(p, nf2)); |
| } |
| return p; |
| } |
| |
