Sorting ArrayList with almost differnet Objects

Newbie & Debugging Questions
#1

Hey guys,

I need to sort an ArrayList but the problem is, even though each class is Extending the class that the ArrayList holds, it can be sorted.

My Sorting Class


public class Sort implements Comparator<Entity>{
	    public int compare(Entity e1, Entity e2) {
	        if(e1.getX() > e2.getX()&&e1.getY() > e2.getY()){
	            return 1;
	        } else {
	            return -1;
	        }
	    }
	    public int compare(Block e1, Block e2) {
	        if(e1.getX() > e2.getX()&&e1.getY() > e2.getY()){
	            return 1;
	        } else {
	            return -1;
	        }
	    }
	    public int compare(Block e1, Player e2) {
	        if(e1.getX() > e2.getX()&&e1.getY() > e2.getY()){
	            return 1;
	        } else {
	            return -1;
	        }
	    }
	}

Used:


Collections.sort(ents,new Sort());

my Array List:


public static ArrayList<Entity>ents=new ArrayList<Entity>();

Entity Class(none are actually in array, other classes extend this class):


package com.iso.ent;

import com.badlogic.gdx.graphics.Texture;
import com.badlogic.gdx.graphics.g2d.Sprite;
import com.badlogic.gdx.graphics.g2d.SpriteBatch;

public class Entity {
	public float x, y, z;
	Sprite sprite;
	public float cartx;
	public float carty;
	public Entity(float cartx, float carty, float z) {
		this.z = z;
		this.cartx=cartx*40/2;
		this.carty=carty*40/2;
		x = (cartx - carty) * 40 / 2;
		y = (((carty + cartx) / 2) + z) * 40 / 2;
		sprite = new Sprite();
	}

	public Entity(float cartx, float carty, float z, Sprite sprite) {
		this.z = z;
		x = (cartx - carty) * 40 / 2;
		y = (((carty + cartx) / 2) + z) * 40 / 2;
		this.sprite = sprite;
	}
	public void draw(SpriteBatch batch){}

	public float getX() {
		return x;
	}

	public void setX(float x) {
		this.x = x;
	}

	public float getY() {
		return y;
	}

	public void setY(float y) {
		this.y = y;
	}

	public float getZ() {
		return z;
	}

	public void setZ(float z) {
		this.z = z;
	}

	public Sprite getSprite() {
		return sprite;
	}

	public void setSprite(Sprite sprite) {
		this.sprite = sprite;
	}

	public void setSprite(Texture tex) {
		this.sprite = new Sprite(tex);
	}

}

Any help would be great

#2

Only the [icode]int compare(Entity e1, Entity e2)[/icode] method will ever be used in the Comparator. This is, because this method implements the interface method, the other two are just other methods of the Sort class.

If you want to do a sort based on types, you will have to do a big if/else clause in the compare method where you check & cast the types as you need.

#3

I changed my code but I’m still getting the same exception:



Exception in thread "LWJGL Application" java.lang.IllegalArgumentException: Comparison method violates its general contract!
	at java.util.TimSort.mergeHi(Unknown Source)
	at java.util.TimSort.mergeAt(Unknown Source)
	at java.util.TimSort.mergeCollapse(Unknown Source)
	at java.util.TimSort.sort(Unknown Source)
	at java.util.TimSort.sort(Unknown Source)
	at java.util.Arrays.sort(Unknown Source)
	at java.util.Collections.sort(Unknown Source)
	at com.iso.main.Game.render(Game.java:85)
	at com.badlogic.gdx.backends.lwjgl.LwjglApplication.mainLoop(LwjglApplication.java:207)
	at com.badlogic.gdx.backends.lwjgl.LwjglApplication$1.run(LwjglApplication.java:114)

Changed sort class:


public class Sort implements Comparator<Entity> {
		public int compare(Entity e1, Entity e2) {
			if (e1.getClass() == Entity.class && e2.getClass() == Entity.class) {
				if (e1.getX() > e2.getX() && e1.getY() > e2.getY()) {
					return 1;
				} else {
					return -1;
				}
			} else if (e1.getClass() == Entity.class
					&& e2.getClass() == Block.class) {
				Block b2=(Block)e2;
				if (e1.getX() > b2.getX() && e1.getY() > b2.getY()) {
					return 1;
				} else {
					return -1;
				}

			} else if (e1.getClass() == Block.class
					&& e2.getClass() == Entity.class) {
				Block b1=(Block)e1;
				if (b1.getX() > e2.getX() && b1.getY() > e2.getY()) {
					return 1;
				} else {
					return -1;
				}
			} else if (e1.getClass() == Block.class
					&& e2.getClass() == Block.class) {
				Block b1=(Block) e1;
				Block b2=(Block) e2;
				if (b1.getX() > b2.getX() && b1.getY() > b2.getY()) {
					return 1;
				} else {
					return -1;
				}
			} else if (e1.getClass() == Player.class
					&& e2.getClass() == Block.class) {
				Block temp=(Block)e2;
				Player p=(Player)e1;
				if (p.getX() >  temp.getX()&& p.getY() > temp.getY()) {
					return 1;
				} else {
					return -1;
				}
			} else if (e1.getClass() == Block.class
					&& e2.getClass() == Player.class) {
				Block temp=(Block)e1;
				Player p=(Player)e2;
				if (temp.getX() > p.getX() && temp.getY() > p.getY()) {
					return 1;
				} else {
					return -1;
				}
			}else{
				return -1;
			}
		}

	}
#4

Your comparison method is invalid. You’re required to follow a specific “contract”. Your code needs to satisfy this:

if x < y and y < z then x < z

It currently does not. Your if-statement comparing X and Y makes no sense actually. What are you trying to accomplish?

EDIT:

  1. You should be using [icode]e1 instanceof Entity[/icode]
  2. If you already know that your objects are all Entities (since that’s the only thing your Comparator works on) there is no need to do any class testing at all. You seem to have problems grasping basic object oriented concepts, so I think you should focus more on learning Java before you try making games, no offense. This is a game developing forum. We’re not here to teach you the basics of Java (and yes, this is part of the basics…).
#5

All it does is check to see if a block is in front of another block. I know the method works because I have tested it out with just the Block class (which extends Entity) but now I need to be able to sort all Entity types.

#6

Please read my edit. Your code has never worked since your compare() function is not doing what it should. Just because it “worked” doesn’t mean that it does not break the contract. The built-in sort() function does not always detect this.

#7

:expressionless: There’s no need to remind me what goes on within this forum. I’m a self taught programmer so i kind-of just learn something when I need to learn it. I’ve never needed to do anything that involved

instanceof

so I don’t know about it. I’m not automatically a beginner programmer because I lacked to read up on one thing so please don’t treat me as such. I may not know the exact terminology of things, but most of the time I know what I am talking about.

besides, when I changed my code to:


public class Sort implements Comparator<Entity>{
		public int compare(Entity e1, Entity e2) {
			if (e1 instanceof Entity && e2 instanceof Entity) {
				if (e1.getX() > e2.getX() && e1.getY() > e2.getY()) {
					return 1;
				} else {
					return -1;
				}
			}else{
				return -1;
			}

I still got the same error. I just changed it into a shorter version of my old code. I think (so I’m not sure) the error comes from the fact that I’m not putting pure Entities to get sorted. so this line:

public int compare(Entity e1, Entity e2) {

since it could be:

public int compare(Block e1,Block e2) {

so any other help would be great :expressionless:

#8

This one line itself is a big warning sign. Seriously, you’re not ready. I’m sorry, but I’m really not trying to be mean here.

I’ll give you one last hint: The problem lies in this line not being consistent with the contract of compare(): [icode]if (e1.getX() > e2.getX() && e1.getY() > e2.getY()) {[/icode]

#9

In line with what theagentd said earlier, this isn’t gamedev-specific. This can easily be found on SO: http://stackoverflow.com/questions/9486605/comparison-method-violates-its-general-contract-in-java-7

#10

I don’t really get why would you need to write 100 lines comparator?

#11

It’s possible, but not for this task. Where do you see a 100-line comparator?

#12

I think you should write so:

public int compare(Entity e1, Entity e2) {
        if (e1.getX() < e2.getX()) 
         return -1;
        if (e1.getX() > e2.getX())
         return 1;
        if (e1.getY() < e2.getY())
         return -1;
        if (e1.getY() > e2.getY())
         return 1;
        return 0;
 }
}