1: <?php
2: /*
3: * Copyright (c) 2014 @trashtoy
4: * https://github.com/trashtoy/
5: *
6: * Permission is hereby granted, free of charge, to any person obtaining a copy of
7: * this software and associated documentation files (the "Software"), to deal in
8: * the Software without restriction, including without limitation the rights to use,
9: * copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the
10: * Software, and to permit persons to whom the Software is furnished to do so,
11: * subject to the following conditions:
12: *
13: * The above copyright notice and this permission notice shall be included in all
14: * copies or substantial portions of the Software.
15: *
16: * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17: * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
18: * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
19: * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
20: * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21: * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22: */
23: /**
24: * PHP class file.
25: * @auhtor trashtoy
26: * @since 2.0.0
27: */
28: namespace Peach\Util;
29:
30: /**
31: * 任意の値やオブジェクトをキーに指定することが出来る Map です. 格納のアルゴリズムは
32: * {@link http://docs.oracle.com/javase/jp/7/api/java/util/HashMap.html java.util.HashMap}
33: * を参考にしています.
34: * キーに使用するオブジェクトは, 出来る限り不変 (イミュータブル) なものを使用してください.
35: * キーに設定したオブジェクトに対して外部から変更が加わった場合,
36: * このオブジェクトの動作は保障されません.
37: */
38: class HashMap implements Map
39: {
40: /**
41: * このマップが持つエントリーの一覧です.
42: * この値は以下のような構造となります. (値は HashMapEntry オブジェクト)
43: *
44: * <pre>
45: * array(
46: * [0] => array(
47: * [0] => entry1
48: * [1] => entry4
49: * [2] => entry5
50: * )
51: * [1] => array(
52: * [0] => entry2
53: * [1] => entry3
54: * )
55: * [2] => ...
56: * )
57: * </pre>
58: *
59: * @var array
60: */
61: private $table;
62:
63: /**
64: * 格納先のインデックスの個数です.
65: * 常に 2 の累乗の値になります.
66: *
67: * @var int
68: */
69: private $capacity;
70:
71: /**
72: * キーの等価性のチェックを行うために使用する Equator です.
73: * @var Equator
74: */
75: private $equator;
76:
77: /**
78: * put() や remove() などで内部構造に変化が加えられたことを示すフラグです.
79: * {@link HashMap::entryList} を呼び出した際にキャッシュを使用するかどうか
80: * 判断するために使用します.
81: *
82: * @var bool
83: */
84: private $modFlag;
85:
86: /**
87: * {@link HashMap::entryList} の返り値のキャッシュデータです.
88: * この値はオブジェクトの内部構造が変化すると無効化されます.
89: *
90: * @var array
91: */
92: private $cache;
93:
94: /**
95: * 新しい HashMap を構築します.
96: * 引数で設定された容量は, オブジェクト構築後に変更することは出来ません.
97: *
98: * @param Map|array $map デフォルトのマッピング (オプション)
99: * @param Equator $e オブジェクトの等価性を判断するための Equator
100: * (NULL の場合は {@link DefaultEquator} が適用されます)
101: * @param int $capacity 容量 (デフォルトは 16, 最小で 2)
102: */
103: public function __construct($map = null, Equator $e = null, $capacity = 16)
104: {
105: $this->table = array();
106: $this->equator = isset($e) ? $e : DefaultEquator::getInstance();
107: $this->capacity = self::detectCapacity($capacity);
108: $this->modFlag = true;
109: $this->cache = array();
110: if (isset($map)) {
111: $this->initTable($map);
112: }
113: }
114:
115: /**
116: * コンストラクタの第一引数が指定された場合に実行される,
117: * マッピングの初期化処理です.
118: *
119: * @param Map|array $map
120: */
121: private function initTable(&$map)
122: {
123: if ($map instanceof Map) {
124: $entryList = $map->entryList();
125: foreach ($entryList as $entry) {
126: $this->put($entry->getKey(), $entry->getValue());
127: }
128: return;
129: }
130: if (is_array($map)) {
131: foreach ($map as $key => $value) {
132: $this->put($key, $value);
133: }
134: return;
135: }
136:
137: throw new \InvalidArgumentException("Argument (" . Values::getType($map) . ") must be array or \\Peach\\Util\\Map");
138: }
139:
140: /**
141: * このマップの容量を計算します.
142: * 引数以上で最小の 2 の累乗となる整数を返します.
143: * @param int $capacity 容量
144: */
145: private static function detectCapacity($capacity)
146: {
147: if ($capacity < 2) {
148: return 2;
149: }
150:
151: $i = 2;
152: while ($i < $capacity) {
153: $i *= 2;
154: }
155: return $i;
156: }
157:
158: /**
159: * 指定されたキーと値をこの Map に関連づけます.
160: * @param mixed $key キー
161: * @param mixed $value 値
162: */
163: public function put($key, $value)
164: {
165: $index = $this->getIndexOf($key);
166: if (!isset($this->table[$index])) {
167: $this->table[$index] = array();
168: }
169: foreach ($this->table[$index] as $entry) {
170: if ($entry->keyEquals($key, $this->equator)) {
171: $entry->setValue($value);
172: $this->modFlag = true;
173: return;
174: }
175: }
176: $this->table[$index][] = $this->createEntry($key, $value);
177: $this->modFlag = true;
178: }
179:
180: /**
181: * 指定された Map の中身をすべて追加します。
182: * もしも引数の Map とこの Map に同じキーが存在していた場合,
183: * 引数のマッピングで上書きされます.
184: *
185: * @param Map $map 格納される Map
186: * @see Map::putAll
187: */
188: public function putAll(Map $map)
189: {
190: $entryList = $map->entryList();
191: foreach ($entryList as $entry) {
192: $this->put($entry->getKey(), $entry->getValue());
193: }
194: }
195:
196: /**
197: * 指定されたキーにマッピングされている値を返します.
198: * マッピングが存在しない場合は代替値 (デフォルトは NULL) を返します.
199: * このメソッドの返り値が NULL (または指定した代替値) の場合, 必ずしもマッピングが存在しないとは限りません.
200: * マッピングの存在を確認する場合は {@link HashMap::containsKey} を使用してください.
201: *
202: * @param mixed $key マッピングのキー
203: * @param mixed $defaultValue マッピングが存在しない場合に返される代替値
204: * @return mixed
205: */
206: public function get($key, $defaultValue = null)
207: {
208: $index = $this->getIndexOf($key);
209: if (!isset($this->table[$index])) {
210: return $defaultValue;
211: }
212: foreach ($this->table[$index] as $entry) {
213: if ($entry->keyEquals($key, $this->equator)) {
214: return $entry->getValue();
215: }
216: }
217: return $defaultValue;
218: }
219:
220: /**
221: * マッピングを空にします.
222: */
223: public function clear()
224: {
225: $this->table = array();
226: $this->modFlag = true;
227: }
228:
229: /**
230: * この Map が持つマッピングの個数を返します.
231: * @return int
232: * @see Map::size
233: */
234: public function size()
235: {
236: $size = 0;
237: foreach ($this->table as $entries) {
238: $size += count($entries);
239: }
240: return $size;
241: }
242:
243: /**
244: * この HashMap に含まれるキーの一覧を返します.
245: * @return array この HashMap に含まれるキーの配列
246: */
247: public function keys()
248: {
249: $result = array();
250: foreach ($this->table as $entries) {
251: foreach ($entries as $entry) {
252: $result[] = $entry->getKey();
253: }
254: }
255: return $result;
256: }
257:
258: /**
259: * 指定されたキーによるマッピングが存在するかどうかを調べます.
260: * マッピングが存在する場合に TRUE を返します.
261: *
262: * @param mixed $key キー
263: * @return bool マッピングが存在する場合に TRUE
264: */
265: public function containsKey($key)
266: {
267: $index = $this->getIndexOf($key);
268: if (!isset($this->table[$index])) {
269: return false;
270: }
271: foreach ($this->table[$index] as $entry) {
272: if ($entry->keyEquals($key, $this->equator)) {
273: return true;
274: }
275: }
276: return false;
277: }
278:
279: /**
280: * 指定されたキーのマッピングを削除します.
281: * @param mixed $key キー
282: */
283: public function remove($key)
284: {
285: $index = $this->getIndexOf($key);
286: if (!isset($this->table[$index])) {
287: return;
288: }
289: foreach ($this->table[$index] as $i => $entry) {
290: if ($entry->keyEquals($key, $this->equator)) {
291: array_splice($this->table[$index], $i, 1);
292: $this->modFlag = true;
293: return;
294: }
295: }
296: return;
297: }
298:
299: /**
300: * このマップに登録されているすべての値を配列で返します.
301: * 返される配列に対する操作はこのマップには反映されません.
302: * @return array
303: */
304: public function values()
305: {
306: $result = array();
307: foreach ($this->table as $entries) {
308: foreach ($entries as $entry) {
309: $result[] = $entry->getValue();
310: }
311: }
312: return $result;
313: }
314:
315: /**
316: * この HashMap に登録されているすべてのエントリーを返します.
317: *
318: * @return array {@link HashMapEntry} の配列
319: */
320: public function entryList()
321: {
322: if ($this->modFlag) {
323: $this->cache = array();
324: foreach ($this->table as $entries) {
325: foreach ($entries as $entry) {
326: $this->cache[] = $entry;
327: }
328: }
329: $this->modFlag = false;
330: }
331: return $this->cache;
332: }
333:
334: /**
335: * 指定されたキーと値をマッピングする, 新しい {@link HashMapEntry} を構築します.
336: * ユーザーは, 必要に応じてこのメソッドをオーバーライドし,
337: * 機能拡張した HashMapEntry を返すようにすることもできます.
338: *
339: * @param mixed $key マッピングのキー
340: * @param mixed $value マッピングの値
341: * @return HashMapEntry 引数の $key と $value をマッピングした HashMapEntry
342: */
343: protected function createEntry($key, $value)
344: {
345: return new HashMapEntry($key, $value);
346: }
347:
348: /**
349: * 指定されたキーのインデックスを返します.
350: * @param string $key
351: * @return int
352: */
353: private function getIndexOf($key)
354: {
355: $hash = $this->equator->hashCode($key);
356: return ($this->capacity - 1) & $hash;
357: }
358: }
359: