Search found 491 matches

by scwizard
Mon Mar 09, 2009 9:15 pm UTC
Forum: Computer Science
Topic: How do I balance a pre-order or post-order binary tree?
Replies: 10
Views: 1137

Re: How do I balance a pre-order or post-order binary tree?

I thought about whole thing a great deal, and I'm now convinced it's not possible. This is basically because you don't really have the freedom to move things up or down (because all the large values are towards the bottom, and all the small values are towards the top). EDIT: Your new post seems inte...
by scwizard
Mon Mar 09, 2009 9:14 pm UTC
Forum: Coding
Topic: C# vs C++
Replies: 40
Views: 5863

Re: C# vs C++

A few months ago I started to write something in C++/CLI, and found that there was an annoying graphical bug with my tree view (that wasn't there when I coded the thing in C++/Win32API). This made me decide to put off .NET junk in general until much later.
by scwizard
Mon Mar 09, 2009 10:46 am UTC
Forum: Coding
Topic: C# vs C++
Replies: 40
Views: 5863

Re: C# vs C++

Actually, Java's generics follow from generic programming found mainly in functional programming, based on the HM type-inference algorithm (and it does a bad job of it too). It's also known as parametric polymorphism (because it takes type parameters), and is quite different from the natural OOP ty...
by scwizard
Mon Mar 09, 2009 6:51 am UTC
Forum: Coding
Topic: C# vs C++
Replies: 40
Views: 5863

Re: C# vs C++

I'd learn them in the order of C++, Java, C#. Many of the programs you use on a day to day basis are written primarily in C++, which is why I'd say learning C++ is important. C++'s most major advantage, is that they allows a very high level of abstraction, while at the same time being very fast (hen...
by scwizard
Mon Mar 09, 2009 6:40 am UTC
Forum: Computer Science
Topic: How do I balance a pre-order or post-order binary tree?
Replies: 10
Views: 1137

Re: How do I balance a pre-order or post-order binary tree?

Well in the paper, the trees are always perfect trees. However if you insert an element into one of those perfect trees, it's no longer perfect, and if you insert many elements the tree can degenerate. I'm trying to make it so that insertions won't make the tree become too unbalanced. The specific t...
by scwizard
Mon Mar 09, 2009 4:27 am UTC
Forum: Computer Science
Topic: How do I balance a pre-order or post-order binary tree?
Replies: 10
Views: 1137

Re: How do I balance a pre-order or post-order binary tree?

piecing the tree back together when adding or removing the root still takes logarithmic time. Well the idea is that you don't, and that you have a series of trees as a result. Did you read that paper I linked you to? http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.5156 element pop_least(...
by scwizard
Sun Mar 08, 2009 12:27 pm UTC
Forum: Computer Science
Topic: How do I balance a pre-order or post-order binary tree?
Replies: 10
Views: 1137

How do I balance a pre-order or post-order binary tree?

There are three common ways of numbering elements of binary trees, pre-order, in-order and post-order . In the examples I give everything is numbered from zero. Tree nodes can store a variety of metadata, including its next and previous elements according to a specific ordering, as well as the numbe...
by scwizard
Sun Mar 08, 2009 8:41 am UTC
Forum: Computer Science
Topic: Better than both a linked list and a deque!
Replies: 64
Views: 5382

Re: Better than both a linked list and a deque!

Now, perhaps you are asking how the sequence number of a node is calculated? That's simple. It's just the number of children in its left subtree plus one. This can be stored in the node and updated every time nodes are inserted and deleted. EDIT: Never mind, I see how it would work, something appro...
by scwizard
Sun Mar 08, 2009 12:21 am UTC
Forum: Computer Science
Topic: Better than both a linked list and a deque!
Replies: 64
Views: 5382

Re: Better than both a linked list and a deque!

tree find( nth, tree ) if (nth == tree.left) return tree if (nth > tree.left) return find( nth-tree.left-1, tree,right ) return find(nth, tree.left) ??? How are you comparing n to tree.left? Lets say the tree is ten elements long. You want to get the 4th element of the tree. The value of that fourt...
by scwizard
Sat Mar 07, 2009 10:48 pm UTC
Forum: Computer Science
Topic: Better than both a linked list and a deque!
Replies: 64
Views: 5382

Re: Better than both a linked list and a deque!

(I figured out how to store data throughout the entire tree, instead of only in the leaves) Yes, this was always quite easy, and someone already asked in this thread why you weren't already doing that. It's not like the data have to be leaves in order to be a doubly linked list. List pointers can p...
by scwizard
Fri Mar 06, 2009 11:58 pm UTC
Forum: Computer Science
Topic: Better than both a linked list and a deque!
Replies: 64
Views: 5382

Re: Better than both a linked list and a deque!

I think we could do better. We could probably get some of those things down to O(1) if we thought about it enough. I've read some papers, and have been inspired. Expect to see a new data structure sometime soon that incorperates a strictly better version of the shrub (I figured out how to store dat...
by scwizard
Sun Mar 01, 2009 9:38 pm UTC
Forum: Coding
Topic: best multi threaded language?
Replies: 16
Views: 1696

Re: best multi threaded language?

I'd go with Ada.

It's compiled, so it's fast. And it has support for multithreading built into the language, and the language itself is all about safety (which is very helpful considering how hard tracking down thread related bugs can be).
by scwizard
Sun Mar 01, 2009 6:21 pm UTC
Forum: Computer Science
Topic: superabacus mystic genetic algorithm project!
Replies: 9
Views: 1562

Re: superabacus mystic genetic algorithm project!

figuring out an efficient algorithm to an NP complete problem would make you instantly famous which is a good enough reason to at least try, right? Winning the lottery will get you instantly rich, which is a good enough reason to at least try. right? Well actually this is a worse idea than playing ...
by scwizard
Sun Mar 01, 2009 4:51 am UTC
Forum: Computer Science
Topic: superabacus mystic genetic algorithm project!
Replies: 9
Views: 1562

Re: superabacus mystic genetic algorithm project!

I've never understood why grad students pour so much effort into NP complete problems. NP complete problems are like a icy wall with no footholds. Looking at my professors , none of them have gotten to the position they're at by doing research on NP complete problems. Also TSP is boring and even mor...
by scwizard
Sun Mar 01, 2009 4:46 am UTC
Forum: Coding
Topic: Creating a bridge between Java and an exterior program
Replies: 16
Views: 1087

Re: Creating a bridge between Java and an exterior program

Java is a poor language for bridging with exterior programs. With a compiled language you would usually want to write a library, but with Java that's not an option.

As for pipes, reading this might help you out: http://en.wikipedia.org/wiki/Pipeline_(Unix)
by scwizard
Sun Mar 01, 2009 2:58 am UTC
Forum: Coding
Topic: How to fix ambiguous conversions (C++)
Replies: 8
Views: 2122

Re: How to fix ambiguous conversions (C++)

Thanks, that answers a bunch of my questions and raises some new ones (and then answers them).
by scwizard
Sun Mar 01, 2009 2:28 am UTC
Forum: Coding
Topic: How to fix ambiguous conversions (C++)
Replies: 8
Views: 2122

Re: How to fix ambiguous conversions (C++)

Could you link to something or other that explains this?
by scwizard
Sun Mar 01, 2009 1:42 am UTC
Forum: Coding
Topic: How to fix ambiguous conversions (C++)
Replies: 8
Views: 2122

Re: How to fix ambiguous conversions (C++)

class A {};
class B : public A {};
class C : public A {};
class D : public B, public C {};

If you have a function that takes an object of type A, and you give it an object of type D, then you get the error.
by scwizard
Sun Mar 01, 2009 12:35 am UTC
Forum: Coding
Topic: Coding: Fleeting Thoughts
Replies: 9979
Views: 1979999

Re: Coding: Fleeting Thoughts

Sometimes I wish programming languages were more like English. In English, if you say something, one of the words in your phrase can have multiple meanings, and the person you're talking to is free to use one meaning, or the other, or both (and laugh because it's a pun) or be pedantic and say that t...
by scwizard
Sun Mar 01, 2009 12:24 am UTC
Forum: Coding
Topic: How to fix ambiguous conversions (C++)
Replies: 8
Views: 2122

How to fix ambiguous conversions (C++)

Lets say you have a system of classes layed out like this: A /\ B C \ / D Is there any way to allow the compiler to convert D to A implicitly? To say "I don't care which way you decide to convert it, just fucking convert it." I know it's possible to hack around this by adding in dummy clas...
by scwizard
Sat Feb 28, 2009 3:23 am UTC
Forum: Coding
Topic: Multiple inheritance gives "ambigous resolution" error (C++)
Replies: 23
Views: 1202

Re: Multiple inheritance gives "ambigous resolution" error (C++)

I'm not trying to do that anymore. I see how things work now and I won't try doing anything too weird.
by scwizard
Sat Feb 28, 2009 2:53 am UTC
Forum: Coding
Topic: Multiple inheritance gives "ambigous resolution" error (C++)
Replies: 23
Views: 1202

Re: Multiple inheritance gives "ambigous resolution" error (C++)

shrub<std::string>::iterator Iter = TestShrub.begin(); while(Iter != TestShrub.end()) { std::cout << *Iter << std::endl; ++Iter; } Iter = TestShrub.rbegin(); while(Iter != TestShrub.rend()) { std::cout << *Iter << std::endl; ++Iter; // Here I want the reverse_iterator version of operator++ to be ca...
by scwizard
Sat Feb 28, 2009 2:28 am UTC
Forum: Coding
Topic: Multiple inheritance gives "ambigous resolution" error (C++)
Replies: 23
Views: 1202

Re: Multiple inheritance gives "ambigous resolution" error (C++)

You're slicing the iterator returned from rbegin() I don't see how I'm slicing anything. Both iterator and reverse_iterator have the same data in this case. When I define reverse_iterator I don't define any data elements. (this isn't reverse_iterator defined in terms of std::reverse_iterator, this ...
by scwizard
Sat Feb 28, 2009 2:04 am UTC
Forum: Coding
Topic: Multiple inheritance gives "ambigous resolution" error (C++)
Replies: 23
Views: 1202

Re: Multiple inheritance gives "ambigous resolution" error (C++)

In any case I wouldn't make the reverse inherit from the forward. You could make them inherit from a common base that implements the common next/prev/deref functionality. Then the forward and reverse just provide the operator interface. But inheriting the reverse from the forward implementation is ...
by scwizard
Sat Feb 28, 2009 1:58 am UTC
Forum: Coding
Topic: Multiple inheritance gives "ambigous resolution" error (C++)
Replies: 23
Views: 1202

Re: Multiple inheritance gives "ambigous resolution" error (C++)

Why not just use std::reverse_iterator? Several reasons, the main one being that it's harder to turn it into a checked iterator because it wouldn't use the FirstLeaf dummy leaf as it's rend(). Actually scratch that. I could still make it checked fairly easily. EDIT: Oh ya, I rem...
by scwizard
Sat Feb 28, 2009 1:51 am UTC
Forum: Coding
Topic: Multiple inheritance gives "ambigous resolution" error (C++)
Replies: 23
Views: 1202

Re: Multiple inheritance gives "ambigous resolution" error (C++)

It's by no means required. The main thing is that it sets up the basic typedefs that are required by the iterator interface so that algorithms can reason about the iterator. So by using std::iterator you can just specify the value type and the iteration category and it uses reasonable defaults for ...
by scwizard
Sat Feb 28, 2009 1:34 am UTC
Forum: Coding
Topic: Multiple inheritance gives "ambigous resolution" error (C++)
Replies: 23
Views: 1202

Re: Multiple inheritance gives "ambigous resolution" error (C++)

Ya, I was looking at the C++ algorithms, and they have no requirements that their arguments be of any type relating to std::iterator. It's all just templating.

So do I even need to have shrub<T>::iterator inherit from std::iterator? What advantages do I gain from doing so?
by scwizard
Sat Feb 28, 2009 1:17 am UTC
Forum: Coding
Topic: Multiple inheritance gives "ambigous resolution" error (C++)
Replies: 23
Views: 1202

Re: Multiple inheritance gives "ambigous resolution" error (C++)

A reverse_iterator can be treated as an iterator. It is treated as an iterator. If it can be treated like an iterator, then why can't I go: shrub<char>::iterator Iter = TestObjet.begin(); Iter = TestObject.rbegin(); That's the type of thing I want to make it able to do. EDIT: Actually, let me check...
by scwizard
Sat Feb 28, 2009 12:44 am UTC
Forum: Coding
Topic: Multiple inheritance gives "ambigous resolution" error (C++)
Replies: 23
Views: 1202

Re: Multiple inheritance gives "ambigous resolution" error (C++)

I haven't done this type of thing before. It's really helping me learn a lot. In this case both iterator and reverse iterator have the same data, so slicing can't occur. Therefore I think it would be advantageous to have reverse_iterator inherit from iterator. Reverse_iterator is a type of iterator,...
by scwizard
Sat Feb 28, 2009 12:38 am UTC
Forum: Computer Science
Topic: Better than both a linked list and a deque!
Replies: 64
Views: 5382

Re: Better than both a linked list and a deque!

Why do you keep referring to O(1) rotations? Are there any other kind? The only kinds of rotations there are are left rotations and right rotations. Both of which are O(1) operations. This is what I know about rotations: If you rotate left, you make it so you have less leaves to the right than you d...
by scwizard
Fri Feb 27, 2009 5:57 pm UTC
Forum: Computer Science
Topic: Better than both a linked list and a deque!
Replies: 64
Views: 5382

Re: Better than both a linked list and a deque!

Ya, that's exactly what I did. And it is log n. You were saying something about log n rotations though that was confusing me. I cannot figure out how to get O(1) counter-based rotations that keep the tree 'mostly' balanced. What do you mean "O(1) counter-based rotations"? Do you mean the r...
by scwizard
Fri Feb 27, 2009 4:25 pm UTC
Forum: Computer Science
Topic: Better than both a linked list and a deque!
Replies: 64
Views: 5382

Re: Better than both a linked list and a deque!

I still don't get what this counter thing is and how it would help you do a lookup by index... Perhaps you could draw a picture?
by scwizard
Fri Feb 27, 2009 4:20 pm UTC
Forum: Coding
Topic: Multiple inheritance gives "ambigous resolution" error (C++)
Replies: 23
Views: 1202

Re: Multiple inheritance gives "ambigous resolution" error (C++)

I'm trying that, and now when I go: shrub<char>::iterator Iter = TestObject.begin(); shrub<char>::reverse_iterator rIter = TestObject.rbegin(); std::list<shrub<char>::iterator*> empl; empl.push_front(&Iter); empl.push_front(&rIter); (stolen from page 312 of TC++PL to help prove a point) I ge...
by scwizard
Fri Feb 27, 2009 3:11 pm UTC
Forum: Coding
Topic: Multiple inheritance gives "ambigous resolution" error (C++)
Replies: 23
Views: 1202

Re: Multiple inheritance gives "ambigous resolution" error (C++)

That's weird. Why would std::iterator define a operator*? std::iterator is only used for inheriting from I thought.

I guess I was wrong.

Well anyways, how do I go about fixing this? If the way I'm writing these iterators is the proper way, then I shouldn't need to have redundant operations.
by scwizard
Fri Feb 27, 2009 3:03 pm UTC
Forum: Computer Science
Topic: Better than both a linked list and a deque!
Replies: 64
Views: 5382

Re: Better than both a linked list and a deque!

Huh? I don't follow. What do you mean by "append the counter" for instance?
by scwizard
Fri Feb 27, 2009 7:13 am UTC
Forum: Coding
Topic: Multiple inheritance gives "ambigous resolution" error (C++)
Replies: 23
Views: 1202

Multiple inheritance gives "ambigous resolution" error (C++)

So I have this data structure I'm implementing , and right now I'm mucking around with implementing all the diverse types of iterators. Currently I have: class iterator : public std::iterator<std::bidirectional_iterator_tag, T> { // Implementation of iterator stuff. } class reverse_iterator : public...
by scwizard
Fri Feb 27, 2009 5:48 am UTC
Forum: Computer Science
Topic: Better than both a linked list and a deque!
Replies: 64
Views: 5382

Re: Better than both a linked list and a deque!

That is the standard (AVL tree) way of balancing and it does use O(lg n) steps, which is why you damn well better only require it in operations which already take O(lg n). It's much simpler than red-<colour not needed due to Fat Tony's birth> trees, but perhaps not as simple as splay trees. I only ...
by scwizard
Fri Feb 27, 2009 2:27 am UTC
Forum: Computer Science
Topic: Better than both a linked list and a deque!
Replies: 64
Views: 5382

Re: Better than both a linked list and a deque!

Well the way I do it is thus: if(Crawler->NumberOfLeavesToTheLeft > Crawler->NumberOfLeavesToTheRight) { RotateRight(Crawler); Crawler = Crawler->Parent; } else if(Crawler->NumberOfLeavesToTheRight > Crawler->NumberOfLeavesToTheLeft) { RotateLeft(Crawler); Crawler = Crawler->Parent; } else { continu...
by scwizard
Thu Feb 26, 2009 4:29 pm UTC
Forum: Computer Science
Topic: Better than both a linked list and a deque!
Replies: 64
Views: 5382

Re: Better than both a linked list and a deque!

Isn't what you've described just an AVLTree? OOPS: Okay, it's not, I missed a kinda important detail :P However, probably the reason it's not done is because you're adding n bytes for every node. That might be more data than you want to store, when you're already storing sizeof(void *)*4 for each n...
by scwizard
Thu Feb 26, 2009 1:08 am UTC
Forum: Computer Science
Topic: Better than both a linked list and a deque!
Replies: 64
Views: 5382

Re: Better than both a linked list and a deque!

scwizard, when did you run into the structure? I was looking for an already implemented one about a month ago. The idea struck me and I implemented it. I didn't take it from anywhere. I was thinking "how would you go about implementing a tree using indices instead of key value pairs?" and...

Go to advanced search