containers php

データコンテナ

PHP の抽象データ コンテナと構造

プロジェクトに依存関係としてインストールする方法

 composer require smoren/containers

単体テスト

 composer install
./vendor/bin/codecept build
./vendor/bin/codecept run unit tests/unit

リンクリスト

リンクされたリスト構造の古典的な実装。スタックやキューとしても使用できます。

 use Smoren  Containers  Structs  LinkedList ;
use Smoren  Containers  Structs  LinkedListItem ;

$ ll = new LinkedList ([ 6 , 4 , 2 ]);
var_dump ( $ ll -> count ()); // output: 3

$ ll -> pushBack ( 1 );
$ ll -> pushFront ( 7 );
var_dump ( $ ll -> count ()); // output: 5
print_r ( $ ll -> toArray ()); // output: [7, 6, 4, 2, 1]

$ ll -> sort ( function ( $ lhs , $ rhs ) {
    return $ lhs > $ rhs ;
});

print_r ( $ ll -> toArray ()); // output: [1, 2, 4, 6, 7]

$ ll -> swap ( $ ll -> getFirst (), $ ll -> getLast ());
print_r ( $ ll -> toArray ()); // output: [7, 2, 4, 6, 1]

$ ll -> swap ( $ ll -> getFirst ()-> getNext (), $ ll -> getLast ()-> getPrev ());
print_r ( $ ll -> toArray ()); // output: [7, 6, 4, 2, 1]

var_dump ( $ ll -> popFront ()); // output: 7
var_dump ( $ ll -> popBack ()); // output: 1
print_r ( $ ll -> toArray ()); // output: [6, 4, 2]

$ ll -> delete ( $ ll -> getFirst ()-> getNext ());
print_r ( $ ll -> toArray ()); // output: [6, 2]

$ llNew = LinkedList:: merge ( new LinkedList ([- 2 , - 1 ]), $ ll , new LinkedList ([ 1 , 2 ]));
var_dump ( $ llNew -> count ()); // output: 6
print_r ( $ llNew -> toArray ()); // output: [-2, -1, 6, 2, 1, 2]

$ ll -> pushBefore ( $ ll -> getFirst (), - 3 );
$ ll -> pushAfter ( $ ll -> getLast (), 3 );
print_r ( $ llNew -> toArray ()); // output: [-3, -2, -1, 6, 2, 1, 2, 3]

/** 
 * @var LinkedListItem $id
 * @var mixed $item 
 */
foreach ( $ ll as $ id => $ item ) {
    // you can iterate collection
}

$ ll -> clear ();
print_r ( $ ll -> toArray ()); // output: []

マップされたコレクション

地図のようなデータ構造。

 use Smoren  Containers  Exceptions  MappedCollectionException ;
use Smoren  Containers  Structs  MappedCollection ;

$ coll = new MappedCollection ([ ' 1 ' => [ ' id ' => 1 ]]);
var_dump ( $ coll -> count ()); // output: 1
print_r ( $ coll -> toArray ()); // output: ['1' => ['id' => 1]]

$ coll -> add ( ' 2 ' , [ ' id ' => 2 ]);
var_dump ( $ coll -> count ()); // output: 1
print_r ( $ coll -> toArray ()); // output: ['1' => ['id' => 1], '2' => ['id' => 2]]

var_dump ( $ coll -> exist ( 1 )); // output: true
var_dump ( $ coll -> exist ( 2 )); // output: true
var_dump ( $ coll -> exist ( 3 )); // output: false

try {
    $ coll -> add ( ' 1 ' , [ ' id ' => 1 , ' extra ' => ' test ' ]);
} catch ( MappedCollectionException $ e ) {
    // cannot silently replace existing value
}

print_r ( $ coll -> get ( 1 )); // output: ['id' => 1]

$ coll -> replace ( ' 1 ' , [ ' id ' => 1 , ' extra ' => ' test ' ]);
print_r ( $ coll -> get ( 1 )); // output: ['id' => 1, 'extra' => 'test']

try {
    $ coll -> get ( ' 3 ' );
} catch ( MappedCollectionException $ e ) {
    // element with id = 3 does not exist so you cannot get it
}

/** 
 * @var string $id
 * @var mixed $item 
 */
foreach ( $ coll as $ id => $ item ) {
    // you can iterate collection
}

$ coll -> clear ();
print_r ( $ coll -> toArray ()); // output: []

マップされたリンクリスト

ID によるマッピングを含む LinkedList。

 use Smoren  Containers  Structs  MappedLinkedList ;

$ mll = new MappedLinkedList ([]);
var_dump ( $ mll -> count ()); // output: 0

$ mll -> pushBack ( 102 , 2 );
$ mll -> pushFront ( 101 , 1 );
$ mll -> pushBack ( 100 , 0 );
var_dump ( $ mll -> count ()); // output: 4
print_r ( $ mll -> toArray ()); // output: [101 => 1, 102 => 2, 100 => 0]]

$ mll -> sort ( function ( $ lhs , $ rhs ) {
    return $ lhs > $ rhs ;
});
print_r ( $ mll -> toArray ()); // output: [100 => 0, 101 => 1, 102 => 2]]

$ mll -> swap ( 100 , 101 );
print_r ( $ mll -> toArray ()); // output: [101 => 1, 100 => 0, 102 => 2]]

var_dump ( $ mll -> popFront ()); // output: [101, 1]
var_dump ( $ mll -> popBack ()); // output: [102, 2]
print_r ( $ mll -> toArray ()); // output: [100 => 0]

$ mllNew = MappedLinkedList:: merge (
    new MappedLinkedList ([- 999 => - 99 ]),
    $ mll ,
    new MappedLinkedList ([ 999 => 99 ])
);
var_dump ( $ mllNew -> count ()); // output: 5
print_r ( $ mllNew -> toArray ()); // output: [-999 => 99, 100 => 0, 999 => 9]

$ mllNew -> pushBefore ( 100 , - 101 , - 1 );
$ mllNew -> pushAfter ( 100 , 101 , 1 );
print_r ( $ mllNew -> toArray ()); // output: [-999 => 99, -101 => -1, 100 => 0, 101 => 1, 999 => 9]

/** 
 * @var string $id
 * @var mixed $value
 */
foreach ( $ mllNew as $ id => $ value ) {
    // you can iterate collection
}

$ mllNew -> clear ();
print_r ( $ mllNew -> toArray ()); // output: []

ソート済みリンクリスト

 use Smoren  Containers  Structs  SortedLinkedList ;
use Smoren  Containers  Exceptions  LinkedListException ;

/**
 * Class IntegerSortedLinkedList
 */
class IntegerSortedLinkedList extends SortedLinkedList
{
    /**
     * @inheritDoc
     */
    protected function getComparator (): callable
    {
        return function ( int $ lhs , int $ rhs ) {
            return $ lhs > $ rhs ;
        };
    }
}

$ sll = new IntegerSortedLinkedList ([ 2 , 5 , 1 ]);
var_dump ( $ sll -> count ()); // output: 3
print_r ( $ sll -> toArray ()); // output: [1, 2, 5]

$ sll -> insert ( 2 );
$ pos = $ sll -> insert ( 3 );
var_dump ( $ sll -> count ()); // output: 5
print_r ( $ sll -> toArray ()); // output: [1, 2, 2, 3, 5]

var_dump ( $ sll -> delete ( $ pos )); // output: 3
var_dump ( $ sll -> count ()); // output: 4
print_r ( $ sll -> toArray ()); // output: [1, 2, 2, 5]

var_dump ( $ sll -> popBack ()); // output: 5
var_dump ( $ sll -> popFront ()); // output: 1
var_dump ( $ sll -> count ()); // output: 2
print_r ( $ sll -> toArray ()); // output: [2, 2]

/** 
 * @var string $id
 * @var mixed $value
 */
foreach ( $ sll as $ id => $ value ) {
    // you can iterate collection
}

$ sll -> clear ();
var_dump ( $ sll -> count ()); // output: 0
print_r ( $ sll -> toArray ()); // output: []

try {
    $ sll -> popBack ();
} catch ( LinkedListException $ e ) {
    // cannot pop when collection is empty
}

try {
    $ sll -> popFront ();
} catch ( LinkedListException $ e ) {
    // cannot pop when collection is empty
}

ソートされたマップされたリンクされたリスト

事前ソートとマッピングを備えた LinkedList。

 use Smoren  Containers  Exceptions  MappedLinkedListException ;
use Smoren  Containers  Structs  LinkedListItem ;
use Smoren  Containers  Structs  SortedMappedLinkedList ;

$ smll = new SortedMappedLinkedList ([ 1 => - 1 , 10 => - 10 , 5 => - 5 ]);
var_dump ( $ smll -> count ()); // output: 3
print_r ( $ smll -> toArray ()); // output: [1 => -1, 5 => -5, 10 => -10]

$ smll -> insert ( 3 , - 3 );
var_dump ( $ smll -> count ()); // output: 4
print_r ( $ smll -> toArray ()); // output: [1 => -1, 3 => -3, 5 => -5, 10 => -10]

$ smll -> popBack ();
$ smll -> popFront ();
var_dump ( $ smll -> count ()); // output: 2
print_r ( $ smll -> toArray ()); // output: [3 => -3, 5 => -5]

/**
 * Class ArrayMappedSortedLinkedList
 */
class ArraySortedMappedLinkedList extends SortedMappedLinkedList
{
    /**
     * @inheritDoc
     */
    protected function getComparator (): callable
    {
        return function ( array $ lhs , array $ rhs ) {
            return $ lhs [ ' a ' ] > $ rhs [ ' a ' ];
        };
    }
}

$ ll = new ArraySortedMappedLinkedList ([
    - 5 => [ ' a ' => 5 ],
    - 1 => [ ' a ' => 1 ],
    - 2 => [ ' a ' => 2 ],
]);
var_dump ( $ smll -> count ()); // output: 3
print_r ( $ smll -> toArray ()); // output: [-1 => ['a' => 1], -2 => ['a' => 2], -5 => ['a' => 5]]

/** 
 * @var string $id
 * @var mixed $value
 */
foreach ( $ smll as $ id => $ value ) {
    // you can iterate collection
}

try {
    $ smll -> insert (- 2 , [ ' a ' => 2 , ' extra ' => ' test ' ]);
} catch ( MappedLinkedListException $ e ) {
    // cannot simply replace existing element
}

/** @var LinkedListItem $pos */
$ pos = $ ll -> delete (- 1 );
print_r ( $ pos -> getData ()); // output: ['a' => 1]
var_dump ( $ smll -> count ()); // output: 2
print_r ( $ smll -> toArray ()); // output: [-2 => ['a' => 2], -5 => ['a' => 5]]

print_r ( $ ll -> popBack ()); // output: [-5, ['a' => 5]]
print_r ( $ ll -> popFront ()); // output: [-2, ['a' => 2]]
var_dump ( $ smll -> count ()); // output: 0
print_r ( $ smll -> toArray ()); // output: []

グラフ

トラバース用ツールを備えたグラフ データ構造。

 use Smoren  Containers  Structs  Graph ;

$ graph = new Graph (
    [ 1 => 11 , 2 => 22 , 3 => 33 , 4 => 44 , 5 => 55 , 6 => 66 ],
    [[ 1 , 2 , ' a ' ], [ 2 , 3 , ' a ' ], [ 3 , 4 , ' a ' ], [ 2 , 5 , ' b ' ], [ 5 , 3 , ' b ' ], [ 5 , 6 , ' c ' ], [ 6 , 4 , ' c ' ]]
);

$ paths = $ graph -> traverseBackward ( 4 );
var_dump ( $ paths ); // output: 3
var_dump ( $ paths [ 0 ]-> toArray ( true )); // output: [4, 3, 2, 1]
var_dump ( $ paths [ 1 ]-> toArray ( true )); // output: [4, 3, 5, 2, 1]
var_dump ( $ paths [ 2 ]-> toArray ( true )); // output: [4, 6, 5, 2, 1]

$ paths = $ graph -> traverseForward ( 1 );
var_dump ( 3 , $ paths ); // output: 3
var_dump ( $ paths [ 0 ]-> toArray ( true )); // output: [1, 2, 3, 4]
var_dump ( $ paths [ 1 ]-> toArray ( true )); // output: [1, 2, 5, 3, 4]
var_dump ( $ paths [ 2 ]-> toArray ( true )); // output: [1, 2, 5, 6, 4]

$ paths = $ graph -> traverseForward ( 1 , [ ' a ' , ' b ' ]);
var_dump ( 2 , $ paths ); // output: 
var_dump ( $ paths [ 0 ]-> toArray ( true )); // output: [1, 2, 3, 4]
var_dump ( $ paths [ 1 ]-> toArray ( true )); // output: [1, 2, 5, 3, 4]

$ graph -> insert ( 7 , 77 );
$ graph -> link ( 7 , 1 , ' a ' );

$ paths = $ graph -> traverseBackward ( 7 );
var_dump ( $ paths ); // output: 3
var_dump ( $ paths [ 0 ]-> toArray ( true )); // output: [4, 3, 2, 1, 7]
var_dump ( $ paths [ 1 ]-> toArray ( true )); // output: [4, 3, 5, 2, 1, 7]
var_dump ( $ paths [ 2 ]-> toArray ( true )); // output: [4, 6, 5, 2, 1, 7]
var_dump ( $ paths [ 2 ]-> reverse ()-> toArray ( true )); // output: [1, 2, 5, 6, 4, 7]