skipswing.java

MG4J (Managing Gigabytes for Java) is a free full-text search engine for large document collections

package it.unimi.dsi.mg4j.test;

import it.unimi.dsi.bits.Fast;

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Component;
import java.awt.Container;
import java.awt.Graphics;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.BorderFactory;
import javax.swing.Box;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.JSlider;
import javax.swing.JTextField;
import javax.swing.event.ChangeEvent;
import javax.swing.event.ChangeListener;


@SuppressWarnings("serial") class InputPanel extends JPanel {
	private JTextField qtf, htf;
	private JSlider js;

	InputPanel( final DrawPanel dp ) { 
	
		JLabel ql, hl, cl;
		int q = 3, h = 3, cache = 12;

		ActionListener clqh = new ActionListener() {
				public void actionPerformed( ActionEvent e ) {
					try {
						int q, h, cache;
						q = Integer.parseInt( qtf.getText() );
						h = Integer.parseInt( htf.getText() );
						cache = js.getValue();
						js.setMaximum( q * ( 1 << h ) );
						if ( cache > q * ( 1 << h ) ) {
							cache = q * ( 1 << h );
							js.setValue( cache );
						}
						dp.setValues( q, h, cache );
						dp.repaint();
					} catch ( Exception exc ) {
						JOptionPane.showMessageDialog( null, exc.getMessage(), "Alert", JOptionPane.ERROR_MESSAGE );
					}
				}
			};

		//Box box = Box.createHorizontalBox();
		JPanel box = new JPanel();

		box.add( ql = new JLabel( "q = " ) );
		box.add( qtf = new JTextField( "3", 3 ) );
		ql.setLabelFor( qtf );
		qtf.addActionListener( clqh );
		box.add( Box.createHorizontalStrut( 20 ) );

		box.add( hl = new JLabel( "h = " ) );
		box.add( htf = new JTextField( "3", 3 ) );
		hl.setLabelFor( htf );
		htf.addActionListener( clqh );
		box.add( Box.createHorizontalStrut( 20 ) );


		Box vbox = Box.createVerticalBox();
		cl = new JLabel( "Actual cache size", JLabel.CENTER );
		cl.setAlignmentX( Component.CENTER_ALIGNMENT );
		vbox.add( cl );

		js = new JSlider( JSlider.HORIZONTAL, 0, q * ( 1 << h ), cache );
		js.setMajorTickSpacing( 10 );
		js.setMinorTickSpacing( 1 );
		js.setPaintTicks( true );
		js.setPaintLabels( true );
		js.setBorder( BorderFactory.createEmptyBorder( 0, 0, 10, 0) );
		js.addChangeListener( new ChangeListener() {
				public void stateChanged( ChangeEvent e ) {
					JSlider source = (JSlider)e.getSource();
					//  if ( source.getValueIsAdjusting() ) return;
					try {
						int q, h, cache;
						q = Integer.parseInt( qtf.getText() );
						h = Integer.parseInt( htf.getText() );
						cache = source.getValue();
						dp.setValues( q, h, cache );
						dp.repaint();
					} catch ( Exception exc ) {
						JOptionPane.showMessageDialog( null, exc.getMessage(), "Alert", JOptionPane.ERROR_MESSAGE );
					}
				}
			});
		cl.setLabelFor( js );
		vbox.add( js );

		box.add( vbox );

		add( box );
		dp.setValues( q, h, cache );
		dp.repaint();
	}

}



@SuppressWarnings("serial") class DrawPanel extends JPanel {
	static final int SS = 15;
	int q, h, cache;
	int b;

	void setValues( int q, int h, int cache ) {
		if ( cache > ( 1 << h ) * q ) 
			throw new IllegalArgumentException( "Maximum cache size: " + b );
		this.q = q;
		this.h = h;
		this.cache = cache;
		b = ( 1 << h ) * q;
	}
	
	private void paintSquare( Graphics g, int i, int h, boolean exists ) {
		int x = getWidth();
		int y = getHeight();
	
		int xcenter = x/2 - b*SS/2 + i*SS;
		int ycenter = 2*y/3 - ( h + 1 ) * SS;

		if ( exists ) g.setColor( Color.BLACK );
		else g.setColor( Color.YELLOW );

		g.fill3DRect( xcenter - SS/2 + 1, ycenter - SS/2 + 1, SS - 2, SS - 2, false );
	}

	private void drawLine( Graphics g, int i, int h, int jt, Color c ) {
		int x = getWidth();
		int y = getHeight();
	
		int xi = x/2 - b*SS/2 + i*SS;
		int xjt = x/2 - b*SS/2 + jt *SS;
		int yy = 2*y/3 - ( h + 1 ) * SS;

		g.setColor( c );
		g.drawLine( xi, yy, xjt, yy );
		g.fillOval( xi - 2, yy - 2, 4, 4 );
		g.fillOval( xjt - 2, yy - 2, 4, 4 );
	}

	public void paint( Graphics g ) {
		g.clearRect( getX(), getY(), getWidth(), getHeight() );

		for ( int i = 0; i < b; i++ )
			paintSquare( g, i, -1, i < cache );
	
	
		for ( int passage = 0; passage < 2; passage++ ) 
			for ( int kq = 0; kq < b; kq++ ) {
				int nextAfter = ( cache + q - 1 ) / q;
				int s, st, k, pt, p;
		
				if ( kq % q == 0 ) {
			
					// Skip record number k
					k = kq / q;
					// Compute the height of the skip tower (s+1)...
					s = st = ( k == 0 )? h : Fast.leastSignificantBit( k ); // TZ(k)
					if ( cache < b ) 
						s = Math.min( s, Fast.mostSignificantBit( cache / q - k ) );
			
					for ( int hh = 0; hh <= st; hh++ ) 
						if ( passage == 1 )
							paintSquare( g, kq, hh, hh <= s && kq < cache );
						else
							if ( hh <= s && kq < cache ) {
								pt = k + ( 1 << hh );
								p = Math.min( pt, nextAfter );
								if ( p < pt ) { 
									drawLine( g, kq, hh, pt * q, Color.WHITE );
									System.out.println( "From " + kq + " (skip index " + k + ") at height " + hh + "(2^h=" + (1<<hh) +  
														") should go to " + pt + " but goes to " + p + " instead" );
								}
								drawLine( g, kq, hh, p * q, Color.BLUE );

							}
				}
			}

	}

}


public class SkipSwing {

	private SkipSwing() {}

	public static void main( final String[] arg ) {
		JFrame jf = new JFrame( "Experimenting skip inverted indices..." );

		jf.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
		jf.setSize( 600, 400 );
		Container jfc = jf.getContentPane();
		jfc.setLayout( new BorderLayout() );

		DrawPanel dp = new DrawPanel();
		jfc.add( new InputPanel( dp ), BorderLayout.SOUTH );
		jfc.add( dp, BorderLayout.CENTER );

		jf.setVisible( true );
	}

}


// Local Variables:
// mode: jde
// tab-width: 4
// End: