Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

Overview

Consider an ordered list interspersed with unordered elements, e.g.:

Alligator
Ant
Falcon <--
Baboon
Badger    
Armadillo <--
Caiman
Cat

How can this list be processed so that all unordered elements are deleted? E.g.:

Alligator
Ant
Baboon
Badger    
Caiman
Cat

Some more information

The unordered elements are always singular, the ordered elements come in groups of at least 2 lines. The general pattern would be:

ordered
ordered
ordered
unordered <--
ordered
ordered
unordered <--
ordered
ordered

The unordered elements can be both lower...

A
B
F <---
D
E

...and higher than the following ordered element:

A
C
B <---
D
E

To make matters even more difficult: The elements can be both upper- and lowercase and contain diacritics (e.g.: ä,ö,à).


Is there any way to accomplish this with bash?

share|improve this question
    
Apparently, from the example you give, what you actually do is reading the list from bottom to top and removing a word if it's not -- in the alphabetical order -- lower than the previous one (i.e. the word on the line below). Is that actually what you are trying to do or did I get it wrong ? –  lgeorget Feb 27 at 17:51
3  
It is not trivial to determine which lines are the ones to be deleted. animal, baboon, yo-yo, zoo could be the ordered lines, the others to be deleted. You can easily detect the points where ordering stops but you do not easily know whether the former or the later line is the problem. You need an unambiguous algorithm for that. –  Hauke Laging Feb 27 at 17:53
    
@HaukeLaging You are right, I didn't consider this when constructing the example. The real case might be a bit easier to solve: It's always one unordered line at a time, so you would have a long list of ordered items (o) interspersed by very few single unordered items (u), e.g.: o-o-o-o-o-o-u-o-o-o-o-o-u-o-o-u. Would this make the problem more feasible to solve with command line tools? –  Glutanimate Feb 27 at 18:02
2  
How do you decise it's B and not C that is out of order in your last example? –  Stéphane Chazelas Feb 27 at 19:04
1  
Some of the ideas here might help - stackoverflow.com/questions/16641879/… –  Graeme Feb 27 at 21:49

2 Answers 2

up vote 4 down vote accepted

This works if the last line is OK:

awk 'BEGIN {IGNORECASE=1}; NR==1 {lastline=$0; next;}; {if($0>lastline) {print lastline; '\
'lastline2=lastline; lastline=$0;} else if ($0>lastline2) lastline=$0; }; '\
'END {print lastline;}' file1.txt

old version (with bugs, for comparison)

awk 'BEGIN {IGNORECASE=1}; NR==1 {lastline=$0; next;}; '\
'{if($0>lastline) print lastline; lastline=$0;}; END {print lastline;}' file
share|improve this answer
    
Thanks for your answer! This works great if all elements are lowercase and don't use any special diacritics (as shown in the examples). Unfortunately the phrases I am working with are both upper/lowercase and contain diacritics. This seems to mess the results up. Would it be possible to modify your script to work under these circumstances? –  Glutanimate Feb 27 at 19:29
    
@Glutanimate I am not familiar with awk's internationalization. I believed this works automatically. What is your locale? If this is not easily possible with awk then you may use Graeme's locale-aware shell solution instead. –  Hauke Laging Feb 27 at 19:43
    
Ah, nervmind. The issue with diacritics was my fault. The first element in the example I linked to ("äpple") should have come after "apple". That's how diacritics are generally sorted in my locale. The issue with different cases remains, though. The items in my list are only sorted alphabetically and without regard to their capitalization. Would it be possible to make awk's sorting case insensitive as well? –  Glutanimate Feb 27 at 19:55
    
@Glutanimate I have made a change. Check whether the case problem is solved now. –  Hauke Laging Feb 27 at 19:59
2  
That turns b c a d e into b a d e –  Stéphane Chazelas Feb 27 at 20:07

Shell solution:

#!/bin/bash

IFS=
before=
read -r current

while read -r after
do
  [[ "$before" < "$current" || "$before" = "$current"  ]] &&
    [[ "$current" < "$after" || "$current" = "$after"  ]] &&
    printf '%s\n' "$current" &&
    before="$current"

  current="$after"
done

[[ "$before" < "$current" || "$before" = "$current"  ]] &&
  printf '%s\n' "$current"

Usage: ./script <input_file

Note that with bash you can use [[..]] comparisons for the lexical comparisons to be locale dependent and less naive (should work with ä,ö,à etc).

With reference to Stephane's point about how to decide for the last example in the question, this gives preference to the later occurrence. So it will actually remove C.

share|improve this answer
    
@Grame: Thank you for this script. It works great with different cases and also performs well for different locales and their diacritics. However, it seems to suffer from the same sorting issue as Hauke's awk snippet. E.g: e f g a h i is truncated to e f h i when it should be e f g h i. –  Glutanimate Feb 27 at 20:19
    
@Glutanimate, I thought this was something relatively trivial to do, its not. You really have to come up with a good algorithm here, which unless you already know approaches to the problem, is going to take an afternoon to do properly. Also as Stephane says, this kind of stuff isn't really suited for shell scripting. IMO though it is fine for light use. You are probably best asking something more abstract on SO or Programmers. I would be interested to know if there is a simple way to do this though! –  Graeme Feb 27 at 21:38
    
@StephaneChazelas, don't know if you will still get notifications for this, but what was the problem with -o? –  Graeme Feb 27 at 21:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.