| Changelog for teds |
| Release |
What has changed? |
| 1.3.0 |
* Optimize Teds\Deque insert() and offsetUnset() calls with offsets when they're closer
to the front of the deque than the end of the Deque.
* Add Teds\strict_equals($v1, $v2): bool with stricter NAN handling than `===`.
* Regenerate function arginfo with namespaced C symbols from stub.php files. |
| 1.2.8 |
* Same as 1.2.7 other than the version and tests folder.
* Update expected test output of the unit test tests/misc/strict_hash_array_recursion_32bit.phpt |
| 1.2.7 |
* Fix an edge case in Teds\strict_hash for arrays with reference cycles.
'$x === $y' should now always imply that Teds\strict_hash($x) === Teds\strict_hash($y) |
| 1.2.6 |
* Fix a build warning in clang for placeholders indicating that a data structure was constructed/unserialized.
* Fix a build warning after change to expected return type of `count_elements` object handler implementation. |
| 1.2.5 |
* Reduce memory usage by refactoring the way properties/fields of data structures are returned, for var_export/var_dump/debug_zval_dump/array type casts/serialize.
In php 8.3+, this should reduce the impact of calling var_export/var_dump/debug_zval_dump on memory usage, and avoid the side effect of keeping around references to fields after those calls..
In all php versions, consistently return temporary arrays for remaining data structures in serialize() and array type casts that will be freed after being used. |
| 1.2.4 |
* Fix test failures/deprecation notices seen in PHP 8.2. |
| 1.2.3 |
* Make pop() on Sequences affect iterators the same way that `$o->offsetUnset(count($o) - 1)` would.
(Move iterators pointing to the removed entry backwards by 1)
* Make pop() on MutableIterable move iterators pointing to that entry backwards.
* Properly convert references to non-references in some Collection constructors/unserializers and `Teds\unique_values()` |
| 1.2.2 |
* Fix bugs in Teds\StrictHashSet/Teds\StrictHashMap iteration behavior.
* Fix bug constructing balanced tree in Teds\StrictTreeSet/Teds\StrictTreeMap from array/unserializing, where certain sizes resulted in trees not maintaining the balancing invariant.
* Fix bug when constructing Teds\IntVector from array when promoting type but not keeping reserved capacity.
* Fix bugs in Teds\StrictSortedVectorSet::__construct |
| 1.2.1 |
* Update documentation
* Make iteration of Teds\StrictSortedVectorSet and Teds\StrictSortedVectorMap account for removals and additions.
* Make removal in Teds\StrictTreeSet and Teds\StrictTreeMap move iterators to the previous node if the iterator pointed to the removed node.
Add a state for iterators being prior to the start of the tree.
Use the state of being before the first value of the tree when calling InternalIterator::rewind on an empty tree or removing an iterator pointing to the first value in a tree.
* Make repacking/removals in Teds\StrictHashSet and Teds\StrictHashMap move InternalIterator positions.
* Change iteration behavior of Teds\Deque to be like Vector, make shift/pop behave the same way as offsetUnset with respect to iteration.
(If the iterator is moved to be before the start of the deque, calling next will move it to the front, and other changes to the Deque will have no effect) |
| 1.2.0 |
* Add `Teds\SortedIntVectorSet` - a Set implementation represented in a way similar to an `Teds\IntVector` with unique sorted integers.
(This may be useful for reducing memory usage and speeding up unserialization, when unserializing large Sets of integers which change infrequently. See benchmarks/benchmark_vector_unserialize.php)
* Add `Teds\ImmutableSortedStringSet` - an immutable Set implementation containing a list of unique strings sorted with strcmp.
(This may be useful for reducing memory usage and speeding up unserialization, when unserializing large Sets of strings which change infrequently to check values for membership in a Set. See benchmarks/benchmark_string_set.php)
* Add `Teds\ImmutableSortedIntSet` - an immutable Set implementation containing a list of unique integers sorted by increasing value.
(This may be useful for reducing memory usage and speeding up unserialization, when unserializing large Sets of integers which change infrequently to check values for membership in a Set.)
* Rename `Teds\BitSet` to `Teds\BitVector`
* Add `Teds\Sequence::insert(int $offset, mixed ...$values)` to the Sequence interfaces and implementations
* Add first/last to the `Teds\Sequence` interface.
* Fix edge cases with var_export/var_dump/debug_zval_dump and cyclic data structures in debug builds and php 8.2.0-dev.
* Make iteration account for offsetUnset/insert/shift/unshift in Sequences. |
| 1.1.2 |
* Fix big-endian builds (#160)
* Make `teds\stable_compare` consistently 1/0/-1 for arrays with different keys on all platforms. |
| 1.1.1 |
* Fix bugs in Teds\Map array access shorthand. |
| 1.1.0 |
* Fix ImmutableSequence throwing for ArrayAccess shorthand read syntax.
* Add CachedIterable as an alternative to ImmutableIterable that lazily evaluates Traversable objects passed into the constructor. (e.g. only runs Generators up to the most recently requested offset)
* Change exception type to `Teds\UnsupportedOperationException` in a few places.
* Add `Teds\is_same_array_handle(array $array1, array $array2): bool` for infinite recursion detection when processing arrays.
* Fix memory leak when initializing `Teds\StrictMinHeap`/`Teds\StrictMaxHeap` from Traversables.
* Fix memory leak when constructing collections from Traversable where rewind throws
* Use first/last as method names for getting the first and last method names. Keep bottom/top as aliases to be deprecated later.
* Add first/last helper methods to more collection types
* Optimize implementations of `$map[$x]` array access shorthand in `Teds\Map` implementations.
* Throw for `$map[] = $value` instead of setting the key for null in `Teds\Map` implementations.
* Fix Teds\IntVector and Teds\LowMemoryVector shift implementation for integers
* Add more methods to Teds\BitSet to read/write bytes/integers, convert to/from strings. |
| 1.0.1 |
* Regenerate arginfo for method aliases, update test expectations |
| 1.0.0 |
* BREAKING CHANGES: Fix incorrect serialization/unserialization result of LowMemoryVector for boolean/null. Incompatible with older releases.
* BUGFIX: Fix converting LowMemoryVector of floats to an array (they were unintentionally converted to integers).
* BREAKING CHANGES: Rename datastructures and interfaces for consistency. Change definitions of interfaces/remove interfaces.
Rename Teds\ImmutableKeyValueSequence to Teds\ImmutableIterable and add an alias for the old name. Aliases will be removed in a future release.
Rename Teds\KeyValueSequence to Teds\MutableIterable and add an alias.
Rename Teds\SortedStrictMap to Teds\StrictTreeMap and add an alias.
Rename Teds\StrictMap to Teds\StrictHashMap and add an alias.
Rename Teds\SortedStrictSet to Teds\StrictTreeSet and add an alias.
Rename Teds\StrictSet to Teds\StrictHashSet and add an alias.
Rename Teds\StableMinHeap to Teds\StrictMinHeap and add an alias.
Rename Teds\StableMaxHeap to Teds\StrictMaxHeap and add an alias.
Change the definition of Teds\Collection to be just a Collection of **values**. Make Teds\Values an alias of Teds\Collection.
Add the interfaces `Teds\Sequence`, `Teds\Map`, `Teds\Set`. |
| 0.14.0 |
* Make `strict_hash` deterministic for `NAN`
* Make `strict_hash` return the same value for signed positive and negative zero. (In php, `0.0 === -0.0`, though var_export/print/var_dump output differ.)
* Fix StrictMap/StrictSet handling of NAN. Make StrictMap/StrictSet treat positive and negative zero floats as the same key, like SortedStrictSet/stable_compare.
* Add bitset source files to package.xml |
| 0.13.0 |
* Add Teds\BitSet providing similar functionality to a Vector of booleans, using a single bit per boolean.
* Fix stub documentation and qualify `\Iterator` for StableMinHeap/StableMaxHeap in documentation. |
| 0.12.0 |
* Breaking changes.
* Fix serialization/unserialization in StableMinHeap/StableMaxHeap.
* Add interfaces for `Teds\Values` (e.g. Heap/Set), Teds\Collection(e.g. StrictMap, StableSortedMap), ListInterface(Vector, Deque, etc.) (the keyword list is reserved)
* Implement ->values() in classes implementing `Teds\Values`.
* Make offsetExists consistently return false when the value of the given key is null across all data structures.
* Add Teds\Collection->containsKey to return true if a key exists without coercing types, and returning true regardless of whether the corresponding key is null.
* Change signature of IntVector::set() and ::push() to match ListInterface
* Add Collection::toArray() (behaves like iterator_to_array).
* Check for exceeding 64-bit capacity limits in more collections to avoid hitting gc size limits
and to avoid unpredictable behavior (e.g. it'd be surprising to have this throw/fatal error only if var_export/var_dump/json_encode was called and PHP's array size limits(2147483648 elements, or at least 32GB) were hit). |
| 0.11.0 |
* Breaking change: Make StableMinHeap/StableMaxHeap stop inheriting from SplHeap to be more memory efficient.
* Properly sort in StableSortedListSet::__construct and __set_state
* Deduplicate code.
* Reduce size/capacity limits to the same limits as array for Deque.
* Add ImmutableSequence::map(), filter()
* Fix bug in Deque::contains(), Deque::indexOf() |
| 0.10.0 |
* Speed up unserializing SortedStrictSet/SortedStrictMap when the input data is already sorted. (If the data is not sorted, then build the binary tree the slow but correct way)
* Add a LowMemoryVector type and IntVector type, supporting reduced memory usage.
* Deduplicate code.
* Fix garbage collection in some classes. |
| 0.9.2 |
* Make SortedStrictSet/SortedStrictMap use a red-black tree that is rebalanced on insertions and removals, guaranteeing worst-case logarithmic time for insertions/removals/lookups. |
| 0.9.1 |
* Make SortedStrictSet/SortedStrictMap use a binary search tree (not yet a balanced tree).
* Associate iterators on SortedStrictSet/SortedStrictMap with nodes of the tree.
Invalidate iterators pointing to a node when that node of the set/map is removed.
* Fix sorting order when instantiating StableSortedListSet/SortedStrictSet/SortedStrictMap from unsorted arrays. |
| 0.9.0 |
* Migrate `Teds\StrictSet`, `Teds\StrictMap`, and `Teds\unique_values` implementation to use an actual hash table instead of a list of unique values. |
| 0.8.0 |
* Add `StableSortedListSet` and `StableSortedListMap` as memory-efficient alternatives to `SortedStrictSet`/`SortedStrictMap`.
* Speed up `SortedStrictSet::__unserialize` and `SortedStrictMap::__unserialize` when data is already sorted.
* Fix crash in `StrictSet` and `SortedStrictSet` during cyclic garbage collection. |
| 0.7.0 |
* Make `Teds\strict_hash` ignore recursion caused by unrelated functions (e.g. var_dump calling `__debugInfo` calling `strict_hash`)
* Add `Teds\binary_search(array $values, mixed $target, callable $comparer = null, bool $useKey=false)`
* Change parent class of `Teds\StableMaxHeap` and `Teds\StableMinHeap` to `SplHeap`.
* Fix deduplication when constructing `StrictSet` from `iterable`, `StrictMap` from `Traversable`.
* Add `Teds\unique_values(iterable): array` using `strict_hash` to check for duplicates. |
| 0.6.0 |
* Make `Teds\stable_compare` sort objects by class name with strcmp before sorting by spl_object_id.
* Add a hash map `StrictMap` using `Teds\stable_hash` as a hash algorithm.
Keys are returned in order of insertion.
* Add a hash set `StrictSet` using `Teds\stable_hash` as a hash algorithm.
* Add a sorted map `SortedStrictMap` using `Teds\stable_compare` as a comparison function.
Keys are returned ordered by `Teds\stable_compare` and no two keys have `stable_compare` return 0 (i.e. no two keys are equivalent).
* Add a sorted set `SortedStrictSet` using `Teds\stable_compare` as a comparison function.
* Add StableMinHeap/StableMaxHeap extending SplMinHeap/SplMaxHeap, using `Teds\stable_compare` as a comparison function. |
| 0.5.1 |
* Add Teds\array_value_first(), Teds\array_value_last()
* Add `Teds\stable_compare($v1, $v2): int` for a stable comparison function of arbitrary values. (see tests/misc/stable_compare.phpt).
Like strcmp, this returns a negative value for less than, and positive for greater than, and 0 for equality.
Note that php's `<` operator is not stable. `'10' < '0a' < '1b' < '9' < '10'`.
stable_compare fixes that by strictly ordering:
`null < false < true < int,float < string < array < object < resource`.
(objects and resources are compared by id, and arrays are compared recursively. Numbers are compared numerically. If an int is equal to a float, then the int is first)
(strings use strcmp)
* Make Deque iteration account for calls to shift/unshift tracking the position of the front of the Deque.
Calls to shift/unshift will do the following:
- Increase/Decrease the value returned by the iterator's key() by the number of elements added/removed to/from the front of the Deque. (`$deque[$iteratorKey] === $iteratorValue` at the time the key and value are returned).
- Repeated calls to shift will cause valid() to return false if the iterator's position ends up before the start of the Deque at the time iteration resumes.
- They will not cause the remaining values to be iterated over more than once or skipped. |
| 0.4.1 |
* Fix computation of next power of 2 for sizes of `2 ** 32` or larger. |
| 0.4.0 |
* Backwards incompatible change: Change `Deque` APIs to be consistent with SplDoublyLinkedList and `array_push`: change pushBack/popBack/pushFront/popFront to push/pop/unshift/shift
* Backwards incompatible change: Remove `$preserve_keys` flag from `Vector::__construct` (Always reindex keys in order of iteration instead).
* Add isEmpty() method to datastructures
* Make exceeding the capacity limit for a vector a fatal error.
* Make Deque::push() and unshift() variadic. |
| 0.3.0 |
* Backwards incompatible change: Change `Vector::indexOf` return type from `int|false` to `?int` (and all other `indexOf*` methods in other data structures)
* Backwards incompatible change: Change `valueAt`/`setValueAt` to get/set in Deque, Vector, and ImmutableSequence
* Add optional parameter `$value = null` to `Vector::setSize()` to allow overriding the value used for padding when lengthening an array.
* Change exception handling for sizes/capacities that are definitely too large to allocate.
* Make Vector::push() variadic and accept 0 or more arguments, like `array_push` does.
* Reclaim unused memory in Deque when roughly a quarter or less of the internal buffer is used.
* Optimize performance of Deque, always use powers of 2 for the capacity of Deque to speed up reads/writes. |
| 0.2.1 |
* Support `$vector[] = $value` and `$deque[] = $value` assignments to append to Vector/Deque.
* Add map() and filter() functions to Vector. |
| 0.2.0 |
* Breaking change: Change `Teds\Vector::__construct` to add an additional parameter `bool $preserveKeys = true`,
and use the original keys of arrays/Traversables by default, throwing for non-integers and invalid integer offsets.
(Similar to the behavior of SplFixedArray::fromArray)
* Convert references to non-references when creating values from iterables.
* Minor performance improvements of `Teds\Vector` |
| 0.1.1 |
* Add Teds\KeyValueVector
* Fix edge cases in Teds\Vector setSize |
| 0.1.0a1 |
* Initial commit |
