| /**************************************************************/ |
| /* ********************************************************** */ |
| /* * * */ |
| /* * PARTITION * */ |
| /* * * */ |
| /* * $Module: PARTITION * */ |
| /* * * */ |
| /* * Copyright (C) 1999, 2000, 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 * */ |
| /* * * */ |
| /* ********************************************************** */ |
| /**************************************************************/ |
| |
| /* module manages partitions (i. e. sets of equivalence classes) of the set */ |
| /* {0, 1, 2, ..., size - 1} */ |
| |
| #ifndef _PARTITION_ |
| #define _PARTITION_ |
| |
| |
| /**************************************************************/ |
| /* Include */ |
| /**************************************************************/ |
| |
| #include "memory.h" |
| |
| |
| /**************************************************************/ |
| /* Constants and types */ |
| /**************************************************************/ |
| |
| #define part_CARD -1 /* index of cardinality of partitioned set */ |
| #define part_ALLOC -2 /* index of size of allocated space */ |
| #define part_STAMPCOUNTER -3 /* index of stampcounter */ |
| #define part_HEAD 3 /* length of head for management purposes */ |
| |
| |
| typedef int ELEMENT; |
| typedef ELEMENT ECLASS, *PARTITION; |
| |
| /* an equivalence class is represented by one of its elements, the */ |
| /* _representative_; a partition is an array to hold the size of the */ |
| /* partitioned set and of the allocated space, the equivalence classes, */ |
| /* their sizes and stamps and the stampcounter: */ |
| /* STAMPCOUNTER ALLOC CARD */ |
| /* | | | */ |
| /* -size - 3, ..., -4, -3, -2, -1, 0, ..., size - 1, size, ..., 2 * size - 1 */ |
| /* <--- stamp[] ----| |--- class[] --> |---- classsize[] ----> */ |
| |
| |
| /**************************************************************/ |
| /* Prototypes */ |
| /**************************************************************/ |
| |
| PARTITION part_Create(int); |
| PARTITION part_Init(PARTITION, int); |
| ECLASS part_Find(PARTITION, ELEMENT); |
| /* gets (the representative of) the class of the second argument */ |
| PARTITION part_Union(PARTITION, ECLASS, ECLASS); |
| /* unions the classes, the representative of the first class is the */ |
| /* representative of the union */ |
| |
| |
| /**************************************************************/ |
| /* Inline functions */ |
| /**************************************************************/ |
| |
| static __inline__ void part_Free(PARTITION p) |
| { |
| if (p != NULL) |
| memory_Free( |
| p - (p[part_ALLOC] - part_HEAD) / 3 - part_HEAD, |
| p[part_ALLOC] * sizeof(int) |
| ); |
| } |
| |
| |
| static __inline__ int part_Size(PARTITION p) |
| { |
| return p[part_CARD]; |
| } |
| |
| |
| static __inline__ BOOL part_Element(PARTITION p, ELEMENT e) |
| { |
| return 0 <= e && e < part_Size(p); |
| } |
| |
| |
| static __inline__ BOOL part_Equivalent(PARTITION p, ELEMENT e1, ELEMENT e2) |
| { |
| return part_Find(p, e1) == part_Find(p, e2); |
| } |
| |
| |
| #endif |
| |