761 sortBlock := aSortBlock |
761 sortBlock := aSortBlock |
762 ! ! |
762 ! ! |
763 |
763 |
764 !SortedCollection methodsFor:'queries'! |
764 !SortedCollection methodsFor:'queries'! |
765 |
765 |
|
766 includes:anObject |
|
767 "return true, if the argument, anObject is in the collection. |
|
768 Redefined, since due to being sorted, the inclusion check can |
|
769 be done with log-n compares i.e. much faster." |
|
770 |
|
771 |index "{ Class: SmallInteger }" |
|
772 initialIndex "{ Class: SmallInteger }" |
|
773 element| |
|
774 |
|
775 "/ if I am small, the inherited linear search is faster ... |
|
776 (lastIndex - firstIndex) < 20 ifTrue:[ |
|
777 firstIndex > lastIndex ifTrue:[ |
|
778 "/ empty |
|
779 ^ false |
|
780 ]. |
|
781 ^ super includes:anObject. |
|
782 ]. |
|
783 |
|
784 initialIndex := self indexForInserting:anObject. |
|
785 ((initialIndex < firstIndex) or:[initialIndex > lastIndex]) ifTrue:[^ false]. |
|
786 (contentsArray basicAt:initialIndex) = anObject ifTrue:[ |
|
787 "the simple case - plain objects" |
|
788 ^ true. |
|
789 ]. |
|
790 |
|
791 "the complex case: the collection may include elements, which are odered only by |
|
792 a single component (e.g. Associations by key). So we have to test all |
|
793 previous and next elements having the same component" |
|
794 |
|
795 "for previous elements: while element is not smaller and not larger than anObject ... compare" |
|
796 index := initialIndex - 1. |
|
797 [index >= firstIndex |
|
798 and:[ |
|
799 element := contentsArray basicAt:index. |
|
800 ((sortBlock value:element value:anObject) or:[sortBlock value:anObject value:element]) not] |
|
801 ] whileTrue:[ |
|
802 element = anObject ifTrue:[ |
|
803 ^ true. |
|
804 ]. |
|
805 index := index - 1. |
|
806 ]. |
|
807 |
|
808 "for next elements: while element is not smaller and not larger than anObject ... compare" |
|
809 index := initialIndex + 1. |
|
810 [index <= lastIndex |
|
811 and:[ |
|
812 element := contentsArray basicAt:index. |
|
813 ((sortBlock value:element value:anObject) or:[sortBlock value:anObject value:element]) not] |
|
814 ] whileTrue:[ |
|
815 element = anObject ifTrue:[ |
|
816 ^ true. |
|
817 ]. |
|
818 index := index + 1. |
|
819 ]. |
|
820 |
|
821 ^ false. |
|
822 |
|
823 " |
|
824 #(7 3 9 10 99) asSortedCollection includes:50 |
|
825 #(7 3 9 10 99) asSortedCollection includes:10 |
|
826 " |
|
827 ! |
|
828 |
766 isSorted |
829 isSorted |
767 "return true. if my elements are sorted" |
830 "return true. if my elements are sorted" |
768 |
831 |
769 ^ true |
832 ^ true |
770 ! |
833 ! |
780 |
843 |
781 isSortedCollection |
844 isSortedCollection |
782 "return true. if I am a sorted collection" |
845 "return true. if I am a sorted collection" |
783 |
846 |
784 ^ true |
847 ^ true |
|
848 ! |
|
849 |
|
850 occurrencesOf:anObject |
|
851 "return how many times the argument, anObject is in the collection. |
|
852 Redefined, since due to being sorted, the range of checked objects |
|
853 can be limited i.e. it can be done much faster. |
|
854 Uses #= (i.e. equality) compare." |
|
855 |
|
856 |index "{ Class: SmallInteger }" |
|
857 tally "{ Class: SmallInteger }" |
|
858 last "{ Class: SmallInteger }" | |
|
859 |
|
860 index := self indexOf:anObject. |
|
861 index == 0 ifTrue:[ |
|
862 ^ 0 |
|
863 ]. |
|
864 |
|
865 index := index + firstIndex - 1. |
|
866 last := lastIndex. |
|
867 |
|
868 "/ there may be multiple of them; count 'em |
|
869 |
|
870 tally := 0. |
|
871 [(index <= last) and:[(contentsArray basicAt:index) = anObject]] whileTrue:[ |
|
872 tally := tally + 1. |
|
873 index := index + 1 |
|
874 ]. |
|
875 ^ tally |
|
876 |
|
877 " |
|
878 #(7 3 9 10 99) asSortedCollection occurrencesOf:50 |
|
879 #(7 3 9 10 99) asSortedCollection occurrencesOf:10 |
|
880 #(7 10 3 10 9 10 10 10 10 10 10 10 10 99) asSortedCollection occurrencesOf:10 |
|
881 " |
|
882 |
|
883 "Modified: 12.4.1996 / 18:48:40 / cg" |
785 ! |
884 ! |
786 |
885 |
787 speciesForCollecting |
886 speciesForCollecting |
788 "Redefined to return an OrderedCollection; |
887 "Redefined to return an OrderedCollection; |
789 see X3J20 spec. (SortedCollection>>collect: should return an OrderedCollection)" |
888 see X3J20 spec. (SortedCollection>>collect: should return an OrderedCollection)" |
1055 #(10 35 20 45 30 5) asSortedCollection median |
1154 #(10 35 20 45 30 5) asSortedCollection median |
1056 #(10 35 20 45 30 5) median |
1155 #(10 35 20 45 30 5) median |
1057 " |
1156 " |
1058 ! ! |
1157 ! ! |
1059 |
1158 |
1060 !SortedCollection methodsFor:'testing'! |
|
1061 |
|
1062 includes:anObject |
|
1063 "return true, if the argument, anObject is in the collection. |
|
1064 Redefined, since due to being sorted, the inclusion check can |
|
1065 be done with log-n compares i.e. much faster." |
|
1066 |
|
1067 |index "{ Class: SmallInteger }" |
|
1068 initialIndex "{ Class: SmallInteger }" |
|
1069 element| |
|
1070 |
|
1071 "/ if I am small, the inherited linear search is faster ... |
|
1072 (lastIndex - firstIndex) < 20 ifTrue:[ |
|
1073 firstIndex > lastIndex ifTrue:[ |
|
1074 "/ empty |
|
1075 ^ false |
|
1076 ]. |
|
1077 ^ super includes:anObject. |
|
1078 ]. |
|
1079 |
|
1080 initialIndex := self indexForInserting:anObject. |
|
1081 ((initialIndex < firstIndex) or:[initialIndex > lastIndex]) ifTrue:[^ false]. |
|
1082 (contentsArray basicAt:initialIndex) = anObject ifTrue:[ |
|
1083 "the simple case - plain objects" |
|
1084 ^ true. |
|
1085 ]. |
|
1086 |
|
1087 "the complex case: the collection may include elements, which are odered only by |
|
1088 a single component (e.g. Associations by key). So we have to test all |
|
1089 previous and next elements having the same component" |
|
1090 |
|
1091 "for previous elements: while element is not smaller and not larger than anObject ... compare" |
|
1092 index := initialIndex - 1. |
|
1093 [index >= firstIndex |
|
1094 and:[ |
|
1095 element := contentsArray basicAt:index. |
|
1096 ((sortBlock value:element value:anObject) or:[sortBlock value:anObject value:element]) not] |
|
1097 ] whileTrue:[ |
|
1098 element = anObject ifTrue:[ |
|
1099 ^ true. |
|
1100 ]. |
|
1101 index := index - 1. |
|
1102 ]. |
|
1103 |
|
1104 "for next elements: while element is not smaller and not larger than anObject ... compare" |
|
1105 index := initialIndex + 1. |
|
1106 [index <= lastIndex |
|
1107 and:[ |
|
1108 element := contentsArray basicAt:index. |
|
1109 ((sortBlock value:element value:anObject) or:[sortBlock value:anObject value:element]) not] |
|
1110 ] whileTrue:[ |
|
1111 element = anObject ifTrue:[ |
|
1112 ^ true. |
|
1113 ]. |
|
1114 index := index + 1. |
|
1115 ]. |
|
1116 |
|
1117 ^ false. |
|
1118 |
|
1119 " |
|
1120 #(7 3 9 10 99) asSortedCollection includes:50 |
|
1121 #(7 3 9 10 99) asSortedCollection includes:10 |
|
1122 " |
|
1123 ! |
|
1124 |
|
1125 occurrencesOf:anObject |
|
1126 "return how many times the argument, anObject is in the collection. |
|
1127 Redefined, since due to being sorted, the range of checked objects |
|
1128 can be limited i.e. it can be done much faster. |
|
1129 Uses #= (i.e. equality) compare." |
|
1130 |
|
1131 |index "{ Class: SmallInteger }" |
|
1132 tally "{ Class: SmallInteger }" |
|
1133 last "{ Class: SmallInteger }" | |
|
1134 |
|
1135 index := self indexOf:anObject. |
|
1136 index == 0 ifTrue:[ |
|
1137 ^ 0 |
|
1138 ]. |
|
1139 |
|
1140 index := index + firstIndex - 1. |
|
1141 last := lastIndex. |
|
1142 |
|
1143 "/ there may be multiple of them; count 'em |
|
1144 |
|
1145 tally := 0. |
|
1146 [(index <= last) and:[(contentsArray basicAt:index) = anObject]] whileTrue:[ |
|
1147 tally := tally + 1. |
|
1148 index := index + 1 |
|
1149 ]. |
|
1150 ^ tally |
|
1151 |
|
1152 " |
|
1153 #(7 3 9 10 99) asSortedCollection occurrencesOf:50 |
|
1154 #(7 3 9 10 99) asSortedCollection occurrencesOf:10 |
|
1155 #(7 10 3 10 9 10 10 10 10 10 10 10 10 99) asSortedCollection occurrencesOf:10 |
|
1156 " |
|
1157 |
|
1158 "Modified: 12.4.1996 / 18:48:40 / cg" |
|
1159 ! ! |
|
1160 |
|
1161 !SortedCollection class methodsFor:'documentation'! |
1159 !SortedCollection class methodsFor:'documentation'! |
1162 |
1160 |
1163 version |
1161 version |
1164 ^ '$Header$' |
1162 ^ '$Header$' |
1165 ! |
1163 ! |