00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014 #include "set.h"
00015
00016 #include <stdlib.h>
00017 #include <memory.h>
00018 #include <limits.h>
00019
00020 static SetStatus setStatus;
00021 static const unsigned int NumFixedPositions = 2;
00022
00023 Set createSet(int l, int h)
00024 {
00025 Set toret = NULL;
00026 setStatus = SetOk;
00027
00028 if ( l >= h ) {
00029 setStatus = SetInvalidRange;
00030 } else {
00031
00032 int size = ( ( h - l ) / ( sizeof( unsigned int ) * CHAR_BIT ) )
00033 + NumFixedPositions + 2
00034 ;
00035
00036 toret = (Set) calloc( size, sizeof( unsigned int ) );
00037
00038
00039 if ( toret != NULL ) {
00040 *( (int *) toret ) = h;
00041 *( ( (int *) toret ) + 1 ) = l;
00042 } else {
00043 setStatus = SetNoMemory;
00044 }
00045 }
00046
00047 return toret;
00048 }
00049
00050 Set createFilledSet(int l, int h)
00051 {
00052 Set toret = createSet( l, h );
00053
00054 if ( getSetStatus() == SetOk ) {
00055 insertSetRange( toret, l, h );
00056 }
00057
00058 return toret;
00059 }
00060
00061 static inline
00062 unsigned int * getBlock(Set s, unsigned int pos)
00063 {
00064 pos /= sizeof( unsigned int ) * CHAR_BIT;
00065 return s + NumFixedPositions + pos;
00066 }
00067
00068 static inline
00069 unsigned int getPositionInBlock(Set s, unsigned int pos)
00070 {
00071 return ( pos %= sizeof( unsigned int ) * CHAR_BIT );
00072 }
00073
00074 bool isWithinBoundsOfSet(Set s, int pos)
00075 {
00076 bool toret = true;
00077
00078 if ( pos < getLowestElement( s )
00079 || pos > getHighestElement( s ) )
00080 {
00081 toret = false;
00082 }
00083
00084 return toret;
00085 }
00086
00087 bool querySetElement(Set s, int pos)
00088 {
00089 bool toret = false;
00090 setStatus = SetOk;
00091
00092 if ( isWithinBoundsOfSet( s, pos ) ) {
00093 unsigned int * blk = getBlock( s, pos );
00094 unsigned int bit = getPositionInBlock( s, pos );
00095 unsigned int mask = 1 << bit;
00096
00097 toret = ( ( *blk ) & mask );
00098 } else setStatus = SetInvalidPosition;
00099
00100 return toret;
00101 }
00102
00103 void insertSetElement(Set s, int pos)
00104 {
00105 setStatus = SetOk;
00106
00107 if ( isWithinBoundsOfSet( s, pos ) ) {
00108 unsigned int * blk = getBlock( s, pos );
00109 unsigned int bit = getPositionInBlock( s, pos );
00110 unsigned int mask = 1 << bit;
00111
00112 *blk |= mask;
00113 } else setStatus = SetInvalidPosition;
00114 }
00115
00116 void deleteSetElement(Set s, int pos)
00117 {
00118 setStatus = SetOk;
00119
00120 if ( isWithinBoundsOfSet( s, pos ) ) {
00121 unsigned int * blk = getBlock( s, pos );
00122 unsigned int bit = getPositionInBlock( s, pos );
00123 unsigned int mask = 1 << bit;
00124
00125 mask = ~mask;
00126 *blk &= mask;
00127 } else setStatus = SetInvalidPosition;
00128 }
00129
00130 inline
00131 SetStatus getSetStatus()
00132 {
00133 return setStatus;
00134 }
00135
00136 void deleteSetRange(Set s, int l, int h)
00137 {
00138 int i;
00139
00140 for(i = l; i <= h; ++i) {
00141 deleteSetElement( s, i );
00142 }
00143 }
00144
00145 void insertSetRange(Set s, int l, int h)
00146 {
00147 int i;
00148
00149 for(i = l; i <= h; ++i) {
00150 insertSetElement( s, i );
00151 }
00152 }
00153
00154 void destroySet(Set s)
00155 {
00156 setStatus = SetOk;
00157 free( s );
00158 }