Metadata-Version: 2.4
Name: triordinal-dlist
Version: 2.0.0
Summary: DList (part of Triordinal): doubly linked list with rational positions and an O(1) precedence test, shared by triordinal-dtree and triordinal-dgraph
Author-email: Enis Olgac <enis@digraphs.info>
License: MIT
Project-URL: Homepage, https://github.com/EnisOlgac/Triordinal
Project-URL: Changelog, https://github.com/EnisOlgac/Triordinal/blob/main/CHANGELOG.md
Keywords: order maintenance,linked list,rational positions,precedence,data structure
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Science/Research
Classifier: Intended Audience :: Developers
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Requires-Python: >=3.9
Description-Content-Type: text/markdown

# DList for Python (triordinal-dlist)

The list shared by [Triordinal](https://github.com/EnisOlgac/Triordinal)'s DTree and DGraph: a doubly linked list of names with rational positions, so that "does a come before b?" is a single comparison, O(1).

```
pip install triordinal-dlist
```

```python
from triordinal.dlist import DList

q = DList("Q")
q.insert_after("a", "[")      # "[" is the start marker (SOURCE)
q.insert_after("b", "a")
q.precedes("a", "b")          # True
```

A new element gets the mediant (a+c)/(b+d) of its neighbors a/b and c/d, so normally no other element moves. Only when a denominator would exceed 64 bits is the smallest surrounding region with enough room renumbered; larger regions must be sparser before they are accepted (as in Bender et al., ESA 2002). Rational positions were Enis Olgac's idea.

Most users install `triordinal-dtree` (or later `triordinal-dgraph`), which pulls this package in. MIT License.
