001: package it.unimi.dsi.mg4j.test;
002:
003: import it.unimi.dsi.bits.Fast;
004:
005: import java.awt.BorderLayout;
006: import java.awt.Color;
007: import java.awt.Component;
008: import java.awt.Container;
009: import java.awt.Graphics;
010: import java.awt.event.ActionEvent;
011: import java.awt.event.ActionListener;
012:
013: import javax.swing.BorderFactory;
014: import javax.swing.Box;
015: import javax.swing.JFrame;
016: import javax.swing.JLabel;
017: import javax.swing.JOptionPane;
018: import javax.swing.JPanel;
019: import javax.swing.JSlider;
020: import javax.swing.JTextField;
021: import javax.swing.event.ChangeEvent;
022: import javax.swing.event.ChangeListener;
023:
024: @SuppressWarnings("serial")
025: class InputPanel extends JPanel {
026: private JTextField qtf, htf;
027: private JSlider js;
028:
029: InputPanel(final DrawPanel dp) {
030:
031: JLabel ql, hl, cl;
032: int q = 3, h = 3, cache = 12;
033:
034: ActionListener clqh = new ActionListener() {
035: public void actionPerformed(ActionEvent e) {
036: try {
037: int q, h, cache;
038: q = Integer.parseInt(qtf.getText());
039: h = Integer.parseInt(htf.getText());
040: cache = js.getValue();
041: js.setMaximum(q * (1 << h));
042: if (cache > q * (1 << h)) {
043: cache = q * (1 << h);
044: js.setValue(cache);
045: }
046: dp.setValues(q, h, cache);
047: dp.repaint();
048: } catch (Exception exc) {
049: JOptionPane.showMessageDialog(null, exc
050: .getMessage(), "Alert",
051: JOptionPane.ERROR_MESSAGE);
052: }
053: }
054: };
055:
056: //Box box = Box.createHorizontalBox();
057: JPanel box = new JPanel();
058:
059: box.add(ql = new JLabel("q = "));
060: box.add(qtf = new JTextField("3", 3));
061: ql.setLabelFor(qtf);
062: qtf.addActionListener(clqh);
063: box.add(Box.createHorizontalStrut(20));
064:
065: box.add(hl = new JLabel("h = "));
066: box.add(htf = new JTextField("3", 3));
067: hl.setLabelFor(htf);
068: htf.addActionListener(clqh);
069: box.add(Box.createHorizontalStrut(20));
070:
071: Box vbox = Box.createVerticalBox();
072: cl = new JLabel("Actual cache size", JLabel.CENTER);
073: cl.setAlignmentX(Component.CENTER_ALIGNMENT);
074: vbox.add(cl);
075:
076: js = new JSlider(JSlider.HORIZONTAL, 0, q * (1 << h), cache);
077: js.setMajorTickSpacing(10);
078: js.setMinorTickSpacing(1);
079: js.setPaintTicks(true);
080: js.setPaintLabels(true);
081: js.setBorder(BorderFactory.createEmptyBorder(0, 0, 10, 0));
082: js.addChangeListener(new ChangeListener() {
083: public void stateChanged(ChangeEvent e) {
084: JSlider source = (JSlider) e.getSource();
085: // if ( source.getValueIsAdjusting() ) return;
086: try {
087: int q, h, cache;
088: q = Integer.parseInt(qtf.getText());
089: h = Integer.parseInt(htf.getText());
090: cache = source.getValue();
091: dp.setValues(q, h, cache);
092: dp.repaint();
093: } catch (Exception exc) {
094: JOptionPane.showMessageDialog(null, exc
095: .getMessage(), "Alert",
096: JOptionPane.ERROR_MESSAGE);
097: }
098: }
099: });
100: cl.setLabelFor(js);
101: vbox.add(js);
102:
103: box.add(vbox);
104:
105: add(box);
106: dp.setValues(q, h, cache);
107: dp.repaint();
108: }
109:
110: }
111:
112: @SuppressWarnings("serial")
113: class DrawPanel extends JPanel {
114: static final int SS = 15;
115: int q, h, cache;
116: int b;
117:
118: void setValues(int q, int h, int cache) {
119: if (cache > (1 << h) * q)
120: throw new IllegalArgumentException("Maximum cache size: "
121: + b);
122: this .q = q;
123: this .h = h;
124: this .cache = cache;
125: b = (1 << h) * q;
126: }
127:
128: private void paintSquare(Graphics g, int i, int h, boolean exists) {
129: int x = getWidth();
130: int y = getHeight();
131:
132: int xcenter = x / 2 - b * SS / 2 + i * SS;
133: int ycenter = 2 * y / 3 - (h + 1) * SS;
134:
135: if (exists)
136: g.setColor(Color.BLACK);
137: else
138: g.setColor(Color.YELLOW);
139:
140: g.fill3DRect(xcenter - SS / 2 + 1, ycenter - SS / 2 + 1,
141: SS - 2, SS - 2, false);
142: }
143:
144: private void drawLine(Graphics g, int i, int h, int jt, Color c) {
145: int x = getWidth();
146: int y = getHeight();
147:
148: int xi = x / 2 - b * SS / 2 + i * SS;
149: int xjt = x / 2 - b * SS / 2 + jt * SS;
150: int yy = 2 * y / 3 - (h + 1) * SS;
151:
152: g.setColor(c);
153: g.drawLine(xi, yy, xjt, yy);
154: g.fillOval(xi - 2, yy - 2, 4, 4);
155: g.fillOval(xjt - 2, yy - 2, 4, 4);
156: }
157:
158: public void paint(Graphics g) {
159: g.clearRect(getX(), getY(), getWidth(), getHeight());
160:
161: for (int i = 0; i < b; i++)
162: paintSquare(g, i, -1, i < cache);
163:
164: for (int passage = 0; passage < 2; passage++)
165: for (int kq = 0; kq < b; kq++) {
166: int nextAfter = (cache + q - 1) / q;
167: int s, st, k, pt, p;
168:
169: if (kq % q == 0) {
170:
171: // Skip record number k
172: k = kq / q;
173: // Compute the height of the skip tower (s+1)...
174: s = st = (k == 0) ? h : Fast.leastSignificantBit(k); // TZ(k)
175: if (cache < b)
176: s = Math.min(s, Fast.mostSignificantBit(cache
177: / q - k));
178:
179: for (int hh = 0; hh <= st; hh++)
180: if (passage == 1)
181: paintSquare(g, kq, hh, hh <= s
182: && kq < cache);
183: else if (hh <= s && kq < cache) {
184: pt = k + (1 << hh);
185: p = Math.min(pt, nextAfter);
186: if (p < pt) {
187: drawLine(g, kq, hh, pt * q, Color.WHITE);
188: System.out.println("From " + kq
189: + " (skip index " + k
190: + ") at height " + hh + "(2^h="
191: + (1 << hh) + ") should go to "
192: + pt + " but goes to " + p
193: + " instead");
194: }
195: drawLine(g, kq, hh, p * q, Color.BLUE);
196:
197: }
198: }
199: }
200:
201: }
202:
203: }
204:
205: public class SkipSwing {
206:
207: private SkipSwing() {
208: }
209:
210: public static void main(final String[] arg) {
211: JFrame jf = new JFrame("Experimenting skip inverted indices...");
212:
213: jf.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
214: jf.setSize(600, 400);
215: Container jfc = jf.getContentPane();
216: jfc.setLayout(new BorderLayout());
217:
218: DrawPanel dp = new DrawPanel();
219: jfc.add(new InputPanel(dp), BorderLayout.SOUTH);
220: jfc.add(dp, BorderLayout.CENTER);
221:
222: jf.setVisible(true);
223: }
224:
225: }
226:
227: // Local Variables:
228: // mode: jde
229: // tab-width: 4
230: // End:
|