1
2
3
4
5
6
7 template<typename T,int N>
8 struct SortArray {
9 };
10
11 template<typename T>
12 struct SortArray<T,1> {
13 T v[1];
14
SortArraySortArray15 SortArray(T *a,int * sens=0)
16 {
17 v[0]=a[0];
18 if(sens) *sens =1;
19 }
SortArraySortArray20 SortArray(const T& a0)
21 {
22 v[0]=a0;
23 }
SortArraySortArray24 SortArray(){}
operator ==SortArray25 bool operator == (const SortArray<T,1> & t) const
26 { return v[0] == t.v[0] ;}
operator <SortArray27 bool operator<(const SortArray<T,1> & t) const
28 { return v[0] < t.v[0] ;}
hashSortArray29 size_t hash() const {return (size_t) v[0];}
30 };
31
32
33 template<typename T>
34 struct SortArray<T,2> {
35 // using std::swap;
36 T v[2];
37
SortArraySortArray38 SortArray(T *a,int * sens=0)
39 { int s=1;
40 v[0]=a[0];
41 v[1]=a[1];
42 if(v[0]>v[1]) s=-s,swap(v[0],v[1]);
43 if(sens) *sens=s;
44 }
45
SortArraySortArray46 SortArray(const T& a0,const T &a1)
47 {
48 v[0]=a0;
49 v[1]=a1;
50 if(v[0]>v[1]) swap(v[0],v[1]);
51 }
SortArraySortArray52 SortArray(){}
operator ==SortArray53 bool operator == (const SortArray<T,2> & t) const
54 { return v[0] == t.v[0] && v[1] == t.v[1] ;}
operator <SortArray55 bool operator<(const SortArray<T,2> & t) const
56 { return v[0] != t.v[0] ? v[0] < t.v[0] : v[1] < t.v[1] ;}
hashSortArray57 size_t hash() const {return (size_t) v[0];}
58 };
59
60
61 template<typename T>
62 struct SortArray<T,3> {
63 T v[3];
SortArraySortArray64 SortArray(T *a,int *sens=0)
65 {
66 int s=1;
67 v[0]=a[0];
68 v[1]=a[1];
69 v[2]=a[2];
70 if(v[0]>v[1]) s=-s,swap(v[0],v[1]);
71 if(v[1]>v[2]) {
72 s=-s,swap(v[1],v[2]);
73 if(v[0]>v[1]) s=-s,swap(v[0],v[1]);
74 ASSERTION(v[0] <= v[1] && v[1] <= v[2] );
75 }
76 if(sens) *sens=s;
77 }
78
SortArraySortArray79 SortArray(){}
operator ==SortArray80 bool operator == (const SortArray<T,3> & t) const
81 { return v[0] == t.v[0] && v[1] == t.v[1] && v[2] == t.v[2] ;}
82
operator <SortArray83 bool operator<(const SortArray<T,3> & t) const
84 { return v[0] != t.v[0] ? v[0] < t.v[0] :
85 ( v[1] != t.v[1] ? v[1] < t.v[1] : v[2] < t.v[2] );}
86
hashSortArray87 size_t hash() const {return (size_t) v[0];}
88 };
89
90 template<typename T>
91 struct SortArray<T,4> {
92 T v[4];
SortArraySortArray93 SortArray(T *a,int *sens=0)
94 {
95 int s=1;
96 v[0]=a[0];
97 v[1]=a[1];
98 v[2]=a[2];
99 v[3]=a[3];
100 if(v[0]>v[1]) s=-s,swap(v[0],v[1]);
101 if(v[1]>v[2]) {
102 s=-s,swap(v[1],v[2]);
103 if(v[0]>v[1]) s=-s,swap(v[0],v[1]);
104 }
105 if(v[2]>v[3]) {
106 s=-s,swap(v[3],v[2]);
107 if(v[1]>v[2]) s=-s,swap(v[1],v[2]);
108 if(v[0]>v[1]) s=-s,swap(v[0],v[1]);
109 }
110
111 ASSERTION(v[0] <= v[1] && v[1] <= v[2] && v[2] <= v[3]);
112
113 if(sens) *sens=s;
114 }
115
SortArraySortArray116 SortArray(){}
operator ==SortArray117 bool operator == (const SortArray<T,4> & t) const
118 { return v[0] == t.v[0] && v[1] == t.v[1] && v[2] == t.v[2] && v[3] == t.v[3] ;}
119
operator <SortArray120 bool operator<(const SortArray<T,4> & t) const
121 { return v[0] != t.v[0] ? v[0] < t.v[0] :
122 ( v[1] != t.v[1] ? v[1] < t.v[1] :
123 ( v[2] != t.v[2] ? v[2] < t.v[2]: v[3] < t.v[3] ));}
hashSortArray124 size_t hash() const {return (size_t) v[0]+((size_t) v[1] << 8 ) + ((size_t) v[2] << 16 ) + ((size_t) v[3] << 24);}
125 };
126 template<typename T,int N>
operator <<(ostream & f,const SortArray<T,N> & item)127 ostream & operator<<(ostream & f,const SortArray<T,N> & item)
128 {
129 for (int i=0;i<N;++i) f << " " << item.v[i];
130 return f;
131 }
132
133 template<typename T,int N>
commonValue(const SortArray<T,N> & t)134 bool commonValue(const SortArray<T,N> & t) {
135 for(int i=1;i<N;i++)
136 if(t.v[i-1]==t.v[i])
137 return true;
138 return false;
139 }
140
141 template<class K,class V>
142 class HashTable {
143 public:
144 struct nKV { size_t next; K k; V v;
nKVHashTable::nKV145 nKV(){} };
146 typedef nKV *iterator;
147 size_t n,nx,nk,ncol,nfind;
148 size_t * head;
149 nKV * t;
150 static const size_t endhash= (size_t) -1;
151
HashTable(size_t nnx,size_t nnk)152 HashTable(size_t nnx,size_t nnk)
153 : n(0),nx(nnx),nk(nnk),ncol(0),nfind(0),
154 head(new size_t[nk]),t(new nKV[nx])
155 { reset();}
156
reset()157 void reset()
158 {
159 n=0;
160 ncol=0;
161 for (size_t j=0;j<nk;++j)
162 head[j]=endhash;
163 }
164
find(const K & key)165 nKV * find(const K & key)
166 {
167 nfind++;
168 for (size_t k=head[key.hash() %nk];k!=endhash;k=t[k].next)
169 {
170 ++ncol;
171 if(key == t[k].k) return t+k;
172 }
173 return 0;
174 }
175 // add FH 21 avril 2009
operator ()(nKV * p)176 size_t operator()(nKV * p) { return p ? p-t : n;}
177
end()178 iterator end(){ return t+n;}
begin()179 iterator begin(){ return t;}
180
add(const K & key,const V & v)181 nKV *add(const K & key,const V & v)
182 {
183 size_t k =key.hash()%nk;
184 assert(n<nx);
185 t[n].v = v;
186 t[n].k = key;
187 t[n].next=head[k];
188 head[k]=n;
189 return t+ n++;
190 }
191
operator [](const K & key)192 V & operator[](const K & key)
193 {
194 nKV *p = find(key);
195 if(p) return p->v;
196 else return t[add(key,V())].v;
197 }
~HashTable()198 ~HashTable()
199 {
200 if(nfind && verbosity>4)
201 cout << " ~HashTable: Cas moyen : " << (double) ncol/ nfind << endl;
202 delete [] head;
203 delete [] t;
204 }
205
206 // pas de copie ....
207 private:
208 HashTable(const HashTable&);
209 void operator=(const HashTable&);
210 };
211