stablematch8.js

/**
 * Cyclic Elimination Stage 3
 * - description needed
 */
function _cycleReduceStage() {
    let stable = false;
	// all or nothing phase
    while(!stable) {
	  // there is a start if any one person has more than 1 preference remaining
      let start = indexWithMultipleRemain();

      if(start) {
        let p = _DB[ _DB[start].id ]; // starting person
        let q = _DB[ _DB[start].choices[1].id ]; // their second preference

        let currentPair = [p,q];
        let cyclePairs = [currentPair]; // first pair in cycle
  			// cyclic reduction
        let cycle = false;

        while(!cycle) {
		  // redefine p and q during the iterative process
          p = _DB[q.choices[q.choices.length - 1 ].id];
          q = _DB[p.choices[1]] ? _DB[p.choices[1].id]  : _DB[p.choices[p.choices.length - 1 ].id] ;
          let newPair = [p,q];

		  // look for a cycle in cyclePairs before pushing into it, check the new p to see if its reoccured
          let spotCycle = _.findIndex(cyclePairs, (pair) => { return pair[0].id == p.id; });
          cyclePairs.push(newPair);

		  // there was a cycle found, go through with the diagnal elimination phase
          if ( spotCycle != -1 ) {
            cycle = true;
  					// cycle pairs should start where the cycle was found
            cyclePairs.splice(0,spotCycle);
            eliminateDiagnals(cyclePairs);
          }
        };
      }	else {
        stable = true;
      }

    };

	// loop condition looking for persons who have multiple remaining preferences
    function indexWithMultipleRemain() {
      let start = false;
      _.forIn(_DB, (person,key) => {
        if( person.choices.length > 1 ) {
          start = (start != false) ? start : key;
        }
      });
      return start;
    }

    // deletes prefences that resulted in the diagnal pattern found above
    function eliminateDiagnals(pairs) {
			// start at second element for diagnal rejection
      for(let i = 1; i < pairs.length; i++) {
				// the [i - 1][1] creates the diagnal effect
        eliminateChoices(_DB[pairs[i][0].id],_DB[pairs[i - 1][1].id]);
      }
    }

    // not needed for now
    //
    // function removeRejects() {
    // 	_.forIn(_DB, (person, key) => {
    // 		if(person.choices.length < 1) {
    // 			console.log("HEY ==> " + person.id)
    // 			deleteFromPool(person.id)
    // 		}
    // 	});
    // }
    // function deleteFromPool(rid) {
    // 	_REMOVED[rid] = _.cloneDeep(_DB[rid]);
    // 	delete _DB[rid];
    // 	_.forIn(_DB, (person,key) => {
    // 		let remove = _.findIndex(person.choices, function(p) { return p.id == rid; });
    // 		person.choices.splice(remove, 1);
    // 	});
    // }

}