-
Notifications
You must be signed in to change notification settings - Fork 1
/
listhelp.py
152 lines (135 loc) · 4.29 KB
/
listhelp.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
# file: listhelp.py
# author: Colin Woodbury
# contact: colingw AT gmail
# about: A module that helps with list processing.
from decorum import *
class picker():
'''An iterator that yields random elements from a given list
until all the elements have been given.
'''
def __init__(self, items, lim=None):
self.items = list(items)
if not lim or lim > len(self.items):
lim = len(self.items)
self.lim = lim
def __len__(self):
return len(self.items)
def __iter__(self):
from random import Random
r = Random()
for x in range(self.lim):
pos = r.randint(0, len(self.items) - 1)
yield self.items[pos]
self.items.remove(self.items[pos])
def concat(items):
'''Concats all the items of the list together as a string.
Made: 03/04/2011 Mod: 05/31/2011 to kick ass.
'''
return ''.join(map(_concat, items))
def _concat(items):
'''The work.'''
if type(items) is str:
return items
elif hasattr(items, '__iter__'):
return concat(items)
return str(items)
def rotate(items, places=1):
'''Rotates elements in a list.'''
size = len(items)
return items[-(size-places):] + items[:-(size-places)]
def scramble(items):
'''Scrambles a given list. Will never return the same list.
What are the chances of this blowing the stack, given a certain word
length? That is to say, what are the chances that picker will generate
an identicle list, say, 1000 times in a row?
'''
if len(items) in (0, 1):
return list(items)
result = [x for x in picker(items)]
if result == list(items):
result = scramble(items)
return result
def frequencies(items):
'''Produces a dictionary of keys equal to the items in 'items',
and values that indicate how many times that item appeared.
'''
freqs = {}
for item in items:
if item in freqs:
freqs[item] += 1
else:
freqs[item] = 1
return freqs
# BINARY SEARCH, SORT TESTS, AND ORDERED INSERTION
def is_sorted(items):
'''Determines if a list is sorted.'''
if len(items) in (0, 1):
return True
for x in range(0, len(items) - 1):
if items[x] > items[x + 1]:
return False
return True
def is_sorted2(items):
'''Determines if a list is sorted, in a functional style. Slower.'''
if len(items) in (0, 1):
return True
pairs = zip(items, items[1:])
return all(map(lambda tup: False if tup[0] > tup[1] else True, pairs))
def bin_search(items, num):
'''A binary search algorithm.'''
size = len(items)
lower = 0
upper = size - 1
loc = -1 # Assume failure.
if size == 0:
return -1
while lower <= upper:
mid = (lower + upper) // 2
if items[mid] < num: # Throw away lower part.
lower = mid+1
elif items[mid] == num: # Found.
loc = mid
break
else: # Throw away upper part.
upper = mid-1
return loc
def ordered_insert(items, num):
'''Inserts the given argument in order into the list.'''
size = len(items)
if size == 0:
items.append(num)
else: # Locate proper insert location.
loc = mod_bin_search(items, num)
if loc == size:
items.append(num)
else:
items.insert(loc, num)
def mod_bin_search(items, num):
'''Used by ordered_insert(), it determines where
a value should be placed within a sorted list.
'''
size = len(items)
lower = 0
upper = size - 1
if num <= items[lower]:
return 0
elif num >= items[upper]:
return size
while lower <= upper:
mid = (lower + upper) // 2
if num == items[mid]:
loc = mid
break
elif num > items[mid] and num < items[mid + 1]:
# Goes to the right of mid.
loc = mid+1
break
elif num < items[mid] and num > items[mid - 1]:
# Goes to the left of mid.
loc = mid
break
elif num > items[mid + 1]:
lower = mid + 1
else: #num < self[mid - 1]:
upper = mid - 1
return loc