Ebbe’s D-universe

Today I got a message on dsource.org about which IDE I’m using. Thought I should share this with you.

Right now I’m using Code::Blocks. I’m using the nightly Ubuntu builds, as they work quite well. It’s also fun to follow the rapid development; One time I reported a small bug, and within a week I could download a nightly without the bug. Nice

Some of the things I like about Code::Blocks is

• Auto-completion (can’t live without this!)
• Syntax highlighting (would also die without this)
• The ability to build for different targets. E.x. you can have a test environment with different flags for the compiler and program, and then the a “release” build with an optimize flag and maybe some different things.
• Nice debugging
• The ability to set up abbreviations. E.x. you can write “class“, press Ctrl-j and it gets replaced with
  1. class $(Class name) {
  2. public:
  3. this() {
  4. |
  5. }
  6. ~this() {}
  7. private:
  8. };

  Here a pop-up box will ask the name for the class.

Can’t quite remember more, but I’m sure there are. You are welcome to come with your suggestions.

PS. Always remember vim! It can be tweaked to be really powerful, and can be used through a ssh connection Power to the vi! But.. it can’t replace a good IDE in my opinion.

This is my first “code” post. I’ve implemented a very basic binary minimum heap in D. A heap is a way to structure your data in a very nice way. It’s running time is quite acceptable, as any operation runs in O(lg n).

A reason to have a min-heap, could be if you wanted to implement the A* path-finding-algorithm. There are of course many more reasons

What it does, is keeping track of values along with a key. It sorts the different values according to the key. You can then extract the value that currently has the smallest key.

Here’s the most important lines:

3. /**
4. Heap made by Esben Damgaard
5. Posted on the blog d.hvemder.dk
6.  
7. "THE BEER-WARE LICENSE" (Revision 42):
8. <ebbe _at_ skummer.com> wrote this file. As long as you retain this notice you can do whatever you want with this stuff. If we meet some day, and you think this stuff is worth it, you can buy me a beer in return. Esben Damgaard
9.  
10. **/
11.  
12. void main() {
13. MinHeap!(char[]) heap = new MinHeap!(char[])();
14. heap.insert(4, "I should be first out( remember to visit d.hvemder.dk )");
15. writefln(heap.extractMin() );
...
25. };
26.  
27. class MinHeap(T) {
...
91. public:
92. void insert(int argKey, T argValue) {
93. nodes.length = nodes.length + 1;
94. nodes[length-1] = new Node!(T)(argKey, argValue);
95. decreaseKey(nodes.length-1, argKey);
96. }
97.  
98. T showMin() {
99. return nodes[0].getValue();
100. }
101.  
102. T extractMin() {
103. if( nodes.length < 1 )
104. return cast(T) null;
105. T temp = nodes[0].getValue();
106. nodes[0] = nodes[length-1];
107. heapify(0);
108. nodes.length = nodes.length - 1;
109. return temp;
110. }
111. };
112. Download this code: heap.d

As you can see you are welcome to do whatever you want to do with the file, as long a you keep my beer-ware license in the file.

The implementation is still quite simple, and I intend to extend it to be both a min-heap and a max-heap. It should also be possible to change a values key. I haven’t quite figured out how to do that though It could be done by just saving an id along with the insert. You should then be able to search for that id. The running time, though isn’t that good for searching in heaps like this one. It needs a little more thinking.

A smart thing I learned while implementing this, is in line 27. Here it is up to the user to define what type the values should be. This makes the heap very dynamic in what can be stored. In line 13 there’s an example where I create a MinHeap which can store char[]. Nice

Here’s one to get you through the day, waiting for the weekend

Robotic Beer Launching Refrigerator

And back to D. I’ve implemented a heap, and will soon post it here.