gistfile1.txt

# Intro to Prototypes
## JS Data Structures 



### Outline

* Objects in Javascript?
	* object literals
	* properties
* Functions 
	* as objects
	* returning objects
	* using apply
	* trying to efficiently create methods 
* Function Prototypes 
	* private variables 
	* private functions 
	* public variables
	* chaining 
* Recursive Structures
	* Tree Structures
		* binary tree 
			* left and right nodes
		* n-ary tree 
			* using an array
	* Trie Structure
		* A tree using an object 


## Prototypes

### Objects
Recall using object literals in JS, i.e. `{}`. We examined how objects let us set properties on them, which became useful later for writing modular code. We could create an object literally as follows:

	var myObject = { greeting: "hello world!"}

or we could construct one explicitly using a `new` method

	var myObject = new Object();
	myObject.greeting = "hello world!"

### Functions as objects

In Javascript, almost everything is an object. Even functions are objects and thus we can set properties on them.

	function Lemon(){};
	Lemon.ripeColor = "yellow";
	
We might even say something like

	function Lemon(){
		console.log("A lemon is ripe if it is " + Lemon.ripeColor);
	};
	Lemon.ripeColor = "yellow";
### Functions returning objects

We might use closures and objects together to create functions to return objects that act an api for some modular code.

	function makeJuicer(brandName){
		
		return {
			getBrandName: function(){
				return brandName;
			}
		};
		
	};

We might want to change this up a bit to add some ability to internally reference things.


	function makeJuicer(brandName ){
		var innerApi =  {
			items: [],
			getBrandName: function(){
				return brandName;
			}, 
			addItem: function(item){
				innerApi.items.push(item)
				console.log("Contains ", innerApi.items);
				return innerApi;
			}
		};
		return innerApi;
	};

We also saw that we could use that javascript has a built in self referential keyword for objects, `this`.



	function makeJuicer(brandName ){
		return {
			items: [],
			getBrandName: function(){
				return brandName;
			}, 
			addItem: function(item){
				this.items.push(item)
				console.log("Contains ", this.items);
				return this;
			}
		};
	};
### Efficiently Creating methods

Recall the following snippet.

	function makeJuicer(brandName){
		
		return {
			blend: function(){
				return "crazy string";
			}
		};
		
	};
	
Say we created two juicers 
	
	var juicer = makeJuicer("SF Local");
	var juicer2 = makeJuicer("SF Neighborhood");
	
then we'd expect that the two juicers were made with functionality that referenced just one function per unit. Hence we decide to test this by checking the following
	
	juicer.blend === juicer2.blend // false


We could separate this out to achieve the desired behavior
	

	var juicerModule =  {
		blend: function(){
			return "crazy string"
		}
	};
	function makeJuicer(brandName){
		this = juicerModule;
		return this;
	};


and we see that it two return objects return the same function reference.

	juicer.blend === juicer2.blend // true

However, if I change juicer it then changes for both objects, i.e.

	juicer.blend = "crazy string";
	
	juicer2.blend() //=> blend is not a function
	
	
### function prototypes


### Own Properties vs Prototype Properties

Let's a define our prototype for a dog

	function Dog(name){
		if(name){
			this.name = name;
		}
	};
	Dog.prototype.name = "Unkown";
	
### Iterating over objects, "for ... in"

Let's imagine we had a more elaborate dog

	function Dog(name, owner, address){
		this.name = name;
		this.owner = owner;
		this.address = address;
	};
	
	Dog.prototype.previousOwner = "unknown";
	
If we wanted to iterate through the object we could do something like the following.

	var spot = new Dog("spot", "joe", "123 Central..");
	
	for(var prop in spot){
		console.log(prop, spot[prop])
	}
	
Notice how this also prints out the previousOwner property. We can ensure that an object and not something in it's prototype has a property using the `hasOwnProperty`.

	for(var prop in spot){
		if(spot.hasOwnProperty(prop)){
			console.log(prop, spot[prop])
		}
	}
#### Exercise

* What does `propertyIsEnumerable` do? How would you use it differently from `hasOwnProperty`?
	

### Doggie Sideeffects

	function Dog(name){
		this.name = name;
	};
	
	Dog.prototype.pastNames = [];
	Dog.prototype.changeName = function(newName){
		this.pastNames.push(this.name);
		this.name = newName;
	};

#### Exercise

* Make a `RightTriangle` Prototype
	* Should have own properties `base`, `height`
	* should have prototype properties:
		* area
		* hypotenuese
* Make 	`RightTriangle`'s `base` and `height` private, and create methods to read these properties.

Rock Papper Scissors

* Make a prototype called `Player`
	* Should have own properties `name` and `response`.
	* Should have prototype properties:
		* `promptForResponse` that prompts the player for a response
		* `checkResponse` that returns the `response` and sets own property `response` to empty string;
* Make a prototype called `RPSGame`
	* should have own properties
		*  `player1` and `player2` that are objects
	* should have prototype property called `checkWinner` that checks if `player1.checkResponse()` is a win, draw, or loss against `player2.chekResponse()`, and re
	* should have prototype property called `play` that does the following:
		*  prompts to see if someone wants to play,
		*  calls `promptForResponse` for both `player1` and `player2`
		*  calls `checkWinner`
		*  alerts winner
		*  prompts to play again then repeats based on response.

	



## Recursive Structures

Let's dicuss some complex data structures that aren't like our previous abstractions. This data abstraction differs in that it's what we call recursive. A **tree** is an object that has some number of **children** and each of these children is also a tree, a **subtree**. If a tree is not a child of another tree we say it is a **root node**, and a tree that is a child of another is called a **node**. A *node* with no children is called a **leaf**.


Turning this into code.

	// A tree is a prototype with some number of children
	function Tree(){
		// has some children
	}
### Binary Tree

Let's make a choice to just start with `2` children, or a `binary-tree`, and modify our prototype to reflect this.

	// A binary tree is a prototype with 2 children
	function BinaryTree() {
		this.leftChild = null;
		this.rightChild = null;
	};

=========
 
#### Practice

* Create a new BinaryTree with a value of your liking
	* Add a leftChild to the BinaryTree
	* Add a rightChild to the BinaryTree
	
* Add an method called `isFull` to a node that returns true if both `leftChild` and `rightChild` are occupied.
	
=========



### A General Tree

Let not assume our tree only has two children. If we remove this restriction then we might just have a collection of children in something like an array.

> What might this look like? Try it. <a href="#general_tree">solution</a>

Let's add a method to our general `Tree` that will add children as Trees.

	Tree.prototype.addChild = function(newValue){
		var newTree = new Tree(newValue);
		this.children.push(newTree)
		return this;
	};


### Inserting into a Binary Tree

Let's add an insert method to our prototype.

	// A binary tree is a prototype with 2 children
	function BinaryTree(value) {
		this.value = value || null;
		this.leftChild = null;
		this.rightChild = null;
	};
	
	// A method for inserting a new value
	BinaryTree.prototype.insert = function(newValue){
		// Something happens here
	};

However, we need some kind of rule for how we are going to insert new values. 

* We will add a new value to `leftChild` if there is no value.
*  If there is a `leftChild` and it is less than the new value we will add the new value to `rightChild`.
*   If a new value is less than `leftChild` we will repeat this process for it's (leftChilds) own `leftChild` and `rightChild`.
*    Similarly, if the value is greater than `leftChild` and `rightChild` already has a value, then we will continue this process for `rightChild`.

		// A binary tree is a prototype with 2 children
		function BinaryTree(value) {
			this.value = value || null;
			this.leftChild = null;
			this.rightChild = null;
		};
		// A method for inserting
		BinaryTree.prototype.insert = function(newValue){
			// if leftChild is null set leftChild to a
			//		 new BinaryTree(newValue)
			// else if leftChild is less than newValue 
			//		and rightChild == null
			//		then  rightChild is new set
			//		to BinaryTree(newValue)
			// otherwise if newValue < leftChild.value
			//		then leftChild.insert(newValue)
			//		else rightChild.insert(newValue)
		};

This wordy first attempt can be turned into something like the following.

		// A binary tree is a prototype with 2 children
		function BinaryTree(value) {
			this.value = value || null;
			this.leftChild = null;
			this.rightChild = null;
		};
		// A method for inserting
		BinaryTree.prototype.insert = function(newValue){
			if( this.leftChild == null){
				 this.leftChild = new BinaryTree(newValue);
			} else if( this.rightChild == null && 
						this.leftChild.value < newValue) {
					this.rightChild = new BinaryTree(newValue);
				
			} else if (leftChild.value < newValue)
				this.leftChild.insert(newValue);
			} else {
				this.rightChild.insert(newValue)
			}
		};
	
#### Practice 
* Write an `isEmpty` method that returns true if both left and right child are empty
* Write a print function that prints all the values in a binary tree (<a href="#print_hint">Hint</a>)
* Write a function that prints the number of leaves in the tree.

### Resources 

* MDN
	* [#The Object Class Instance](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Introduction_to_Object-Oriented_JavaScript#The_Object_.28Class_Instance.29)
	* [#The Constructor](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Introduction_to_Object-Oriented_JavaScript#The_Constructor)
	* [#The property Attribute](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Introduction_to_Object-Oriented_JavaScript#The_Property_.28object_attribute.29)
	* [#The Methods](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Introduction_to_Object-Oriented_JavaScript#The_methods)

* JS Garden
	* [#objects](http://bonsaiden.github.io/JavaScript-Garden/#object.general)

	* [#prototytpes](http://bonsaiden.github.io/JavaScript-Garden/#object.prototype)
* [Random Blog](http://www.phpied.com/3-ways-to-define-a-javascript-class/)


* [Trie](http://en.wikipedia.org/wiki/Prefix_tree)

Hints etc:
		
* <div id="general_tree"> A General Tree</div>

		function Tree(value){
			this.value = value;
			this.children = [];
		}
* 
*<div id="print_hint"> Copy part of code for the insert function and modify it using your handy isEmpty function. </div>*