What is Hashing search algorithm ?

  • generate key from value by using certain function.
  • the key is called hash.
  • if same key is generated the key is incremented.
  • you can use same function when you find and set value.

in the following example the key is generated by that function.

key = value % (length of values * 2)

Code

/***************************************
 * util
 ***************************************/
var initData = function(list){
  for(var i = 0; i < list.length; i++){
    list[i] = 0;
  }
  return list;
};

/***************************************
 * set
 ***************************************/
var setData = function(data, targets){
  var key,
      length = targets.length,
      max = targets.length-1;
  data.forEach(function(value){
    key = value % length;
    if(targets[key] === 0){
      targets[key] = value;
    }else{
      while(true){
        key++; // next to or start
        if(key === max){
          key = 0;
        }
        
        if(targets[key] === 0){
          targets[key] = value;
          break;
        }
      }
    }
  });
  return targets;
};

/***************************************
 * search
 ***************************************/
var hashSearch = function(value, list){
  var length = list.length,
      max = list.length -1,
      key = value % length,
      target;
  
  while(true){
    target = list[key];
    if(target === value){
      break;
    }
    if(key === max){
      key = 0;
    }else{
      key++;
    }
  }
  return key;
};

/***************************************
 * main
 ***************************************/
var rawData = [12,25,36,20,30,8,41],
    data = new Array(rawData.length * 2), // prepare * 1.5 - 2 length
    target = 36,
    result;

data = initData(data);
data = setData(rawData, data); // [0, 0, 30, 0, 0, 0, 20, 0, 36, 8, 0, 25, 12, 41] 

result = hashSearch(target, data);
console.log('index of tartget(' + target + ') is ' + result);

Test

/***************************************
 * util
 ***************************************/
var initData = function(list){
  for(var i = 0; i < list.length; i++){
    list[i] = 0;
  }
  return list;
};

/***************************************
 * set
 ***************************************/
var setData = function(data, targets){
  var key,
      length = targets.length,
      max = targets.length-1;
  data.forEach(function(value){
    key = value % length;
    if(targets[key] === 0){
      targets[key] = value;
    }else{
      while(true){
        key++; // next to or start
        if(key === max){
          key = 0;
        }
        
        if(targets[key] === 0){
          targets[key] = value;
          break;
        }
      }
    }
  });
  return targets;
};

/***************************************
 * search
 ***************************************/
var hashSearch = function(value, list){
  var length = list.length,
      max = list.length -1,
      key = value % length,
      target;
  
  while(true){
    target = list[key];
    if(target === value){
      break;
    }
    if(key === max){
      key = 0;
    }else{
      key++;
    }
  }
  return key;
};

/***************************************
 * main
 ***************************************/
var rawData = [12,25,36,20,30,8,41],
    data = new Array(rawData.length * 2), // prepare * 1.5 - 2 length
    target = 36,
    result;

data = initData(data);
data = setData(rawData, data); // [0, 0, 30, 0, 0, 0, 20, 0, 36, 8, 0, 25, 12, 41] 

result = hashSearch(target, data);
console.log('index of tartget(' + target + ') is ' + result);

See the Pen hashing search algorithm in JavaScript by Tomoyuki kashiro (@Tkashiro) on CodePen.

What is Binary search algorithm ?

the algorithm compares the search key value with the key value of the middle element of the array. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the search key is less than the middle element’s key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right. If the remaining array to be searched is empty, then the key cannot be found in the array and a special “not found” indication is returned.

http://en.wikipedia.org/wiki/Binary_search_algorithm

The array you look for in have to sorted.

Code

/***************************************
 * search
 ***************************************/
var binarySearch = function(list, target){
  var middleIndex,
      middle,
      result = 'nothing';
  
  while(list.length > 0){

    var middleIndex = Math.floor(list.length/2);
    var middle = list[middleIndex];
  
    if(middle === target){
      result = target;
      break;
    }

    if(middle > target){
      list = list.slice(0,middleIndex);
    }else{
      list = list.slice(middleIndex+1);
    }

  }
  return result;
  
};

/***************************************
 * main
 ***************************************/
var list = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19],
  target = 15,
  result = binarySearch(list, target);

console.log(list);
console.log('index of tartget(' + target + ') is ' + result);

Test

/***************************************
 * search
 ***************************************/
var binarySearch = function(list, target){
  var middleIndex,
      middle,
      result = 'nothing';
  
  while(list.length > 0){

    var middleIndex = Math.floor(list.length/2);
    var middle = list[middleIndex];
  
    if(middle === target){
      result = target;
      break;
    }

    if(middle > target){
      list = list.slice(0,middleIndex);
    }else{
      list = list.slice(middleIndex+1);
    }

  }
  return result;
  
};
/***************************************
 * search using closure
 ***************************************/
//var binarySearch = function(list, target){
//  var result;
//  
//  (function search(list, target){
//    var middleIndex = Math.floor(list.length/2);
//    var middle = list[middleIndex];
//  
//    if(middle === target){
//      result = target;
//      return;
//    }
//
//    if(middle > target){
//      list = list.slice(0,middleIndex);
//    }else{
//      list = list.slice(middleIndex+1);
//    }
//    
//    if(list.length === 0){
//      result = 'nothing';
//    }else{
//      search(list, target); 
//    }
//    
//  })(list, target);
//  
//  return result;
//};

/***************************************
 * main
 ***************************************/
var list = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19],
  target = 15,
  result = binarySearch(list, target);

console.log(list);
console.log('index of tartget(' + target + ') is ' + result);

See the Pen Binary search algorithm in JavaScript by Tomoyuki kashiro (@Tkashiro) on CodePen.

What is linear search algorithm ?

  • find something in order from the beginning of array.

Code

/***************************************
  * Util
  ***************************************/
var getRandomNumList = function(num) {
  var i, j, tmp, random = new Array(num);
  random[0] = 0;

  for(i = num - 1; i > 0; i--){
    j = Math.floor(Math.random() * (i+1));
    tmp = random[i] || i;
    random[i] = random[j] || j;
    random[j] = tmp;
  }
  return random;
};

/***************************************
 * search
 ***************************************/
var linearSearch = function(list, target){
  var result = null,
      i = 0, value;
  for(; i < list.length; i++){
    value = list[i];
    if(value === target){
      result = i;
      break;
    }
  }
  return result;
};

/***************************************
 * main
 ***************************************/
var list = getRandomNumList(100),
  target = 83;
  result = linearSearch(list, target);

console.log(list);
console.log('index of tartget(' + target + ') is ' + result);

Test

/***************************************
 * Util
 ***************************************/
var getRandomNumList = function(num) {
  var i, j, tmp, random = new Array(num);
  random[0] = 0;

  for(i = num - 1; i > 0; i--){
    j = Math.floor(Math.random() * (i+1));
    tmp = random[i] || i;
    random[i] = random[j] || j;
    random[j] = tmp;
  }
  return random;
};

/***************************************
 * search
 ***************************************/
var linearSearch = function(list, target){
  var result = null,
      i = 0, value;
  for(; i < list.length; i++){
    value = list[i];
    if(value === target){
      result = i;
      break;
    }
  }
  return result;
};

/***************************************
 * main
 ***************************************/
var list = getRandomNumList(100),
  target = 83;
  result = linearSearch(list, target);

console.log(list);
console.log('index of tartget(' + target + ') is ' + result);

See the Pen Linear search algorithm in JavaScript by Tomoyuki kashiro (@Tkashiro) on CodePen.

Outline

understand about shadow dom deeply. if you have not read session 1 yet please check it.

Multi shadow root

Shadow trees added to a host are stacked in the order they’re added, starting with the most recent first. The last one added is the one that renders.

Reference: http://www.html5rocks.com/en/tutorials/webcomponents/shadowdom-301/#toc-shadow-multiple

code:

<div id="host">
	<span>contents</span>
</div>
<script>
	var host = document.querySelector('#host');
	var root1 = host.createShadowRoot();
	var root2 = host.createShadowRoot();

	root1.innerHTML = '<div>root1 inner</div>';
	root2.innerHTML = '<div>root2 inner</div>';
</script>

result:

screenshot

screenshot

Shadow Insertion Points

code:

<div id="host">
	<h2>contents</h2>
</div>
<script>
	var container = document.querySelector('div');
	
	var root1 = container.createShadowRoot();
	var root2 = container.createShadowRoot();
	root1.innerHTML = '<div>Root 1</div><content></content>';
	root2.innerHTML = '<div>Root 2</div><shadow></shadow>';
</script>

result:

  • root2 insert shadowRoot of container
  • root1 insert Shadow Insertion Points of root2
  • content insert <content> of root1

screenshot

screenshot

content.getDistributedNodes()

You can not get inner element of ‘'. You have to use `content.getDistributedNodes`.

<div id="host2">
	<h2 id="title">title</h2>
</div>

<script>
	var host = document.querySelector('#host2');
	var root1 = host.createShadowRoot();
	var root2 = host.createShadowRoot();

	root1.innerHTML = '<content select="#title"></content>';
	root2.innerHTML = '<shadow></shadow>';

	// you can not get h2 in content element
	console.log(root1.querySelector('content[select="#title"] h2')); // null;

	var content = root1.querySelector('content[select="#title"]');
	console.log(content.getDistributedNodes()); // h2#title
</script>

element.getDestinationInsertionPoints()

You can find insert point which the element insert into using element.getDestinationInsertionPoints()

<div id="host2">
	<h2 id="title">title</h2>
</div>

<script>
	var host = document.querySelector('#host2');
	var root1 = host.createShadowRoot();
	var root2 = host.createShadowRoot();

	root1.innerHTML = '<content select="#title"></content>';
	root2.innerHTML = '<shadow></shadow>';

	var h2 = document.querySelector('h2#title');
	console.log(h2.getDestinationInsertionPoints()); // 
	
</script>

result:

This means that h2#title is in <content> in <shadow>.

screenshot

Reference

Outline

We’ve not had way to import html until now. But from now, we can import html documents using html import.

Capability

can i use : http://caniuse.com/#feat=imports

At the moment (2014/11/01) we can it only Google Chrome, Opera, and Chrome for Android

Usage

Import HTML from main HTML

You can import HTML using <link rel="import">

main HTML

<head>
	<link rel="import" href="/path/to/imports/stuff.html">
</head>

You have to append elements you import if you want to use it.

Imported HTML (stuff.html)

<nav>
	<ul>
		<li>page 1</li>
		<li>page 2</li>
		<li>page 3</li>
	</ul>
</nav>

<script>
	var importDoc = document.currentScript.ownerDocument; // imported HTML
	var mainDoc = document; // main HTML
	var nav = importDoc.querySelector('nav');
	mainDoc.querySelector('.navi-outer').appendChild(nav.cloneNode(true));
</script>

You can also use imported elements from main HTML like that.

main HTML

var link = document.querySelector('link[rel="import"]');
var nav = link.import.querySelector('nav');
document.querySelector('.navi-outer').appendChild(nav.cloneNode(true));

Import CSS in imported HTML

Imported HTML

<link rel="stylesheet" href="/path/to/imports/stuff.css">

You have to append link tag if you want to apply that style.

Imported HTML (stuff.html)

<link rel="stylesheet" href="/path/to/imports/stuff.css">
<script>
	var importDoc = document.currentScript.ownerDocument; // imported HTML
	var mainDoc = document; // main HTML
	var style = importDoc.querySelector('link[rel="stylesheet"]');
	mainDoc.head.appendChild(style.cloneNode(true));
</script>

Javascript context in imported HTML

You can use those contexts in imported document.

  • imported HTML context using document.currentScript.ownerDocument.
  • main HTML context using document

Notice

  • Resources from other origins need to be CORS-enabled.
  • Browser of course will cache each document you import.
  • Javascript are parsed and executed once if you import same url html twice.
  • Do not block main document parsing.
  • You have to add css and html tag after import html.

References