Skip to content

Instantly share code, notes, and snippets.

@riobard
Created Mar 20, 2012
Embed
What would you like to do?
Koch Snowflake Generator using Stack based on Linked List
/*
* common import used for drawing.
*/
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Dimension;
import java.awt.event.ActionListener;
import java.awt.event.ActionEvent;
import javax.swing.JPanel;
import javax.swing.JFrame;
class Stack<Item> {
private int N; // size of the stack
private Node first; // top of stack
// helper linked list class
private class Node {
private Item item;
private Node next;
}
public Stack() {
first = null;
N = 0;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return N;
}
public void push(Item item) {
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
N++;
}
public Item pop() {
if (isEmpty()) return null;
Item item = first.item;
first = first.next;
N--;
return item;
}
public static void main(String[] args) {
Stack<String> s = new Stack<String>();
s.push("hello");
s.push("world");
s.push("foo");
s.push("bar");
System.out.println("Size size = " + s.size());
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.pop());
System.out.println(s.pop());
}
}
interface SegmentsList {
void add( Segment seg );
Segment remove(); // return null if list is empty, otherwise return segment
int totalAdded(); // returns the total number of adds
int maximumSize(); // return the maximum size of the list
}
class Segment {
public int level, x1, y1, x2, y2;
public Segment(int level, int x1, int y1, int x2, int y2) {
this.level = level;
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
}
}
class SegStack extends Stack<Segment> implements SegmentsList {
private int add_cnt = 0;
public void add(Segment seg) {
this.add_cnt++;
push(seg);
}
public Segment remove() {
return pop();
}
public int totalAdded() {
return this.add_cnt;
}
public int maximumSize() {
return size();
}
}
public class KochGen extends JPanel implements ActionListener {
/*
* Configuration constants.
*/
private static final int INTERVAL = 1000; // 1000 ms
private static final int WINDOW_WIDTH = 250;
private static final int WINDOW_HEIGHT = 250;
private static final Color BG_COLOR = Color.WHITE;
private javax.swing.Timer timer;
/*
* instance variables.
*/
private int maxLevel = 5;
private int curLevel = 0;
/* keeps current window size */
private int width = -1;
private int height = -1;
private SegStack L;
public KochGen() {
setPreferredSize(
new Dimension( WINDOW_WIDTH, WINDOW_HEIGHT ) );
setBackground( BG_COLOR );
timer = new javax.swing.Timer(INTERVAL, this);
timer.start();
}
protected void paintComponent( Graphics g ) {
super.paintComponent( g );
Graphics2D g2d = (Graphics2D)g;
int w = getWidth();
int h = getHeight();
if ( w != width || h != height ) {
width = w;
height = h;
}
g.setColor( Color.red );
/* drawing code */
int s = Math.max(width,height) / 5;
kochSegment( g2d, curLevel, w/2, s/2, w-s, h-s );
kochSegment( g2d, curLevel, w-s, h-s, s, h-s );
kochSegment( g2d, curLevel, s, h-s, w/2, s/2 );
}
private void kochSegment(Graphics2D g, int level, int x1, int y1, int x2, int y2) {
L = new SegStack();
L.add(new Segment(level, x1, y1, x2, y2));
while (!L.isEmpty()) {
Segment seg = L.remove();
x1 = seg.x1;
x2 = seg.x2;
y1 = seg.y1;
y2 = seg.y2;
level = seg.level - 1;
if (level < 0) {
g.drawLine(x1, y1, x2, y2);
} else {
int dx = (x2-x1); int dy = (y2-y1);
int dx3 = dx/3; int dy3 = dy/3;
int ox = x1 + dx/2 + dy3; int oy = y1 + dy/2 - dx3;
L.add(new Segment(level, x1, y1, x1+dx3, y1+dy3));
L.add(new Segment(level, x1+dx3, y1+dy3, ox, oy ));
L.add(new Segment(level, ox, oy, x1+2*dx3, y1+2*dy3 ));
L.add(new Segment(level, x1+2*dx3, y1+2*dy3, x2, y2 ));
}
}
}
/**
* Invoked every animation step.
*/
public void actionPerformed( ActionEvent evt ) {
curLevel++;
if ( curLevel > maxLevel ) curLevel = 0;
repaint();
}
public static void runApplication( JPanel app ) {
/* create frame */
JFrame frame = new JFrame();
frame.setSize( app.getPreferredSize() );
frame.setTitle( app.getClass().getName() );
frame.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
frame.add( app );
frame.setVisible( true );
}
/*
* Create the frame to show the application
*/
public static void main( String[] args ) {
KochGen app = new KochGen();
runApplication(app);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment