Linked-list Style Data Structure

[impossiblerobot]

Again, I humbly approach the monastery ...

In a wizard-style web application I've created, I use the following data structure to track navigation:

$navigation_map = {
    first_page       => {
        PREVIOUS => '',
        NEXT     => 'second_page',
    },
    second_page      => {
        PREVIOUS => 'first_page',
        NEXT     => 'third_page',
    },
     third_page         => {
        PREVIOUS => 'second_page',
        NEXT     => 'fourth_page',
    },
    fourth_page         => {
        PREVIOUS => 'third_page',
        NEXT     => '',
    },
};

which allows me to say $navigation_map->{second_page}{NEXT} to find out what the next screen should be.

Unfortunately, the same list of pages does not appear in each of the installations of this app, so constructing the navigation map and editing the links for each instance is a pain. What I should be able to do is use an array, so I can just do this:

$navigation_map = [qw(first_page second_page third_page fourth_page)];

So I created an object to build the hash structure for me (from an array):

package List::Navigator;

sub new
{
    my $class = shift;
    my ($list) = @_;

    my $data = {};
    my ($previous, $next);
    for my $item (@$list)
    {
        $data->{$item}{PREVIOUS} = $previous;
        $data->{$previous}{NEXT} = $item if defined $previous;
        $previous = $item;
    }
    bless $data, $class;
}

I could then use it as:

my $nav_list = [qw( first_page second_page third_page fourth_page )];

my $navigation_map = List::Navigator->new( $nav_list );

Of course the next natural step was creating accessors so that I could say $navigation_map->next('second_page') instead of $navigation_map->{second_page}{NEXT}. I also created a "current page" pointer so I could use the class as an iterator.

This solution seems to work well for my current usage, since I currently have no need to insert or delete entries (which would require building additional methods). However, my question (finally) is: What better (or alternate) ways would you suggest for implementing this functionality? Is there a generic solution I should be looking at?

Impossible Robot

[merlyn]

If the data were more structured, I'd look at marshalling it as XML, and using XML::XPath for queries and updates. This would let you find pages based on name to get the "next" or "previous" pages trivially, including doing inserts and rewriting the XML to your marshall file if you need. You could also find associated data by storing it deeper in the same node:

<pages>
  <page ident="first page" />
  <page ident="second page">
    <validation type="numeric"/>
  </page>
  <page ident="third page" />
</pages>

This would be a simple format to edit, and to process electronically.

-- Randal L. Schwartz, Perl hacker

[impossiblerobot]

Thanks, merlyn. Although it seems a little heavy for this particular application, it is a useful approach that I had not considered and might find a use for.


Impossible Robot

[Abigail-II]

You are asking about alternative ways to implement "this functionality", but what is your module actually offering as functionality? Is there more than just next/previous based on named indices? If not, I'd keep the entries in an array, and use a hash to map names to indices.

The only reason to use linked lists instead of arrays is performance for inserts and deletes. But you aren't inserting or deleting.

Abigail

[impossiblerobot]

Thanks, Abigail-II, for pointing out the vagueness in my question. The specific functionality that I am looking for at this point is essentially as you stated:

• The ability to define the data structure simply (preferably using an array or list).
• The ability to find out the name of the next or previous item based on the the current (or a named) item.

Although I currently do not need to insert or delete elements, I might need to in the future. However, since my lists will never be that long, and I would not do it that often, I could probably still use your suggestion (and rebuild the entire index when necessary) without any noticable performance issues.

In any case, it seems that you are advocating trying to use a data structure appropriate to the task, rather than relying on a generic structure that might be less suited. Am I understanding correctly?


Impossible Robot

[Abigail-II]

In any case, it seems that you are advocating trying to use a data structure appropriate to the task, rather than relying on a generic structure that might be less suited. Am I understanding correctly?

Yes, that's the Perl (and Unix) way. You have a large toolkit at your disposal, with lots of different tools. Different tools for different jobs. Use your toolkit. The saying "if all you have is a hammer, everything looks like a nail" is not at all appropriate for Perl.

Abigail

[Zaxo]

Linked lists have a gotcha in perl. If you implement them with references, you can easily create cycles which perl cannot destroy. That happens because each element's refcount is held up by its predecessor. That is easily handled with a DESTROY method which breaks the cycle by overwriting the reference to successor with other data.

In recent perl, it is possible to use weak references to avert the problem.

I like the idea of using Graph for the sort of thing you're doing.

After Compline,
Zaxo

[Juerd]

I'm not familiar with linked lists, and have never used them. They don't seem to be worth the trouble (normal Perl arrays work well enough). For wizardish web applications, I often just use numeric indexes (internally mapped to page names), or I store only the next page's name and let the browser handle the history.back(). Even iterating over an array each time would be more efficient than building a large data structure, I think.

Your list thingy would be quite a bit faster if you used arrays instead of hashes for saving the NEXT and PREVIOUS. You can use constants for array indexes to maintain readability.

- Yes, I reinvent wheels.
- Spam: Visit eurotraQ.

[impossiblerobot]

Thanks, Juerd.

Unfortunately, the application I am working with already requires knowing both the 'next' and 'previous' views, and I don't have time to completely restructure it at this time.

Since this navigation list will be fairly short, and it will only be accessed a few times in each invocation of the script, efficiency probably won't be as much of an issue. However...

Modifying my code to use arrays (with constants) was trivial, and it is much faster than using a hash (which will be useful if I need to use this code with longer lists or access it more often). However, iterating over the array each time (even with exiting on a successful match) was slower than building the data structure when accessing it a couple of times.


Impossible Robot

[BUU]

(cheating horribly, since your using the First page, second page etc)

my @pages=(page1=>page2=>page3=>page4=>);
my $i=get_current_page();
my $next_page=$pages[$i+1];
my $prev_page=$page[$i-1];

Or somethign like that? Or am i totally missing something

[rir]

It seems you could just use an array with a current position marker.


sub new {
    die "bad param count" unless 2 == @_;
    my ($me, $arr_ref) = @_;
    bless { current => 0, data => $arr_ref},
          ref $me ||$me;
}