1 | /* |
---|
2 | Copyright 2006 by Sean Luke |
---|
3 | Licensed under the Academic Free License version 3.0 |
---|
4 | See the file "LICENSE" for more information |
---|
5 | */ |
---|
6 | |
---|
7 | |
---|
8 | package ec.gp; |
---|
9 | import ec.*; |
---|
10 | import ec.util.*; |
---|
11 | import java.util.Hashtable; |
---|
12 | import java.util.Enumeration; |
---|
13 | |
---|
14 | /* |
---|
15 | * GPSetType.java |
---|
16 | * |
---|
17 | * Created: Fri Aug 27 20:55:42 1999 |
---|
18 | * By: Sean Luke |
---|
19 | */ |
---|
20 | |
---|
21 | /** |
---|
22 | * A GPSetType is a GPType which contains GPAtomicTypes in a set, and is used |
---|
23 | * as a generic GP type. For more information, see GPType |
---|
24 | * |
---|
25 | * GPSetTypes implement their set using both a hash table and an array. |
---|
26 | * if the size of the set is "significantly big", then the hash table |
---|
27 | * is used to look up membership in the set (O(1), but with a big constant). |
---|
28 | * If the size is small, then the array is used (O(n)). The dividing line |
---|
29 | * is determined by the constant START_USING_HASH_BEYOND, which you might |
---|
30 | * play with to optimize for your system. |
---|
31 | * |
---|
32 | * @see ec.gp.GPType |
---|
33 | * @author Sean Luke |
---|
34 | * @version 1.0 |
---|
35 | */ |
---|
36 | |
---|
37 | public final class GPSetType extends GPType |
---|
38 | { |
---|
39 | public static final String P_MEMBER = "member"; |
---|
40 | public static final String P_SIZE = "size"; |
---|
41 | |
---|
42 | /** A packed, sorted array of atomic types in the set */ |
---|
43 | public int[] types_packed; |
---|
44 | |
---|
45 | /** A sparse array of atomic types in the set */ |
---|
46 | public boolean[] types_sparse; |
---|
47 | |
---|
48 | /** The hashtable of types in the set */ |
---|
49 | public Hashtable types_h; |
---|
50 | |
---|
51 | /** You should not construct new types. */ |
---|
52 | public GPSetType() { } |
---|
53 | |
---|
54 | |
---|
55 | /** Sets up the packed and sparse arrays based on the hashtable */ |
---|
56 | public void postProcessSetType(int totalAtomicTypes) |
---|
57 | { |
---|
58 | // load the hashtable into the arrays |
---|
59 | int x=0; |
---|
60 | types_packed = new int[types_h.size()]; |
---|
61 | types_sparse = new boolean[totalAtomicTypes]; |
---|
62 | Enumeration e = types_h.elements(); |
---|
63 | while(e.hasMoreElements()) |
---|
64 | { |
---|
65 | GPAtomicType t = (GPAtomicType)(e.nextElement()); |
---|
66 | types_packed[x++] = t.type; |
---|
67 | types_sparse[t.type] = true; |
---|
68 | } |
---|
69 | |
---|
70 | // Sort the packed array |
---|
71 | java.util.Arrays.sort(types_packed); |
---|
72 | } |
---|
73 | |
---|
74 | |
---|
75 | public void setup(final EvolutionState state, Parameter base) |
---|
76 | { |
---|
77 | super.setup(state,base); |
---|
78 | |
---|
79 | // Make my Hashtable |
---|
80 | types_h = new Hashtable(); |
---|
81 | |
---|
82 | // How many atomic types do I have? |
---|
83 | int len = state.parameters.getInt(base.push(P_SIZE),null,1); |
---|
84 | if (len<=0) |
---|
85 | state.output.fatal("The number of atomic types in the GPSetType " + |
---|
86 | name + " must be >= 1.",base.push(P_SIZE)); |
---|
87 | |
---|
88 | // Load the GPAtomicTypes |
---|
89 | for(int x=0;x<len;x++) |
---|
90 | { |
---|
91 | String s = state.parameters.getString(base.push(P_MEMBER).push(""+x),null); |
---|
92 | if (s==null) |
---|
93 | state.output.fatal("Atomic type member #" + x + |
---|
94 | " is not defined for the GPSetType " + name + |
---|
95 | ".",base.push(P_MEMBER).push(""+x)); |
---|
96 | GPType t = GPType.typeFor(s,state); |
---|
97 | if (!(t instanceof GPAtomicType)) // uh oh |
---|
98 | state.output.fatal("Atomic type member #" + x + |
---|
99 | " of GPSetType " + name + |
---|
100 | " is not a GPAtomicType.", |
---|
101 | base.push(P_MEMBER).push(""+x)); |
---|
102 | |
---|
103 | if (types_h.get(t)!=null) |
---|
104 | state.output.warning("Atomic type member #" + x + |
---|
105 | " is included more than once in GPSetType " + |
---|
106 | name + ".", |
---|
107 | base.push(P_MEMBER).push(""+x)); |
---|
108 | types_h.put(t,t); |
---|
109 | } |
---|
110 | } |
---|
111 | |
---|
112 | |
---|
113 | public final boolean compatibleWith(final GPInitializer initializer,final GPType t) |
---|
114 | { |
---|
115 | // if the type is me, then I'm compatible with it. |
---|
116 | if (t.type == type) return true; |
---|
117 | |
---|
118 | // if the type is an atomic type, then I'm compatible with it if I contain it. |
---|
119 | // Use the sparse array. |
---|
120 | else if (t.type < initializer.numAtomicTypes) // atomic type, faster than doing instanceof |
---|
121 | return types_sparse[t.type]; |
---|
122 | |
---|
123 | // else the type is a set type. I'm compatible with it if we contain |
---|
124 | // an atomic type in common. Use the sorted packed array. |
---|
125 | else |
---|
126 | { |
---|
127 | GPSetType s = (GPSetType)t; |
---|
128 | int x=0; int y=0; |
---|
129 | for( ; x < types_packed.length && y < s.types_packed.length ; ) |
---|
130 | { |
---|
131 | if (types_packed[x] == s.types_packed[y]) return true; |
---|
132 | else if (types_packed[x] < s.types_packed[y]) x++; |
---|
133 | else y++; |
---|
134 | } |
---|
135 | return false; |
---|
136 | } |
---|
137 | } |
---|
138 | } |
---|