cpython/Lib/collections/__init__.py at 3.5 · python/cpython · GitHub

Repository navigation

History

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

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

526

527

528

529

530

531

532

533

534

535

536

537

538

539

540

541

542

543

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

571

572

573

574

575

576

577

578

579

580

581

582

583

584

585

586

587

588

589

590

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646

647

648

649

650

651

652

653

654

655

656

657

658

659

660

661

662

663

664

665

666

667

668

669

670

671

672

673

674

675

676

677

678

679

680

681

682

683

684

685

686

687

688

689

690

691

692

693

694

695

696

697

698

699

700

701

702

703

704

705

706

707

708

709

710

711

712

713

714

715

716

717

718

719

720

721

722

723

724

725

726

727

728

729

730

731

732

733

734

735

736

737

738

739

740

741

742

743

744

745

746

747

748

749

750

751

752

753

754

755

756

757

758

759

760

761

762

763

764

765

766

767

768

769

770

771

772

773

774

775

776

777

778

779

780

781

782

783

784

785

786

787

788

789

790

791

792

793

794

795

796

797

798

799

800

801

802

803

804

805

806

807

808

809

810

811

812

813

814

815

816

817

818

819

820

821

822

823

824

825

826

827

828

829

830

831

832

833

834

835

836

837

838

839

840

841

842

843

844

845

846

847

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

864

865

866

867

868

869

870

871

872

873

874

875

876

877

878

879

880

881

882

883

884

885

886

887

888

889

890

891

892

893

894

895

896

897

898

899

900

901

902

903

904

905

906

907

908

909

910

911

912

913

914

915

916

917

918

919

920

921

922

923

924

925

926

927

928

929

930

931

932

933

934

935

936

937

938

939

940

941

942

943

944

945

946

947

948

949

950

951

952

953

954

955

956

957

958

959

960

961

962

963

964

965

966

967

968

969

970

971

972

973

974

975

976

977

978

979

980

981

982

983

984

985

986

987

988

989

990

991

992

993

994

995

996

997

998

999

1000

'''This module implements specialized container datatypes providing

alternatives to Python's general purpose built-in containers, dict,

list, set, and tuple.

* namedtuple factory function for creating tuple subclasses with named fields

* deque list-like container with fast appends and pops on either end

* ChainMap dict-like class for creating a single view of multiple mappings

* Counter dict subclass for counting hashable objects

* OrderedDict dict subclass that remembers the order entries were added

* defaultdict dict subclass that calls a factory function to supply missing values

* UserDict wrapper around dictionary objects for easier dict subclassing

* UserList wrapper around list objects for easier list subclassing

* UserString wrapper around string objects for easier string subclassing

'''

__all__ = ['deque', 'defaultdict', 'namedtuple', 'UserDict', 'UserList',

'UserString', 'Counter', 'OrderedDict', 'ChainMap']

# For backwards compatibility, continue to make the collections ABCs

# available through the collections module.

from _collections_abc import *

import _collections_abc

__all__ += _collections_abc.__all__

from operator import itemgetter as _itemgetter, eq as _eq

from keyword import iskeyword as _iskeyword

import sys as _sys

import heapq as _heapq

from _weakref import proxy as _proxy

from itertools import repeat as _repeat, chain as _chain, starmap as _starmap

from reprlib import recursive_repr as _recursive_repr

try:

from _collections import deque

except ImportError:

pass

else:

MutableSequence.register(deque)

try:

from _collections import defaultdict

except ImportError:

pass

################################################################################

### OrderedDict

################################################################################

class _OrderedDictKeysView(KeysView):

def __reversed__(self):

yield from reversed(self._mapping)

class _OrderedDictItemsView(ItemsView):

def __reversed__(self):

for key in reversed(self._mapping):

yield (key, self._mapping[key])

class _OrderedDictValuesView(ValuesView):

def __reversed__(self):

for key in reversed(self._mapping):

yield self._mapping[key]

class _Link(object):

__slots__ = 'prev', 'next', 'key', '__weakref__'

class OrderedDict(dict):

'Dictionary that remembers insertion order'

# An inherited dict maps keys to values.

# The inherited dict provides __getitem__, __len__, __contains__, and get.

# The remaining methods are order-aware.

# Big-O running times for all methods are the same as regular dictionaries.

# The internal self.__map dict maps keys to links in a doubly linked list.

# The circular doubly linked list starts and ends with a sentinel element.

# The sentinel element never gets deleted (this simplifies the algorithm).

# The sentinel is in self.__hardroot with a weakref proxy in self.__root.

# The prev links are weakref proxies (to prevent circular references).

# Individual links are kept alive by the hard reference in self.__map.

# Those hard references disappear when a key is deleted from an OrderedDict.

def __init__(*args, **kwds):

'''Initialize an ordered dictionary. The signature is the same as

regular dictionaries, but keyword arguments are not recommended because

their insertion order is arbitrary.

'''

if not args:

raise TypeError("descriptor '__init__' of 'OrderedDict' object "

"needs an argument")

self, *args = args

if len(args) > 1:

raise TypeError('expected at most 1 arguments, got %d' % len(args))

try:

self.__root

except AttributeError:

self.__hardroot = _Link()

self.__root = root = _proxy(self.__hardroot)

root.prev = root.next = root

self.__map = {}

self.__update(*args, **kwds)

def __setitem__(self, key, value,

dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):

'od.__setitem__(i, y) <==> od[i]=y'

# Setting a new item creates a new link at the end of the linked list,

# and the inherited dictionary is updated with the new key/value pair.

if key not in self:

self.__map[key] = link = Link()

root = self.__root

last = root.prev

link.prev, link.next, link.key = last, root, key

last.next = link

root.prev = proxy(link)

dict_setitem(self, key, value)

def __delitem__(self, key, dict_delitem=dict.__delitem__):

'od.__delitem__(y) <==> del od[y]'

# Deleting an existing item uses self.__map to find the link which gets

# removed by updating the links in the predecessor and successor nodes.

dict_delitem(self, key)

link = self.__map.pop(key)

link_prev = link.prev

link_next = link.next

link_prev.next = link_next

link_next.prev = link_prev

link.prev = None

link.next = None

def __iter__(self):

'od.__iter__() <==> iter(od)'

# Traverse the linked list in order.

root = self.__root

curr = root.next

while curr is not root:

yield curr.key

curr = curr.next

def __reversed__(self):

'od.__reversed__() <==> reversed(od)'

# Traverse the linked list in reverse order.

root = self.__root

curr = root.prev

while curr is not root:

yield curr.key

curr = curr.prev

def clear(self):

'od.clear() -> None. Remove all items from od.'

root = self.__root

root.prev = root.next = root

self.__map.clear()

dict.clear(self)

def popitem(self, last=True):

'''od.popitem() -> (k, v), return and remove a (key, value) pair.

Pairs are returned in LIFO order if last is true or FIFO order if false.

'''

if not self:

raise KeyError('dictionary is empty')

root = self.__root

if last:

link = root.prev

link_prev = link.prev

link_prev.next = root

root.prev = link_prev

else:

link = root.next

link_next = link.next

root.next = link_next

link_next.prev = root

key = link.key

del self.__map[key]

value = dict.pop(self, key)

return key, value

def move_to_end(self, key, last=True):

'''Move an existing element to the end (or beginning if last==False).

Raises KeyError if the element does not exist.

When last=True, acts like a fast version of self[key]=self.pop(key).

'''

link = self.__map[key]

link_prev = link.prev

link_next = link.next

soft_link = link_next.prev

link_prev.next = link_next

link_next.prev = link_prev

root = self.__root

if last:

last = root.prev

link.prev = last

link.next = root

root.prev = soft_link

last.next = link

else:

first = root.next

link.prev = root

link.next = first

first.prev = soft_link

root.next = link

def __sizeof__(self):

sizeof = _sys.getsizeof

n = len(self) + 1 # number of links including root

size = sizeof(self.__dict__) # instance dictionary

size += sizeof(self.__map) * 2 # internal dict and inherited dict

size += sizeof(self.__hardroot) * n # link objects

size += sizeof(self.__root) * n # proxy objects

return size

update = __update = MutableMapping.update

def keys(self):

"D.keys() -> a set-like object providing a view on D's keys"

return _OrderedDictKeysView(self)

def items(self):

"D.items() -> a set-like object providing a view on D's items"

return _OrderedDictItemsView(self)

def values(self):

"D.values() -> an object providing a view on D's values"

return _OrderedDictValuesView(self)

__ne__ = MutableMapping.__ne__

__marker = object()

def pop(self, key, default=__marker):

'''od.pop(k[,d]) -> v, remove specified key and return the corresponding

value. If key is not found, d is returned if given, otherwise KeyError

is raised.

'''

if key in self:

result = self[key]

del self[key]

return result

if default is self.__marker:

raise KeyError(key)

return default

def setdefault(self, key, default=None):

'od.setdefault(k[,d]) -> od.get(k,d), also set od[k]=d if k not in od'

if key in self:

return self[key]

self[key] = default

return default

@_recursive_repr()

def __repr__(self):

'od.__repr__() <==> repr(od)'

if not self:

return '%s()' % (self.__class__.__name__,)

return '%s(%r)' % (self.__class__.__name__, list(self.items()))

def __reduce__(self):

'Return state information for pickling'

inst_dict = vars(self).copy()

for k in vars(OrderedDict()):

inst_dict.pop(k, None)

return self.__class__, (), inst_dict or None, None, iter(self.items())

def copy(self):

'od.copy() -> a shallow copy of od'

return self.__class__(self)

@classmethod

def fromkeys(cls, iterable, value=None):

'''OD.fromkeys(S[, v]) -> New ordered dictionary with keys from S.

If not specified, the value defaults to None.

'''

self = cls()

for key in iterable:

self[key] = value

return self

def __eq__(self, other):

'''od.__eq__(y) <==> od==y. Comparison to another OD is order-sensitive

while comparison to a regular mapping is order-insensitive.

'''

if isinstance(other, OrderedDict):

return dict.__eq__(self, other) and all(map(_eq, self, other))

return dict.__eq__(self, other)

try:

from _collections import OrderedDict

except ImportError:

# Leave the pure Python version in place.

pass

################################################################################

### namedtuple

################################################################################

_class_template = """\

from builtins import property as _property, tuple as _tuple

from operator import itemgetter as _itemgetter

from collections import OrderedDict

class {typename}(tuple):

'{typename}({arg_list})'

__slots__ = ()

_fields = {field_names!r}

def __new__(_cls, {arg_list}):

'Create new instance of {typename}({arg_list})'

return _tuple.__new__(_cls, ({arg_list}))

@classmethod

def _make(cls, iterable, new=tuple.__new__, len=len):

'Make a new {typename} object from a sequence or iterable'

result = new(cls, iterable)

if len(result) != {num_fields:d}:

raise TypeError('Expected {num_fields:d} arguments, got %d' % len(result))

return result

def _replace(_self, **kwds):

'Return a new {typename} object replacing specified fields with new values'

result = _self._make(map(kwds.pop, {field_names!r}, _self))

if kwds:

raise ValueError('Got unexpected field names: %r' % list(kwds))

return result

def __repr__(self):

'Return a nicely formatted representation string'

return self.__class__.__name__ + '({repr_fmt})' % self

def _asdict(self):

'Return a new OrderedDict which maps field names to their values.'

return OrderedDict(zip(self._fields, self))

def __getnewargs__(self):

'Return self as a plain tuple. Used by copy and pickle.'

return tuple(self)

{field_defs}

"""

_repr_template = '{name}=%r'

_field_template = '''\

{name} = _property(_itemgetter({index:d}), doc='Alias for field number {index:d}')

'''

def namedtuple(typename, field_names, verbose=False, rename=False):

"""Returns a new subclass of tuple with named fields.

>>> Point = namedtuple('Point', ['x', 'y'])

>>> Point.__doc__ # docstring for the new class

'Point(x, y)'

>>> p = Point(11, y=22) # instantiate with positional args or keywords

>>> p[0] + p[1] # indexable like a plain tuple

>>> x, y = p # unpack like a regular tuple

>>> x, y

(11, 22)

>>> p.x + p.y # fields also accessible by name

>>> d = p._asdict() # convert to a dictionary

>>> d['x']

>>> Point(**d) # convert from a dictionary

Point(x=11, y=22)

>>> p._replace(x=100) # _replace() is like str.replace() but targets named fields

Point(x=100, y=22)

"""

# Validate the field names. At the user's option, either generate an error

# message or automatically replace the field name with a valid name.

if isinstance(field_names, str):

field_names = field_names.replace(',', ' ').split()

field_names = list(map(str, field_names))

typename = str(typename)

if rename:

seen = set()

for index, name in enumerate(field_names):

if (not name.isidentifier()

or _iskeyword(name)

or name.startswith('_')

or name in seen):

field_names[index] = '_%d' % index

seen.add(name)

for name in [typename] + field_names:

if type(name) != str:

raise TypeError('Type names and field names must be strings')

if not name.isidentifier():

raise ValueError('Type names and field names must be valid '

'identifiers: %r' % name)

if _iskeyword(name):

raise ValueError('Type names and field names cannot be a '

'keyword: %r' % name)

seen = set()

for name in field_names:

if name.startswith('_') and not rename:

raise ValueError('Field names cannot start with an underscore: '

'%r' % name)

if name in seen:

raise ValueError('Encountered duplicate field name: %r' % name)

seen.add(name)

# Fill-in the class template

class_definition = _class_template.format(

typename = typename,

field_names = tuple(field_names),

num_fields = len(field_names),

arg_list = repr(tuple(field_names)).replace("'", "")[1:-1],

repr_fmt = ', '.join(_repr_template.format(name=name)

for name in field_names),

field_defs = '\n'.join(_field_template.format(index=index, name=name)

for index, name in enumerate(field_names))

)

# Execute the template string in a temporary namespace and support

# tracing utilities by setting a value for frame.f_globals['__name__']

namespace = dict(__name__='namedtuple_%s' % typename)

exec(class_definition, namespace)

result = namespace[typename]

result._source = class_definition

if verbose:

print(result._source)

# For pickling to work, the __module__ variable needs to be set to the frame

# where the named tuple is created. Bypass this step in environments where

# sys._getframe is not defined (Jython for example) or sys._getframe is not

# defined for arguments greater than 0 (IronPython).

try:

result.__module__ = _sys._getframe(1).f_globals.get('__name__', '__main__')

except (AttributeError, ValueError):

pass

return result

########################################################################

### Counter

########################################################################

def _count_elements(mapping, iterable):

'Tally elements from the iterable.'

mapping_get = mapping.get

for elem in iterable:

mapping[elem] = mapping_get(elem, 0) + 1

try: # Load C helper function if available

from _collections import _count_elements

except ImportError:

pass

class Counter(dict):

'''Dict subclass for counting hashable items. Sometimes called a bag

or multiset. Elements are stored as dictionary keys and their counts

are stored as dictionary values.

>>> c = Counter('abcdeabcdabcaba') # count elements from a string

>>> c.most_common(3) # three most common elements

[('a', 5), ('b', 4), ('c', 3)]

>>> sorted(c) # list all unique elements

['a', 'b', 'c', 'd', 'e']

>>> ''.join(sorted(c.elements())) # list elements with repetitions

'aaaaabbbbcccdde'

>>> sum(c.values()) # total of all counts

>>> c['a'] # count of letter 'a'

>>> for elem in 'shazam': # update counts from an iterable

... c[elem] += 1 # by adding 1 to each element's count

>>> c['a'] # now there are seven 'a'

>>> del c['b'] # remove all 'b'

>>> c['b'] # now there are zero 'b'

>>> d = Counter('simsalabim') # make another counter

>>> c.update(d) # add in the second counter

>>> c['a'] # now there are nine 'a'

>>> c.clear() # empty the counter

>>> c

Counter()

Note: If a count is set to zero or reduced to zero, it will remain

in the counter until the entry is deleted or the counter is cleared:

>>> c = Counter('aaabbc')

>>> c['b'] -= 2 # reduce the count of 'b' by two

>>> c.most_common() # 'b' is still in, but its count is zero

[('a', 3), ('c', 1), ('b', 0)]

'''

# References:

# http://en.wikipedia.org/wiki/Multiset

# http://www.gnu.org/software/smalltalk/manual-base/html_node/Bag.html

# http://www.demo2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm

# http://code.activestate.com/recipes/259174/

# Knuth, TAOCP Vol. II section 4.6.3

def __init__(*args, **kwds):

'''Create a new, empty Counter object. And if given, count elements

from an input iterable. Or, initialize the count from another mapping

of elements to their counts.

>>> c = Counter() # a new, empty counter

>>> c = Counter('gallahad') # a new counter from an iterable

>>> c = Counter({'a': 4, 'b': 2}) # a new counter from a mapping

>>> c = Counter(a=4, b=2) # a new counter from keyword args

'''

if not args:

raise TypeError("descriptor '__init__' of 'Counter' object "

"needs an argument")

self, *args = args

if len(args) > 1:

raise TypeError('expected at most 1 arguments, got %d' % len(args))

super(Counter, self).__init__()

self.update(*args, **kwds)

def __missing__(self, key):

'The count of elements not in the Counter is zero.'

# Needed so that self[missing_item] does not raise KeyError

return 0

def most_common(self, n=None):

'''List the n most common elements and their counts from the most

common to the least. If n is None, then list all element counts.

>>> Counter('abcdeabcdabcaba').most_common(3)

[('a', 5), ('b', 4), ('c', 3)]

'''

# Emulate Bag.sortedByCount from Smalltalk

if n is None:

return sorted(self.items(), key=_itemgetter(1), reverse=True)

return _heapq.nlargest(n, self.items(), key=_itemgetter(1))

def elements(self):

'''Iterator over elements repeating each as many times as its count.

>>> c = Counter('ABCABC')

>>> sorted(c.elements())

['A', 'A', 'B', 'B', 'C', 'C']

# Knuth's example for prime factors of 1836: 2**2 * 3**3 * 17**1

>>> prime_factors = Counter({2: 2, 3: 3, 17: 1})

>>> product = 1

>>> for factor in prime_factors.elements(): # loop over factors

... product *= factor # and multiply them

>>> product

1836

Note, if an element's count has been set to zero or is a negative

number, elements() will ignore it.

'''

# Emulate Bag.do from Smalltalk and Multiset.begin from C++.

return _chain.from_iterable(_starmap(_repeat, self.items()))

# Override dict methods where necessary

@classmethod

def fromkeys(cls, iterable, v=None):

# There is no equivalent method for counters because setting v=1

# means that no element can have a count greater than one.

raise NotImplementedError(

'Counter.fromkeys() is undefined. Use Counter(iterable) instead.')

def update(*args, **kwds):

'''Like dict.update() but add counts instead of replacing them.

Source can be an iterable, a dictionary, or another Counter instance.

>>> c = Counter('which')

>>> c.update('witch') # add elements from another iterable

>>> d = Counter('watch')

>>> c.update(d) # add elements from another counter

>>> c['h'] # four 'h' in which, witch, and watch

'''

# The regular dict.update() operation makes no sense here because the

# replace behavior results in the some of original untouched counts

# being mixed-in with all of the other counts for a mismash that

# doesn't have a straight-forward interpretation in most counting

# contexts. Instead, we implement straight-addition. Both the inputs

# and outputs are allowed to contain zero and negative counts.

if not args:

raise TypeError("descriptor 'update' of 'Counter' object "

"needs an argument")

self, *args = args

if len(args) > 1:

raise TypeError('expected at most 1 arguments, got %d' % len(args))

iterable = args[0] if args else None

if iterable is not None:

if isinstance(iterable, Mapping):

if self:

self_get = self.get

for elem, count in iterable.items():

self[elem] = count + self_get(elem, 0)

else:

super(Counter, self).update(iterable) # fast path when counter is empty

else:

_count_elements(self, iterable)

if kwds:

self.update(kwds)

def subtract(*args, **kwds):

'''Like dict.update() but subtracts counts instead of replacing them.

Counts can be reduced below zero. Both the inputs and outputs are

allowed to contain zero and negative counts.

Source can be an iterable, a dictionary, or another Counter instance.

>>> c = Counter('which')

>>> c.subtract('witch') # subtract elements from another iterable

>>> c.subtract(Counter('watch')) # subtract elements from another counter

>>> c['h'] # 2 in which, minus 1 in witch, minus 1 in watch

>>> c['w'] # 1 in which, minus 1 in witch, minus 1 in watch

-1

'''

if not args:

raise TypeError("descriptor 'subtract' of 'Counter' object "

"needs an argument")

self, *args = args

if len(args) > 1:

raise TypeError('expected at most 1 arguments, got %d' % len(args))

iterable = args[0] if args else None

if iterable is not None:

self_get = self.get

if isinstance(iterable, Mapping):

for elem, count in iterable.items():

self[elem] = self_get(elem, 0) - count

else:

for elem in iterable:

self[elem] = self_get(elem, 0) - 1

if kwds:

self.subtract(kwds)

def copy(self):

'Return a shallow copy.'

return self.__class__(self)

def __reduce__(self):

return self.__class__, (dict(self),)

def __delitem__(self, elem):

'Like dict.__delitem__() but does not raise KeyError for missing values.'

if elem in self:

super().__delitem__(elem)

def __repr__(self):

if not self:

return '%s()' % self.__class__.__name__

try:

items = ', '.join(map('%r: %r'.__mod__, self.most_common()))

return '%s({%s})' % (self.__class__.__name__, items)

except TypeError:

# handle case where values are not orderable

return '{0}({1!r})'.format(self.__class__.__name__, dict(self))

# Multiset-style mathematical operations discussed in:

# Knuth TAOCP Volume II section 4.6.3 exercise 19

# and at http://en.wikipedia.org/wiki/Multiset

# Outputs guaranteed to only include positive counts.

# To strip negative and zero counts, add-in an empty counter:

# c += Counter()

def __add__(self, other):

'''Add counts from two counters.

>>> Counter('abbb') + Counter('bcc')

Counter({'b': 4, 'c': 2, 'a': 1})

'''

if not isinstance(other, Counter):

return NotImplemented

result = Counter()

for elem, count in self.items():

newcount = count + other[elem]

if newcount > 0:

result[elem] = newcount

for elem, count in other.items():

if elem not in self and count > 0:

result[elem] = count

return result

def __sub__(self, other):

''' Subtract count, but keep only results with positive counts.

>>> Counter('abbbc') - Counter('bccd')

Counter({'b': 2, 'a': 1})

'''

if not isinstance(other, Counter):

return NotImplemented

result = Counter()

for elem, count in self.items():

newcount = count - other[elem]

if newcount > 0:

result[elem] = newcount

for elem, count in other.items():

if elem not in self and count < 0:

result[elem] = 0 - count

return result

def __or__(self, other):

'''Union is the maximum of value in either of the input counters.

>>> Counter('abbb') | Counter('bcc')

Counter({'b': 3, 'c': 2, 'a': 1})

'''

if not isinstance(other, Counter):

return NotImplemented

result = Counter()

for elem, count in self.items():

other_count = other[elem]

newcount = other_count if count < other_count else count

if newcount > 0:

result[elem] = newcount

for elem, count in other.items():

if elem not in self and count > 0:

result[elem] = count

return result

def __and__(self, other):

''' Intersection is the minimum of corresponding counts.

>>> Counter('abbb') & Counter('bcc')

Counter({'b': 1})

'''

if not isinstance(other, Counter):

return NotImplemented

result = Counter()

for elem, count in self.items():

other_count = other[elem]

newcount = count if count < other_count else other_count

if newcount > 0:

result[elem] = newcount

return result

def __pos__(self):

'Adds an empty counter, effectively stripping negative and zero counts'

result = Counter()

for elem, count in self.items():

if count > 0:

result[elem] = count

return result

def __neg__(self):

'''Subtracts from an empty counter. Strips positive and zero counts,

and flips the sign on negative counts.

'''

result = Counter()

for elem, count in self.items():

if count < 0:

result[elem] = 0 - count

return result

def _keep_positive(self):

'''Internal method to strip elements with a negative or zero count'''

nonpositive = [elem for elem, count in self.items() if not count > 0]

for elem in nonpositive:

del self[elem]

return self

def __iadd__(self, other):

'''Inplace add from another counter, keeping only positive counts.

>>> c = Counter('abbb')

>>> c += Counter('bcc')

>>> c

Counter({'b': 4, 'c': 2, 'a': 1})

'''

for elem, count in other.items():

self[elem] += count

return self._keep_positive()

def __isub__(self, other):

'''Inplace subtract counter, but keep only results with positive counts.

>>> c = Counter('abbbc')

>>> c -= Counter('bccd')

>>> c

Counter({'b': 2, 'a': 1})

'''

for elem, count in other.items():

self[elem] -= count

return self._keep_positive()

def __ior__(self, other):

'''Inplace union is the maximum of value from either counter.

>>> c = Counter('abbb')

>>> c |= Counter('bcc')

>>> c

Counter({'b': 3, 'c': 2, 'a': 1})

'''

for elem, other_count in other.items():

count = self[elem]

if other_count > count:

self[elem] = other_count

return self._keep_positive()

def __iand__(self, other):

'''Inplace intersection is the minimum of corresponding counts.

>>> c = Counter('abbb')

>>> c &= Counter('bcc')

>>> c

Counter({'b': 1})

'''

for elem, count in self.items():

other_count = other[elem]

if other_count < count:

self[elem] = other_count

return self._keep_positive()

########################################################################

### ChainMap (helper for configparser and string.Template)

########################################################################

class ChainMap(MutableMapping):

''' A ChainMap groups multiple dicts (or other mappings) together

to create a single, updateable view.

The underlying mappings are stored in a list. That list is public and can

be accessed or updated using the *maps* attribute. There is no other

state.

Lookups search the underlying mappings successively until a key is found.

In contrast, writes, updates, and deletions only operate on the first

mapping.

'''

def __init__(self, *maps):

'''Initialize a ChainMap by setting *maps* to the given mappings.

If no mappings are provided, a single empty dictionary is used.

'''

self.maps = list(maps) or [{}] # always at least one map

def __missing__(self, key):

raise KeyError(key)

def __getitem__(self, key):

for mapping in self.maps:

try:

return mapping[key] # can't use 'key in mapping' with defaultdict

except KeyError:

pass

return self.__missing__(key) # support subclasses that define __missing__

def get(self, key, default=None):

return self[key] if key in self else default

def __len__(self):

return len(set().union(*self.maps)) # reuses stored hash values if possible

def __iter__(self):

return iter(set().union(*self.maps))

def __contains__(self, key):

return any(key in m for m in self.maps)

def __bool__(self):

return any(self.maps)

@_recursive_repr()

def __repr__(self):

return '{0.__class__.__name__}({1})'.format(

self, ', '.join(map(repr, self.maps)))

@classmethod

def fromkeys(cls, iterable, *args):

'Create a ChainMap with a single dict created from the iterable.'

return cls(dict.fromkeys(iterable, *args))

def copy(self):

'New ChainMap or subclass with a new copy of maps[0] and refs to maps[1:]'

return self.__class__(self.maps[0].copy(), *self.maps[1:])

__copy__ = copy

def new_child(self, m=None): # like Django's Context.push()

'''New ChainMap with a new map followed by all previous maps.

If no map is provided, an empty dict is used.

'''

if m is None:

m = {}

return self.__class__(m, *self.maps)

@property

def parents(self): # like Django's Context.pop()

'New ChainMap from maps[1:].'

return self.__class__(*self.maps[1:])

def __setitem__(self, key, value):

self.maps[0][key] = value

def __delitem__(self, key):

try:

del self.maps[0][key]

except KeyError:

raise KeyError('Key not found in the first mapping: {!r}'.format(key))

def popitem(self):

'Remove and return an item pair from maps[0]. Raise KeyError is maps[0] is empty.'

try:

return self.maps[0].popitem()

except KeyError:

raise KeyError('No keys found in the first mapping.')

def pop(self, key, *args):

'Remove *key* from maps[0] and return its value. Raise KeyError if *key* not in maps[0].'

try:

return self.maps[0].pop(key, *args)

except KeyError:

raise KeyError('Key not found in the first mapping: {!r}'.format(key))

def clear(self):

'Clear maps[0], leaving maps[1:] intact.'

self.maps[0].clear()

################################################################################

### UserDict

################################################################################

class UserDict(MutableMapping):

# Start by filling-out the abstract methods

def __init__(*args, **kwargs):

if not args:

raise TypeError("descriptor '__init__' of 'UserDict' object "

"needs an argument")

self, *args = args

if len(args) > 1:

raise TypeError('expected at most 1 arguments, got %d' % len(args))

if args:

dict = args[0]

elif 'dict' in kwargs:

dict = kwargs.pop('dict')

import warnings

warnings.warn("Passing 'dict' as keyword argument is deprecated",

PendingDeprecationWarning, stacklevel=2)

else:

dict = None

self.data = {}

if dict is not None:

self.update(dict)

if len(kwargs):

self.update(kwargs)

def __len__(self): return len(self.data)

def __getitem__(self, key):

if key in self.data:

return self.data[key]

if hasattr(self.__class__, "__missing__"):

return self.__class__.__missing__(self, key)

raise KeyError(key)

def __setitem__(self, key, item): self.data[key] = item

def __delitem__(self, key): del self.data[key]

def __iter__(self):

return iter(self.data)

# Modify __contains__ to work correctly when __missing__ is present

def __contains__(self, key):

return key in self.data

# Now, add the methods in dicts but not in MutableMapping

def __repr__(self): return repr(self.data)

View remainder of file in raw view

cpython/Lib/collections/init.py at 3.5 · python/cpython · GitHub

Repository navigation

init.py

init.py

cpython/Lib/collections/__init__.py at 3.5 · python/cpython · GitHub

Repository navigation

Expand file tree

Breadcrumbs

__init__.py

Latest commit

History

Breadcrumbs

__init__.py

File metadata and controls

cpython/Lib/collections/init.py at 3.5 · python/cpython · GitHub

init.py

init.py