Author Topic: Looking for ideas to sort a kind of list  (Read 6182 times)

0 Members and 1 Guest are viewing this topic.

Pepe

  • Newt
  • Posts: 85
Looking for ideas to sort a kind of list
« on: October 06, 2010, 03:47:05 PM »
Hi!

I have a list of lists. Each one of the sub-lists has two elements. The first one is also a list that shows a hierarchy, and the second is a name. p.e.

Code: [Select]
(((1) "OneName") ((0 1) "Xampl") ((0 0 1) "Subname") ((1 0 1) "SpainIsDifferent") ((1 1) "AAI") ((0 1 1) "yVivaSanFermín") ((1 1 1) "VivaElVinoDeRioja"))
This list represents a tree like this:

1.-"OneName"
  1.0.- "Xampl"
    1.0.0.- "Subname"
    1.0.1.- "SpainIsDifferent"
  1.1.- "AAI"
    1.1.0.- "YVivaSanFermín"
    1.1.1.- "VivaElVinoDeRioja"


I want to sort the list alphabetically but keeping the hierachy, so the tree should remain like this:

1.-"OneName"
  1.0.- "AAI"
    1.0.0.- "VivaElVinoDeRioja"
    1.0.1.- "YVivaSanFermín"
  1.1.- "Xampl"
    1.1.0.- "SpainIsDifferent"
    1.1.1.- "Subname"

I'm a bit thick today, and I can't find a solution (nor explain it better... :cry:).

Would anybody help me, please?  :angel:

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
Re: Looking for ideas to sort a kind of list
« Reply #1 on: October 06, 2010, 08:00:51 PM »
So you want to sort on the first element list?
Code: [Select]
(caar '(((1) "OneName")
((0 1) "Xampl")
((0 0 1) "Subname")
((1 0 1) "SpainIsDifferent")
((1 1) "AAI")
((0 1 1) "yVivaSanFermín")
((1 1 1) "VivaElVinoDeRioja")))

(1)

If we sort on a list '(1 1 1) give an example of the next entry in the database?

I'm wondering why you need these particular pointers  (1) (0 1) is there some binary requirement?
I've reached the age where the happy hour is a nap. (°ż°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

alanjt

  • Needs a day job
  • Posts: 5352
  • Standby for witty remark...
Re: Looking for ideas to sort a kind of list
« Reply #2 on: October 07, 2010, 01:31:07 AM »
I want to sort the list alphabetically but keeping the hierachy, so the tree should remain like this:

1.-"OneName"
  1.0.- "AAI"
    1.0.0.- "VivaElVinoDeRioja"
    1.0.1.- "YVivaSanFermín"
  1.1.- "Xampl"
    1.1.0.- "SpainIsDifferent"
    1.1.1.- "Subname"
Perhaps I'm missing something, but how is that alphabetical?
Civil 3D 2019 ~ Windohz 7 64bit
Dropbox

Daniel J. Ellis

  • Swamp Rat
  • Posts: 811
Re: Looking for ideas to sort a kind of list
« Reply #3 on: October 07, 2010, 03:16:22 AM »
It is on each hierachy level, so in that example he'd want AAI, Xampl, and Zoological sorted alphabetically, then have VivaElVinoDeRioja and YVivaSanFermín sorted alphabetically under AAI, and so on.

dJE
===
dJE

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
Re: Looking for ideas to sort a kind of list
« Reply #4 on: October 07, 2010, 10:05:34 AM »
Oh I see it now, thanks for the pointer.

Sort on level 2 second item in the list.
Then re assign the pointers.

Is that correct?
I've reached the age where the happy hour is a nap. (°ż°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

uncoolperson

  • Guest
Re: Looking for ideas to sort a kind of list
« Reply #5 on: October 07, 2010, 11:03:26 AM »
break the list (keeping pointers)- though it doesn't look like you need to do this
sort
reassemble the list hierarchy (using pointers for relation not for order)
assign new pointers


do what cab said.

Pepe

  • Newt
  • Posts: 85
Re: Looking for ideas to sort a kind of list
« Reply #6 on: October 07, 2010, 11:39:42 AM »
Quote
If we sort on a list '(1 1 1) give an example of the next entry in the database?

Thank you for the interest and sorry for answer so late (job, job, job...).

Next entry (just in the same list) should be quite similar:
Code: [Select]
(((2) "Another Item") ((0 2) "ILoveMyMom") ((0 0 2) "MyMomIsLovely") ((1 0 2) "AndMyCatToo")) ((1 2) "MyTaylorIsRich"))
And so on...

Guitar_Jones

  • Guest
Re: Looking for ideas to sort a kind of list
« Reply #7 on: October 07, 2010, 02:56:54 PM »
Heres an ugly idea that seems to work.
Code: [Select]
(defun stringlist (a /  b c fn match sn)
(mapcar '(lambda (b) (if (= (cadr b) a)(setq fn (car b)))) alist)
(setq match (vl-remove-if
'(lambda (b)
(or
(/= (vl-list->string fn)(vl-list->string (cdr (car b))))
(/= (strlen (vl-list->string fn))(strlen (vl-list->string (cdr (car b)))))
)
)
alist
)
)
(mapcar '(lambda (c) (setq sn (acad_strlsort (append sn (list (cadr c)))))) match)
sn
);defun


(defun sortlist (zlist / )
(foreach x zlist
(setq slist (append slist (list x)))
(if (stringlist x) (sortlist (stringlist x)))
)
)      


(defun finalsort ( alist / slist finalist)
(sortlist (cdr (nth 0 alist)))
(setq finalist (mapcar '(lambda (b c) (if b (list (car b) c) b)) alist slist))
finalist
)



(finalsort '(((1) "OneName") ((0 1) "Xampl") ((0 0 1) "Subname") ((1 0 1) "SpainIsDifferent") ((1 1) "AAI") ((0 1 1) "yVivaSanFermín") ((1 1 1) "VivaElVinoDeRioja")))

gile

  • Gator
  • Posts: 2507
  • Marseille, France
Re: Looking for ideas to sort a kind of list
« Reply #8 on: October 08, 2010, 04:08:39 AM »
Hi,

IMO the most 'natural' way to build a tree in LISP is using nested lists.
Each node is a list which countains its child nodes as list too. the first item (car) in each node is the node name.

Code: [Select]
(setq tree
       '(("OneName"
      ("Xampl"
       ("SubName")
       ("SpainIsDifferent")
      )
      ("AAI"
       ("YVivaSanFermín")
       ("VivaElVinoDeRioja")
      )
     )
     ("Another Item"
      ("ILoveMyMom"
       ("MyMomIsLovely")
       ("AndMyCatToo")
      )
      ("MyTaylorIsRich")
     )
    )
)

This kind of list is quite easy to sort using a recursive process:

Code: [Select]
(defun SortTree (lst)
  (vl-sort (mapcar '(lambda (x)
      (if (cdr x)
(cons (car x) (SortTree (cdr x)))
        x
      )
    )
   lst
   )
   '(lambda (x1 x2)
      (< (car x1) (car x2))
    )
  )
)

(SortTree tree) returns:

(("Another Item"
   ("ILoveMyMom"
     ("AndMyCatToo")
     ("MyMomIsLovely")
   )
   ("MyTaylorIsRich")
 )
  ("OneName"
    ("AAI"
      ("VivaElVinoDeRioja")
      ("YVivaSanFermín")
    )
    ("Xampl"
      ("SpainIsDifferent")
      ("SubName")
    )
  )
)
Speaking English as a French Frog

gile

  • Gator
  • Posts: 2507
  • Marseille, France
Re: Looking for ideas to sort a kind of list
« Reply #9 on: October 08, 2010, 06:39:48 AM »
Some more functions using this kind of tree (examples using the upper defined tree list).

Get a node (ant its children) by its name:
Code: [Select]
(defun GetNode (node tree)
  (if tree
    (cond
      ((assoc node tree))
      ((GetNode node (apply 'append (mapcar 'cdr tree))))
    )
  )
)

Quote
_$ (GetNode "OneName" tree)
("OneName" ("Xampl" ("SubName") ("SpainIsDifferent")) ("AAI" ("YVivaSanFermín") ("VivaElVinoDeRioja")))
_$ (GetNode "ILoveMyMom" tree)
("ILoveMyMom" ("MyMomIsLovely") ("AndMyCatToo"))

Get a node by a list of index (note the list is 0 indexed and goes from higher level to deeper)
Code: [Select]
(defun GetNodeAt (ind tree)
  (if tree
    (if    (cdr ind)
      (GetNodeAt (cdr ind) (cdr (nth (car ind) tree)))
      (nth (car ind) tree)
    )
  )
)

Quote
_$ (GetNodeAt '(0) tree)
("OneName" ("Xampl" ("SubName") ("SpainIsDifferent")) ("AAI" ("YVivaSanFermín") ("VivaElVinoDeRioja")))
_$ (GetNodeAt '(1) tree)
("Another Item" ("ILoveMyMom" ("MyMomIsLovely") ("AndMyCatToo")) ("MyTaylorIsRich"))
_$ (GetNodeAt '(0 1) tree)
("AAI" ("YVivaSanFermín") ("VivaElVinoDeRioja"))
_$ (GetNodeAt '(1 0 1) tree)
("AndMyCatToo")
Speaking English as a French Frog

Lee Mac

  • Seagull
  • Posts: 12905
  • London, England
Re: Looking for ideas to sort a kind of list
« Reply #10 on: October 08, 2010, 09:21:33 AM »
Nice functions Gile :-)

I thought I'd try to write a 'GetIndexOf' function, but am really struggling  :-( More coffee needed I think.

CAB

  • Global Moderator
  • Seagull
  • Posts: 10401
Re: Looking for ideas to sort a kind of list
« Reply #11 on: October 08, 2010, 11:11:06 AM »
Nice explanation Gile.
Using nested lists is the way to go.
Pepe should use that and apply the prefix as needed later. i.e. (2) (0 2) etc.
I've reached the age where the happy hour is a nap. (°ż°)
Windows 10 core i7 4790k 4Ghz 32GB GTX 970
Please support this web site.

dgorsman

  • Water Moccasin
  • Posts: 2437
Re: Looking for ideas to sort a kind of list
« Reply #12 on: October 08, 2010, 11:12:37 AM »
For the LISP purist, lists are the way to go.  But I'm a little dirty - I think XML would be better.
If you are going to fly by the seat of your pants, expect friction burns.

try {GreatPower;}
   catch (notResponsible)
      {NextTime(PlanAhead);}
   finally
      {MasterBasics;}

Pepe

  • Newt
  • Posts: 85
Re: Looking for ideas to sort a kind of list
« Reply #13 on: October 08, 2010, 04:00:01 PM »
Thank you all for the hints! (Specially to Gile and Guitar_Jones.)

I haven't been able to visit this place as much as I'd like these past days, but I promise I'll meditate and think out how to use all this ideas during this weekend (a long one in Spain!  ;-) ).

Thanks again!  :-)

gile

  • Gator
  • Posts: 2507
  • Marseille, France
Re: Looking for ideas to sort a kind of list
« Reply #14 on: October 17, 2010, 03:57:54 AM »
Quote
I thought I'd try to write a 'GetIndexOf' function, but am really struggling

Here's a way:

Code: [Select]
(defun GetIndexOf (node tree / foo1 foo2)
  (defun foo1 (ind node tree)
    (if    tree
      (if (assoc node tree)
    (reverse (cons (vl-position (assoc node tree) tree) ind))
    (foo2 (cons 0 ind) node tree)
      )
    )
  )
  (defun foo2 (ind node tree)
    (if    tree
      (cond
    ((foo1 ind node (cdar tree)))
    (T (foo2 (cons (1+ (car ind)) (cdr ind)) node (cdr tree)))
      )
    )
  )
  (foo1 nil node tree)
)
Speaking English as a French Frog