Double-linked lists in Java
package com.chuckkann.datastructures.indexedlist;
import com.chuckkann.datastructures.Collection;
import com.chuckkann.datastructures.DataStructureException;
import com.chuckkann.datastructures.DsIterator;
import com.chuckkann.datastructures.IndexedList;
import java.util.Comparator;
public class DoubleLinkedList> implements IndexedList {
private static final long serialVersionUID = 1L;
private int numElements;
private DoubleLinkedList.Node head;
private DoubleLinkedList.Node tail;
/**
* Constructor to create an instance of the class.
*/
public DoubleLinkedList() {
numElements = 0;
head = null;
tail = null;
}
/* (non-Javadoc)
* @see com.chuckkann.datastructures.Collection#size()
*/
@Override
public int size() {
return numElements;
}
/* (non-Javadoc)
* @see com.chuckkann.datastructures.Collection#iterator()
*/
@Override
public DsIteratoriterator() {
return (DsIterator) new DoubleLinkedList.ListLinkedInArrayIterator();
}
/* (non-Javadoc)
* @see com.chuckkann.datastructures.Collection#isEmpty()
*/
@Override
public booleanisEmpty() {
return (numElements == 0);
}
/* (non-Javadoc)
* @see com.chuckkann.datastructures.Collection#clear()
*/
@Override
public void clear() {
numElements = 0;
head = null;
tail = null;
}
/* (non-Javadoc)
* @see com.chuckkann.datastructures.IndexedList#add(java.lang.Comparable)
*/
@Override
public void add(E element) {
add(numElements, element);
}
/* (non-Javadoc)
* @see com.chuckkann.datastructures.IndexedList#add(int, java.lang.Comparable)
*/
@Override
public void add(int index, E element) {
// check if index is valid
if (index < 0 || index >numElements)
throw new ArrayIndexOutOfBoundsException();
//
// Add element to the IndexedList
//
// Add item to list
// case 1 : add at start of list
if (index == 0) {
if (head == null) { // IndexedList is empty
tail = head = new DoubleLinkedList.Node(element, null, null);
}
else { // IndexedList has elements
head = new DoubleLinkedList.Node(element, head, null);
// set prev pointer of the previous head to current head
head.nextPtr.prevPtr = head;
}
numElements = numElements + 1;
}
// case 2 : add at end of list
else if (index == numElements) {
// create node with previous link to current tail
DoubleLinkedList.Node next = new DoubleLinkedList.Node(element, null, tail);
tail.setNextPtr(next);
tail = next;
numElements = numElements + 1;
}
// case 3 : add is in the middle of the list
else {
// Find the insertion point
DoubleLinkedList.NodefoundPtr = findPrevPtr(index);
// Insert new Node with element
DoubleLinkedList.NodenewPtr = new DoubleLinkedList.Node(element, foundPtr.getNextPtr(), foundPtr);
newPtr.getNextPtr().prevPtr = newPtr;
foundPtr.setNextPtr(newPtr);
numElements = numElements + 1;
}
}
@Override
public void add(CollectionelementsCollection) throws DataStructureException {
if (this == elementsCollection)
throw new DataStructureException("You cannot add a Collection to itself");
add(numElements, elementsCollection);
}
/* (non-Javadoc)
* @see com.chuckkann.datastructures.IndexedList#add(int, com.chuckkann.datastructures.Collection)
*/
@Override
public void add(int index, CollectionelementsCollection) throws DataStructureException {
// If the add(index, element) method is called, it requires that the chain is walked
// each time to find the insertion point. This is O(m*n), where n is the size
// of the original collection, and m is size of the added collection. This
// could be O(n^2) if n and m are approximately the same size. Make a better implementation.
if (this == elementsCollection)
throw new DataStructureException("You cannot add a Collection to itself");
int ip = index; // ip is insertion point
for (E element: elementsCollection)
{
this.add(ip, element);
ip = ip + 1;
}
}
@Override
public void add(E[] elementsArray) {
add(numElements, elementsArray);
}
/* (non-Javadoc)
* @see com.chuckkann.datastructures.IndexedList#add(int, java.lang.Comparable[])
*/
@Override
public void add(int index, E[] elementsArray) {
if (index < 0 || index >numElements)
throw new IndexOutOfBoundsException();
// The add(index, element) method is called, it requires that the chain is walked
// each time to find the insertion point. This is O(m*n), where n is the size
// of the original collection, and m is size of the added collection. This
// could be O(n^2) if n and m are approximately the same size.
// Make a better implementation.
int ip = index; // ip is insertion point
for (E element: elementsArray)
{
this.add(ip, element);
ip = ip + 1;
}
}
/* (non-Javadoc)
* @see com.chuckkann.datastructures.IndexedList#remove(int)
*/
@Override
public E remove(int index) {
// check if index is valid
if (index < 0 || index >= numElements)
throw new ArrayIndexOutOfBoundsException();
E retVal = null;
// First item on the list
if (index == 0) {
retVal = head.getElement();
head = head.getNextPtr();
//set previous pointer of the new head to null
head.prevPtr = null;
numElements = numElements - 1;
if (head == null)
tail = head;
}
else {
// Stop one before the current item to get a pointer to the item to remove
// Get the value of the item to return it.
DoubleLinkedList.Nodeptr = findPrevPtr(index);
retVal = ptr.getNextPtr().getElement();
// Take element out of list
// Put free item on free space
ptr.setNextPtr(ptr.getNextPtr().getNextPtr());
numElements = numElements - 1;
if (index == numElements) {
tail = ptr;
}
else {
// set previous pointer of next node to this node
ptr.nextPtr.prevPtr = ptr;
}
}
return retVal;
}
/* (non-Javadoc)
* @see com.chuckkann.datastructures.IndexedList#retrieve(int)
*/
@Override
public E retrieve(int index) {
// check if index is valid
if (index < 0 || index >= numElements)
throw new ArrayIndexOutOfBoundsException();
DoubleLinkedList.NodenextPtr = head;
for (int i = 0; i< index; i++) {
nextPtr = nextPtr.getNextPtr();
}
return nextPtr.getElement();
}
/* (non-Javadoc)
* @see com.chuckkann.datastructures.IndexedList#set(int, java.lang.Comparable)
*/
@Override
public E set(int index, E element) {
// check if index is valid
if (index < 0 || index >= numElements)
throw new ArrayIndexOutOfBoundsException();
DoubleLinkedList.Nodeptr = findPrevPtr(index+1);
E retVal = ptr.getElement();
ptr.setValue(element);
return retVal;
}
/* (non-Javadoc)
* @see com.chuckkann.datastructures.IndexedList#indexOf(java.lang.Comparable)
*/
@Override
public int indexOf(E element) {
return indexOf(0, element, null);
}
/* (non-Javadoc)
* @see com.chuckkann.datastructures.IndexedList#indexOf(int, java.lang.Comparable)
*/
@Override
public int indexOf(int index, E element) {
return indexOf(index, element, null);
}
/* (non-Javadoc)
* @see com.chuckkann.datastructures.IndexedList#indexOf(java.lang.Comparable, java.util.Comparator)
*/
@Override
public int indexOf(E element, Comparator comparator) {
return indexOf(0, element, comparator);
}
/* (non-Javadoc)
* @see com.chuckkann.datastructures.IndexedList#indexOf(int, java.lang.Comparable, java.util.Comparator)
*/
@Override
public int indexOf(int index, E element, Comparator comparator) {
// check if index is valid
if (index < 0 || index >numElements)
throw new ArrayIndexOutOfBoundsException();
// Ignore all nodes up to the index node
DoubleLinkedList.Nodeptr = head;
for (int i = 0; i< index; i++) {
ptr = ptr.getNextPtr();
}
// Loop to find the index of the next element matching
// by comparator or comparable. If not found, return -1.
for (int i = index; i comparator) {
DoubleLinkedList.Nodeptr = tail;
for (int i = numElements-1; i>= 0; i--) {
if (comparator != null) {
if (comparator.compare(ptr.getElement(), element) == 0)
return i;
}
else {
if ((ptr.getElement()).compareTo(element) == 0)
return i;
}
ptr = ptr.getPrevPtr();
}
return -1;
}
/**
* @param index
* @return
*/
private DoubleLinkedList.NodefindPrevPtr(int index) {
DoubleLinkedList.NodenextPtr = head;
for (int i = 0; i< (index-1); i++) {
nextPtr = nextPtr.getNextPtr();
}
return nextPtr;
}
/**
* @author chuck
*
* @param
*/
private static class Node> {
private E value;
private DoubleLinkedList.NodenextPtr;
private DoubleLinkedList.NodeprevPtr;
public Node(E value, DoubleLinkedList.NodenextPtr, DoubleLinkedList.NodeprevPtr) {
this.value = value;
this.nextPtr = nextPtr;
this.prevPtr = prevPtr;
}
public DoubleLinkedList.NodegetNextPtr() {
return this.nextPtr;
}
public DoubleLinkedList.NodegetPrevPtr() {
return this.prevPtr;
}
public void setNextPtr(DoubleLinkedList.Node index) {
this.nextPtr = index;
}
public void setPrevPtr(DoubleLinkedList.Node index) {
this.prevPtr = index;
}
public E getElement() {
return this.value;
}
public E setValue(E value) {
E retVal = this.value;
this.value = value;
return retVal;
}
public String toString() {
if (value == null)
return "null";
return value.toString();
}
}
/**
* @author chuck
*
*/
private class ListLinkedInArrayIterator implements DsIterator {
DoubleLinkedList.NodelastPtr; // lastPtr needed for remove
DoubleLinkedList.NodemyPtr;
public ListLinkedInArrayIterator() {
lastPtr = null;
myPtr = head;
}
@Override
public booleanhasNext() {
if (myPtr == null)
return false;
else
return true;
}
@Override
public booleanhasPrevious() {
if (lastPtr == null)
return false;
else
return true;
}
@Override
public E next() {
E retvar = (E)myPtr.getElement();
lastPtr = myPtr;
myPtr = myPtr.getNextPtr();
return retvar;
}
@Override
public E previous() {
E retvar = (E)lastPtr.getElement();
myPtr = lastPtr;
lastPtr = lastPtr.getPrevPtr();
return retvar;
}
@Override
public void setIteratorToStart() {
while (hasPrevious()) {
previous();
}
}
@Override
public void setIteratorToEnd() {
while (hasNext()) {
next();
}
}
@Override
public void remove() {
if (lastPtr == null)
myPtr = null;
else {
lastPtr.setNextPtr(myPtr.getNextPtr());
myPtr.getNextPtr().prevPtr = lastPtr;
myPtr = lastPtr;
numElements = numElements - 1;
}
}
}
}
Game in Java
import processing.core.*;
import java.util.Random;
import java.util.Vector;
public class Swarm extends PApplet {
public static void main(String args[]) {
PApplet.main("Swarm");
}
// All the creatures (the first is the main one, the children are next)
Vector creatures;
// The enemy (moves towards the player as it spawns)
Enemy enemy;
// So we can just use rnd each time
Random rnd = new Random();
// Have we collided with the enemy
boolean collided;
// Delay after colliding before restarting the game
int delay;
@Override
public void settings() {
// TODO: Customize screen size and so on here
size(900, 900);
// An initial size of 20, doing well if we get that many
creatures = new Vector<>(20);
// Add the initial creature
creatures.add(new Creature(1));
//for (int i = 0; i < 170; i++) creatures.add(new Creature(0.3f));
// Create the enemy to move to the middle of the screen initially
enemy = new Enemy(width/2,height/2);
// Not collided
collided = false;
// Delay before restart once collided is set
delay = 100;
}
@Override
public void setup() {
// TODO: Your custom drawing and setup on applet start belongs here
clear();
// Makes the art cleaner
noStroke();
}
@Override
public void draw() {
// TODO: Do your drawing for each frame here
// clear();
// Set the background to a light grey
background(51);
// Draw all the creatures
for (Creature creature : creatures) {
// Move towards the mouse position
creature.move(mouseX, mouseY);
// Draw it
creature.draw();
// Did we collide with any
collided |= creature.collides(enemy);
}
// Move the enemy (it respawns once it goes out of range, and returns true to spawn a new creature)
if (enemy.move(mouseX, mouseY)) {
creatures.add(new Creature(0.3f));
}
// Draw the enemy (it changes color to gray once it collides)
enemy.draw(collided);
// If we collided, then start countdown to reset
if (collided) {
delay--;
if (delay == 0) settings();
}
}
private class Creature {
// The scale of the shape (1 is the base size)
private final float scale;
float x;
float y;
float xvel;
float yvel;
// Offset angle (in radians)
float angle;
// Distance from origin (x, y)
float offset;
// Can it collide
boolean collides;
// Using radius squared means we can avoid doing square root
float radius_squared;
public Creature(float scale) {
this.scale = scale;
angle = 0;
offset = 0;
xvel = 0;
yvel = 0;
collides = true;
// Size is 96 pixels, so radius is 48
radius_squared = 48 * 48;
if (scale != 1) {
// Distance from the center (increases as the number of creatures increases)
offset = 70 + rnd.nextInt(70 + creatures.size());
// Initial angle (approximately 0 - pi)
angle = rnd.nextInt(3141) / 1000f;
// Can't be hit (until it starts getting close)
collides = false;
// The size to collide with
radius_squared = (48 * scale) * (48 * scale);
}
}
// Move towards x, y
public boolean move(int x, int y) {
// The difference between x positions
float dx = x - this.x;
// Is it close, then rapidly adjust velocity
if (dx < 32 && dx > -32) {
if (dx > 0.25 && xvel > 0) {
xvel -= 0.5f;
}
if (dx < -0.25 && xvel < 0) {
xvel += 0.5f;
}
} else {
// Accelerate to left or right depending on direction
if (dx > 0) {
if (xvel < 5) xvel += 0.25;
}
else
{
if (xvel > -5) xvel -= 0.25;
}
}
this.x += xvel;
float dy = y - this.y;
// Is it close, then rapidly adjust velocity
if (dy < 32 && dy > -32) {
if (dy > 0.25 && yvel > 0) {
yvel -= 0.5f;
}
if (dy < -0.25 && yvel < 0) {
yvel += 0.5f;
}
} else {
// Accelerate vertically depending on direction
if (dy > 0) {
if (yvel < 5) yvel += 0.25;
}
else
{
if (yvel > -5) yvel -= 0.25;
}
}
this.y += yvel;
// Once it gets close, make it so it can collide
if (dx < 10 && dx > -10 && dy < 10 && dy > -10) {
collides = true;
}
return false;
}
public void draw() {
// Light grey
fill(192);
// Position to display at
float cx = x + offset * sin(angle);
float cy = y + offset * cos(angle);
// Main circle
ellipse(cx, cy, 96 * scale, 96 * scale);
// Black eyes
fill(30);
ellipse(cx - 30 * scale, cy - 30 * scale, 32 * scale, 32 * scale);
ellipse(cx + 30 * scale, cy - 30 * scale, 32 * scale, 32 * scale);
// Eye balls
fill(200);
ellipse(cx - 25 * scale, cy - 35 * scale, 12 * scale, 12 * scale);
ellipse(cx + 25 * scale, cy - 35 * scale, 12 * scale, 12 * scale);
// Mouth
fill(30);
triangle(cx - 35 * scale, cy + 10 * scale, cx + 35 * scale, cy + 10 * scale, cx, cy + 30 * scale);
// Orbit around the main
angle += offset / 10000;
}
public boolean collides(Creature other) {
// If it can't collide, then exit
if (!collides) return false;
// Calculate the screen position
float cx = x + offset * sin(angle);
float cy = y + offset * cos(angle);
// Get the delta x squared
float xd = (cx - other.x) * (cx - other.x);
// Get the delta y squared
float yd = (cy - other.y) * (cy - other.y);
// Rather than sqrt(xd+yd) < radius we can just compared the radius squared with distance squared
return (xd + yd < radius_squared + other.radius_squared);
}
}
private class Enemy extends Creature {
public Enemy(int targetX, int targetY) {
super(1);
// Head towards targetX, targetY
reset(targetX, targetY);
}
private void reset(int targetX, int targetY) {
// Randomly pick an edge to start on
switch (rnd.nextInt(3)) {
case 0:
y = -50;
x = rnd.nextInt(width);
break;
case 1:
y = height+50;
x = rnd.nextInt(width);
break;
case 2:
x = -50;
y = rnd.nextInt(height);
break;
case 3:
x = width+50;
y = rnd.nextInt(height);
break;
}
// Move towards player (speeds up based on the number of creatures)
int spd = 175 - creatures.size();
if (spd < 50) spd = 50;
xvel = (targetX - x) / spd;
yvel = (targetY - y) / spd;
}
public boolean move(int targetX, int targetY) {
// Move towards original player position
x += xvel;
y += yvel;
// Offscreen so reset
if (x > width + 100 || x < - 100) {
reset(targetX, targetY);
return true;
}
// Offscreen so reset
if (y > height + 100 || y < - 100) {
reset(targetX, targetY);
return true;
}
// Not offscreen
return false;
}
public void draw(boolean collides) {
// Once it has collided, display in grey
if (collides) {
fill(144);
} else {
// Make it an angry red
fill(180, 40, 40);
}
// Squarish shape (rounded corners)
rect(x - 40, y - 40, 80, 80, 25);
fill(30);
// Draw 3 fangs
for (int i = 0; i < 3; i++) {
triangle(x - 30 + i * 20, y + 20, x - 10 + i * 20, y + 20, x - 20 + i * 20, y + 30);
}
// Draw eyes
fill(196);
ellipse(x - 30, y - 30, 30, 30);
ellipse(x + 30, y - 30, 30, 30);
// Draw eye balls, that indicate the direction it is heading in
fill(30);
ellipse(x - 30 + xvel * 3, y - 30 + yvel * 3, 10, 10);
ellipse(x + 30 + xvel * 3, y - 30 + yvel * 3, 10, 10);
}
}
}