Tango provides a number of collection classes, sometimes also called container classes.

Tango はいくつかのコレクションクラスを提供します。ときにコンテナクラスと呼ばれることもあります。

In tango they are located in the tango.util.collection package, which is home to a variety of templated containers.
Tango では、tango.util.collection にそれらのパッケージを位置づけていて、それらはさまざまなテンプレートライブラリのホームになっています。


Collection classes store things, and do so in different ways.
コレクションクラスはモノを異なる方法で収容します。

For example, the user can choose between a list and an array to store the same information
たとえば、利用者は同じ情報の収容方法を List か Array かで選択することができます。
 - each storage mechanism has its own pros and cons.
 ※それぞれのストレージの方法は一長一短があります。

The collection classes are templates, which means they need a type parameter specified for the things to be stored.
コレクションクラスはテンプレートクラスです。
これは、使用の際にテンプレートパラメータを入力する必要があるということです。

It is good practice to define an alias for the type one wants to use 
使用の際には別名をつけるのがいい習慣です。

---
alias LinkSeq!(int) MyIntList;

auto list = new MyIntList;
list.add(1);
---




The following table is an overview of the existing collections.
以下の表は既存のコレクションの概要です。

The first column list the kind of storage, the column heading list the kind of implementations
最初の列がストレージの種類です。また、行頭は実装の種類となっています。


table)
         | Array    | Link                 | Tree    | Hash
Bag      | ArrayBag |                      | TreeBag |
Set      |          |                      |         | HashSet
Sequence | ArraySeq | LinkSeq, CircularSeq |         |
Map      |          | LinkMap              | TreeMap | HashMap




Bag

This is the simplest container.
これは、もっとも単純なコンテナです。

Throw everything in.
すべてのものを投げ込むことができます

The sequence of elements is not defined.
要素のシーケンスは定義されていません。

（C++のSTLでいうstd::vectorのようなものでしょうか…）

Set

In a set there are no duplicates.
Set はコピーが発生しません。

The distinction between Set and Bag is that the latter may have duplicates.
Set と Bag の違いは、後者においてはコピーが発生するかも知れないということです。

（C++のSTLでいうstd::setのようなものでしょうか…）


Sequence

A container that will store the elements in the sequence they were added.
このコンテナは加えるによって連続した要素を収納します。

（C++のSTLでいうstd::listのようなものでしょうか…）

Map

An associative container.
連想配列コンテナです

It has a set of keys.
キーのセットを持っています。

Each key is unique and is mapped to a value.
それぞれのキーは単一で、それぞれに値がマップされます

Both the key and the value type are template parameters.
キーと値の型はテンプレートパラメータで与えられます。

（C++のSTLでいうstd::mapのようなものでしょうか…）

Arrays

They can access their members very fast and without the need for any special sequence.
それらはそれらのメンバにとても早くアクセスすることができます。また、特別なシーケンスを省いています。

But insertion that need to increase the size, is very slow.
しかし、サイズが増大するような挿入はとても遅い欠点があります。

The array then needs to be reallocated and all data must be copied over. 
Array はアロケーションの再確保後にすべてのデータをコピーする必要があるからです。



Linked lists

These containers can increase their size with constant cost.
これらのコンテナは一定のコスト(時間)で容量を増やすことができます。

Every element is allocated and linked.
すべての要素は割り当てられていて、リンクされています。

The drawback is that finding an element in the middle of a linked list, require iteration over the list.
欠点は、リストの中身の要素を見つけ出すのに、リストをたどっていくという繰り返しを必要とするということです。

For big data collections, this is too slow.
大きなコレクションになると、これは非常に遅い操作となります。



Trees

Containers that use a binary tree to access their members.
このコンテナは2分木を使用してメンバにアクセスします。

The cost for insertion and the retrieval is low.
検索と挿入のコストは低いといえます。



Hashes

Hashes are the fastest container in general, but they need much memory.
ハッシュはおそらくもっとも動作の速いコンテナですが、その分メモリを大量に消費します。

Also the elements need to support a good toHash() implementation.
また、要素は良い toHash() 関数を実装している必要があります。



Model and Method Overview
モデルとメソッドの概要

fig)








Create collections
コレクションの作成

The easiest form is to instantiate directly and use an auto variable to hold the reference.
最も簡単な形は、auto を使うことで型推論を行うことです。


---
auto list2 = new LinkSeq!( int );
---


In most cases a collection type is use more than once.
たいていの場合、コレクションは複数回使います。

So it is good to have an alias.
その場合 alias で別名を持たせてやるのがいいでしょう。

---
alias LinkSeq!( char[] ) StrList;
StrList list1 = new StrList;
---







Add and remove elements
要素の追加と削除

Each container type has it own set of methods.
それぞれのコンテナ型は独自にメソッドを保有しています。



---
list1.append( "The first item in list1" );
list2.prepend( 2 );
---



See the Methods exposed by the collection classes to get a good overview.
適宜コレクションクラスの概要を見て把握してください。







Visiting contained elements
要素を巡回する

The typical, and simplest pattern is 
典型的で、もっとも単純なパターンは

---
    foreach (key, value; map)
             Stdout.formatln ("Key: {0}, Value: {1}", key, value);
---

One variation is using only 'value' instead of both 'key' and 'value'.
ひとつのバリエーションは、「値」と「キー」のかわりに、「値」のみを使っています。

Both of these utilize a slightly more efficient mechanism to visit each contained element (or element pair), as they can avoid heap activity when instantiating an Iterator.
これら両方を使う際、要素や要素のペアを巡回する際にヒープを節約することができる、わずかに効率的なメカニズムであるIteratorが利用できます。

---
    auto it = map.keys();

    // The call to .more returns true if there are more elements,
    // and switches the iterator to the next one if available.
    while(it.more){
          char[] key; 
          auto value = it.get(key);
          Stdout.formatln ("Key: {0}, Value:{1}", key, value);
    }
---

For associative containers, the iterator's get method has an out parameter for key retrival.
連想コンテナのため、Iteratorはgetメソッドがあり、outパラメータに指定することでキーを取り出すことができます。


The keys() method is used to also get a set of the key values.
keys()メソッドは、ひと組のキーと値を得るのに用いられます。

For the 'normal' containers, like LinkSeq etc.
LinkSeqのような普通のコンテナのために

the elements() method is used to get a conventional iterator.
elements() メソッドによって従来のイテレータを得るのに用いられます。

Each container also supports foreach() directly. 
それぞれのコンテナは直接foreach文をサポートしています。








Asynchronous mutation during iteration
繰り返し中に起こる非同期突然変異（？）

Iterators are sensitive to container changes whilst they operate, and will throw an exception when this occurs.
イテレータはその操作中に起こるコンテナの容量の変更操作に敏感で、これが起こると例外を投げます。

This it to ensure the client sees a consistent view of the container for the lifetime of the iterator.
この操作を確実にこなすには、Iteratorが有効な間、コンテナを変更してはいけません。






Caution with iterators
Iteratorに関する注意

It is currently not possible to modify the container while iterating over it with foreach or an iterator.
現在、 foreach やIteratorによって繰り返し操作が行われている間、コンテナを修正することができません。

To delete certain elements from a container it is necessary to do it in two steps.
コンテナから特定の要素を削除するには、2段階の操作が必要です。

First find the elements to delete, then do the deletion 
まず、削除する要素を見つけ出します。それから(foreachやイテレータを使い終わったら)削除してください


---
// 1. Build a list of elements to delete
auto dellist = new LinkSeq!(int);
foreach( int i; container ){
  if( i >= 3 && i < 7 ){
    // container.remove( i ); /* NOT POSSIBLE */
    dellist.append( i );
  }
}
// 2. Iterate over this deletion list and
// delete the items in the original container.
foreach( int i; dellist ){
    container.remove( i );
}
---

This may be rectified in the future.
これは将来調整するかもしれません。







InterleavingIterator
インターリービングイテレータ

This more complex Iterator shows why interators are still useful, even if we have the foreach construct.
たとえ私たちがforeach構文を使えるとしても、この複雑なIteratorはなぜ未だ役に立つかということを示しています。

InterleavingIterators allow you to combine the elements of two different enumerations as if they were one enumeration before they are seen by their consumers.
インターリービングイテレータはあなたが2つの異なる列挙された要素を結合することを許可します。あたかもそれらが結合される前であるかのように。

This sometimes allows one to avoid use of a collection object, to temporarily combine two sets of Collection elements() that need to be collected together for common processing.
これらは、まれに、コレクションクラスを新たに作成することを避けるために許可することがあります。
これは、2つのコレクションの要素を共通の処理にかけたい場合に一時的に結合します。

The elements are revealed (via get()) in a purely interleaved fashion, alternating between the first and second enumerations unless one of them has been exhausted, in which case all remaining elements of the other are revealed until it too is exhausted.
それらの要素は現れます。
重なった方式で。
1つ目と2つ目の列挙の中を交互に行き来します。
片方のすべての要素が空にならない限り。
その場合、もう片方の残りの要素はやはり空になるまで巡回されます。

---
import tango.util.collection.ArrayBag;
import tango.util.collection.iterator.InterleavingIterator;

void testInterleavingIterator(){
    int[] result;

    // Create and fill the containers
    auto l1 = new LinkSeq!(int);
    auto l2 = new ArraySeq!(int);
    for( int i = 0; i < 6; i+=2 ){
        l1.append( i );
        l2.append( i+1 );
    }

    // define the InterleavingIterator
    auto it = new InterleavingIterator!(int)(l1.elements, l2.elements);

    // use the InterleavingIterator to iterate over the container
    while (it.more)
        result ~= it.get;

    // test the result
    assert(result == [0, 1, 2, 3, 4, 5], "testInterleavingIterator");
}
---


FilteringIterator
フィルタリングイテレータ

allow you to filter out elements from other enumerations before they are seen by their consumers
フィルタリングイテレータはイテレータの利用前に、列挙から要素をフィルタリングすることで除外することができます 


---
import tango.util.collection.LinkSeq;
import tango.util.collection.ArraySeq;
import tango.util.collection.iterator.FilteringIterator;

void testFilteringIterator(){
    int[] result;
    alias ArrayBag!(int) IntBag;

    // Create and fill the container
    auto ib = new IntBag;
    for( int i = 0; i < 20; i++ ){
        ib.add( i );
    }

    // define the FilteringIterator with a function literal
    auto it = new FilteringIterator!(int)( ib.elements(), (int i){ 
        return i >= 3 && i < 7; 
    });

    // use the FilteringIterator to iterate over the container
    while (it.more())
        result ~= it.get();

    // test the result
    assert( result == [ 3, 4, 5, 6 ], "testFilteringIterator" );
}
---



Comparators
コンペレータ

Sorted containers like trees, need to compare the elements.
ソートされたコンテナはツリーコレクションを好みます

The algorithm that is used for this comparison can be user specified.
この比較を用いたアルゴリズムはユーザに指定されます。

E.g. strings can be sorted in different ways.
たとえば、文字列は異なる方法によってソートされます

If you want a bag to have its addIf using your compare method, this can be done like this
もしあなたがあなたの比較メソッドを持つ addIfをもった bag がほしいなら、これはこのようになります

---
    // Create a bag that is not case sensitive
    auto nameSet = new TreeBag!(char[])( null, 
      new class() Comparator!(char[]){
        int compare( char[] first, char[] second ){
            return Ascii.icompare( first, second );
        }
    });

    nameSet.addIf( "Alice" );
    nameSet.addIf( "Bob" );
    nameSet.addIf( "aliCe" ); // will not be added
---





Screeners
スクリーナー

Each container has the possibility to have a predicate as a so called screener.
各コンテナはスクリーナーに呼ばれる可能性がある

The definition can be found in the Collection class.
その定義は、コレクションクラスに見つけられる。

---
alias bool delegate(T) Predicate;
---

This delegate will be called, each time a new element is to be inserted into the container.
このデリゲートが呼ばれると、呼ばれた時に新しい要素がコンテナに挿入される。

If the screener returns false, the container throws an IllegalElementException to the caller.
もしスクリーナーがfalseを返せば、コンテナはIllegalElementExceptionを呼んだ関数に投げます。


---
    // Create a restricted container
    auto ratioSamples = new ArraySeq!(float)( (float v){
        // restrict element to the range 0.0 .. 0.99999..
        return v >= 0.0f && v < 1.0f;
    });

    // try to insert some values
    try{
        ratioSamples.append( 0.0f );      // OK
        ratioSamples.append( 0.5f );      // OK
        ratioSamples.append( 0.99999f );  // OK
        ratioSamples.append( 1.0f );      // Bang
        // will never get here
        assert( false );
    } catch( IllegalElementException e ){
    }
---

To test if an element is allowed for a certain container, use the bool allows( T ) methode, which is part of the Collection class. 
特定のコンテナ(?)で許容された要素をテストするためには、コレクションクラスの一環として、 bool allows( T ) メソッドを使ってください。







Bag and Set
BagとSetについて

Bags are collections supporting multiple occurrences of elements. Sets do only support unique elements.
Bagはコレクションに要素に複数のデータをサポートしますが、Setは一つのエレメントには一つのデータしかサポートしません。

In both, the sequence of elements is not defined.
両方とも、シーケンスのエレメントは定義されていません。

An exception is TreeBag, there the elements are ordered in their natural way.
TreeBagを除いて。これらの要素は自然な方法でオーダーされます。

Or the user supplies a Comparator object.
あるいは、コンペレーターオブジェクトで供給されるかもしれません。

Both bags support the addIf() method.
両方のBagはaddIf()メソッドをサポートしています。

So they can be used like sets.
したがってSetも同様のことが可能です。

HashSet uses a hash algorithm to find potential duplicates very fast, but this algorithm can use a lot of memory.
HashSetはハッシュを使うアルゴリズムを使用して可能性のある複製を高速で探し当てます。が、このアルゴリズムは多くのメモリを消費します。





Sequence, the ordered storage
シーケンスと要求のストレージ

Sequences are indexed, sequentially ordered collections.
シーケンスは連続的に要求を目録したコレクションです。

Indices are always in the range 0 .. size() -1.
インデックスはいつも[0..size() -1]の範囲をとります。

All accesses by index are checked, raising exceptions if the index falls out of range.
インデックスをチェックすればすべての要素にアクセスすることができます。
ひとつずつ増やしていくことで、範囲外にでなければ。

The elements() enumeration for all sequences is guaranteed to be traversed (via more()/get()) in sequential order.
elements() はエミュレーションします。すべての保証付きのシーケンスのために。more()とget()を使って連続的な要求をする際に。

	・Seq is an interface for all sequences
	Seqはすべてのシーケンスのインターフェースです。
	
	・ArraySeq implementing class, uses an array.
	ArraySeqは配列を使って実装されたクラスです。
	
	Best used when the storage size is not changed too often, or a fast element access per index is needed.
	サイズの滅多に変わらない、あるいは要素へindexでののアクセス速度が速いストレージにおいて最良の結果を出します。
	
	・LinkSeq implementing class, uses element nodes which are allocated dynamically and linked with each other.
	LinkSeqはリスト構造を使って動的に分配されたノードを使って他とつながっているノードを使用して実装されています。
	
	This implementation can easy append elements and remove elements from the head (take()).
	この実相は、先頭へ take()メソッドを使うことで簡単に要素数を増やすことができ、また、削除することができます。
	
	Making random access to elements per index is slow, because it is neccessary to follow the links from the beginning of the storage.
	ランダムアクセスを使って要素にアクセスする場合はとても遅いものになります。なぜなら、最初の要素からストレージ内をたどる必要があるからです。
	
	・CircularSeq is similar to LinkSeq. But this class uses double linked cells.
	CircularSeqは、LinkSeqに似ています。しかし、このクラスは要素を二重に結合しています（たぶん一番最後と最初をつなげること）。
	
	So all operations are equal in operation, nevertheless the are started from the beginning or end of the list.
	したがって最初からスタートした命令も最後からスタートした命令もすべての命令は同じ意味を持っています。（結局は最初や最後などは指定できていないのと同じだから。）
	
	


Map, the associative Storage
マップ（連想ストレージ）

Maps maintain keyed elements.
Mapは要素にキーを保持しています。

Any kind of Object or primitive type may serve as a key for an element.
何かのオブジェクト系あるいはプリミティブなタイプの値が要素のためのキーとなります

Each key is unique and is associated with one value.
それぞれのキーは単一で、一つの値を連想させます。


---
    import tango.store.HashMap;
    // ...
    alias HashMapT!(char[], char[]) StrStrMap;

    auto map = new StrStrMap();
    map.add("key1", "value1");
    char[] key = "key1";
    Stdout.format ("Key: {0}, Value:{1}", key, map.get(key)).newline;
---



Hash vs Tree
ハッシュアルゴリズム対ツリーアルゴリズム

Sets and Maps are available with tree or hash implementation.
SetとMapはツリーかハッシュの実相を利用できます

When should one choose which?
どちらかを選ぶとき、どちらを選びますか？

Using a tree means it is necessary to navigate a tree structure to find an element.
ツリーを使うということは、木構造の道を進んで要素を見つけ出す必要があるということです。

The number of stages to traverse is around O(log2(n)). 
アクセスのためのステップ数は要素数に応じて、 O(log2(n)) の割合で指数的に増えます。

When using a hash, an array is used to store a given number of buckets.
ハッシュを使うとき、配列はそのストアをバケツの数で与えられます。？
（たぶん、一定の要素数の静的な配列が、要素数に応じて増えていくということ？

A hash function is used to calculate a hash from the object value.
ハッシュ関数はオブジェクトの値によってハッシュを計算します

A hash is a n-bit integer value, which should be mostly unique for each object.
ハッシュは、n-bitの整数値で、それは、それぞれのオブジェクト間でほぼ単一なものとなる必要があります

The same content of an object must always calculate the same hash value.
オブジェクトの内容が同じ場合は同じハッシュが生成される必要があります。

This value is used when the bucket to store or retrieve the element is chosen. 
この値はバケツに保存するために、あるいは要素を選択し、回収するために使われます。

In the best case, this algorithm can find the element directly (if the bucket contains exactly one element).
最良の場合は、このアルゴリズムは要素を直接見つけることができるというものです。（バケツは厳密に一つの要素を含む場合です。）

That would be access in constant time or O(1).
その場合のアクセス速度はコンスタントで、 O(1) となります。

But if the bucket holds many elements, then (depending on the bucket implementation) this can lead to a linear search.
しかし、バケツは多くの要素を持ちます。それから（バケツの実相に依存しますが）これの読み取りはリニアサーチ(一つずつ検索すること)です。

In a good hash this should not happen.
いいハッシュではこれは起こってはなりません。

To ensure the buckets are not too full, the array for them should be chosen big.
バケツが満タンにならないことを保証するには、配列は大きなものを選ばなければなりません。

This means, hash needs much more memory than tree and a good quality hash function for the stored object, to be efficient. 
これが意味するものは、ハッシュはツリーより多くのメモリを使用し、そして、オブジェクトをストアするのに効率の良い品質のハッシュ関数を必要とします。




D builtin arrays and hashes vs. ArraySeq and HashMap
D組み込みの配列とハッシュ対ArraySeqとHashMap

D already supports builtin dynamic arrays and hashes.
Dはすでに組み込みで直接動的配列やハッシュをサポートしています

Why should one use a template container for these container types?
なぜこれらのテンプレートのコンテナ型を使う必要があるのでしょうか？

There is nothing against the builtin arrays/hashes, use them if they have all you need.
あなたが必要に応じて組み込みの配列やハッシュを使うことに何も否定要素はありません。

Be aware of the additional features the tango container ArraySeq/HashMap has:
tangoのコンテナのArraySeqやHashMapには、追加の特性があることに注目してください。
たとえば、、

	・A screener function to restrict the inserted elements to a configurable set.
	スクリーナー関数で厳密に要素を挿入するようにSetを設定することができます。
	
	・Iterators that can implement various behaviour.
	イテレータが実装されていてさまざまなふるまいをさせることができます
	
	・the tango collections are compatible between each other, because they implement common interfaces.
	tangoのコレクションはそれぞれの間で互換性があります。なぜならそれぞれの実装は共通のインターフェースを使用しているからです。
	
	So it is theoretical possible to exchange a ArraySeq container with a LinkSeq container, if you only use the methods from View.
	したがって、それはArraySeqコンテナを変更するうえでの理論的な可能性となります。もしあなたがView関数を使いたいだけだったとしても。






In Review
レビューでは

Don't reinvent the wheel, use containers where ever possible. 
車輪を再発明するな。可能な限りコンテナを使え。

Choose the appropriate container class for you needs.
適当なコンテナクラスをあなたの必要に応じて選びなさい。





Suggestion for this documentation
このドキュメンテーションによる提案

・Show the use of procedure
プロシージャ（手続き）を使うのを見せれ。






References
参照
For further readings on hash tables, see this Wikipedia-article