Dart - クラスの定義(二分探索木, ツリーの要素を削除するメソッド)

Dart: Up and Running
(O'Reilly Media)
Kathy Walrath Seth Ladd (著)
[Kindle版]
このブログでの感想

開発環境

• OS X Mavericks - Apple (OS)
• Dart Editor (開発環境)
• Dartium | Dart/ Structured web apps (ブラウザ, Dart VM 用 (Chromium with the Dart VM))
• Safari (ブラウザ, JavaScript 用)
• Dart (プログラミング言語)

C実践プログラミング 第3版 (Steve Oualline (著)、 望月 康司 (監訳) (翻訳)、谷口 功 (翻訳)、オライリー・ジャパン)のⅢ部(高度なプログラミング概念)の17章(高度なポインタ)、17-12(プログラミング実習)、実習17-4.をDartで解いてみる。

その他参考書籍

• What is Dart? [Kindle版] (O'Reilly Media) Kathy Walrath Seth Ladd (著) このブログでの感想

17-12(プログラミング実習)、実習17-4.

コード

sample.dart

import 'dart:html';

void main(){
  InputElement t0 = querySelector('#t0');
  InputElement read_file = querySelector('#read_file');
  InputElement insert = querySelector('#tree_insert');
  InputElement t1 = querySelector('#t1');
  InputElement delete = querySelector('#tree_delete');
  InputElement input = querySelector('#f0');
  InputElement run = querySelector('#run_dart');
  InputElement clear = querySelector('#clear');
  Element pre = querySelector('#pre0');
  RegExp pattern = new RegExp(r'\s+');
  RegExp pattern1 = new RegExp('[^A-Za-z]');
  var t = new Tree();
  read_file.onClick.listen((MouseEvent event){
    FileReader reader = new FileReader();
    try{
      File f = input.files.first;
      reader.readAsText(f);
      reader.onLoad.listen((Event event){
        String text = reader.result;
        var words = text.trim().split(pattern);
        words.removeWhere((String word) => word.contains(pattern1));
        words.forEach((String s) => t.insert(s));
      });
    }catch(e){
      pre.text = window.navigator.userAgent + '\n';
      pre.text += '$e\n';
    }
  });
  insert.onClick.listen((MouseEvent event){
    var word = t0.value;
    if(!word.contains(pattern1)){
      t.insert(word);
    }
  });
  delete.onClick.listen((MouseEvent event){
    var word = t1.value;
    if(!word.contains(pattern1)){
      t.delete(word);
    }
  });
  run.onClick.listen((MouseEvent event){
    pre.text = window.navigator.userAgent + '\n';
    pre.text += '$t';
  });
  clear.onClick.listen((MouseEvent event){
    pre.text = '';
    t = new Tree();
  });
}

class Node{
  String a;
  Tree left;
  Tree right;
  Node(var x){
    a = x;
    left = null;
    right = null;
  }
  String toString(){
    if(a == null){
      return '';
    }
    return left.toString() + a + '\n' + right.toString();
  }
}
class Tree{
  Node root;
  Tree(){
    root = null;
  }
  void insert(String x){
    if(root == null){
      root = new Node(x);
    } else if(x.compareTo(root.a) < 0){
      if(root.left == null){
        root.left = new Tree();
      }
      root.left.insert(x);
    } else if(x.compareTo(root.a) > 0){
      if(root.right == null){
        root.right = new Tree();
      }
      root.right.insert(x);
    }
  }
  void delete(String x){
    if(root == null){
      return;
    }
    if(x.compareTo(root.a) < 0){
      root.left.delete(x);
    } else if(x.compareTo(root.a) > 0){
      root.right.delete(x);
    } else {
      if(root.left == null && root.right == null){
        root = null;
      } else if (root.left == null){
        root = root.right.root;
      } else if (root.right == null){
        root = root.left.root;
      } else {
        var  min = root.right.findMin();
        root.right.delete(min.a);
        min.left = root.left;
        min.right = root.right;
        root = min;
      }
    }
  }
  Node findMin(){
    if(root == null){
      throw "findMin";
    }
    if(root.left == null){
      return root;
    }
    return root.left.findMin();
  }
  String toString(){
    var result = '';
    if(root == null){
      return '';
    }
    if(root.left == null){
      result += '';
    } else {
      result += root.left.toString();
    }
    result += root.a + '\n';
    if(root.right == null){
      result += '';
    } else {
      result += root.right.toString();
    }
    return result;
  }
}

追加する単語:

削除する単語: