Pike-devel November 2002

pike-devel@lists.lysator.liu.se

6 participants
56 discussions

Re: Proposal for new ADT interface
by Martin Stjernholm, Roxen IS ＠ Pike developers forum 03 Nov '02

03 Nov '02

> (when `== on the data elements are true?). Rather when a < b and a > b are both false. But that's right; even in ordered collections it would be wise to keep an integer position in the iterators as often as possible. / Martin Stjernholm, Roxen IS Previous text: >2002-11-03 15:55: >Subject: Re: Proposal for new ADT interface >-------------------------------------------------------------------- >> Well, that could require an element walk through in some cases, e.g. >> in the new multiset implementation, which would be more expensive. >> Anyway, if there is an order then "before" should always be the same >> as "less" so it doesn't matter much. > >Yes. Since the multiset order is known, it can very well cheat and >only do walking when needed (when `== on the data elements are true?). > >Giving an error when the iterators aren't comparable seems like a good >behaviour (iterators from different or edited multisets or mappings, >for instance), since doing < and > comparison on those are bound to be >a mistake. > >Any plans on a Heap, btw? > > > / Brevbäraren >

1 0

Re: Proposal for new ADT interface
by Martin Nilsson (Fake Build Master) ＠ Pike (-) developers forum 03 Nov '02

03 Nov '02

Plans to do what? Add an iterator to ADT.Heap? / Martin Nilsson (Fake Build Master) Previous text: >2002-11-03 15:55: >Subject: Re: Proposal for new ADT interface >-------------------------------------------------------------------- >> Well, that could require an element walk through in some cases, e.g. >> in the new multiset implementation, which would be more expensive. >> Anyway, if there is an order then "before" should always be the same >> as "less" so it doesn't matter much. > >Yes. Since the multiset order is known, it can very well cheat and >only do walking when needed (when `== on the data elements are true?). > >Giving an error when the iterators aren't comparable seems like a good >behaviour (iterators from different or edited multisets or mappings, >for instance), since doing < and > comparison on those are bound to be >a mistake. > >Any plans on a Heap, btw? > > > / Brevbäraren >

1 0

Re: Proposal for new ADT interface
by Martin Stjernholm, Roxen IS ＠ Pike developers forum 03 Nov '02

03 Nov '02

> Anyway, the iterator's `< shouldn't compare the data values, it should > compare the iterators - "before", not "less". Well, that could require an element walk through in some cases, e.g. in the new multiset implementation, which would be more expensive. Anyway, if there is an order then "before" should always be the same as "less" so it doesn't matter much. / Martin Stjernholm, Roxen IS Previous text: >2002-11-03 08:00: >Subject: Re: Proposal for new ADT interface >-------------------------------------------------------------------- >> Not really. If you have an unordered set you might get two iterators >> that iterates over all members in different order. > >Of course. But with for instance mappings, the iterator uses the same >order until the mapping is changed or indexed. (Then the operator can >give an error, just like when the operator is used on an iterator over >some other data.) > >Anyway, the iterator's `< shouldn't compare the data values, it should >compare the iterators - "before", not "less". > > > / Brevbäraren >

1 0

Re: Proposal for new ADT interface
by Martin Nilsson (Fake Build Master) ＠ Pike (-) developers forum 03 Nov '02

03 Nov '02

Not really. If you have an unordered set you might get two iterators that iterates over all members in different order. / Martin Nilsson (Fake Build Master) Previous text: >2002-11-02 22:56: >Subject: Re: Proposal for new ADT interface >-------------------------------------------------------------------- >> Ok. Good point. Come to think about it, iterators in ordered >> collections ought to have `< and `> too. > >Shouldn't all iterators? >An iterator is by definition doing something ordered, isn't it...? > > > / Brevbäraren >

4 6

Re: unix_time and UTC
by Johan Sundstr�m (�rkehertig av Lysators rootgrupp) ＠ Pike (-) developers forum 03 Nov '02

03 Nov '02

Noted. Thanks for the clarifications. / Johan Sundström (ärkehertig av Lysators rootgrupp) Previous text: >2002-11-03 08:03: >Subject: Re: unix_time and UTC >-------------------------------------------------------------------- >> Calendar->set_timezone() does not seem to apply to unix_time() at >> present. Is this intentional? The two operations below should IMO >> return the same number: > >unix_time() and time() returns the number of seconds since 1 Jan 1970 >0:00 UTC (when UTC was introduced and GMT was dropped, BTW). >That number doesn't change with timezones. > > > / Brevbäraren >

1 0

Re: Proposal for new ADT interface
by Martin Nilsson (Fake Build Master) ＠ Pike (-) developers forum 02 Nov '02

02 Nov '02

1 0

#X
by Johan Sundstr�m (�rkehertig av Lysators rootgrupp) ＠ Pike (-) developers forum 02 Nov '02

02 Nov '02

The extra space generated by this is a bug, I presume? #define FOO(X) #X #define BAR(Y) FOO(Y) int main() { write("%O\n", BAR(baz)); } (The output from the above is "baz " in 7.3, at least.)

3 8

unix_time and UTC
by Johan Sundstr�m (�rkehertig av Lysators rootgrupp) ＠ Pike (-) developers forum 02 Nov '02

02 Nov '02

Calendar->set_timezone() does not seem to apply to unix_time() at present. Is this intentional? The two operations below should IMO return the same number: Pike v7.3 release 58 running Hilfe v3.5 (Incremental Pike Frontend) > Calendar.TimeRange t = Calendar.Second(); > t->unix_time() + t->utc_offset(); (1) Result: 1036154266 > t->set_timezone("UTC")->unix_time(); (2) Result: 1036157866

1 4

unix_time and UTC
by Johan Sundstr�m (�rkehertig av Lysators rootgrupp) ＠ Pike (-) developers forum 02 Nov '02

02 Nov '02

1 0

Proposal for new ADT interface
by Peta, jo det �r jag ＠ Pike developers forum 02 Nov '02

02 Nov '02

I'm currently working on a thesis that should bring Pike some new ADTs. I'm currently working on a common interface for the new ADTs and this is a draft of how it might be. The goal of the interface is resemble as much as possible of the current types array, multiset and mapping. Another goal with the interface is to keep it as minimal as possible. No unnecessary methods. The reason is simple, lack of time. The time I've got on hand is far to little to do a trough out analysis of possible fields of application and methods in the ADTs. The solution is to keep the interface incomplete by sufficient to work with a few algorithms and let other add new methods when they develop new algorithms. The base of the interface is four different concepts, one base concept and three sub-concepts that inherit all the methods from the base concept. Collection |---- Sequence |---- Set |---- Map Additional sub-concepts to the sub-concepts could be added later, for example sorted set. If an ADT implements all the methods in a concept and its super concepts it is an implementation of the concept. Collection Collection is the base concept of all the ADTs. The reason it is called collection is that all the ADTs in the library is in some way a collection of items. iterator _get_iterator() Return an iterator for this ADT positioned at the first item in the ADT. int _sizeof() Return the current size of the ADT. array _values() Return an array with the values in the ADT. int is_empty() Return 0 if the ADT do has elements. int max_size() Return the maximal size of the ADT if there is any, otherwise -1. void clear() Clear the ADT. void add_all(collection col) Add all the items in the collection col to this collection. Sequence A sequence is a linear container that allows index-based access and automatically expands to accommodate new elements. A vector is a good example. void insert(int ind, mixed item) Insert an item in the sequence at the index ind. The size of the sequence is increased by one and the items at index and above have their indices increases by one. Throw an error if ind is out of range. int remove(mixed item) Remove the item item from the sequence. Return the number of removed items. int index_of(int ind, mixed item) Return the index of the first item in the sequence with the index ind or higher that mach the item item. -1 if no object was found. Throw an error if ind is out of range. void add(mixed item) Add the object item as fast as possible to the sequence. Int remove_at(int ind) Remove the item at the index ind. The size of the sequence is decreased by one and the items above ind have their indices decreases by one. Return 0 if the removal failed. Throw an error if ind is out of range. iterator get_iterator(int ind) Get an iterator for this ADT positioned at the index ind. Throw an error if ind is out of range. mixed '[](int ind) Return the item at index ind in the sequence. Throw an error if ind is out of range. Mixed '[]=(int ind, mixed item) Set the index ind to be item. Throw an error if ind is out of range Set Set is a collection containing any number of items but only one of each item. iterator get_iterator(mixed item) Get an iterator for this ADT positioned at the item or null if the item could not be found. int '[](set set, mixed item) Return 1 if the item could be found in the set, 0 if it couldn't int '[]=(mixed item, int exist) Add the item to the set if exist is true remove the item if exist is false. Map A map is a data structure that allows you to associate a key with one or more values and then quickly retrieve those values using the key. array _indices() Return an array with the indices in the map. iterator get_iterator(mixed key) Get an iterator for this ADT positioned at the key or null if the key could not be found. int remove(mixed key) Remove the pair with the key key. Return 0 if the key could not be removed. mixed '[](mixed key) Return the item associated with the key if it could be found, 0 if it couldn't mixed '[]=(mixed key, mixed item) If there is an item with the key key then the associated item will be overwritten with the supplied item. If there is no key in the map a new key-item pair will be added. Iterator changes I've also analysed the current iterators and how well they would work with generic algorithms and I found that it is only one thing that really lacks, the possibility to walk backwards. Actually the possibility to walk backwards is already there, it just doesn't have it's own method. iterator '-=(int n) Move the iterator n steps backwards int has_previous() Return true if the iterator can move one step backwards. int has_next() Return true if the iterator can move one step forwards. It have the same use as '! but since there is a has_previous I believe it should be a has_next to. int '==(iterator iter) Return true if the two iterators is pointing to the same object. Well this is briefly what I have in mind. If you have any questions or comments you're more then welcome.

4 11

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

Pike-devel November 2002