The Big Programming Thread - Page 685

On December 03 2015 05:55 spinesheath wrote:
Typically a stack only has one generic argument and that's the type of the data it holds. I don't know a reason why I would want to specify a "StackNode" type. I want to put stuff on the stack and pop it off. Let the stack figure out how to hold that stuff.

In C# you could specify that your generic type parameter needs to have a parameterless constructor, but it doesn't seem like Java has that functionality. So you're left with using a IStackNodeFactory interface that has a CreateStackNode method, or trying to find and call a somehow fitting constructor via reflection (which is like rolling a dice). The factory requires the user to provide yet another class just to use your stack. For a simple container type that's waaaaaaaay to complex.

On December 03 2015 05:56 WarSame wrote:
Ahhh great point. So I should allow them to, for example, make a MinStack, but then just fill it with MinStackNodes automatically? It ended up this way because I was having problems with inheriting MinStack from Stack - I'll give your feedback a whirl and see what I come up with. Thanks!

EDIT: I'm not really sure how to replace the StackNodes with MinStackNodes after the inheritance, though. That was the original reason that I did all the weird stuff I didd.

On December 03 2015 15:52 waffelz wrote:
Could someone give me a hint where should I look if I want to know how comparing really works?
Like:

if (string a == string b)
{
}

I mean on a deep down level. How exactly does the comparison work? Did the strings get compared for each bit or is there some optimisation involved (I assume so in terms of strings). Do they get compared per character? How does it work on other data-types? Just need a general direction where to go for this kind of stuff since google keeps flooding me with “how to”-articles.

I have to write a small paper on the subject of searching this semester and would like to actually figure something out myself rather than acting like I did by simply comparing different search algorithms and thought that figuring out a few improved algorithms for cases where you normally would have to use linear searchalgorithms / lazysearch because your data might be unsorted / doesn’t support the usual algorithms properly.

EDIT: I should also note that my results aren’t that important, focus of this is the scientific progress, so it would be fine if I came to the conclusion that my algorithms aren’t better (which I assume is most likely besides in some very special cases). I just liked to include some actual testing where the results have the potential to surprise me while also being able to justify the time I need to sink in compared to the low CP I get for it.

On December 03 2015 05:16 WarSame wrote:
So I've been at the library 9-6 for today and yesterday preparing for my job. I've run into a snag with Java, and I can't understand the answers I've googled.

I'm creating a generic stack Stack<T extends StackNode<E>, E>, with StackNode<E>. However, I can't declare a new StackNode in my Stack properly. Using

T node = new T(data);

throws an error on the T, saying it can't be instantiated. Google results say this is due to erasure, but not really how to get around it. This seems to be the best answer, but I can't figure out how to apply it to my specific case. Where do I place the function mentioned? Where do I call it from? How do you call it? The comments tried to clear it up but I can't understand those well enough, either.

My current attempt in Stack looks like:

public class Stack<T extends StackNode<E>, E> {
	private T top;
	private int size;
	public Stack(E data){
		T node = createContents(T.class, data);
		this.top = node;
	}
}

and in StackNode:

public class StackNode<E> {
	private E data;
	private StackNode<E> next;
	public E createContents(Class<E> clazz, E data) throws InstantiationException, IllegalAccessException{
		return clazz.newInstance();
	}
	public StackNode(E data){
		this.data = data;
		this.next = null;
	}
}

However, Stack has 2 errors - it can't find CreateContents and it says that T.class is an illegal literal. Further, the "constructor" is only able to call the empty constructor. I think that can be handled by calling another function that sets the value of data, although I'm not sure how to get the value where it needs to be. If anyone can give me advice on how to do this or tell me a better way to do this I'm all ears. Thanks!

class Stack<E> {
    private static class Node<E> {
        ... //don't need to keep this private can just access fields directly really, this class is hidden in stack already
    }
    ...
}

class MinStack extends Stack<E> {
     private Node minimum;

     public MinStack(Comparator<E> comparator) {
        ...
     }
     
     @Override
     public Node push (E data) {
         super(data);
         //do your logic to update minimum using compartor
     }

     public E minimum () { ... }
}

On December 03 2015 17:25 Ropid wrote:
It depends on the language you talk about, but string is probably not a basic data type and is defined in the language itself and you have the source of that installed somewhere. You could look up the source of "==", though it's probably terrible to read.

If you use an IDE like Visual Studio for your stuff, you could try to step into the "==" function call with the debugger. You could follow what's done on the two strings step-by-step.

On December 03 2015 17:04 teamamerica wrote:


I'd also mention that reflection seems unnecessary. StackNode seems like a prime candidate for a private static nested class inside stack, no need for it to be public. I see what you're going for with MinStack but I'd argue that the node knowing the minimum is confusing concerns. What is minimum in the context of a node? It doesn't even know it's part of a bigger data structure. If you're going to have that you can just keep track of min on the stack itself.

Not written Java in a while but this is how I'd imagine itd look. Note I use a Comparator rather then using Comparable because a lot of classes don't implement Comparable so why force someone to wrap them to use your cool codez? See https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html as an example for how a Java collection that inherits from an unordered collection offers an ordered subclass.

class Stack<E> {
    private static class Node<E> {
        ... //don't need to keep this private can just access fields directly really, this class is hidden in stack already
    }
    ...
}

class MinStack extends Stack<E> {
     private Node minimum;

     public MinStack(Comparator<E> comparator) {
        ...
     }
     
     @Override
     public Node push (E data) {
         super(data);
         //do your logic to update minimum using compartor
     }

     public E minimum () { ... }
}