??????????????????????????????Python???????????????????????????????????????н???
1 # coding=utf-8
2
3 __all__=['ADTString']
4
5 class ADTString(object):
6     '''
7     ???????????????????????·???
8     '''
9     def __init__(self?? d=''):
10         '''
11         data????洢??
12         '''
13         self.data = d
14
15     def StrCopy(self):
16         '''
17         ?????????????????data
18         '''
19         return self.data
20
21     def ClearString(self):
22         '''
23         ???????
24         '''
25         self.data = ''
26
27     def StringEmpty(self):
28         '''
29         ?ж????????????????True??False
30         '''
31         return False if len(self.data) else True
32
33     def StrLength(self):
34         '''
35         ?????????????
36         '''
37         return len(self.data)
38
39     def StrCompare(self?? T):
40         '''
41         ???????T???б????????T????1???????T????0??С???T????-1
42         '''
43         len_S = self.StrLength()
44         len_T = T.StrLength()
45         len_min = min(len_S?? len_T)
46         len_max = max(len_S?? len_T)
47         i=j=0
48         while(True):
49             if (i>=len_min):
50                 if len_min==len_max:
51                     return 0
52                 elif (j >=len_min):
53                     return 1 if len_S  > len_T else -1
54
55             if(self.data[i]==T.data[j]):
56                 i=i+1
57                 j=j+1
58             elif self.data[i]<T.data[j]:
59                 return -1
60             elif self.data[i]>T.data[j]:
61                 return 1
62
63     def Concat(self?? S2):
64         '''
65         ??????????S2
66         '''
67         return self.data+S2.data
68
69     def SubString(self?? pos?? len_):
70         '''
71         ?????????У???pos???????len_???????
72         pos?????????????
73         '''
74         if pos >= 0:
75             if len(self.data) < pos:
76                 return -1
77             return self.data[pos:pos+len_]
78         else:
79             if len_==0 or pos==-1:
80                 return ''
81             elif pos+len_==0 or abs(pos)<len_:
82                 return self.data[pos:-1]+self.data[-1]
83             else:
84                 return self.data[pos:pos+len_]
85
86     def Index(self?? T?? pos):
87         '''
88         ??????S?д?????T????????????????????????е?pos???????????γ????λ?????????-1
89         '''
90         len_T = T.StrLength()
91         len_S = self.StrLength()
92         if len_S < len_T + pos:
93             return -1
94
95         p1 = pos
96         p2 = pos + len_T
97         while(p2<=len_S):
98             if self.SubString(p1?? len_T) == T.data:
99                 return p1
100             else:
101                 p1=p1+1
102                 p2=p2+1
103
104         if p2 > len_S:
105             return -1
106
107     def IndexBruteforce(self?? T?? pos):
108         '''
109         ?????????????????S?д?????T????????????????????????е?pos???????????γ????λ?????????-1?????????????????????
110         '''
111         len_T = T.StrLength()
112         len_S = self.StrLength()
113         i=pos
114         j=0
115         while(True):
116             if i >= len_S or j >= len_T:
117                 break
118             if(self.data[i]==T.data[j]):
119                 i=i+1
120                 j=j+1
121             else:
122                 i=i-j+1
123                 j=0
124
125         return i-j if j>=len_T else -1
126
127     def GetNext(self):
128         '''
129         ????KMP??????????next????
130         '''
131         len_S=self.StrLength()
132         next=[0]
133         i=1
134         while(True):
135             if i>=len_S:
136                 break
137
138             k = next[i-1]
139             while(self.data[k]!=self.data[i] and k!=0):
140                 k=next[k-1]
141             if self.data[k]==self.data[i]:
142                 next.append(k+1)
143             else:
144                 next.append(0)
145
146             i=i+1
147         return next
148
149     def IndexKMP(self?? T?? pos):
150         '''
151         KMP?????????????S?д?????T????????????????????????е?pos???????????γ????λ?????????-1?????????????????????
152         '''
153         next=self.GetNext()
154         len_T = T.StrLength()
155         len_S = self.StrLength()
156         i=pos
157         j=0
158         while(True):
159             if i >= len_S or j >= len_T:
160                 break
161             if(self.data[i]==T.data[j]):
162                 i=i+1
163                 j=j+1
164             else:
165                 i=i+next[i]+1
166                 j=0
167         return i-j if j>=len_T else -1
168
169
170
171     def Replace(self?? T?? V):
172         '''
173         ???V?滻????S?У????????????T?????????????
174         '''
175         string = ''
176         len_S = len(self.data)
177         len_T = len(T.data)
178         p1=p2=0
179         while(True):
180             pos = self.Index(T?? p2)
181             if pos == -1:
182                 string+=self.data[p2:]
183                 break
184             else:
185                 p1=pos
186                 string+=self.data[p2:p1]
187                 string+= V.data
188                 p2=p1+len_T
189
190         if string == '':
191             return self.data
192         else:
193             return string
194
195     def StrInsert(self?? pos?? T):
196         '''
197         ?????????pos???????????T;pos??????????????
198         '''
199         len_S = len(self.data)
200         if len_S < pos or len_S <abs(pos):
201             return -1
202
203         return self.data[:pos]+T.data+self.data[pos:]
204
205     def StrDelete(self?? pos?? len_):
206         '''
207         ?????????pos??????????len_????????
208         posС??0?????????
209         '''
210         len_S = len(self.data)
211         if pos >= 0:
212             if len_S < pos:
213                 return -1
214             return self.data[:pos]+self.data[pos+len_:]
215         else:
216             if len_S < abs(pos) :
217                 return -1
218             return self.data[:pos-len_]+self.data[pos:]
219
220 if __name__ == '__main__':
221     from ADTString import ADTString
222     # ????????readme???
223     print help(ADTString)
??????3?У?__all__?ж??????????????from <module> import * ??????????????
??????15~218?У??????Щ?????????????У???86~105?е?Index??????????SubString?????????????107~125?У??????????????????????149~167?У??????KMP????????????
??????223?У?????????????????????????ο??????
????????????????е??????????unittest??飬?????????У?????е????????????
1 # conding=utf-8
2
3 from ADTString import ADTString
4 import unittest
5
6 class TestADTStringMethods(unittest.TestCase):
7     def setUp(self):
8         self.obj = ADTString()
9
10     def tearDown(self):
11         pass
12
13     def test_StrCopy(self):
14         self.obj.data=''
15         self.assertEqual(self.obj.StrCopy()?? '')
16         self.obj.data='goodgoogle'
17         self.assertEqual(self.obj.StrCopy()?? 'goodgoogle')
18         self.obj.data='!'
19         self.assertEqual(self.obj.StrCopy()?? '!')
20
21     def test_ClearString(self):
22         self.obj.data='goodgoogle'
23         self.obj.ClearString()
24         self.assertEqual(self.obj.data?? '')
25
26     def test_StringEmpty(self):
27         self.obj.data=''
28         self.assertEqual(self.obj.data?? '')
29
30     def test_StrLength(self):
31         self.obj.data='123'
32         self.assertEqual(self.obj.StrLength()?? 3)
33         self.obj.data=''
34         self.assertEqual(self.obj.StrLength()?? 0)
35
36     def test_StrCompare(self):
37         obj_T=ADTString('goodgoogle')
38         self.obj.data='goodgoogle'
39         self.assertEqual(self.obj.StrCompare(obj_T)??0)
40         self.obj.data='goodgoogl'
41         self.assertEqual(self.obj.StrCompare(obj_T)??-1)
42         self.obj.data='goodgooglea'
43         self.assertEqual(self.obj.StrCompare(obj_T)??1)
44
45     def test_Concat(self):
46         self.obj.data='good'
47         obj_S2=ADTString('google')
48         self.assertEqual(self.obj.Concat(obj_S2)??'goodgoogle')
49         self.obj.data=''
50         self.assertEqual(self.obj.Concat(obj_S2)??'google')
51
52     def test_SubString(self):
53         self.obj.data='goodgoogle'
54         self.assertEqual(self.obj.SubString(0??0)??'')
55         self.assertEqual(self.obj.SubString(0??1)??'g')
56         self.assertEqual(self.obj.SubString(0??4)??'good')
57         self.assertEqual(self.obj.SubString(0??100)??'goodgoogle')
58         self.assertEqual(self.obj.SubString(100??1)??-1)
59         self.assertEqual(self.obj.SubString(-50??0)??'')
60         self.assertEqual(self.obj.SubString(-5??0)??'')
61         self.assertEqual(self.obj.SubString(-1??0)??'')
62         self.assertEqual(self.obj.SubString(-1??1)??'')
63         self.assertEqual(self.obj.SubString(-1??2)??'')
64         self.assertEqual(self.obj.SubString(-6??1)??'g')
65         self.assertEqual(self.obj.SubString(-6??6)??'google')
66         self.assertEqual(self.obj.SubString(-6??100)??'google')
67         self.assertEqual(self.obj.SubString(-6??10)??'google')
68
69     def test_Index(self):
70         self.obj.data='goodgoogle'
71         obj_T=ADTString('good')
72         self.assertEqual(self.obj.Index(obj_T?? 0)??0)
73         self.assertEqual(self.obj.Index(obj_T?? 1)??-1)
74         self.obj.data='googlegood'
75         self.assertEqual(self.obj.Index(obj_T?? 0)??6)
76         self.assertEqual(self.obj.Index(obj_T?? 7)??-1)
77         self.obj.data=''
78         self.assertEqual(self.obj.Index(obj_T?? 0)??-1)
79
80     def test_IndexBruteforce(self):
81         self.obj.data='goodgoogle'
82         obj_T=ADTString('good')
83         self.assertEqual(self.obj.Index(obj_T?? 0)??0)
84         self.assertEqual(self.obj.Index(obj_T?? 1)??-1)
85         self.obj.data='googlegood'
86         self.assertEqual(self.obj.Index(obj_T?? 0)??6)
87         self.assertEqual(self.obj.Index(obj_T?? 7)??-1)
88         self.obj.data=''
89         self.assertEqual(self.obj.Index(obj_T?? 0)??-1)
90
91     def test_IndexKMP(self):
92         self.obj.data='goodgoogle'
93         obj_T=ADTString('good')
94         self.assertEqual(self.obj.Index(obj_T?? 0)??0)
95         self.assertEqual(self.obj.Index(obj_T?? 1)??-1)
96         self.obj.data='googlegood'
97         self.assertEqual(self.obj.Index(obj_T?? 0)??6)
98         self.assertEqual(self.obj.Index(obj_T?? 7)??-1)
99         self.obj.data=''
100         self.assertEqual(self.obj.Index(obj_T?? 0)??-1)
101
102     def test_Replace(self):
103         self.obj.data='good'
104         obj_T=ADTString('good')
105         obj_V=ADTString('replace')
106         self.assertEqual(self.obj.Replace(obj_T?? obj_V)??'replace')
107         self.obj.data='googlegood'
108         self.assertEqual(self.obj.Replace(obj_T?? obj_V)??'googlereplace')
109         self.obj.data='goodgooglegood'
110         self.assertEqual(self.obj.Replace(obj_T?? obj_V)??'replacegooglereplace')
111         self.obj.data=''
112         self.assertEqual(self.obj.Replace(obj_T?? obj_V)??'')
113         self.obj.data='aaa'
114         self.assertEqual(self.obj.Replace(obj_T?? obj_V)??'aaa')
115
116     def test_StrInsert(self):
117         self.obj.data='goodgoogle'
118         obj_T=ADTString('insert')
119         self.assertEqual(self.obj.StrInsert(0??obj_T)??'insertgoodgoogle')
120         self.assertEqual(self.obj.StrInsert(100??obj_T)??-1)
121         self.assertEqual(self.obj.StrInsert(len(self.obj.data)??obj_T)??'goodgoogleinsert')
122         self.assertEqual(self.obj.StrInsert(4??obj_T)??'goodinsertgoogle')
123         self.assertEqual(self.obj.StrInsert(-1??obj_T)??'goodgooglinserte')
124         self.assertEqual(self.obj.StrInsert(-100??obj_T)??-1)
125
126     def test_StrDelete(self):
127         self.obj.data='goodgoogle'
128         self.assertEqual(self.obj.StrDelete(0??4)??'google')
129         self.assertEqual(self.obj.StrDelete(0??100)??'')
130         self.assertEqual(self.obj.StrDelete(-1??1)??'goodgooge')
131         self.assertEqual(self.obj.StrDelete(-2??3)??'goodgle')
132         self.assertEqual(self.obj.StrDelete(-2??100)??'le')
133         self.assertEqual(self.obj.StrDelete(-100??1)??-1)
134
135
136 suite = unittest.TestLoader().loadTestsFromTestCase(TestADTStringMethods)
137 unittest.TextTestRunner(verbosity=2).run(suite)
??????е??????￡?
test_ClearString (__main__.TestADTStringMethods) ... ok
test_Concat (__main__.TestADTStringMethods) ... ok
test_Index (__main__.TestADTStringMethods) ... ok
test_IndexBruteforce (__main__.TestADTStringMethods) ... ok
test_IndexKMP (__main__.TestADTStringMethods) ... ok
test_Replace (__main__.TestADTStringMethods) ... ok
test_StrCompare (__main__.TestADTStringMethods) ... ok
test_StrCopy (__main__.TestADTStringMethods) ... ok
test_StrDelete (__main__.TestADTStringMethods) ... ok
test_StrInsert (__main__.TestADTStringMethods) ... ok
test_StrLength (__main__.TestADTStringMethods) ... ok
test_StringEmpty (__main__.TestADTStringMethods) ... ok
test_SubString (__main__.TestADTStringMethods) ... ok
----------------------------------------------------------------------
Ran 13 tests in 0.001s
OK
[Finished in 0.1s]