//--------------------- COLLECTIONS ------------------------------

// LinkedList
/*
function LinkedList() {
	this.head = new Node( null, null, null );
	this.tail = new Node( null, null, null );
	this.head.next = this.tail;
	this.tail.previous = this.head;
	this.tail.next = this.tail;
}

function Node( _element, _previous, _next ) {
	this.element = _element;
	this.previous = _previous;
	this.next = _next;
}

LinkedList.prototype.addLast = function( _element ) {
	var previous = this.tail.previous;
	var node = new Node( _element, previous, this.tail );
	previous.next = node;
	this.tail.previous = node;
}

LinkedList.prototype.addFirst = function( _element ) {
	var node = new Node( _element, this.head, this.head.next );
	this.head.next.previous = node;
	this.head.next = node;
}

LinkedList.prototype.size = function() {
	var size = 0;
	var node = this.head;
	while( node.next != this.tail ) {
		size++;
		node = node.next;
	}
	return size;
}

LinkedList.prototype.isEmpty = function() {
	return this.head.next == this.tail;
}

LinkedList.prototype.getFirst = function() {
	return this.head.next.element;
}

LinkedList.prototype.getLast = function() {
	return this.tail.previous.element;
}

LinkedList.prototype.indexAt = function(_index) {
	var i = 0;
	var node = this.head.next;
	while( i != _index ) {
		i++;
		node = node.next;
	}
	return node.element;
}
*/

//  LinkedList

function LinkedList() {}
LinkedList.prototype = {
  length: 0,
  first: null,
  last: null,

  each: function(fn) {
    var node = this.first, n = this.length;
    for (var i = 0; i < n; i++) {
      fn(node, i);
      node = node.next;
    }
  },

  at: function(i) {
    if (!(i >= 0 && i < this.length)) { return null; }
    var node = this.first;
    while (i--) { node = node.next; }
    return node;
  },
  
  withData: function(data) {
    var node = this.first, n = this.length;
    while (n--) {
      if (node.data == data) { return node; }
      node = node.next;
    }
    return null;
  },

  randomNode: function() {
    var n = Math.floor(Math.random() * this.length);
    return this.at(n);
  },

  toArray: function() {
    var arr = [], node = this.first, n = this.length;
    while (n--) {
      arr.push(node.data || node);
      node = node.next;
    }
    return arr;
  }
};

LinkedList.Node = function(data) {
  this.prev = null; this.next = null;
  this.data = data;
};

LinkedList.Circular = function() {};
LinkedList.Circular.Methods = {
  append: function(node) {
    if (this.first === null) {
      node.prev = node;
      node.next = node;
      this.first = node;
      this.last = node;
    } else {
      node.prev = this.last;
      node.next = this.first;
      this.first.prev = node;
      this.last.next = node;
      this.last = node;
    }
    this.length++;
  },

  prepend: function(node) {
    if (this.first === null) {
      this.append(node);
      return;
    } else {
      node.prev = this.last;
      node.next = this.first;
      this.first.prev = node;
      this.last.next = node;
      this.first = node;
    }
    this.length++;
  },

  insertAfter: function(node, newNode) {
    newNode.prev = node;
    newNode.next = node.next;
    node.next.prev = newNode;
    node.next = newNode;
    if (newNode.prev == this.last) { this.last = newNode; }
    this.length++;
  },

  insertBefore: function(node, newNode) {
    newNode.prev = node.prev;
    newNode.next = node;
    node.prev.next = newNode;
    node.prev = newNode;
    if (newNode.next == this.first) { this.first = newNode; }
    this.length++;
  },

  remove: function(node) {
    if (this.length > 1) {
      node.prev.next = node.next;
      node.next.prev = node.prev;
      if (node == this.first) { this.first = node.next; }
      if (node == this.last) { this.last = node.prev; }
    } else {
      this.first = null;
      this.last = null;
    }
    node.prev = null;
    node.next = null;
    this.length--;
  }
};

LinkedList.Circular.prototype = new LinkedList;
for (var method in LinkedList.Circular.Methods) {
  LinkedList.Circular.prototype[method] = LinkedList.Circular.Methods[method];
}

LinkedList.Circular.fromArray = function(list, useNodes) {
  var linked = new LinkedList.Circular();
  var n = list.length;
  while (n--) { linked.prepend(useNodes ? new LinkedList.Node(list[n]) : list[n]); }
  return linked;
};



// Hashmap ---------------------------------------------------------------------------

function HashMap() {
	this.objects = new Array();
}

HashMap.prototype.put = function( _key, _object ) {
	this.objects[ '@' + _key ] = _object;
}

HashMap.prototype.get = function( _key ) {
	_key = String( _key );
	if( _key.match( '^@.*$' ) ) {
		return this.objects[ _key ];
	}
	return this.objects[ '@' + _key ];
}

HashMap.prototype.getKeys = function() {
	return this.objects;
}

HashMap.prototype.toString = function() {
	var string = 'HashMap [ ';
	for( var key in this.objects ) {
		string += key + ' = ' + this.objects[ key ] + ', ';
	}
	if( string.length > 10 ) {
		string = string.substring( 0, string.length - 2 );
	}
	string += ' ]';
	return string;
}
// eigene
HashMap.prototype.size = function(){
	var size = 0;
	for (key in this.objects){
		if (typeof(key) != "function") size ++;
	}
	return size;
}

HashMap.prototype.containsKey = function(_key){
    var contains = false;
    var keyname = '@' + _key
   	for (key in this.objects){
		if (key.toString() == keyname.toString()) {
		    contains = true;
		}
	}
	return contains;
}

HashMap.prototype.clear = function(){
	this.objects = new Array();
}

HashMap.prototype.isEmpty=function(){
 return this.size()==0;
}

HashMap.prototype.remove = function(_key) {
    var keyname = '@' + _key
    var dummyHashMap = new HashMap();
    for (key in this.objects){
      if (key.toString() != keyname.toString()) {
	  dummyHashMap.put (key.substring( 1, key.length),this.objects[key]);
	  }
	}
	this.clear();
	for (key in dummyHashMap.objects){
	     this.put (key.substring( 1, key.length),dummyHashMap.objects[key]);
    }
}

HashMap.prototype.containsValue = function(value){
	var contains = false;
	for (key in this.objects){
		if (this.objects[key] = value) contains = true;
	}
	return contains;
}

HashMap.prototype.toArray = function(value){
	var resultArray = new Array();
	for (key in this.objects){
		if ( this.objects.hasOwnProperty(key)){
		  resultArray.push (this.objects[key]);
		}
	}
	return resultArray;
}


// Arrays -----------------------------------------------------------------------

Array.prototype.contains = function (element){          
	for (var i = 0; i < this.length; i++){
		if (this[i] == element){  
			return true; 
			}         
		}          
	return false;  
};