OLD | NEW |
1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 part of dart._internal; | 5 part of dart._internal; |
6 | 6 |
7 /** | 7 /** |
8 * Marker interface for [Iterable] subclasses that have an efficient | 8 * Marker interface for [Iterable] subclasses that have an efficient |
9 * [length] implementation. | 9 * [length] implementation. |
10 */ | 10 */ |
(...skipping 739 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
750 const EmptyIterator(); | 750 const EmptyIterator(); |
751 bool moveNext() => false; | 751 bool moveNext() => false; |
752 E get current => null; | 752 E get current => null; |
753 } | 753 } |
754 | 754 |
755 /** An [Iterator] that can move in both directions. */ | 755 /** An [Iterator] that can move in both directions. */ |
756 abstract class BidirectionalIterator<T> implements Iterator<T> { | 756 abstract class BidirectionalIterator<T> implements Iterator<T> { |
757 bool movePrevious(); | 757 bool movePrevious(); |
758 } | 758 } |
759 | 759 |
760 /** | |
761 * This class provides default implementations for Iterables (including Lists). | |
762 * | |
763 * The uses of this class will be replaced by mixins. | |
764 */ | |
765 class IterableMixinWorkaround<T> { | |
766 static bool contains(Iterable iterable, var element) { | |
767 for (final e in iterable) { | |
768 if (e == element) return true; | |
769 } | |
770 return false; | |
771 } | |
772 | |
773 static void forEach(Iterable iterable, void f(o)) { | |
774 for (final e in iterable) { | |
775 f(e); | |
776 } | |
777 } | |
778 | |
779 static bool any(Iterable iterable, bool f(o)) { | |
780 for (final e in iterable) { | |
781 if (f(e)) return true; | |
782 } | |
783 return false; | |
784 } | |
785 | |
786 static bool every(Iterable iterable, bool f(o)) { | |
787 for (final e in iterable) { | |
788 if (!f(e)) return false; | |
789 } | |
790 return true; | |
791 } | |
792 | |
793 static dynamic reduce(Iterable iterable, | |
794 dynamic combine(previousValue, element)) { | |
795 Iterator iterator = iterable.iterator; | |
796 if (!iterator.moveNext()) throw IterableElementError.noElement(); | |
797 var value = iterator.current; | |
798 while (iterator.moveNext()) { | |
799 value = combine(value, iterator.current); | |
800 } | |
801 return value; | |
802 } | |
803 | |
804 static dynamic fold(Iterable iterable, | |
805 dynamic initialValue, | |
806 dynamic combine(dynamic previousValue, element)) { | |
807 for (final element in iterable) { | |
808 initialValue = combine(initialValue, element); | |
809 } | |
810 return initialValue; | |
811 } | |
812 | |
813 /** | |
814 * Removes elements matching [test] from [list]. | |
815 * | |
816 * This is performed in two steps, to avoid exposing an inconsistent state | |
817 * to the [test] function. First the elements to retain are found, and then | |
818 * the original list is updated to contain those elements. | |
819 */ | |
820 static void removeWhereList(List list, bool test(var element)) { | |
821 List retained = []; | |
822 int length = list.length; | |
823 for (int i = 0; i < length; i++) { | |
824 var element = list[i]; | |
825 if (!test(element)) { | |
826 retained.add(element); | |
827 } | |
828 if (length != list.length) { | |
829 throw new ConcurrentModificationError(list); | |
830 } | |
831 } | |
832 if (retained.length == length) return; | |
833 list.length = retained.length; | |
834 for (int i = 0; i < retained.length; i++) { | |
835 list[i] = retained[i]; | |
836 } | |
837 } | |
838 | |
839 static bool isEmpty(Iterable iterable) { | |
840 return !iterable.iterator.moveNext(); | |
841 } | |
842 | |
843 static dynamic first(Iterable iterable) { | |
844 Iterator it = iterable.iterator; | |
845 if (!it.moveNext()) { | |
846 throw IterableElementError.noElement(); | |
847 } | |
848 return it.current; | |
849 } | |
850 | |
851 static dynamic last(Iterable iterable) { | |
852 Iterator it = iterable.iterator; | |
853 if (!it.moveNext()) { | |
854 throw IterableElementError.noElement(); | |
855 } | |
856 dynamic result; | |
857 do { | |
858 result = it.current; | |
859 } while(it.moveNext()); | |
860 return result; | |
861 } | |
862 | |
863 static dynamic single(Iterable iterable) { | |
864 Iterator it = iterable.iterator; | |
865 if (!it.moveNext()) throw IterableElementError.noElement(); | |
866 dynamic result = it.current; | |
867 if (it.moveNext()) throw IterableElementError.tooMany(); | |
868 return result; | |
869 } | |
870 | |
871 static dynamic firstWhere(Iterable iterable, | |
872 bool test(dynamic value), | |
873 dynamic orElse()) { | |
874 for (dynamic element in iterable) { | |
875 if (test(element)) return element; | |
876 } | |
877 if (orElse != null) return orElse(); | |
878 throw IterableElementError.noElement(); | |
879 } | |
880 | |
881 static dynamic lastWhere(Iterable iterable, | |
882 bool test(dynamic value), | |
883 dynamic orElse()) { | |
884 dynamic result = null; | |
885 bool foundMatching = false; | |
886 for (dynamic element in iterable) { | |
887 if (test(element)) { | |
888 result = element; | |
889 foundMatching = true; | |
890 } | |
891 } | |
892 if (foundMatching) return result; | |
893 if (orElse != null) return orElse(); | |
894 throw IterableElementError.noElement(); | |
895 } | |
896 | |
897 static dynamic lastWhereList(List list, | |
898 bool test(dynamic value), | |
899 dynamic orElse()) { | |
900 // TODO(floitsch): check that arguments are of correct type? | |
901 for (int i = list.length - 1; i >= 0; i--) { | |
902 dynamic element = list[i]; | |
903 if (test(element)) return element; | |
904 } | |
905 if (orElse != null) return orElse(); | |
906 throw IterableElementError.noElement(); | |
907 } | |
908 | |
909 static dynamic singleWhere(Iterable iterable, bool test(dynamic value)) { | |
910 dynamic result = null; | |
911 bool foundMatching = false; | |
912 for (dynamic element in iterable) { | |
913 if (test(element)) { | |
914 if (foundMatching) { | |
915 throw IterableElementError.tooMany(); | |
916 } | |
917 result = element; | |
918 foundMatching = true; | |
919 } | |
920 } | |
921 if (foundMatching) return result; | |
922 throw IterableElementError.noElement(); | |
923 } | |
924 | |
925 static elementAt(Iterable iterable, int index) { | |
926 if (index is! int) throw new ArgumentError.notNull("index"); | |
927 RangeError.checkNotNegative(index, "index"); | |
928 int elementIndex = 0; | |
929 for (var element in iterable) { | |
930 if (index == elementIndex) return element; | |
931 elementIndex++; | |
932 } | |
933 throw new RangeError.index(index, iterable, "index", null, elementIndex); | |
934 } | |
935 | |
936 static String join(Iterable iterable, [String separator]) { | |
937 StringBuffer buffer = new StringBuffer(); | |
938 buffer.writeAll(iterable, separator); | |
939 return buffer.toString(); | |
940 } | |
941 | |
942 static String joinList(List list, [String separator]) { | |
943 if (list.isEmpty) return ""; | |
944 if (list.length == 1) return "${list[0]}"; | |
945 StringBuffer buffer = new StringBuffer(); | |
946 if (separator.isEmpty) { | |
947 for (int i = 0; i < list.length; i++) { | |
948 buffer.write(list[i]); | |
949 } | |
950 } else { | |
951 buffer.write(list[0]); | |
952 for (int i = 1; i < list.length; i++) { | |
953 buffer.write(separator); | |
954 buffer.write(list[i]); | |
955 } | |
956 } | |
957 return buffer.toString(); | |
958 } | |
959 | |
960 Iterable<T> where(Iterable iterable, bool f(var element)) { | |
961 return new WhereIterable<T>(iterable, f); | |
962 } | |
963 | |
964 static Iterable map(Iterable iterable, f(var element)) { | |
965 return new MappedIterable(iterable, f); | |
966 } | |
967 | |
968 static Iterable mapList(List list, f(var element)) { | |
969 return new MappedListIterable(list, f); | |
970 } | |
971 | |
972 static Iterable expand(Iterable iterable, Iterable f(var element)) { | |
973 return new ExpandIterable(iterable, f); | |
974 } | |
975 | |
976 Iterable<T> takeList(List list, int n) { | |
977 // The generic type is currently lost. It will be fixed with mixins. | |
978 return new SubListIterable<T>(list, 0, n); | |
979 } | |
980 | |
981 Iterable<T> takeWhile(Iterable iterable, bool test(var value)) { | |
982 // The generic type is currently lost. It will be fixed with mixins. | |
983 return new TakeWhileIterable<T>(iterable, test); | |
984 } | |
985 | |
986 Iterable<T> skipList(List list, int n) { | |
987 // The generic type is currently lost. It will be fixed with mixins. | |
988 return new SubListIterable<T>(list, n, null); | |
989 } | |
990 | |
991 Iterable<T> skipWhile(Iterable iterable, bool test(var value)) { | |
992 // The generic type is currently lost. It will be fixed with mixins. | |
993 return new SkipWhileIterable<T>(iterable, test); | |
994 } | |
995 | |
996 Iterable<T> reversedList(List list) { | |
997 return new ReversedListIterable<T>(list); | |
998 } | |
999 | |
1000 static void sortList(List list, int compare(a, b)) { | |
1001 if (compare == null) compare = Comparable.compare; | |
1002 Sort.sort(list, compare); | |
1003 } | |
1004 | |
1005 static void shuffleList(List list, Random random) { | |
1006 if (random == null) random = new Random(); | |
1007 int length = list.length; | |
1008 while (length > 1) { | |
1009 int pos = random.nextInt(length); | |
1010 length -= 1; | |
1011 var tmp = list[length]; | |
1012 list[length] = list[pos]; | |
1013 list[pos] = tmp; | |
1014 } | |
1015 } | |
1016 | |
1017 static int indexOfList(List list, var element, int start) { | |
1018 return Lists.indexOf(list, element, start, list.length); | |
1019 } | |
1020 | |
1021 static int lastIndexOfList(List list, var element, int start) { | |
1022 if (start == null) start = list.length - 1; | |
1023 return Lists.lastIndexOf(list, element, start); | |
1024 } | |
1025 | |
1026 static void _rangeCheck(List list, int start, int end) { | |
1027 RangeError.checkValidRange(start, end, list.length); | |
1028 } | |
1029 | |
1030 Iterable<T> getRangeList(List list, int start, int end) { | |
1031 _rangeCheck(list, start, end); | |
1032 // The generic type is currently lost. It will be fixed with mixins. | |
1033 return new SubListIterable<T>(list, start, end); | |
1034 } | |
1035 | |
1036 static void setRangeList(List list, int start, int end, | |
1037 Iterable from, int skipCount) { | |
1038 _rangeCheck(list, start, end); | |
1039 int length = end - start; | |
1040 if (length == 0) return; | |
1041 | |
1042 if (skipCount < 0) throw new ArgumentError(skipCount); | |
1043 | |
1044 // TODO(floitsch): Make this accept more. | |
1045 List otherList; | |
1046 int otherStart; | |
1047 if (from is List) { | |
1048 otherList = from; | |
1049 otherStart = skipCount; | |
1050 } else { | |
1051 otherList = from.skip(skipCount).toList(growable: false); | |
1052 otherStart = 0; | |
1053 } | |
1054 if (otherStart + length > otherList.length) { | |
1055 throw IterableElementError.tooFew(); | |
1056 } | |
1057 Lists.copy(otherList, otherStart, list, start, length); | |
1058 } | |
1059 | |
1060 static void replaceRangeList(List list, int start, int end, | |
1061 Iterable iterable) { | |
1062 _rangeCheck(list, start, end); | |
1063 if (iterable is! EfficientLength) { | |
1064 iterable = iterable.toList(); | |
1065 } | |
1066 int removeLength = end - start; | |
1067 int insertLength = iterable.length; | |
1068 if (removeLength >= insertLength) { | |
1069 int delta = removeLength - insertLength; | |
1070 int insertEnd = start + insertLength; | |
1071 int newEnd = list.length - delta; | |
1072 list.setRange(start, insertEnd, iterable); | |
1073 if (delta != 0) { | |
1074 list.setRange(insertEnd, newEnd, list, end); | |
1075 list.length = newEnd; | |
1076 } | |
1077 } else { | |
1078 int delta = insertLength - removeLength; | |
1079 int newLength = list.length + delta; | |
1080 int insertEnd = start + insertLength; // aka. end + delta. | |
1081 list.length = newLength; | |
1082 list.setRange(insertEnd, newLength, list, end); | |
1083 list.setRange(start, insertEnd, iterable); | |
1084 } | |
1085 } | |
1086 | |
1087 static void fillRangeList(List list, int start, int end, fillValue) { | |
1088 _rangeCheck(list, start, end); | |
1089 for (int i = start; i < end; i++) { | |
1090 list[i] = fillValue; | |
1091 } | |
1092 } | |
1093 | |
1094 static void insertAllList(List list, int index, Iterable iterable) { | |
1095 RangeError.checkValueInInterval(index, 0, list.length, "index"); | |
1096 if (iterable is! EfficientLength) { | |
1097 iterable = iterable.toList(growable: false); | |
1098 } | |
1099 int insertionLength = iterable.length; | |
1100 list.length += insertionLength; | |
1101 list.setRange(index + insertionLength, list.length, list, index); | |
1102 for (var element in iterable) { | |
1103 list[index++] = element; | |
1104 } | |
1105 } | |
1106 | |
1107 static void setAllList(List list, int index, Iterable iterable) { | |
1108 RangeError.checkValueInInterval(index, 0, list.length, "index"); | |
1109 for (var element in iterable) { | |
1110 list[index++] = element; | |
1111 } | |
1112 } | |
1113 | |
1114 Map<int, T> asMapList(List l) { | |
1115 return new ListMapView<T>(l); | |
1116 } | |
1117 | |
1118 static bool setContainsAll(Set set, Iterable other) { | |
1119 for (var element in other) { | |
1120 if (!set.contains(element)) return false; | |
1121 } | |
1122 return true; | |
1123 } | |
1124 | |
1125 static Set setIntersection(Set set, Set other, Set result) { | |
1126 Set smaller; | |
1127 Set larger; | |
1128 if (set.length < other.length) { | |
1129 smaller = set; | |
1130 larger = other; | |
1131 } else { | |
1132 smaller = other; | |
1133 larger = set; | |
1134 } | |
1135 for (var element in smaller) { | |
1136 if (larger.contains(element)) { | |
1137 result.add(element); | |
1138 } | |
1139 } | |
1140 return result; | |
1141 } | |
1142 | |
1143 static Set setUnion(Set set, Set other, Set result) { | |
1144 result.addAll(set); | |
1145 result.addAll(other); | |
1146 return result; | |
1147 } | |
1148 | |
1149 static Set setDifference(Set set, Set other, Set result) { | |
1150 for (var element in set) { | |
1151 if (!other.contains(element)) { | |
1152 result.add(element); | |
1153 } | |
1154 } | |
1155 return result; | |
1156 } | |
1157 } | |
1158 | 760 |
1159 /** | 761 /** |
1160 * Creates errors throw by [Iterable] when the element count is wrong. | 762 * Creates errors throw by [Iterable] when the element count is wrong. |
1161 */ | 763 */ |
1162 abstract class IterableElementError { | 764 abstract class IterableElementError { |
1163 /** Error thrown thrown by, e.g., [Iterable.first] when there is no result. */ | 765 /** Error thrown thrown by, e.g., [Iterable.first] when there is no result. */ |
1164 static StateError noElement() => new StateError("No element"); | 766 static StateError noElement() => new StateError("No element"); |
1165 /** Error thrown by, e.g., [Iterable.single] if there are too many results. */ | 767 /** Error thrown by, e.g., [Iterable.single] if there are too many results. */ |
1166 static StateError tooMany() => new StateError("Too many elements"); | 768 static StateError tooMany() => new StateError("Too many elements"); |
1167 /** Error thrown by, e.g., [List.setRange] if there are too few elements. */ | 769 /** Error thrown by, e.g., [List.setRange] if there are too few elements. */ |
1168 static StateError tooFew() => new StateError("Too few elements"); | 770 static StateError tooFew() => new StateError("Too few elements"); |
1169 } | 771 } |
OLD | NEW |