Raed Tabani

I think I understand the concept behind balancing a BST which is achieved by acts of rotations. simply, whenever an imbalance occurs, either the number of nodes on the left of the current subtree outweighs or fall behind those to it's right by a factor more than 1, then a better root is needed to be found. which is mainly achieved  by either rotating left which brings the right child as the new root or by rotating right which brings the left one. but things are not always this simple as the immediate child my not be the best fit which is the case of left followed by a right imbalance and a right-left one, where further rotation to the child is needed in the opposite direction followed by the regular logic.

my insertion code(without balancing) works fine, but when I add my balancing logic and try to print my tree It gives me weird results.
public Node insert(Node current,int key, int depth){                        if(current == null){                        Node temp = new Node(key);            temp.depth=depth;            temp.height=0;                        if(current==root){                                root=temp;            }            return temp;        }                if(key<current.key){                        current.left = insert(current.left,key,current.depth+1);                                }        else{                                    current.right =insert(current.right,key,current.depth+1);                    }        

as for my balance logic is
int leftHeight = getHeight(current.left);        int rightHeight = getHeight(current.right);                current.height= Math.max(leftHeight,rightHeight)+1;        current.balance=getBalance(current);                if(current.balance>1){                        if(current.left.balance<0){                                current.left = leftRotation(current.left);            }                        current= rightRotation(current);                    }        else if(current.balance <-1){                        if(current.right.balance >0){                                current.right = rightRotation(current.right);            }                        current =  leftRotation(current);        }                                return current;            }    

my rotation logic
public Node rightRotation(Node current){                        Node newNode = current.left;        current.left= newNode.right;        newNode.right= current;                                current.height = Math.max(getHeight(current.left),getHeight(current.right))+1;        newNode.height = Math.max(getHeight(newNode.left),getHeight(newNode.right))+1;        return newNode;            }
 public Node leftRotation(Node current){                        Node newNode = current.right;        current.right= newNode.left;        newNode.left= current;                        current.height = Math.max(getHeight(current.left),getHeight(current.right))+1;        newNode.height = Math.max(getHeight(newNode.left),getHeight(newNode.right))+1;        return newNode;            }    

Hey guys ,
I'm learning about databases and at the moment I want to implement a BST in code, I managed to do it using a while loop as following:
public class BinaryTree { Node root=null; void insertNode(int key){ Node currentNode =new Node(key); if(root ==null){ root= currentNode; System.out.println("added Node "+ currentNode.key +" as a root"); } else{ Node focusNode = root; while(true){ if(focusNode.key > currentNode.key){ if(focusNode.leftChild == null){ focusNode.leftChild = currentNode; focusNode.leftChild.parent = focusNode; System.out.println("added node" + currentNode.key +" as a left child of "+ focusNode.key); return; } else{ focusNode=focusNode.leftChild; } } else{ if(focusNode.rightChild == null){ focusNode.rightChild = currentNode; focusNode.rightChild.parent = focusNode; System.out.println("added node" + currentNode.key +" as a right child of "+ focusNode.key); return; } else{ focusNode=focusNode.rightChild; } } } } }

but now I'm trying to get rid of the loop and do it recursively instead, I came up with this code but now the insertNode() takes two parameters and I'm not sure if this the best way to implement it
void insertNode(int key, Node parentNode){ Node currentNode =new Node(key); Node focusNode = parentNode; if(focusNode.key > currentNode.key){ if(focusNode.leftChild == null){ focusNode.leftChild = currentNode; focusNode.leftChild.parent = focusNode; System.out.println("added node" + currentNode.key +" as a left child of "+ focusNode.key); return; } else{ insertNode(key,focusNode.leftChild); } } else{ if(focusNode.rightChild == null){ focusNode.rightChild = currentNode; focusNode.rightChild.parent = focusNode; System.out.println("added node" + currentNode.key +" as a right child of "+ focusNode.key); return; } else{ insertNode(key,focusNode.rightChild); } }

how can I make it better?

I also struggle to see the point of the red light, just by showing what spots are available aren't we also saying which spots are not? but I think you're right about it being more "fault tolerant", a faulty no light in an only green system gives the false impression that a spot is occupied where it's not, while the same scenario in 2 colored system could mean either ways. but then again, wouldn't this two light system be a little confusing for Color blind people, especially with the emphasis to use Red and Green(not that I'm an expert in colorblindness )? in a one light system, its says follow the light doesn't matter it's color, it's not racist

anyways, I'd love to give this a go, however I want to do it from the users/drivers perspective that is:
1- the first UI(Activity as I'll be making it in android) will be the external Sign, it shows a number of the available spots and lets user in if at least 1 spot is available.
2- the second UI will be the internal sign, I will make it like the garage with two columns : Section - Number ex A 9
I could go further and make a third activity where the user gets to choose which spot to park in but I think it's unnecessary for now.

but I'm thinking of making the car as an object, and the reason for that is in order to make this more of a real life simulation, I want the car not only to provide stimulus for entry but once parked it would wait for a while then unpark and leave byitself. so it should know for how long to park then invoke getTheHellOutOfGarage();

I still haven't coded anything yet, but I thought it was interesting that I automatically started thinking (falling for the trap) of what objects do I have and what can they do and what attributes they have, but Instead this time I tried to tackle this from addressing the problems point of view.

This is a self-parking facility

I'm not sure if I'm being over analytical here, as I'm not sure if this qualifies as a problem, but I did ask myself is this significant at all for this design? who is responsible for parking is it the car or the garage itself ie where is the park() located? nevertheless, it led me to this Problem : choose which spot to park a car in if there is any available at a given time. which led to another Problem : how to ensure that no car gets in only to find all spot are taken. to which the solution is the LED sign at the entrance.

LED signs at the entrance to show how many spots are available.

Problem : how to find out if the Garage has available spots and how many? it is achieved by keeping track of the numbers of cars inside the garage, parked or not , at the moment VS total number of slots . where:
a- the number of cars ++ as soon as a car gets in and not necessarily parked yet
b- the number of cars -- only once the car exits garage.

Above each spot in the garage is a sensor that can sense whether or not there is a vehicle in the spot. If the spot is open, a green light above the spot will be activated. This helps customers find open spots. This also helps the system update the sign at the entrance to show how many open spots there are in the garage.

at first I thought, isn't it enough to have the garage tell you the number of spots available? do I really need to have this especially that the outer LED sign is in no way related to any spot's state,occupied or not, but merely dependent on number of cars. then I just realize that this along with the inner LED sign, address a diffrent problem than the outer one, which was to answer the question "if I get in will I find a spot to park?", and now its asnwering the problem: where is an available spot located and how to find it easier and quicker. and having the Garage divided in into four sections: A, B, C, and D sections. serves to make this easier and more efficient coding wise.


so far these are the main problems that i identified, and I want to ask you
1- am thinking in the right direction?
2- did I miss a major problem?
3- throughout this excesise, I did struggle with the "who does what to whom" pattern of thinking. which is to say who's responsibility is it which boils down to where this Method() should be located, for example when you said " facility that has LED signs at the entrance to show how many spots are available." I asked to who is it showing this to? is it for cars to know "can I go inside" or for the Garage to know" can I let more cars in"

you know as I was having a go at this exercise, and so many others. I did struggle with the lack of context, as in what problems this program supposed to solve and what are the needs of the users . so I started to come up with these scenarios, imaginary problems , that may or may never be needed by the user, but nevertheless fun to try . but if I was to summarize what your saying is to define the set of bare minimum necessary problems, rather than Objects, as the context for the program?

In "you were asked to..." who is "you" and who is asking to do this? You, the programmer? In what context would you, the programmer, be asked to move a car to a different spot? Why do you need to move it? To me this just sounds like conjecture and imagining that software objects are somehow magically connected to the real objects. This is part of the trap I mentioned and the futile and fruitless thought exercises that come out of it.

Ask yourself, if this were a real system being used by real people in a real parking lot, what scenario would require a change in the parking spot to be reflected in the system? Does it even matter that someone moved a Vehicle from one spot to another? Why does it matter? How does modeling some kind of behavior in the system make it easier to understand the code? How does it help organize the actions that must take place to update the current system state? What effects do these actions have on the user/customer? Do you have any legal right to touch someone's vehicle while it is parked in your facility? What happens when you try to move a car and the alarm goes off?

Sure, this is just an exercise but to make anything you "learn" from it applicable in a real-world scenario, you also have to keep the context of the problem realistic to some extent.

I was thinking of OP's "program" as a parking manager or a Valet, where you get Vehicle Objects and choose the appropriate slot to park it in, so by "you" I guess I was referring to the user. but I think I understand what your saying, which is, if there's no need for something why make it or perhaps don't just make something because that is how it is in real life, but think of it as why do I need to do this and does it matter? in case of changing slots aka movingVehicle(), I think if we had a GUI where each slot corresponds to a specific View , then wouldn't it matter?

Campbell Ritchie wrote:

Tushar Goel wrote: . . . you don't have to compare true. So instead of . . .

Spot on

In fact you can get nasty errors if you use == true or == false and write = instead of == by mistake.

I didn't know I could do that, thanks, I'll keep it in mind from now on

how can I ask the compiler for time? and does it return type in seconds?
but after a second try, I managed to reduce my loops to just one for loop and that is for Centi-seconds, and using both / and % operator I converted it to String format of Minutes:seconds:centisconds
//make it run for 12000 centiseconds = 2 minutes for(int i=0;i<12000;i++){ if ( goOn ) { try { Thread.sleep(10); } catch (InterruptedException e) { e.printStackTrace(); } elapsedTime++; timer.post(new Runnable() { @Override public void run() { timer.setTex t(elapsedTime/6000 +" : "+(elapsedTime/100)%60+ " : " + elapsedTime%100); } });
is this better?

Mike. J. Thompson wrote:Do you just want to know the time it took to solve the puzzle, or are you displaying the stop watch and updating it every second?

I want it to display and update the stopwatch every second, or perhaps centisecond

hi Saikrishnan,
what a great topic, personally I found it so helpful and it got me excited to take a shot at the Parking Lot design myself.
before I do that, however, I'm wanted to ask you a couple of questions regarding your design

1- why did you choose to make Car, Bus, MotorCycle a subclass of Vehicle instead of "code internal to a single class" as Paul mentioned? I'm not sure if this is the right analogy, but this does remind me of a card "game" that I did and more precisely the Card class. your way seems to me like having each suit(Hearts,Spades..etc) as a SubClass of Card where it could have easly been a String Value called suit or an enum.

2- why did you decide to make each slot individually then fill them one by one rather than having a slot object hold an arraylist of cars plus rules?

3- do your slots serve as references to vehicle objects? I thought it was "odd" that your parking lot slots held Slot Objects instead of Vehicle

sandeeprajsingh tandon wrote:Hi Folks...
Would it be better/worse if each vehicle knew the slot it was parked in and each slot knew the vehicle that is parked on it ie. Vehicle should have a ref to Slot and viceversa ?. That ways, the signature of the unpark could be unpark (uniqueToken, slotNumber). Unpark could simply get the slot on that number and free it up.

Please critique

hi sandeeprajsingh(why didn't I just copy and paste your name )
I'm not sure I'm in a position to be giving a critique, but nevertheless I want to share what I think.
I could understand why a car would need to know the slot where it's parked at, so it could serve as a reference for the car Object. so for example, you were asked to move a specific car to another location, It could easily be done by asking the car which slot it's at and then just swap slots. however, isn't it enough for slot to just know if it's occupied or not? not to mention, if the slot is a reference for car object, doesn't it necessarily mean that it knows which car is on it( by saying slot[number].getname())?

it's is a MediaPlayer Object and I just updated the code, thanks man . although I did ask this question on stackOverflow, and as for where to play the background music, It was clear to me that a Service is best given that the music is independent of an activity's life cycle. however, I also learned that Service runs on the UI thread and I was wondering if starting a thread within the service would help reduce load on the main thread and make app run smoother?

I'm making a puzzle App in which there's a timer that starts with the puzzle and stops when the user solves it, it tells the time it takes to finish the puzzle. so far for my timer, I built 3 nested for loops; a loop for Hours that runs 24 times, a loop for minutes that runs 60 times and finally a loop for seconds that runs for 60 times as well, and at the heart of it I used Thread.sleep(1000) and the change is shown through a TextView(this is for android)
I would like to get some feedback on the whole thing. btw, I added code to stop and resume the stopwatch.

mainLoop: for( int hours = hour ; hours < 24 ; hours ++){ for( int min=minute ; min < 60 ; min ++){ for( int sec = second ; sec < 60 ; sec ++){ //this is used to control/pause the timer if(goOn==true){ try { Thread.sleep(1000); } catch (InterruptedException e) { e.printStackTrace(); }} else{ break mainLoop; } finalHours = hours; finalMin = min; finalSec = sec; timer.post(new Runnable() { @Override public void run() { timer.setText(finalHours +" : "+ finalMin +" : "+ finalSec); } }); } } } } }); time.start();}

I'm trying to build an app where a piece of Music is played whenever the onCreate() is called, and I want for this music to be played throughout the whole app ie across Activities. what I've done so far is to create a Thread,within the OnCreate(), and I called it backgroundMusic, inside of it I created A MediaPlayer Object from a music piece in my Raw Folder. given that the music itself only runs for a minute or so and the average time spent on the app is more, I made a while Loop that as long as the app is running checks if the music is playing, if not then call start();
backgroundMusic = new Thread(new Runnable() { @Override public void run() { while ( appIsRunning ){ if( ! music.isPlaying () ){ music.start(); } } } });backgroundMusic.start();

the code runs just fine, however I did notice some Lag especially later when some other Threads and Images gets loaded.what I want to ask, is this an appropriate way to play background Music? is there a better more efficient way of doing that?
also, how do I make the music stop as the app closes?

Darryl Burke wrote:A couple of comments:
-- Suit and rank attributes in a deck of cards are better represented by enums rather than a String and an int.
-- Your class that represents a card (singular) is called Cards (plural). That's misleading. Why not name it Card?

All that matters to the user of the Deck class is that it can supply a Card. How it does that and how the remaining cards are stored is an internal matter of the Deck. So yes, its ArrayList should be private, and Deck could have a public or package-private method Card getCard().

Similar logic would apply to the Player class.

is there an API in ArrayList class that moves(adds to receiver and remove from giver) element across ArrayLists?

Hint: what does the remove(int) method return?

it returns, in my case, the card to be removed
so my new code will become
private void dealCards(){ for(int x = 0 ; x < playerCount ; x++){ for(int y = 0 ; y < 10; y++){ playerList.get(x).pile.add(deck.deck.remove(0)); } } }

about the enums, being unfamiliar with them, I want to ask why are they better to represent my cards suits and numbers? from my brief and very recent knowledge of the enum Class I sort of built this picture of it as a global Array with constant values, that is accessable across classes. so in a way is it to overcome the restriction imposed by encapsulation and private modifiers since multiple classes need to use them?