import 'dart:math' show Random;

 final _rnd = Random();

 final _seed = 100;

 class OrderedArray {

   List<int> _array;

   int _realLength;

   OrderedArray(int capacity) {

     _array = List<int>(capacity);

     _realLength = 0;

   }

   int get capacity => _array.length;

   int get length => _realLength;

   void fill(double percent) {

     for (var i = 0; i < capacity * percent; i++) {

       insert(_rnd.nextInt(_seed));

     }

   }

   bool insert(int v) {

     if (_realLength == capacity) {

       return false;

     } else {

       if (_realLength == 0) {

         _array[0] = v;

       } else {

         int i;

         for (i = 0; i < _realLength; i++) {

           if (_array[i] >= v) break;

         }

         for (var j = _realLength; j > i; j--) {

           _array[j] = _array[j - 1];

         }

         _array[i] = v;

       }

       _realLength++;

       return true;

     }

   }

   int find(int key) {

     if (_realLength == 0) {

       return -1;

     }

     if (key < _array[0] || key > _array[_realLength - 1]) {

       return -1;

     }

     int lower = 0, upper = _realLength - 1, mid;

     while (lower <= upper) {

       mid = (lower + upper) ~/ 2;

       if (_array[mid] == key) {

         return mid;

       } else if (_array[mid] > key) {

         upper = mid - 1;

       } else {

         lower = mid + 1;

       }

     }

     return -1;

   }

   // Attention! after modifed the array is maybe not ordered ever.

   bool modify(int pos, int newValue) {

     if (pos < 0 || pos > _realLength - 1) {

       return false;

     } else {

       _array[pos] = newValue;

       // sort(0, _realLength - 1);

       return true;

     }

   }

   bool delete(int key) {

     var pos = find(key);

     if (pos < 0) {

       return false;

     } else {

       for (var i = pos; i < _realLength - 1; i++) {

         _array[i] = _array[i + 1];

       }

       _realLength--;

       return true;

     }

   }

   int operator [](int pos) {

     if (pos < 0 || pos > _realLength - 1) {

       return null;

     } else {

       return _array[pos];

     }

   }

   // the below is equal to modify, but don't have return type;

   void operator []=(int pos, int newValue) {

     if (pos >= 0 && pos < _realLength) {

       _array[pos] = newValue;

       // sort(0, _realLength - 1);

     }

   }

   void sort(int start, int end) {

     if (start >= end) return;

     var pl = start, pr = end, key = _array[pl];

     while (pl < pr) {

       while (_array[pr] >= key && pr > pl) pr--;

       if (pr > pl) {

         _array[pl] = _array[pr];

         pl++;

       }

       while (_array[pl] <= key && pl < pr) pl++;

       if (pl < pr) {

         _array[pr] = _array[pl];

         pr--;

       }

     }

     _array[pl] = key;

     sort(start, pl - 1);

     sort(pl + 1, end);

   }

   void display() {

     var sb = StringBuffer();

     sb.write('[');

     if (_realLength > 0) {

       for (var i = 0; i < _realLength - 1; i++) {

         sb.write('${_array[i]}, ');

       }

       sb.write('${_array[_realLength - 1]}');

     }

     sb.write(']');

     print(sb.toString());

   }

 }

 void main() {

   var arr = OrderedArray(100);

   arr.fill(0.2);

   arr.display();

   var key = _rnd.nextInt(_seed);

   if (arr.insert(key)) {

     print('insert \'$key\' successed.');

     arr.display();

   } else {

     print('insert \'$key\' failed.\n');

   }

   key = _rnd.nextInt(_seed);

   var pos = arr.find(key);

   if (pos >= 0) {

     print('found the key: $key at $pos\n');

   } else {

     print('can not find the key: $key\n');

   }

   key = _rnd.nextInt(_seed);

   pos = arr.length ~/ 2;

   var oldValue = arr[pos];

   if (arr.modify(pos, key)) {

     print('modified the old value ($oldValue) to the new: $key at $pos');

   }

   pos = arr.length;

   oldValue = arr[pos];

   if (arr.modify(pos, key)) {

     print('modified the old value ($oldValue) to the new: $key at $pos\n');

   } else {

     print('the position to be modified is out of bound.\n');

   }

   arr.display();

   arr[0] = _rnd.nextInt(_seed);

   arr[arr.length] = _rnd.nextInt(_seed);

   arr.display();

   print('now sort the array:');

   arr.sort(0, arr.length - 1);

   arr.display();

   key = _rnd.nextInt(_seed);

   if (arr.delete(key)) {

     arr.display();

     print('has deleted the key: $key');

   } else {

     print('can not find the key to delete: $key');

   }

   print('now delete the key: ${arr[arr.length ~/ 2]}');

   arr.delete(arr[arr.length ~/ 2]);

   arr.display();

 }