PHPでゲール-シャプレイ (Gale-Shapley) アルゴリズム書いてみた

# 概要
ゲール-シャプレイ (Gale-Shapley) アルゴリズムをPHPで実装してみた。安定結婚問題を解くもの。
適当なデータ引っ張ってきて、適用して遊ぶ予定。

#### 参考
[安定マッチング問題 - 情報学広場](https://www.google.co.jp/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&uact=8&ved=0ahUKEwj5-oXUptPTAhVGO7wKHZKkDKMQFgguMAE&url=https%3A%2F%2Fipsj.ixsq.nii.ac.jp%2Fej%2F%3Faction%3Drepository_uri%26item_id%3D95196%26file_id%3D1%26file_no%3D1&usg=AFQjCNGZv9D0ZTS8cDCCEaj48snPE4FSXQ&sig2=H9GM9rSbyTVg-5DWF993kw)

# 動機
- ストレス解消
- PHPの勉強

#### ありか
https://github.com/kuredev/Algorithm

# コード

```php:GaleShapley.php
<?php

namespace Kuredev\GaleShapley;

/**
 *
 * @author kure
 *         Usage
 *
 */
class GaleShapley {
	private $menArray = array ();
	private $womenArray = array ();
	private $matches;

	/**
	 *
	 * @param array $menArray
	 * @param array $womenArray
	 */
	public function __construct(array $menArray, array $womenArray) {
		$this->menArray = $menArray;
		$this->womenArray = $womenArray;
		$this->matches = new Matches ();
	}

	private function isFreeMan(array $menArray) {
		$flag = null;
		foreach ( $menArray as $man ) {
			if ($man->isMarried ()) {
			}else{
				return true;
			}
		}
		return false;
	}

	private function getWomanByName(string $name){
		foreach ($this->womenArray as $woman){
			if($woman->getName() === $name){
				return $woman;
			}
		}
	}

	private function getManByName(string $name){
		foreach ($this->menArray as $man){
			if($man->getName() === $name){
				return $man;
			}
		}
	}

	private function getFreeMan(array $memArray) {
		foreach ( $memArray as $man ) {
			if (! $man->isMarried ()) {
				return $man;
			}
		}
	}

	public function calc() {
		while ( $this->isFreeMan ( $this->menArray ) ) {
			// foreach ( $this->menArray as $m ) {
			$m = $this->getFreeMan ( $this->menArray );
			// mの選好リストの先頭の女性をwとする
			$w = $this->getWomanByName($m->getMostPreferPerson ());
			// wがフリー
			if (! $w->isMarried ()) {
				$this->matches->addMatch ( new Match ( $m, $w ) );
			} else {
				// wの婚約相手をm'とする
				$marriedManName = $w->getMarriedMan ();
				$m_ = $this->getManByName($marriedManName);
				// wはmよりm'が好き
				if ($w->isMorePrefered ( $m_, $m )) {
					// mの選好リストからwを削除する
					$m->deletePrederdWoman ( $w->getName () );
				} else {
					// Mから(m',w)を削除し、(m,w)を加える
					$this->matches->deleteMatch ( $m_->getName (), $w->getName () );
					$this->matches->addMatch ( new Match ( $m, $w ) );
					$m_->deletePreferPerson ( $w->getName () );
				}
			}
		}
//		var_dump($this->matches);
		return $this->matches;
	}
}


class Match {
	private $man, $woman;
	public function __construct(Man $man, Woman $woman) {
		$this->man = $man;
		$this->woman = $woman;
	}
	public function getWoman() {
		return $this->woman;
	}
	public function getMan() {
		return $this->man;
	}
	public function getWomanName() {
		return $this->woman->getName ();
	}
	public function getManName() {
		return $this->man->getName ();
	}
}

class Matches {
	private $matchArr = array ();
	public function addMatch(Match $m) {
		array_push ( $this->matchArr, $m );
		$m->getMan ()->marry ( $m->getWoman ()->getName () );
		$m->getWoman ()->marry ( $m->getMan ()->getName () );
	}
	public function deleteMatch(string $manName, string $womanName) {
		foreach ( $this->matchArr as $key => $match ) {
			if ($match->getManName () === $manName) {
				if ($match->getWomanName () === $womanName) {
					unset ( $this->matchArr [$key] );
					$match->getWoman ()->unMarry ();
					$match->getMan ()->unMarry ();
				}
			}
		}
	}
}

class Man extends Person {
	public function getMarriedWoman() {
		return $this->marriedName;
	}
	public function deletePrederdWoman(string $womanName) {
		if (($key = array_search ( $womanName, $this->preferArray )) !== false) {
			unset ( $this->preferArray [$key] );
		}
	}
}

class Woman extends Person {
	public function getMarriedMan() {
		return $this->marriedName;
	}
}

class Person {
	protected  $name;
	protected  $preferArray;
	protected  $marriedName;

	/**
	 * p1がp2より好きか
	 *
	 * @param unknown $p1
	 * @param unknown $p2
	 */
	public function isMorePrefered($p1, $p2) {
		$p1num = array_keys ( $this->preferArray, $p1->getName () ) [0];
		$p2num = array_keys ( $this->preferArray, $p2->getName () ) [0];
		if ($p1num < $p2num) {
			return true;
		} else {
			return false;
		}
	}

	/**
	 *
	 * @param string $name
	 * @param array[string] $preferArray
	 */
	public function __construct($name, $preferArray) {
		$this->name = $name;
		$this->preferArray = $preferArray;
	}

	public function getMostPreferPerson() {
		return array_values ( $this->preferArray ) [0];
	}

	public function isMarried() {
		if ($this->marriedName == null) {
			return false;
		} else {
			return true;
		}
	}
	public function getName() {
		return $this->name;
	}

	public function deletePreferPerson(string $name) {
		if (($key = array_search ( $name, $this->preferArray )) !== false) {
			unset ( $this->preferArray [$key] );
		}
	}
	public function marry($name) {
		$this->marriedName = $name;
	}
	public function unMarry() {
		$this->marriedName = null;
	}
}

```