12/21 マップ

「マップ」とは「キー(key)と値（value)の対応表」であり、 キーと値の「登録(Insert)」、 キーを指定した「検索(Find)」、「削除(Erase)」ができる抽象データ型である。

具体例としては、 電話帳「名前（キー）と電話番号（値）の対応」、 学籍名簿「学籍番号（キー）と名前（値）の対応」 などを考えれば良い。

課題１

以下は線形リストを用いた簡単なマップの一部である。 「利用例」が実行できるようにプログラムを完成させなさい。 

#include <iostream>
#include <string>
using namespace std;

// 最初からテンプレートにするとデバッグが大変なので、
// まずは、「キー」も「値」も string 型のマップを作成する。
// テンプレート化は後で行う。

/* 線形リストによるマップ  MapLinear クラス  */

class MapLinear 
{
    class Cell {

        string key;
        string value;
        Cell* next;

      public:
        Cell( string k, string d, Cell* n) : key(k), value(d), next(n) { };

      friend class MapLinear;
   };

  Cell* head;

  public:

    MapLinear( ); 
    ~MapLinear( ); 

    bool Insert( string key, string value );
            // key と value を対で登録する。
            // key が同じデータを２重に登録することはできないものとする。
            // 登録に失敗した場合は false 成功した場合は true を返す。

    bool Find( string key, string & value ) const;
            // key に対応するデータを見つける。
            // 無ければ false を返す。
            // 有れば true を返し、対応する「値」を参照引数 value で返す。

  private:

    void makeEmpty( Cell* p );
    bool find( string key, string & value, Cell* p ) const;
};

MapLinear::MapLinear( )
{
    head=NULL;
}

MapLinear::~MapLinear( )
{
    makeEmpty( head );
}

void MapLinear::makeEmpty( Cell* p )
{
    if ( p != NULL ) {
        if ( p->next != NULL ) 
            makeEmpty( p->next );
        delete p;
    }
}

bool MapLinear::Insert( string key, string value )
{
    string dummy;

    if ( ! Find( key, dummy ) ) {
        // ここを埋めよ。
        // 同じキーのデータが無ければ追加する。
        // 場所はどこでも良いが、先頭が楽だろう。
        return true;
    } 
    else
        return false;
        // 同じキーを持つデータが存在した場合は、false を返す。
}

bool MapLinear::Find( string key, string & value ) const
{
   return find( key, value, head ); 
   // リストの先頭を指定して、プライベート関数 find を呼んでいる。
}

bool MapLinear::find( string key, string & value, Cell* p ) const
{
    if ( p == NULL ) {
       return false;
    }
    else if ( p->key == key ) {
       //  ここを埋めよ。
       // 
    }
    else {
       // ここを埋めよ。再帰呼び出しを使うこと。
    }
}


/* 利用例 */


int main()
{

  MapLinear staff;  // 教員のアドレス帳

  staff.Insert( "mino",      "mino_at_csci.yanamashi.ac.jp" );

  staff.Insert( "yoshikawa", "yoshi_at_yanamashi.ac.jp"  );

  staff.Insert( "watanabe",  "nabe_at_s.cs.yanamashi.ac.jp" );

  staff.Insert( "kobayashi", "masaki_at_esi.yanamashi.ac.jp" );

  staff.Insert( "suzuki",    "stomo_at_yanamashi.ac.jp" );

  string address;

  if ( staff.Find( "mino", address ) ) {
    cout << address;
  }

  return 0;
}

課題２

以下のヒントに従い、 課題１の MapLinear に削除関数 Erase を加えなさい。 適当な main 関数で動作をテストすること。 


class MapLinear 
{
    class Cell {

      public:
        string key;
        string value;
        Cell* next;

        Cell( string k, string d, Cell* n) : key(k), value(d), next(n) { };
   };

  Cell* head;

  public:

    MapLinear( );  
    ~MapLinear( ); 
    bool Insert( string key, string value );
    bool Find( string key, string & value ) const;

    bool Erase( string key );
            // key の値に対応するデータを削除する
            // 該当するデータが無い場合は false を返す

  private:
    void makeEmpty( Cell* p );
    bool find( string key, string & value, Cell* p ) const;
    bool erase( string key, Cell* & p );     
    //         p が参照引数であることが重要！
};


...

bool MapLinear::Erase( string key  )
{
    return erase( key, head );
}

bool MapLinear::erase( string key, Cell* & p )
                     //         p が参照引数であることが重要！
{
    if ( p == NULL ) {
       return false;
    }
    else if ( p->key == key ) {
        //  ここを埋めよ。
        // ..
        // ..
        // ..
    }
    else {
        // ここを埋めよ。再帰呼び出しを使うこと。
    }
}

課題３

マップには、登録された内容をすべてもらさず処理する機能も必要である。 そのためのメンバ関数として、この授業では以下の関数を用意する。

void SetBegin( )
カレントポインタ（インデックス）を最初のデータに合わせる。
void Next( )
カレントポインタ（インデックス）を次のデータに合わせる。 次のデータがない場合は、データを指さないようにする （例えばポインタを NULL にする）。
bool IsValid( ) const
カレントポインタ（インデックス）がデータを指してる場合に true を返す。
bool CurrentItem( string & k, string & x ) const
カレントポインタ（インデックス）が指すデータの「値」を参照引数で返す。 返り値は IsValid( ) と同じ。

何が「最初」で、何が「次」なのかは自由に決めて良い。 大事なことは「最初」からはじめて「次」、「次」とたどると、データ を「もれなく、かつ重複無く」たどれることである。

以下は線形リストを用いたマップについての上記関数の実装例である。これらを MapLinear に追加し、登録された全データを出力するテストを行いなさい。 

class MapLinear {

...
    //private member を一つ追加
    Cell* current;
...
};

MapLinear:: MapLinear( )  {

...
    current = NULL;
...
}

void MapLinear:: SetBegin( ) 
{
    current = head;
}

void MapLinear:: Next( ) 
{
    if ( current != NULL ) 
        current = current->next;
}

bool MapLinear:: IsValid( ) const
{
    return ( current != NULL );
}

bool MapLinear:: CurrentItem( string & k , string & v ) const
{
    if ( current == NULL ) {
       return false;
    } 
    else {
       k = current->key;
       v = current->value;
       return true;
    }
}

課題４

ここまでで作成したクラス MapLinear をテンプレート化し、 任意の型の「キー」と任意の型の「値」で使えるようにしなさい。 テンプレートパラメータは一つだけではなく幾つでも使うことができる。 その方法については以下を参考にすること。 

template < typename KeyType, typename ValueType >
class MapLinear {

     KeyType key;
     ValueType value;
...


}

template < typename KeyType, typename ValueType >
MapLinear<KeyType,ValueTpe>::MapLinear( )
{
... 

}

...


int main( )
{
   MapLinear<string,string>   pr;

   ....
}